數據網格產品經常會使用P2P進行通信,借此機會系統地學習一下P2P網絡和其資源搜索策略。
### 1 P2P網絡架構
談到P2P就涉及到一個概念:**Overlay Network(覆蓋網絡)**。所謂覆蓋網絡是應用層網絡,幾乎不考慮網絡層和物理層,它具體指的就是建立在另一個網絡上的網絡。例如P2P網絡就是覆蓋網絡,因為它運行在互聯網之前,但允許對未知IP主機的訪問。通過DHT等算法,可以在事先不知道IP地址的情況下,訪問到存儲某個文件的結點。

常見的P2P系統主要有Unstructured Network和Structured Network兩種架構。
### 1.1 Unstructured Network
非結構化的P2P網絡并不給覆蓋網絡強加某種特定架構,而是結點間隨機形成鏈接。最流行的P2P網絡,像Bittorrent、eMule、Gnutella、Kazaa等都是非結構化的P2P協議。因為缺少結構,所以網絡面對頻繁的動態添加和刪除結點時,依然能夠健壯地運行。但也正因為缺少結構,所以當某個結點想要搜索某些數據或文件時,查詢必須flood整個網絡(詳見1.3搜索策略)。

### 1.2 Structured Network
結構化P2P網絡將覆蓋網絡組織成某種特定的拓撲結構,并且它的協議能夠保證:**任何結點都能高效地搜索網絡中的資源**,即使資源是非常冷門的。常見的結構化P2P網絡通常實現**一致性哈希**或者其變種**分布式哈希表DHT**分配文件的所有權到特定的結點。

### 1.3?搜索策略
兩種P2P網絡可以使用不同的檢索策略:中央索引、本地索引和分布式索引。分布式索引策略是對其他兩種策略的權衡。

#### 中央索引(中央服務器)
由一個中央服務器統一保存資源與結點的關系。這種方式搜索效率比較高,因為可以通過中央索引直接定位到目標結點,然而這種方式有時并不可行,特別是集群規模特別大時。

#### 本地索引(flooding搜索)
每個結點保存自己的資源信息,當尋找不屬于自己的資源時,會flooding整個網絡進行尋找。這種flooding的方式會在網絡中引起大量的traffic,并使每個結點都要處理查詢請求而導致高CPU和內存使用率。并且flooding不保證通信質量,所以flooding也無法保證一定能夠找到保存指定數據的那個結點。因為熱數據在多個結點上存在,所以比較容易搜索成功。反之,冷數據只在很少的結點上存在,所以搜索很可能會以失敗告終。并且搜索效率也很低,也容易導致安全問題。

#### 分布式索引
為了高效地在網絡中搜索,結點需要保存滿足特定條件的鄰居的列表,這使得整個網絡在高頻率的添加刪除結點時,沒有非結構化網絡那樣健壯。使用DHT路由的結構化P2P網絡的著名軟件有BitTorrent,Kad Network,以及各種研究項目Chord等。**基于DHT的網絡在網絡計算系統中也有廣泛的應用,它幫助實現高效的資源發現和應用程序調度等**。
典型的P2P網絡使用的架構和搜索策略如下:

### 2?基本的分區算法
經典的分區算法有直接取模和哈希取模。假設有K臺服務器,我們可以這樣確定數據X所在的服務器i:
???直接取模**i = X mod k**:問題是數據分布不均勻。
???哈希取模**i = hash(X) mod k**:問題是1)根據集群和數據規模,散列沖突可能會比較嚴重(只能通過替換更好的哈希算法來平衡);2)擴容添加結點或故障刪除結點時(k->k±1),所有數據都要重新映射到新的結點上(通過后面介紹的兩種分布式哈希可以解決)。

### 3?一致性哈希
### 3.1?構造
**將結點和數據映射到同一個線性地址空間**,結點負責保存前一結點到本結點之間的數據。

### 3.2 Lookup過程
首先,**藍色**結點確定**紅色**結點負責保存key1。然后,**藍色**結點將lookup或insert請求發送給**紅色**結點。所以lookup過程的算法復雜度是O(1)。

### 3.3?添加刪除結點
當添加刪除結點時,影響的只是很小的一部分數據。

### 4?分布式哈希表
分布式哈希表DHT是一種概念模型或者說思想,其主要思路是:將每條文件索引K文件名或其他屬性的哈希值-V存儲文件的結點IP地址,組成一張巨大的文件索引哈希表。然后,再將這張大表按照一定規則分割成許多小塊,并分布到各個結點上,每個結點負責維護其中一塊。**DHT使用一致性哈希的思想來最小化拓撲結構變化帶來的影響,并構造overlay網絡實現高效地搜索**。
首先,將結點和數據映射到同一個線性地址空間,每個結點只負責地址空間中的一部分數據,但結點負責的信息通常是有重疊和冗余的。通常我們將這個線性地址空間看成一個環:

邏輯上地址空間形成的環對應著底層的物理拓撲結構,要注意的是真正的(underlay)的拓撲結構和邏輯的(overlay)拓撲結構通常是無關聯的:

根據不同的DHT實現,查找過程會有不同。但不同的算法實現都類似于下圖所示的過程,在地址空間中利用各種算法高效地找到負責保存數據的結點。注意,最后找到的數據分為兩種:
???value就是我們要找的數據,它直接存儲在結點上,這對于數據量不大的情況來說比較合適。
???value不是我們要找的數據,而是數據存儲在另一臺機器的地址信息(如下圖所示)。這種間接的存儲方式多了一步數據的獲取,但是對于大文件的存儲來說更加合適。

### 5 Chord實現
接下來要介紹的是最常見的MIT的Chord版DHT實現。
### 4.1 Chord環和Finger表
首先,Chord使用SHA-1哈希函數(生成160位的id)和取模:
???**Node-id = SHA1(IP/mac)**
???**Key-id = SHA1(key)**
???**id-space mod?**
### 4.2 Lookup過程
對于Chord版的DHT實現來說,這種Lookup過程是通過一張叫做Finger表的路由表來完成的,它根據計算數據id指數級增長時對應的各個結點,形成表中的信息:

在沒有finger表的情況下,需要不斷訪問后繼結點繼續lookup,即O(n)跳才能找到目標結點:

有了finger表,就可以實現O(logN)的高效lookup:

### 5?算法復雜度對比
除了搜索/路由外,其他幾項都是DHT占優:

### 參考資料
1 Princeton -?[P2P Systems and Distributed Hash Tables](http://www.cs.princeton.edu/courses/archive/spr11/cos461/docs/lec22-dhts.pdf)
2 Overlay Network:[http://en.wikipedia.org/wiki/Overlay_network](http://en.wikipedia.org/wiki/Overlay_network)
3 Peer-to-Peer:[http://en.wikipedia.org/wiki/Peer-to-peer](http://en.wikipedia.org/wiki/Peer-to-peer)
4 Structured Homogenous P2P Overlay Networks
5?[memcached全面剖析--4. memcached的分布式算法](http://blog.charlee.li/memcached-004/)