在去中心化的世界中，分布式哈希表 (DHT) 近年来产生了革命性的影响。第一代对等网络架构的混乱、临时的拓扑结构已被一组具有涌现秩序、可证明的属性和卓越性能的拓扑结构所取代。DHT 算法的知识将成为未来分布式应用程序开发的关键要素。

许多研究型 DHT 由大学开发，被开源社区采纳并实施。也存在一些专有实现，但目前没有可用的 SDK；相反，它们嵌入在商业上可用的产品中。每种 DHT 方案通常都被标榜为独立的实体，与其他所有方案都不同。实际上，各种可用的方案都适合于一个多维矩阵。选择一个，进行一些调整，最终会得到另一个方案。现有的研究型 DHT，例如 Chord、Kademlia 和 Pastry，因此是开发您自己的自定义方案的起点。每种方案都具有可以以多种方式组合的属性。为了充分表达选项范围，让我们从一个基本设计开始，然后增加复杂性以获得有用的属性。

基本上，DHT 执行哈希表的功能。您可以存储键值对，并且如果您有键，则可以查找值。值不一定持久存储在磁盘上，尽管您当然可以将 DHT 基于持久哈希表之上，例如 Berkeley DB；事实上，这已经完成了。关于 DHTs 有趣的事情是，存储和查找分布在多台机器之间。与现有的主/从数据库复制架构不同，所有节点都是可以自由加入和离开网络的对等方。尽管网络成员资格的周期性随机变化似乎很混乱，但 DHTs 对性能做出了可证明的保证。

为了开始我们对 DHT 设计的探索，我们从一个循环双向链表开始。列表中的每个节点都是网络上的一台机器。每个节点都保留对列表中下一个和上一个节点的引用，即其他机器的地址。我们必须定义一个顺序，以便我们可以确定列表中每个节点的“下一个”节点是什么。Chord DHT 使用的方法来确定下一个节点如下：为每个节点分配一个唯一的 k 位随机 ID。将节点排列成一个环，使 ID 沿环顺时针方向递增。对于每个节点，下一个节点是顺时针方向距离最小的节点。对于大多数节点，这是 ID 最接近但仍大于当前节点 ID 的节点。唯一的例外是 ID 最大的节点，其后继节点是 ID 最小的节点。这种距离度量在距离方法（清单 1）中更具体地定义。

# This is a clockwise ring distance function.
# It depends on a globally defined k, the key size.
# The largest possible node id is 2**k.
def distance(a, b):
    if a==b:
        return 0
    elif a<b:
        return b-a;
    else:
        return (2**k)+(b-a);

每个节点本身都是一个标准的哈希表。要从哈希表中存储或检索值，您只需在网络中找到适当的节点，然后在那里执行正常的哈希表存储或查找。确定哪个节点适合特定键（Chord 使用的那个）的简单方法与确定特定节点 ID 的后继节点的方法相同。首先，获取键并对其进行哈希处理以生成一个精确的 k 位键。将此数字视为节点 ID，并通过从环中的任何点开始并顺时针工作直到找到 ID 最接近但仍大于键的节点来确定哪个节点是其后继节点。您找到的节点是负责存储和查找该特定键的节点（清单 2）。使用哈希生成键是有益的，因为哈希通常分布均匀，并且不同的键在网络中的所有节点上均匀分布。

# From the start node, find the node responsible
# for the target key
def findNode(start, key):
    current=start
    while distance(current.id, key) > \
          distance(current.next.id, key):
        current=current.next
    return current

# Find the responsible node and get the value for
# the key
def lookup(start, key):
    node=findNode(start, key)
    return node.data[key]

# Find the responsible node and store the value
# with the key
def store(start, key, value):
    node=findNode(start, key)
    node.data[key]=value

这种 DHT 设计很简单，但完全足以实现分布式哈希表的目的。给定一个具有完美正常运行时间的静态节点网络，您可以从任何节点和键开始，并找到负责该键的节点。需要记住的重要一点是，尽管到目前为止的示例代码看起来像一个相当普通的双向链表，但这只是 DHT 的模拟。在真正的 DHT 中，每个节点都将在不同的机器上，并且对它们的所有调用都需要通过某种套接字协议进行通信。

为了使当前设计更有用，最好考虑节点加入和离开网络的情况，无论是故意的还是在发生故障的情况下。为了启用此功能，我们必须为我们的网络建立一个加入/离开协议。Chord 加入协议的第一步是使用正常的查找协议查找新节点 ID 的后继节点。新节点应插入在找到的后继节点和该节点的上一个节点之间。新节点负责上一个节点负责的键的一部分。为了确保所有查找都能正常工作，在先前的节点将其下一个节点指针更改为指向新节点之前，应将适当部分的键复制到新节点。

离开非常简单；离开节点将其所有存储的信息复制到其上一个节点。然后，上一个节点将其下一个节点指针更改为指向离开节点的后继节点。加入和离开代码类似于从普通链表中插入和删除元素的代码，但增加了在加入/离开节点及其邻居之间迁移数据的要求。在普通链表中，您删除一个节点以删除其保存的数据。在 DHT 中，节点的插入和删除与数据的插入和删除无关。可以将 DHT 节点视为类似于持久哈希表实现（例如 Berkeley DB）中使用的周期性重新调整的桶。

允许网络拥有动态成员，同时确保存储和查找仍然正常运行，这无疑是对我们设计的改进。但是，性能很差——O(n)，预期性能为 n/2。遍历的每个节点都需要与网络上不同的机器进行通信，这可能需要建立 TCP/IP 连接，具体取决于选择的传输方式。因此，n/2 个遍历节点可能会非常慢。

为了获得更好的性能，Chord 设计添加了一个层以实现 O(log n) 性能。每个节点不是存储指向下一个节点的指针，而是存储一个“finger table”，其中包含 k 个节点的地址。当前节点的 ID 与 finger table 中节点的 ID 之间的距离呈指数级增长。路径上到达特定键的每个遍历节点都比上一个节点在对数上更近，总共遍历 O(log n) 个节点。

为了使对数查找工作，finger table 需要保持最新。过时的 finger table 不会破坏查找，只要每个节点都有最新的下一个指针，但只有当 finger table 正确时，查找才是对数的。更新 finger table 需要为表中的每个 k 个槽找到一个节点地址。对于任何槽 x，其中 x 为 1 到 k，finger[x] 通过获取当前节点的 ID 并查找负责键 (id+2^(x-1)) mod (2^k) 的节点来确定（清单 3）。在执行查找时，您现在在每个跳跃点有 k 个节点可供选择，而不是每个跳跃点只有一个。对于您从起始节点访问的每个节点，您都遵循 finger table 中距离键最短的条目（清单 4）。

def findFinger(node, key):
    current=node
    for x in range(k):
        if distance(current.id, key) > \
           distance(node.finger[x].id, key):
            current=node.finger[x]
    return current

def lookup(start, key):
    current=findFinger(start, key)
    next=findFinger(current, key)
    while distance(current.id, key) > \
          distance(next.id, key):
        current=next
        next=findFinger(current, key)
    return current

到目前为止，我们或多或少地定义了 Chord DHT 设计的原始版本，正如发明它的 MIT 团队所描述的那样。但这只是 DHT 世界的冰山一角。可以进行许多修改，以建立与原始 Chord 论文中描述的不同的属性，而不会失去 Chord 提供的对数性能和保证的查找。

DHT 可能有用的一个属性是能够被动地更新 finger table，需要定期执行查找以刷新表。使用 MIT Chord，您必须执行查找，击中 finger table 中所有 k 个项目的 O(log n) 个节点，这可能会导致大量的流量。如果节点可以在其他节点联系它进行查找时将其他节点添加到其 finger table 中，这将是有利的。由于已经建立了对话以进行查找，因此检查执行查找的节点是否是本地 finger table 的良好候选者几乎没有额外的开销。不幸的是，Chord 中的 finger table 链接是单向的，因为距离度量不是对称的。节点通常不会在其 finger table 中节点的 finger table 中。

解决此问题的一个方案是用基于 XOR 的距离度量替换 Chord 的模加距离度量。两个节点 A 和 B 之间的距离定义为节点 ID 的 XOR，节点 ID 被解释为无符号整数的二进制表示形式（清单 5）。XOR 是一种令人愉悦的距离度量，因为它是对称的。由于 distance(A, B) == distance(B, A)，对于任何两个节点，如果 A 在 B 的 finger table 中，则 B 在 A 的 finger table 中。这意味着节点可以通过记录查询它们的节点的地址来更新其 finger table，从而显着减少节点更新流量。它还简化了 DHT 应用程序的编码，因为您不需要保留单独的线程来定期调用 update 方法。相反，您只需在调用 lookup 方法时更新。

def distance(a, b):
    return a^b # In Python, this means a XOR b,
               # not a to the power of b.

到目前为止提出的设计的一个问题是到达给定节点的路径是脆弱的。如果路径中的任何节点拒绝合作，则查找将被卡住。在任意两个节点之间只有一条路径，因此绕过损坏的节点是不可能的。Kademlia DHT 通过加宽 finger table 来解决这个问题，使其为每个 finger table 槽包含一个 j 个引用的桶，而不是只有一个，其中 j 在整个网络中全局定义。现在每个跳跃点都有 j 个不同的选择，因此大约有 j*log(n) 条可能的路径。但是，路径的数量少于此，因为随着路径越来越接近目标，它们会收敛。但是，可能路径的数量可能大于 1，因此这是一个改进。

Kademlia 更进一步，根据记录的正常运行时间对桶中的节点进行排序。较旧的节点优先用于查询，只有在没有足够旧节点的情况下才添加新引用。除了提高查询的可靠性之外，这种方法还提供了额外的好处，即对网络的攻击（其中快速创建新节点以挤出好节点）将失败——甚至不会被注意到。

重要的是要理解，这些不同的属性不与特定的 DHT 实现绑定。我们从头开始逐步构建了一个 DHT 设计，将其开发成类似于 Chord 的东西，然后对其进行了修改，使其更像 Kademlia。不同的方法或多或少可以混合和匹配。您的 finger table 桶可以有 1 个槽或 j 个槽，具体取决于您是使用模加还是 XOR 作为距离度量。您可以始终跟随最近的节点，也可以根据正常运行时间或根据其他一些标准对它们进行排名。您可以从其他几种 DHT 设计中汲取灵感，例如 Pastry、OceanStore 和 Coral。您还可以使用自己的想法来设计满足您需求的完美设计。我自己，我对基本 Chord 设计进行了一些修改，以添加诸如匿名性、拜占庭容错查找、地理路由和高效广播消息以进入网络等属性。这样做很有趣，而且比您想象的要容易。

现在您已经知道如何创建自己的 DHT 实现，您可能想知道可以使用此代码执行哪些疯狂的事情。尽管可能有很多我尚未想到的 DHT 应用程序，但我知道人们已经在从事诸如文件共享、创建用于备份数据的共享硬盘驱动器、用对等名称解析系统替换 DNS、可扩展聊天和无服务器游戏等项目。

对于本文，我将代码捆绑到一个有趣的小示例应用程序中，这可能会引起读者对我之前在 Linux Journal 网站上关于对等 Superworms 的采访的兴趣（请参阅“资源”）。该应用程序是一个分布式端口扫描器，它将结果存储在模拟的 DHT 中（清单 6）。给定一个功能齐全的 DHT 实现，此脚本将具有一些方便的属性。首先，它允许多台机器为大规模扫描互联网贡献结果。这样，所有扫描活动都不能与单台机器关联。此外，它可以避免冗余扫描。如果主机已被扫描，则从 DHT 中获取结果，从而避免多次扫描。不需要中央服务器来保存所有结果或协调参与者的活动。此应用程序可能看起来有点隐蔽，但重点是鉴于 DHT 库，编写它很简单。相同的方法可以用于其他类型的分布式项目。

def __main__():
    id=int(random.uniform(0,2**k))
    node=Node(id)
    join(node, initialContact)

    line=raw_input('Enter an IP to scan: ').trim()
    key=long(sha.new(line).hexdigest(),16)
    value=lookup(node, key)
    if value==None:
        f=os.popen('nmap '+args[1])
        lines=f.readlines()
        value=string.join(lines, '\n')
        store(node, key, value)

在我们这个分为两部分的系列文章中，我们讨论了构建 DHT 的理论。下次，我们将讨论在实际应用中使用 DHT 的实际问题。