论文笔记

这是四个原始分布式哈希表(Distributed Hash Table, DHT)中的一个，在 ACM 数据通信特别兴趣组(Special Interest Group on Data Communication, SIGCOMM)的会议上发表（计算机网络顶尖会议之一）。

论文PDF¹
项目页面

作者

Ion Stoica 罗马尼亚裔美国计算机科学家，加州大学伯克利分校计算机科学教授和 AMPLab 联合主任，Conviva、Databricks 联合创始人及首席技术官。个人主页
Robert Tappan Morris 美国计算机科学家，在康奈尔大学研究生期间制作了莫里斯蠕虫（并被定罪）。哈佛大学文学学士学位，哈佛大学博士，麻省理工终身教授。个人主页
David Karger 麻省理工大学计算机科学和人工智能实验室教授。哈佛大学文学学士学位和斯坦福大学计算机科学博士。个人主页
Marinus Frans (Frans) Kaashoek 荷兰计算机科学家，麻省理工教授
Hari Balakrishnan 麻省理工教授

前置知识

一致性哈希

首先要思考在这种问题：如果数据被散布到 $N$ 个服务器中，如何检索数据实际在哪一个服务器中？

通常最简单的办法是使用某个哈希算法，计算出一个数值，并对 $N$ 取模： $Hash(key) \mod N$ ，这样就可以得到一个 $[0,N)$ 的输出，只需要将数据存入对应的服务器即可。并且对于任意的数据，都可以快速计算出其被存放在哪一个服务器中

但是，如果要增删服务器个数，则会出现很麻烦的问题。对于绝大部分的 $key$ ， $Hash(key) \mod N \ne Hash(key) \mod (N \pm 1)$
因此如果网络要进行动态变化，几乎所有的节点都需要重新缓存。而在分布式网络中，动态变化是极为常见的。这将导致很多的问题

麻省理工在 1997 年在 Consistent Hashing and Random Trees: Distributedd Caching Protocols for Relieving Hot Spots on the World Wide Web² 中提出了一致性哈希算法(Consistent Hashing)

对资源和服务器都使用一样的哈希函数计算出其标识符，并放置到环上。如下图，对于 SHA1 的 $2^{160}Bits$ 将所有可能的哈希结果取值连成一个环。并在服务器和资源根据其哈希值放置到对应的位置，形成下图（红色为服务器，黄色为资源）

对于一个任意的资源，其将会被存放在其在环内位置顺时针旋转的第一个服务器中
当要检索特定的资源 $key$ ，只需要计算出 $Hash(key)$ ，然后沿着环顺时针找到第一个可用的服务节点即可（如果一个节点失效，则可以将请求发送给下一个节点）

使用这种方式，当一个节点被移除或是被添加，只会影响其相邻的节点，而不会对整个网络造成影响

更详细的细节可以参考论文

简介

在一致性哈希中，仍然存在一个麻烦的问题：尽管节点的动态加入和离开只会影响部分资源，但是所有的节点都需要更新其路由表
当节点数量很大，比如 P2P 下载时，可能会有百万、千万数目的节点，并且这些节点在每个时刻都会有大量的加入和离开

要解决这个问题，就引出了 Chord 算法

指针表

Chord 的精髓在于其哈希表。在一致性哈希的基础上，每个节点需要维护一个指针表(finger table)

指针表包含如下内容

// Section 地址区间
type Section struct {
    Start       int             // 起始地址
    Interval    int             // 区间
    Node        NodeAddressh    // 起始地址后的第一个节点
}
type FingerTable struct {
    Fingers     []Section;      // 当前节点的路由表
    Successor   NodeAddress;    // 后继节点
    Predecessor NodeAddress;    // 前驱节点
}

在逻辑上，指针表是一个带有额外节点信息的双向成环链表

其重点在于这个特殊的区间地址
在整个指针表中，第 $i$ 个区间起始于 $(n+2^{k-1})\mod 2^m, 1<=k<=m$ 。
每个区间的地址范围则是其开始位置到下一个区间的开始位置。
区间对应的节点是其起始位置后的第一个节点。

在 Chord 中，对于 $m$ 位输出的哈希函数（最大值为 $2^m$ ），指针表中的个数为 $m$

如图，对于 $4$ 位的输出，其哈希的取值范围为 $[0,15]$ ，由于其拓扑结构会形成一个环，因此其中 $16$ 对应的就是 $0$
对于节点 $0$ ，其每个区间对应的起始节点分别是节点 $1,2,4,16(0)$
如果有节点位于 $0,2,13$ 则会生成如下的指针表

键	值	start	interval	node
前驱节点	16
后继节点	2
指纹表	1	1	$[0,1)$	2
	2	2	$[1,2)$	2
	3	4	$[2,4)$	13
	4	8	$[4,8)$	13

因此，对于长度为 $2^m$ 的哈希函数，其只需要存储长度为 $m$ 的表，也即空间复杂度为 $O(log_{2}{N})$ ，因此如果要更新，也只会影响部分节点

从表中，也可以发现，Chord 是存在冗余的，如 $1$ 、 $2$ 和 $3$ 、 $4$ 实际上分别是相同的，因此冗余了一倍的数据

检索

实际上，从数值上来看，很容易想到二叉树，因此实际上完全可以按照二叉树的思路进行检索

如要检索一个特定的节点，首先要查找其处于哪一个区间。时间复杂度 $O(1)$ （可以直接根据哈希值计算出所属区间）
接着由该区间对应的节点进行下一步检索。时间复杂度 $O(log_{2}{N})$
重复上述过程直至检索到对应的内容

整个检索的时间复杂度为 $O(logN)$

定理2：在有 $N$ 个节点的网络中，要查找特定的后继节点，必须要通信的节点个数为 $O(logN)$

这是论文中提出的一条定理，其证明如下

假设节点 $n$ 希望检索资源 $k$ 的存储的后继节点 $p$

如果 $n \ne q$ ，那么 $n$ 需要从其指针表中查找距离 $k$ 最近的节点。假设其对应的是指针表中的第 $i$ 项，并且该区间对应的节点是 $f$ ，那么 $distance(n,f) >= 2^{i-1}$ 。而 $f$ 和 $p$ 都位于第 $i$ 个区间中，按照指针表的规律，可以得知 $distance(f,p) <= 2^{i-1}$
也即，可以得知， $f$ 与 $p$ 的距离小于 $n$ 到 $p$ 的距离——每次检索距离都会收敛，并且至少距离折半

检索部分伪代码

// ask node n to find id's successor
n.find_successor(id)
	n' = find_predecessor(id)
    return n'.successor

// ask node n to find id's predecessor
n.find_predecessor(id)
	n' = n
    while(id not in (n', n'.successor])
    	n' = n'.closest_preceding_finger(id)
    return n'

// return closest finger preceding id
n.closest_preceding_finger(id)
	for i = m downto 1
    	if (finger[i].node in (n, id))
        	return finger[i].node
    return n

插入

插入和删除节点类似，以插入为例

要确保算法的正确性，必须确保节点加入和离开后，保证以下两点：

每个节点的后继都应该正确
每一个资源都应该被存放在其应该存放的节点中
初始化节点 $n$ 的前驱和指针表
更新其他节点的指针表和前驱节点
更新高层应用的状态

定理3：在有 $N$ 个节点的网络中，任意节点的加入和离开更新指针表的复杂度为 $O(log^2N)$

插入部分伪代码

#define successor finger[1].node

// node n joins the network;
// n' is an arbitrary node in the network
n.join(n')
    if(n')
        init_finger_table(n')
        update_others()
        // move keys in (predecessor, n] from successor
    else // n is the only node in the network
        for i = 1 to m
            finger[i].node = n
        predecessor = n

// initialize finger table of local node
// n' is an arbitrary node already in the network
n.init_finger_table(n')
    finger[1].node = n'.find_successor(finger[1].start)
    predecessor = successor.predecessor
    successor.predecessor = n
    for i = 1 to m-1
        if (finger[i+1].start in [n, finger[i].node))
            finger[i+1].node = finger[i].node
        else
            finger[i+1].node = n'.find)successor(finger[i+1].start)

// update all nodes whose finger
// table should refer to n
n.update_others()
    for i = 1 to m
        // find last node p those i-th finger might be n
        p = find_predecessor(n-2^(i-1))
        p.update_finger_table(n, i)

// if s is i-th finger of n, update n's finger table with s
n.update_finger_table(s, i)
    if (s in [n, finger[i].node))
        finger[i].node = s
        p = predecessor // get first node preceding n
        p.update_finger_table(s, i)

稳定性

在高并发网络下，往往无法保证“正确性”，在一个节点插入的同时可能会有别的查询任务执行
因此实际上共有 $3$ 种可能：

所有信息正常：可以正确、快速查询到数据
后继指针正确，但指针表错误：可以正确查询到数据，但是可能会很慢
后续指针错误，资源还未同步到新的节点：可能会导致查询失败

要保障高并发情况下的正确性，就应该在修改节点时，尽可能不要对整个网络产生修改
在加入节点 $n$ 时，只需要正确使用 $n'$ 查询并设置后继
在节点 $n$ 运行过程中，需要周期性地运行稳定性函数，判断后继节点的前驱是否要被更新为当前节点的前驱；同时还需要向后继节点 $s$ 通知检查更新 $n$
当 $s$ 被通知要更新时，需要判断是否需要更新前驱节点为 $n$
最后则是对指针表的更新，对指针表的每一项更新指针表

论文中对于指针表的更新并不是那么详细，理论上如果可以做到延迟更新，只通知原本存储资源的节点。
每次有请求发送到原节点时，由其返回新节点的信息要求重新请求并更新指针表似乎对整个系统的消耗更小？
（该部分仅为个人想法）

稳定性部分伪代码

n.join(n')
    predecessor = nil
    successor = n'.find_successor(n)

// periodically verify n's immediate successor,
// and tell the successor about n 
n.stabilize()
    x = successor.predecessor
    if (x in (n, successor))
        successor = x
    successor.notify(n)

// n' thinks it might be our predecessor
n.notify()
    if(predecessor is nil or n' in (predecessor, n))
        predecessor = n'

// periodically refresh finger table entries
n.fix_fingers()
    i = random index > 1 into finger[]
    finger[i].node = find_successor(finger[i].start)

定理

在论文中共提出并证明了了这些理论

For any set of $N$ $N$ nodes and $K$ $K$ keys, with high probability:
- Each node is responsible for at most $(1+\epsilon)K/N$ keys
- When an $(N+1)^{st}$ node joins or leaves the network, responsibility for $O(K/N)$ keys changes hands (and only to or from the joining or leaving node)
With high probability (or under standard hardness assumptions), the number of nodes that must be contacted to find a successor in an N-node network is $O(logN)$
With high probability, any node joining or leaving an N-node Chord network will use $O(log^2N)$ messages to re-establish the Chord routing invariants and finger tables
Once a node can successfully resolve a given query, it will always be able to do so in the future
At some time after the last join all successor pointers will be correct
If we take a stable network with $N$ nodes, and another set of up to $N$ nodes joins the network with no finger pointers (but with correct successor pointers), then lookups will still take $O(logN)$ time with high probability
If we use a successor list of length $r=O(logN)$ in a network that is initially stable, and then every node fails with probability $1/2$ , then with high probability find_successor returns the closest living successors to the query key
If we use a successor list of length $r=O(logN)$ in a network that is initially stable, and then every node fails with probability $1/2$ , then the expected time to execute find_successor in the failed network is $O(logN)$

与 Freenet 对比

Freenet 是一个点对点的文件索引系统
在 Chord 中也提到了 Freenet，而在学习 Freenet 时，也可以发现其与 DHT 有非常高的相似性

Chord 和 Freenet 的差异主要在于路由表以及拓扑结构上。

Freenet 为了确保匿名性，并非任意两个节点都可以直接联通，这将会导致路由表、拓扑结构无法处于理想状态。为了加速查询，Freenet 使用查询缓存，来确保资源逐渐向其理想节点“移动”。但这个移动是不可控的，因此单纯向距离更近的节点查询并不一定能成功检索到资源（资源可能距离理想位置的节点还很远，但检索者已经向理想位置的节点发起查询）

而 Chord 中并不需要考虑匿名性，路由表可以经过精心设计来确保查询效率（而非 Freenet 中的动态调控），这确保了一定可以成功检索资源

Chord: A Scalable Peer-to-peer Lookup Service for Internet Applications