複製鏈接
請複製以下鏈接發送給好友

分佈式散列表

鎖定
分佈式散列表(英語:Distributed Hash Table,簡稱DHT)是分佈式計算系統中的一類,用來將一個關鍵值(key)的集合分散到所有在分佈式系統中的節點,並且可以有效地將消息轉送到唯一一個擁有查詢者提供的關鍵值的節點(Peers)。
中文名
分佈式散列表
外文名
Distributed Hash Table
簡    稱
DHT
分    類
分佈式計算系統中的一類
性    質
離散性

分佈式散列表簡介

分佈式散列表示意圖 分佈式散列表示意圖
分佈式散列表的節點類似散列表中的存儲位置。分佈式散列表通常是為了擁有極大節點數量的系統,而且在系統的節點常常會加入或離開(例如網絡斷線)而設計的。在一個結構性的延展網絡(overlay network)中,參加的節點需要與系統中一小部份的節點溝通,這也需要使用分佈式散列表。
分佈式散列表可以用以創建更復雜的服務,例如分佈式文件系統點對點技術文件分享系統、合作的網頁高速緩存、多播任播域名系統以及實時通信等。

分佈式散列表發展背景

研究分佈式散列表的主要動機是為了開發點對點系統,像是Napster、Gnutella及Freenet。這些系統得益於使用分散在互聯網上的各項資源以提供實用的應用,特別在帶寬硬盤存儲空間上,他們所提供的文件分享功能因此得到最大的好處。
這些系統使用不同的方法來解決如何找到擁有某數據的節點的問題。Napster 使用中央的索引服務器:每個節點加入網絡的同時,會將他們所擁有的文件列表傳送給服務器,這使得服務器可以進行搜索並將結果回傳給進行查詢的節點。但中央索引服務器讓整個系統易受攻擊,且可能造成法律問題。於是,Gnutella 和相似的網絡改用大量查詢模式(flooding query model):每次搜索都會把查詢消息廣播給網絡上的所有節點。雖然這個方式能夠防止單點故障(single point of failure),但比起 Napster 來説卻極沒效率。
最後,Freenet 使用了完全分佈式的系統,但它建置了一套使用經驗法則的基於關鍵值的轉送方法(key based routing)。在這個方法中,每個文件與一個關鍵值相結合,而擁有相似關鍵值的文件會傾向被相似的節點構成的集合所保管。於是查詢消息就可以根據它所提供的關鍵值被轉送到該集合,而不需要經過所有的節點。然而,Freenet 並不保證存在網絡上的數據在查詢時一定會被找到。
分佈式散列表為了達到 Gnutella 與 Freenet 的分散性(decentralization)以及 Napster 的效率與正確結果,使用了較為結構化的基於關鍵值的轉送方法。不過分佈式散列表也有個 Freenet 有的缺點,就是隻能作精確搜索,而不能只提供部份的關鍵字;但這個功能可以在分佈式散列表的上層實做。
最初的四項分佈式散列表技術——內容可尋址網絡(Content addressable network,CAN)、Chord(Chord project)[1]、Pastry(Pastry (DHT)),以及 Tapestry (DHT)(Tapestry (DHT))皆同時於2001年發表。從那時開始,相關的研究便一直十分活躍。在學術領域以外,分佈式散列表技術已經被應用在BitTorrent及CoralCDN(Coral Content Distribution Network)等。

分佈式散列表性質

分佈式散列表本質上強調以下特性:
離散性:構成系統的節點並沒有任何中央式的協調機制。
伸縮性:即使有成千上萬個節點,系統仍然應該十分有效率。
容錯性:即使節點不斷地加入、離開或是停止工作,系統仍然必須達到一定的可靠度。
要達到以上的目標,有一個關鍵的技術:任一個節點只需要與系統中的部份節點溝通。一般來説,若系統有n 個節點,那麼只有 Θ(logn) 個節點是必須的。因此,當成員改變的時候,只有一部分的工作(例如數據或關鍵值的傳送,散列表的改變等)必須要完成。
有些分佈式散列表的設計尋求能對抗網絡中惡意的節點的安全性,但仍然保留參加節點的匿名性。在其他的點對點系統(特別是文件分享)中較為少見。參見匿名點對點技術
最後,分佈式散列表必須處理傳統分佈式系統可能遇到的問題,例如負載平衡數據完整性,以及效能問題(特別是確認轉送消息、數據存儲及讀取等動作能快速完成)。

分佈式散列表結構

分佈式散列表的結構可以分成幾個主要的組件[2][3]。其基礎是一個抽象的關鍵值空間(keyspace),例如説所有160位長的字符串集合。關鍵值空間分區(keyspace partitioning)將關鍵值空間分區成數個,並指定到在此係統的節點中。而延展網絡則連接這些節點,並讓他們能夠藉由在關鍵值空間內的任一值找到擁有該值的節點。
當這些組件都準備好後,一般使用分佈式散列表來存儲與讀取的方式如下所述。假設關鍵值空間是一個160位長的字符串集合。為了在分佈式散列表中存儲一個文件,名稱為 filename 且內容為 data,我們計算出 filename 的 SHA1 散列值——一個160位的關鍵值 k——並將消息 put(k,data) 送給分佈式散列表中的任意參與節點。此消息在延展網絡中被轉送,直到抵達在關鍵值空間分區中被指定負責存儲關鍵值 k 的節點。而 (k,data) 即存儲在該節點。其他的節點只需要重新計算 filename 的散列值 k,然後提交消息 get(k) 給分佈式散列表中的任意參與節點,以此來找與 k 相關的數據。此消息也會在延展網絡中被轉送到負責存儲 k 的節點。而此節點則會負責傳回存儲的數據 data。
以下分別描述關鍵值空間分區及延展網絡的基本概念。這些概念在大多數的分佈式散列表實現中是相同的,但設計的細節部份則大多不同。

分佈式散列表關鍵值空間分區

大多數的分佈式散列表使用某些穩定散列(consistent hashing)方法來將關鍵值對應到節點。此方法使用了一個函數 δ(k1,k2) 來定義一個抽象的概念:從關鍵值k1 到 k2 的距離。每個節點被指定了一個關鍵值,稱為ID。ID 為 i 的節點擁有根據函數 δ 計算,最接近 i 的所有關鍵值。
例:Chord 分佈式散列表實現將關鍵值視為一個圓上的點,而 δ(k1,k2) 則是沿着圓順時鐘地從 k1 走到 k2 的距離。結果,圓形的關鍵值空間就被切成連續的圓弧段,而每段的端點都是節點的ID。如果 i1 與 i2 是鄰近的 ID,則 ID 為 i2 的節點擁有落在 i1 及 i2 之間的所有關鍵值。
穩定散列擁有一個基本的性質:增加或移除節點只改變鄰近ID的節點所擁有的關鍵值集合,而其他節點的則不會被改變。對比於傳統的散列表,若增加或移除一個位置,則整個關鍵值空間就必須重新對應。由於擁有數據的改變通常會導致數據從分佈式散列表中的一個節點被搬到另一個節點,而這是非常浪費帶寬的,因此若要有效率地支持大量密集的節點增加或離開的動作,這種重新配置的行為必須儘量減少。

分佈式散列表延展網絡

每個節點保有一些到其他節點(它的鄰居)的連結。將這些連結總合起來就形成延展網絡。而這些連結是使用一個結構性的方式來挑選的,稱為網絡拓樸。
所有的分佈式散列表實現拓樸有某些基本的性質:對於任一關鍵值 k,某個節點要不就擁有 k,要不就擁有一個連結能連結到距離較接近 k 的節點。因此使用以下的貪心算法即可容易地將消息轉送到擁有關鍵值 k 的節點:在每次運行時,將消息轉送到 ID 較接近 k 的鄰近節點。若沒有這樣的節點,那我們一定抵達了最接近 k 的節點,也就是擁有 k 的節點。這樣的轉送方法有時被稱為“基於關鍵值的轉送方法”。
除了基本的轉送正確性之外,拓樸中另有兩個關鍵的限制:其一為保證任何的轉送路徑長度必須儘量短,因而請求能快速地被完成;其二為任一節點的鄰近節點數目(又稱最大節點度(Degree (graph theory)))必須儘量少,因此維護的花費不會過多。當然,轉送長度越短,則最大節點度越大。以下列出常見的最大節點度及轉送長度(n 為分佈式散列表中的節點數)
最大節點度 O(1),轉送長度 O(logn)
最大節點度 O(logn),轉送長度 O(logn / loglogn)
最大節點度 O(logn),轉送長度 O(logn)
最大節點度 O(n1 / 2),轉送長度 O(1)
第三個選擇最為常見。雖然他在最大節點度與轉送長度的取捨中並不是最佳的選擇,但這樣的拓樸允許較為有彈性地選擇鄰近節點。許多分佈式散列表實現利用這種彈性來選擇延遲較低的鄰近節點
最大的轉送長度與直徑有關:最遠的兩節點之間的最短距離。無疑地,網絡的最大轉送長度至少要與它的直徑一樣長,因而拓樸也被最大節點度與直徑的取捨限制住,而這在圖論中是基本的性質。因為貪婪算法(Greedy Method)可能找不到最短路徑,因此轉送長度可能比直徑長。

分佈式散列表示例

分佈式散列表實現與協議
Bamboo
Bunshin
內容可尋址網絡 (Content Addressable Network)
Chord
DKS系統
Kademlia
Leopard
MACE
Pastry
P-Grid
Tapestry
分佈式散列表的應用
BitTorrent:文件分享應用。BitTorrent 可以選用DHT作為分佈式Tracker。
Warez P2P:文件分享應用。
The Circle:文件分享應用與聊天。
CSpace:安全的溝通系統。
Codeen:網頁高速緩存。
CoralCDN
Dijjer
eMule:文件分享應用。
I2P:匿名網絡。
JXTA:開放源代碼的點對點平台。
NEOnet:文件分享應用。
Overnet:文件分享應用。