分布式散列表

分散式杂凑表（英语：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：一个高效能、分散式的物件快取系统。