《雲數據管理：挑戰與機遇》2.2　P2P係統

本節書摘來自華章出版社《雲數據管理》一書中的第2章，第2節，作者迪衛艾肯特·阿格拉沃爾，更多章節內容可以訪問雲棲社區“華章計算機”公眾號查看

P2P係統

作為傳統的客戶端–服務器模式的另外一種可替代方式，P2P（peer-to-peer）架構提供了一種可行的方案，P2P係統中的很多技術都已經在數據中心中得到了成功應用。P2P係統的主要目標是在數百萬並發用戶的情況下，確保數十億對象的可用性，如音樂文件。為了實現上述目標，必須在物理網絡之上構建一層虛擬的或邏輯的覆蓋（overlay）網絡。抽象地講，覆蓋構建了不同站點之間的相互通信方式以及數據存儲方式。最簡單的形式是一個對象可以看成是一個鍵–值對。覆蓋提供了對象檢索方法，並支持兩種基本操作：給定一個鍵和值，可以把鍵–值元組插入（insert）到覆蓋中，同時，給定一個鍵值，可以查詢（lookup）並返回對應的值。覆蓋一般可以表示成圖的形式，以站點為節點，用邊來連接不同的站點，可以分為結構化覆蓋和非結構化覆蓋。

非結構化覆蓋沒有在節點間的邏輯圖上增加任何特定的結構。集中式方案是這種P2P設計的最簡單實現，最早由Napster[Carlsson and Gustavsson, 2001]加以應用，Napster方案用一個中央服務器來存儲所有的鍵值和用來標識這些鍵值所在網絡節點的數據庫。每次鍵–值元組的查找都需要訪問中央服務器。Napster於1999年發布，最高同時150萬用戶在線，2001年7月由於法律問題關閉。

除此之外，Gnutella（https://en.wikipedia.org/wiki/Gnutella）使用了分布式設計，每個節點都有若幹個鄰居，並且在本地數據庫中存儲若幹個鍵。當需要查找鍵k時，某個站點首先檢查自己的本地數據庫，判斷k是否在本地。如果在本地，則直接返回相應的值，否則，該站點遞歸地詢問鄰居站點。通常情況下，需要使用一個限製閾值來限定消息的無限製傳播。

另外一方麵，結構化覆蓋在不同的節點上強加了具有良好定義的數據結構。這種數據結構一般稱作分布式哈希表（Distributed Hash Table, DHT），DHT可以將對象映射到不同的站點，並且，給定相應的鍵，DHT可以快速檢索相應的數據對象。特別是，在結構化覆蓋中，邊是按照特定的規則選擇的，數據被存儲在預先確定的站點上。通常情況下，每一個站點負責維護一個表，該表存儲了用於查找操作的下一跳（next-hop）。我們將用一種非常流行的稱為Chord[Stoica et al., 2001]的P2P係統來對結構化覆蓋進行舉例說明。在Chord中，每一個節點都使用一致性哈希函數（如SHA-1）進行哈希，哈希到一個m位的標識符空間中（2m個ID），其中，m一般取160。所有的站點依據各自的ID號被組織成一個邏輯環。鍵也被哈希到相同的標識符空間中，鍵（及其相應的值）存儲在後繼節點中，即下一個具有較大ID的節點。

一致性哈希可以確保：對任何n個節點和k個鍵的集合，一個節點最多負責個(1+∈)k/n鍵。另外，當一個新的節點加入或離開時，O(k/n)個鍵需要移動。為了支持高效和可擴展的查詢，係統中的每一個節點都需要維護一個查詢表（finger table）。節點n的查詢表的第i個元素是第一個後繼節點或者等於n+2i。圖2-8展示了針對不同的網絡規模，一個給定節點的路由表中的指針。換句話說，第i個指針沿著環指向1/2(m–i)方向。當接收到一個針對id項的查詢時，節點首先檢查是否存儲在本地。如果不在本地，則將該查詢往前發送給其查詢表中最大的節點。假設Chord環中的節點呈正態分布，每一步中搜索空間的節點數量減半。因此，查詢跳數的期望值是O(logn)，其中，n是Chord環中節點的數量。