Chord (Consistent Hashing, DHT)

对于上面问题，有几种比较典型的办法来解决。

方案一、Napster：使用一个中心服务器接收所有的查询，服务器告知去哪下载其所需要的数据。如图 2 所示。存在的问题是中心服务器单点失效导致整个网络瘫痪。

方案二、Gnutella：使用消息洪泛（message flooding）来定位数据。一个消息被发到系统内每一个节点，直到找到其需要的数据为止。如图 3 所示。当然，使用生存时间（TTL）来限制网络内转发消息的数量。存在的问题是消息数与节点数成线性关系，导致网络负载较重。

方案三、SN（Super Node）型。现在大多数采用所谓超级节点（Super Node），SN 保存网络中节点的索引信息，这一点和中心服务器类型一样，但是网内有多个 SN，其索引信息会在这些 SN 中进行传播，所以整个系统的崩溃几率就会小很多。尽管如此，网络还是有崩溃的可能。

方案四、分布式哈希表系统（Distributed Hash Table，DHT）。主要思想是： 首先，每条文件索引被表示成一个(K, V)对，K称为关键字，可以是文件名（或文件的其他描述信息）的哈希值，V是实际存储文件的节点的 IP 地址（或节点的其他描述信息）。所有的文件索引条目（即所有的（K, V）对）组成一张大的文件索引哈希表，只要输入目标文件的 K 值，就可以从这张表中查出所有存储该文件的节点地址。然后，再将上面的大文件哈希表分割成很多局部小块，按照特定的规则把这些小块的局部哈希表分布到系统中的所有参与节点上，使得每个节点负责维护其中的一块。 这样，节点查询文件时，只要把查询报文路由到相应的节点即可（该节点维护的哈希表分块中含有要查找的(K,V)对）。如图 4 所示。

这里介绍的 Chord 算法就是解决网络内节点定位问题的一种 DHT 实现。它通过多个节点跳转找到我们所查找的资源。

考虑如下场景：节点 n 寻找 KID 为 id 的资源，此时节点 n 首先问询是否在下一个节点上（find_successor），这要看资源 k 的 KID 是否在该节点 NID 和下一个节点的 NID 之间，若在则说明资源 k 被分配给了下一个节点，若不在则在下一个节点上发起同样的查询，问询下下一个点是否有该资源。如此迭代下去，用伪代码定义这个操作：

n.find_successor(id)
  if (id є (n; successor])
    return successor;
  else
    // 将查询沿着环进行下去
    return successor.find_successor(id);

如图 6 所示。

节点 N8 寻找 K54 这个资源，N8.find_successor(K54)发现下一个节点 N14 不合符 $54\in (8;14]$ ，于是 N14 发起同样的搜索，然后一跳一跳后直到节点 N56 满足 $54\in (51;56]$ ，于是得知资源 K54 在 N56 这个节点上。

在一个有 N 个节点的环上，这样的查找方法显然在最坏的时候要查找 N 次才能得到所需资源的位置，查找次数与节点个数成线性关系。显然，这样的效率不给力，所以 Chord 使用了可伸缩资源定位的方式来提高效率。

在每个节点 N 上都维护了最多有 m 项（m 为 ID 的位数）的路由表（称为 finger table），用来定位资源。这个表的第 $i$ 项是该节点的后继节位置，至少包含到 $2^{(i-1)}$ 后的位置。还是延续上边的例子。

节点 N8 的路由表中（如图 7 所示），左边那一栏包含了 N8+1 到 N8+32 的位置，右边那一栏每个位置对应的实际存在的节点。比如 N8+1-->N14，表示在 N8 后的第一个位置上的资源由 N14 来负责。这样记录有以下优势：

• 每个节点只包含全网中一小部分节点的信息。
  
• 每个节点对于临近节点负责的位置知道的更多，比如 N8 节点对于 N14 负责的位置知道 3 处，而对 N21 负责的位置只知道 1 处。
  
• 路由表通常不包含直接找到后继节点的信息，往往需要询问其他节点来完成。
  

当在某个节点上查找资源时，首先判断其后继节点是不是就持有该资源， 若没有则直接从该节点的路由表从最远处开始查找， 看哪一项离持有资源的节点最近（发现后跳转），若没有则说明本节点自身就有要寻找的资源。如此迭代下去。

例如：节点 N8 寻找 K54 这个资源，如图 8 所示。

首先，在 N8 上查找后继节点为 N14，发现 K54 并不符合 $54\in (8;14]$ 的要求，那么直接在 N8 的路由表上查找符合这个要求的表项（由远及近查找），此时 N8 的路由表为图 9 所示。

我们发现路由表中最远的一项 N8+32=N42 满足 $42\in (8;54]$ ，则说明 N42 这个点离持有 K54 这个资源的节点最近（因为 N42 在该路由表中离 N8 这个节点最远），那么此时跳到 N42 这个节点上继续查找。N42 的后继节点为 N48，不符合 $54\in (42;48]$ 的要求，说明 N48 不持有资源 54，此时，开始在 N42 的路由表上查找。

N42 节点的路由表为图 10 所示。

我们由远及近开始查找，发现 N42+8=N51 满足 $51\in (42;54]$ ，则说明 N51 这个点离持有 K54 这个资源的节点最近，那么此时跳到 N51 这个节点上继续查找。N51 节点的后继节点为 N56，符合 $54\in (51;56]$ ，此时定位完成，N56 持有资源节点 K54。