唐福林博客雨

Jun

分布式计算与DHT网络
2008-06-06 7:43 pm 作者：tangfl.openid.35.com

引用：http://www.wikilib.com/wiki?title=DHT%E7%BD%91%E7%BB%9C

分布式散列表（英语：Distributed Hash Table，简称DHT）是分布式计算系统中的一类，用来将一个关键值（key）的集合分散到所有在分布式系统中的节点，并且可以有效地将讯息转送到唯一一个拥有查询者提供的关键值的节点（Peers）。这里的节点类似散列表中的储存位置。分布式散列表通常是为了拥有极大节点数量的系统，而且在系统的节点常常会加入或离开（例如网络断线）而设计的。在一个结构性的延展网络（overlay network）中，参加的节点需要与系统中一小部份的节点沟通，这也需要使用分布式散列表。分布式散列表可以用以建立更复杂的服务，例如分布式档案系统、点对点技术档案分享系统、合作的网页快取、多播、任播（anycast）、网域名称系统以及即时通讯等。
目录

* 1 发展背景
* 2 性质
* 3 结构
o 3.1 关键值空间分割
o 3.2 延展网络
* 4 范例
o 4.1 分布式散列表实作与协定
o 4.2 分布式散列表的应用
* 5 参见
* 6 参考资料
* 7 外部链接

发展背景

研究分布式散列表的主要动机是为了开发点对点系统，像是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)

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

最大的转送长度与直径有关：最远的两节点之间的最短距离。无疑地，网络的最大转送长度至少要与它的直径一样长，因而拓撲也被最大节点度与直径的取舍限制住[4]，而这在图论中是基本的性质。因为贪婪算法(Greed Method)可能找不到最短路径，因此转送长度可能比直径长[5]。

范例

分布式散列表实作与协定

* Bamboo[6]
* Bunshin[7]
* 内容可寻址网络 (Content Addressable Network)
* Chord
* DKS系统[8]
* Kademlia
* Leopard
* MACE[9]
* Pastry
* P-Grid
* Tapestry

分布式散列表的应用

* BitTorrent：档案分享应用。BitTorrent 可以选用DHT作为分布式Tracker。
* Warez P2P：档案分享应用。
* The Circle：档案分享应用与聊天。
* CSpace：安全的沟通系统。
* Codeen：网页快取。
* CoralCDN
* Dijjer
* eMule：档案分享应用。
* I2P：匿名网络。
* JXTA：开放原始码的点对点平台。
* NEOnet：档案分享应用。
* Overnet：档案分享应用。

参见

* memcached：一个高效能、分布式的物件快取系统。