分散式雜湊表

分散式雜湊表示意圖

分散式雜湊表（英語：distributed hash table，缩写DHT）是分散式計算系統中的一類，用來將一個關鍵值（key）的集合分散到所有在分散式系統中的節點，並且可以有效地將訊息轉送到唯一一個擁有查詢者提供的關鍵值的節點（Peers）。這裡的節點類似雜湊表中的儲存位置。分散式雜湊表通常是為了擁有極大節點數量的系統，而且在系統的節點常常會加入或離開（例如網路斷線）而設計的。在一個結構性的覆盖网络（overlay network）中，參加的節點需要與系統中一小部份的節點溝通，這也需要使用分散式雜湊表。分散式雜湊表可以用以建立更複雜的服務，例如分散式檔案系統、點對點技術檔案分享系統、合作的網頁快取、多播、任播、網域名稱系統以及即時通訊等。

發展背景

研究分散式雜湊表的主要動機是為了開發點對點系統，像是Napster、Gnutella及Freenet。這些系統得益於使用分散在網際網路上的各項資源以提供實用的應用，特別在頻寬及硬碟儲存空間上，他們所提供的檔案分享功能因此得到最大的好處。

這些系統使用不同的方法來解決如何找到擁有某資料的節點的問題。Napster使用中央的索引伺服器：每個節點加入網路的同時，會將他們所擁有的檔案列表傳送給伺服器，這使得伺服器可以進行搜尋並將結果回傳給進行查詢的節點。但中央索引伺服器讓整個系統易受攻擊，且可能造成法律問題。於是，Gnutella和相似的網路改用大量查詢模式（flooding query model）：每次搜尋都會把查詢訊息廣播給網路上的所有節點。雖然這個方式能夠防止單點故障（single point of failure），但比起Napster來說卻極沒效率。

最後，Freenet使用了完全分散式的系統，但它建置了一套使用經驗法則的基於關鍵值的轉送方法（key based routing（英语：key based routing））。在這個方法中，每個檔案與一個關鍵值相結合，而擁有相似關鍵值的檔案會傾向被相似的節點構成的集合所保管。於是查詢訊息就可以根據它所提供的關鍵值被轉送到該集合，而不需要經過所有的節點。然而，Freenet並不保證存在網路上的資料在查詢時一定會被找到。

分散式雜湊表為了達到Gnutella與Freenet的分散性（decentralization）以及Napster的效率與正確結果，使用了較為結構化的基於關鍵值的轉送方法。不過分散式雜湊表也有個Freenet有的缺點，就是只能作精確搜尋，而不能只提供部份的關鍵字；但這個功能可以在分散式雜湊表的上層實做。

最初的四項分散式雜湊表技術——內容可定址網路（Content addressable network（英语：Content addressable network），CAN）、Chord（Chord project（英语：Chord project））^[1]、Pastry（Pastry (DHT)（英语：Pastry (DHT)）），以及Tapestry (DHT)（Tapestry (DHT)（英语：Tapestry (DHT)））皆同時於2001年發表。從那時開始，相關的研究便一直十分活躍。在學術領域以外，分散式雜湊表技術已經被應用在BitTorrent及CoralCDN（Coral Content Distribution Network（英语：Coral Content Distribution Network））等。

性質

分散式雜湊表本質上強調以下特性：

• 離散性：構成系統的節點並沒有任何中央式的協調機制。
• 伸縮性：即使有成千上萬個節點，系統仍然應該十分有效率。
• 容錯性：即使節點不斷地加入、離開或是停止工作，系統仍然必須達到一定的可靠度。

要達到以上的目標，有一個關鍵的技術：任一個節點只需要與系統中的部份節點溝通。一般來說，若系統有${\displaystyle n}$個節點，那麼只有${\displaystyle \Theta (\log n)}$個節點是必須的（見後述）。因此，當成員改變的時候，只有一部分的工作（例如資料或關鍵值的傳送，雜湊表的改變等）必須要完成。

有些分散式雜湊表的設計尋求能對抗網路中惡意的節點的安全性，但仍然保留參加節點的匿名性。在其他的點對點系統（特別是檔案分享）中較為少見。參見匿名點對點技術。

最後，分散式雜湊表必須處理傳統分散式系統可能遇到的問題，例如負載平衡、資料完整性，以及效能問題（特別是確認轉送訊息、資料儲存及讀取等動作能快速完成）。

結構

分散式雜湊表的結構可以分成幾個主要的元件^[2][3]。其基礎是一個抽象的關鍵值空間（keyspace），例如說所有160位元長的字元串集合。關鍵值空間分割（keyspace partitioning）將關鍵值空間分割成數個，並指定到在此系統的節點中。而延展網路則連接這些節點，並讓他們能夠藉由在關鍵值空間內的任一值找到擁有該值的節點。

當這些元件都準備好後，一般使用分散式雜湊表來儲存與讀取的方式如下所述。假設關鍵值空間是一個160位元長的字元串集合。為了在分散式雜湊表中儲存一個檔案，名稱為${\displaystyle filename}$且內容為${\displaystyle data}$，我們計算出${\displaystyle filename}$的SHA1雜湊值——一個160位元的關鍵值${\displaystyle k}$——並將訊息${\displaystyle put(k,data)}$送給分散式雜湊表中的任意參與節點。此訊息在延展網路中被轉送，直到抵達在關鍵值空間分割中被指定負責儲存關鍵值${\displaystyle k}$的節點。而${\displaystyle (k,data)}$即儲存在該節點。其他的節點只需要重新計算${\displaystyle filename}$的雜湊值${\displaystyle k}$，然後送出訊息 ${\displaystyle get(k)}$給分散式雜湊表中的任意參與節點，以此來找與${\displaystyle k}$相關的資料。此訊息也會在延展網路中被轉送到負責儲存${\displaystyle k}$的節點。而此節點則會負責傳回儲存的資料${\displaystyle data}$。

以下分別描述關鍵值空間分割及延展網路的基本概念。這些概念在大多數的分散式雜湊表實作中是相同的，但設計的細節部份則大多不同。

關鍵值空間分割

大多數的分散式雜湊表使用某些穩定雜湊（consistent hashing）方法來將關鍵值對應到節點。此方法使用了一個函數${\displaystyle \delta (k_{1},k_{2})}$來定義一個抽象的概念：從關鍵值${\displaystyle k_{1}}$到${\displaystyle k_{2}}$的距離。每個節點被指定了一個關鍵值，稱為ID。ID為${\displaystyle i}$的節點擁有根據函數${\displaystyle \delta }$計算，最接近${\displaystyle i}$的所有關鍵值。

例：Chord分散式雜湊表實作將關鍵值視為一個圓上的點，而${\displaystyle \delta (k_{1},k_{2})}$則是沿著圓順時鐘地從${\displaystyle k_{1}}$走到${\displaystyle k_{2}}$的距離。結果，圓形的關鍵值空間就被切成連續的圓弧段，而每段的端點都是節點的ID。如果${\displaystyle i_{1}}$與${\displaystyle i_{2}}$是鄰近的ID，則ID為${\displaystyle i_{2}}$的節點擁有落在${\displaystyle i_{1}}$及${\displaystyle i_{2}}$之間的所有關鍵值。

穩定雜湊擁有一個基本的性質：增加或移除節點只改變鄰近ID的節點所擁有的關鍵值集合，而其他節點的則不會被改變。對比於傳統的雜湊表，若增加或移除一個位置，則整個關鍵值空間就必須重新對應。由於擁有資料的改變通常會導致資料從分散式雜湊表中的一個節點被搬到另一個節點，而這是非常浪費頻寬的，因此若要有效率地支援大量密集的節點增加或離開的動作，這種重新配置的行為必須盡量減少。

将相近的关键值分配给了距离相近的节点Locality-preserving_hashing（英语：Locality-preserving_hashing），可以实现更短的查询延迟，从而提高DHT的查询效率。相关工作包括Self-Chord^[4]和LDHT^[5]

延展網路

每個節點保有一些到其他節點（它的鄰居）的連結。將這些連結總合起來就形成延展網路。而這些連結是使用一個結構性的方式來挑選的，稱為網路拓樸。

所有的分散式雜湊表實作拓樸有某些基本的性質：對於任一關鍵值${\displaystyle k}$，某個節點要不就擁有${\displaystyle k}$，要不就擁有一個連結能連結到距離較接近${\displaystyle k}$的節點。因此使用以下的貪心演算法即可容易地將訊息轉送到擁有關鍵值${\displaystyle k}$的節點：在每次執行時，將訊息轉送到ID較接近${\displaystyle k}$的鄰近節點。若沒有這樣的節點，那我們一定抵達了最接近${\displaystyle k}$的節點，也就是擁有${\displaystyle k}$的節點。這樣的轉送方法有時被稱為「基於關鍵值的轉送方法」。

除了基本的轉送正確性之外，拓樸中另有兩個關鍵的限制：其一為保證任何的轉送路徑長度必須盡量短，因而請求能快速地被完成；其二為任一節點的鄰近節點數目（又稱最大節點度（Degree (graph theory)（英语：Degree (graph theory)）））必須盡量少，因此維護的花費不會過多。當然，轉送長度越短，則最大節點度越大。以下列出常見的最大節點度及轉送長度（${\displaystyle n}$為分散式雜湊表中的節點數）

• 最大節點度${\displaystyle O(1)}$，轉送長度${\displaystyle O(\log n)}$
• 最大節點度${\displaystyle O(\log n)}$，轉送長度${\displaystyle O(\log n/\log \log n)}$
• 最大節點度${\displaystyle O(\log n)}$，轉送長度${\displaystyle O(\log n)}$
• 最大節點度${\displaystyle O(n^{1/2})}$，轉送長度${\displaystyle O(1)}$

第三個選擇最為常見。雖然他在最大節點度與轉送長度的取捨中並不是最佳的選擇，但這樣的拓樸允許較為有彈性地選擇鄰近節點。許多分散式雜湊表實作利用這種彈性來選擇延遲較低的鄰近節點。

最大的轉送長度與直徑有關：最遠的兩節點之間的最短跳数（Hop Distance）。無疑地，網路的最大轉送長度至少要與它的直徑一樣長，因而拓樸也被最大節點度與直徑的取捨限制住^[6]，而這在圖論中是基本的性質。因為貪婪演算法（Greedy Method）可能找不到最短路徑，因此轉送長度可能比直徑長^[7]。

範例

分散式雜湊表實作與協定

• Bamboo^[8]
• Bunshin^[9]
• 內容可定址網路（Content Addressable Network）
• Chord（英语：Chord）
• DKS系統^[10]
• Kademlia
• Leopard
• MACE（英语：MACE）^[11]
• Pastry（英语：Pastry (DHT)）
• P-Grid（英语：P-Grid）
• Tapestry（英语：Tapestry (DHT)）

分散式雜湊表的應用

• BitTorrent：檔案分享應用。BitTorrent可以選用DHT作為分散式Tracker。
• Warez P2P（英语：Warez P2P）：檔案分享應用。
• The Circle：檔案分享應用與聊天。
• CSpace：安全的溝通系統。
• Codeen（英语：Codeen）：網頁快取。
• CoralCDN（英语：CoralCDN）
• Dijjer
• eMule：檔案分享應用。
• I2P：匿名網路。
• JXTA（英语：JXTA）：開放原始碼的點對點平台。
• NEOnet：檔案分享應用。
• Overnet：檔案分享應用。

参考文献

1. （英文） Hari Balakrishnan, M. Frans Kaashoek, David Karger, Robert Morris與Ion Stoica, Looking up data in P2P systems （页面存档备份，存于互联网档案馆）. 於Communications of the ACM, 2003年1月
2. （英文） Moni Naor與Udi Wieder. Novel Architectures for P2P Applications: the Continuous-Discrete Approach （页面存档备份，存于互联网档案馆）. Proc. SPAA, 2003年
3. （英文） Gurmeet Singh Manku. Dipsea: A Modular Distributed Hash Table （页面存档备份，存于互联网档案馆）.博士論文（史丹佛大學），2004年8月
4. （英文） Agostino Forestiero, Emilio Leonardi, Carlo Mastroianni and Michela Meo. Self-Chord: a Bio-Inspired P2P Framework for Self-Organizing Distributed Systems. IEEE/ACM Transactions on Networking, 2010.
5. （英文） W. Wu, Y. Chen, X. Zhang, X. Shi, B. Deng, X. Li. LDHT: locality-aware distributed hash tables. Proc. of International Conference on Information Networking (ICOIN), 2008.
6. （英文） 存档副本. [2012-01-10]. （原始内容存档于2012-02-17）. 
7. （英文） Gurmeet Singh Manku, Moni Naor, and Udi Wieder. Know thy Neighbor's Neighbor: the Power of Lookahead in Randomized P2P Networks （页面存档备份，存于互联网档案馆）. Proc. STOC, 2004.
8. 存档副本. [2007-01-21]. （原始内容存档于2020-09-01）. 
9. 存档副本. [2007-01-21]. （原始内容存档于2018-10-05）. 
10. 存档副本. [2017-09-12]. （原始内容存档于2012-01-20）. 
11. 存档副本. [2017-09-12]. （原始内容存档于2005-10-18）. 

外部連結

• （英文） Distributed Hash Tables, Part 1 （页面存档备份，存于互联网档案馆）由Brandon Wiley所著。
• （英文） Sloppy Hashing and Self-Organizing Clusters由CoralCDN專案提供的著作。
• （英文） Tangosol Coherence （页面存档备份，存于互联网档案馆）介紹一個類似DHT的架構，但所有節點都知道網路中其他參與者的資訊。

參見

• memcached：一個高效能、分散式的物件快取系統。