分布式散列表

分布式散列表示意图

分布式散列表（英语：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））等。

性质[编辑]

分布式散列表本质上强调以下特性：

离散性：构成系统的节点并没有任何中央式的协调机制。
伸缩性：即使有成千上万个节点，系统仍然应该十分有效率。
容错性：即使节点不断地加入、离开或是停止工作，系统仍然必须达到一定的可靠度。

要达到以上的目标，有一个关键的技术：任一个节点只需要与系统中的部分节点沟通。一般来说，若系统有<math>n</math>个节点，那么只有<math>\Theta(\log n)</math>个节点是必须的（见后述）。因此，当成员改变的时候，只有一部分的工作（例如资料或关键值的发送，散列表的改变等）必须要完成。

有些分布式散列表的设计寻求能对抗网络中恶意的节点的安全性，但仍然保留参加节点的匿名性。在其他的点对点系统（特别是文件分享）中较为少见。参见匿名点对点技术。

最后，分布式散列表必须处理传统分布式系统可能遇到的问题，例如负载平衡、资料完整性，以及性能问题（特别是确认转送消息、资料存储及读取等动作能快速完成）。

结构[编辑]

分布式散列表的结构可以分成几个主要的组件^[2]^[3]。其基础是一个抽象的关键值空间（keyspace），例如说所有160位长的字符串集合。关键值空间分割（keyspace partitioning）将关键值空间分割成数个，并指定到在此系统的节点中。而延展网络则连接这些节点，并让他们能够借由在关键值空间内的任一值找到拥有该值的节点。

当这些组件都准备好后，一般使用分布式散列表来存储与读取的方式如下所述。假设关键值空间是一个160位长的字符串集合。为了在分布式散列表中存储一个文件，名称为<math>filename</math>且内容为<math>data</math>，我们计算出<math>filename</math>的SHA1散列值——一个160位的关键值<math>k</math>——并将消息<math>put(k, data)</math>送给分布式散列表中的任意参与节点。此消息在延展网络中被转送，直到抵达在关键值空间分割中被指定负责存储关键值<math>k</math>的节点。而<math>(k, data)</math>即存储在该节点。其他的节点只需要重新计算<math>filename</math>的散列值<math>k</math>，然后提交消息 <math>get(k)</math>给分布式散列表中的任意参与节点，以此来找与<math>k</math>相关的资料。此消息也会在延展网络中被转送到负责存储<math>k</math>的节点。而此节点则会负责传回存储的资料<math>data</math>。

以下分别描述关键值空间分割及延展网络的基本概念。这些概念在大多数的分布式散列表实现中是相同的，但设计的细节部分则大多不同。

关键值空间分割[编辑]

大多数的分布式散列表使用某些稳定散列（consistent hashing）方法来将关键值对应到节点。此方法使用了一个函数<math>\delta(k_1, k_2)</math>来定义一个抽象的概念：从关键值<math>k_1</math>到<math>k_2</math>的距离。每个节点被指定了一个关键值，称为ID。ID为<math>i</math>的节点拥有根据函数<math>\delta</math>计算，最接近<math>i</math>的所有关键值。

例：Chord分布式散列表实现将关键值视为一个圆上的点，而<math>\delta(k_1, k_2)</math>则是沿着圆顺时钟地从<math>k_1</math>走到<math>k_2</math>的距离。结果，圆形的关键值空间就被切成连续的圆弧段，而每段的端点都是节点的ID。如果<math>i_1</math>与<math>i_2</math>是邻近的ID，则ID为<math>i_2</math>的节点拥有落在<math>i_1</math>及<math>i_2</math>之间的所有关键值。

稳定散列拥有一个基本的性质：增加或移除节点只改变邻近ID的节点所拥有的关键值集合，而其他节点的则不会被改变。对比于传统的散列表，若增加或移除一个位置，则整个关键值空间就必须重新对应。由于拥有资料的改变通常会导致资料从分布式散列表中的一个节点被搬到另一个节点，而这是非常浪费带宽的，因此若要有效率地支持大量密集的节点增加或离开的动作，这种重新配置的行为必须尽量减少。

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

延展网络[编辑]

每个节点保有一些到其他节点（它的邻居）的链接。将这些链接总合起来就形成延展网络。而这些链接是使用一个结构性的方式来挑选的，称为网络拓朴。

所有的分布式散列表实现拓朴有某些基本的性质：对于任一关键值<math>k</math>，某个节点要不就拥有<math>k</math>，要不就拥有一个链接能链接到距离较接近<math>k</math>的节点。因此使用以下的贪心算法即可容易地将消息转送到拥有关键值<math>k</math>的节点：在每次执行时，将消息转送到ID较接近<math>k</math>的邻近节点。若没有这样的节点，那我们一定抵达了最接近<math>k</math>的节点，也就是拥有<math>k</math>的节点。这样的转送方法有时被称为“基于关键值的转送方法”。

除了基本的转送正确性之外，拓朴中另有两个关键的限制：其一为保证任何的转送路径长度必须尽量短，因而请求能快速地被完成；其二为任一节点的邻近节点数目（又称最大节点度（Degree (graph theory)（英语：Degree (graph theory)）））必须尽量少，因此维护的花费不会过多。当然，转送长度越短，则最大节点度越大。以下列出常见的最大节点度及转送长度（<math>n</math>为分布式散列表中的节点数）

最大节点度<math>O(1)</math>，转送长度<math>O(\log n)</math>
最大节点度<math>O(\log n)</math>，转送长度<math>O(\log n / \log \log n)</math>
最大节点度<math>O(\log n)</math>，转送长度<math>O(\log n)</math>
最大节点度<math>O(n^{1/2})</math>，转送长度<math>O(1)</math>

第三个选择最为常见。虽然他在最大节点度与转送长度的取舍中并不是最佳的选择，但这样的拓朴允许较为有弹性地选择邻近节点。许多分布式散列表实现利用这种弹性来选择延迟较低的邻近节点。

最大的转送长度与直径有关：最远的两节点之间的最短跳数（Hop Distance）。无疑地，网络的最大转送长度至少要与它的直径一样长，因而拓朴也被最大节点度与直径的取舍限制住^[6]，而这在图论中是基本的性质。因为贪心算法（Greedy Method）可能找不到最短路径，因此转送长度可能比直径长^[7]。

示例[编辑]