數據網格產品經常會使用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/)