《雲資料管理：挑戰與機遇》一2.2P2P系統

本節書摘來自華章出版社《雲資料管理：挑戰與機遇》一書中的第二章，第2.2節，作者[美] 迪衛艾肯特•阿格拉沃爾（divyakant agrawal） 蘇迪皮托•達斯（sudipto das）阿姆魯•埃爾•阿巴迪（amr el abbadi）  更多章節内容可以通路雲栖社群“華章計算機”公衆号檢視。

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（http://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環中節點的數量。