Chord：标识符环上的查找，不是中心目录

破除误解#

误解二：对等查找就是 Napster 去掉中心、或 Gnutella 换一套更省带宽的泛洪。 论文相关工作把两者都写成反例：Napster 一类系统把定位交给特殊服务器，Gnutella 一类系统用广播换可扩展性。Chord 只提供 lookup(key)，返回负责该键的节点的 IP 地址；它不规定文件名怎么切词，也不保证匿名。Freenet 被拿来对照：文档不指派给固定服务器，查找是在找缓存副本，于是不能保证已存在的文档一定能取回，也不能给出检索代价的下界。Chord 不提供匿名，但查找在可预期的步数内结束，结果是成功或明确失败。把本页读成某个文件共享品牌的兴衰，会把“键到节点”这条原语，换成另一套产品史。

误解三：$O(\log N)$ 是一张在任意损坏的覆盖网上都成立的最坏情况发票，仿真曲线可以直接当成公网时延。 定理 2 的表述带“高概率”，或者——因为他们选用 SHA-1 而不是 $k$-universal 哈希——改写成“基于标准困难性假设”。证明依赖标识符大致随机、每跳至少把剩余标识符距离减半；手指过时但仍然后继正确，查找仍然正确，只是可能退化成沿后继线性走。仿真里 $N=2^k$、$k$ 从 3 到 14，共存放 $100\cdot 2^k$ 个键，路径长度的均值大约是 $\frac12\log_2 N$，因为随机距离的二进制表示里大约一半的位是 1，跟一张手指就清掉一位。这是标识符跳数，不是 IP 毫秒。原型跑在美国 RON 试验床的十个站点上，超过十个“节点”是同一站点上的多份进程；中位查找时延大约 180 到 285 毫秒，并不能外推成百万节点公网覆盖网的实测。

误解四：GFS、Bigtable 和 Chord 都是“分布式系统论文”，中心还是对等只是实现细节。 GFS 用单主节点记住块在哪；客户端先问主，再跟 chunkserver 说话。Bigtable 用锁服务选 master、用元数据表找到 tablet，客户端把位置缓存起来。两者都把“谁知道全局形状”收成少量特权进程。Chord 的软件是链进应用的库，节点功能对等，没有逻辑根。分布式系统 里最贵的往往是谁必须出现在热路径上：Google 那两篇把热路径上的元数据做成可缓存的中心；Chord 把热路径做成对数跳的对等对话。把它们并成一句“都是分布式存储”，会把查找装置读丢。

标识符环、后继与手指表#

协议的心脏是对哈希函数的分布式求值：键被映射到负责它的节点。基哈希选用 SHA-1 一类函数，给节点和键各分配一个 $m$ 位标识符。节点标识通常是 IP 地址的哈希，键标识是键本身的哈希。$m$ 要大到碰撞概率可以忽略。原型里键长 160 位，节点之间用 TCP 说话，查找按迭代风格实现——发起者自己一连串去问，而不是把请求递归转发出去。仿真器同样实现迭代风格。

标识符按模 $2^m$ 排成环。键 $k$ 交给标识符等于 $k$、或沿环顺时针第一个跟上 $k$ 的节点，记作 $\mathrm{successor}(k)$。论文图 2 用 $m=3$ 的小圆讲完这件事：节点落在 0、1、3，键 1 在节点 1，键 2 在节点 3，键 6 在节点 0。节点加入时，它从后继那里接管自己到后继之间的那段键；离开时，自己的键交还给后继。其余分配不动。定理 1 把 1997 年的负载结论搬过来：高概率下每个节点负责至多 $(1+\varepsilon)K/N$ 个键，成员变化只使 $O(K/N)$ 个键换手。不用虚拟节点时，$\varepsilon$ 可以到 $O(\log N)$ 这一档；一致性哈希原文用每个物理节点跑多个虚拟节点把 $\varepsilon$ 压成任意小常数。Chord 为了陈述干净，正文里先不用虚拟节点，负载因此可以高过均值一个对数因子。他们给出一个先验上界的例子：若假定每个 IPv4 地址至多一个 Chord 服务，每台跑 32 个虚拟节点，负载会好很多。这是论文里的计数，不是一份要读者去开的集群配方。

只记住后继，查找就已经正确：询问沿后继一跳一跳走，直到第一次遇上后继于该标识符的节点。最坏要走完 $N$ 个节点。手指表把这件事加速。每个节点至多 $m$ 项，第 $i$ 项是环上至少领先自己 $2^{i-1}$ 的第一个节点，也就是 $\mathrm{successor}((n+2^{i-1})\bmod 2^m)$。第一项恰好是后继。表项同时记下对方的 Chord 标识和 IP 地址（以及端口）。节点对自己身后不远处知道得细，对远处知道得粗；一张手指表通常不够直接读出任意键的后继。于是查找变成：若键落在自己和后继之间，答案就是后继；否则在手指里找最靠近且仍在目标之前的节点，把问题交给它。每一步至少把剩余标识符距离减半，这就是定理 2 的几何图像。小圆上的例子：节点 3 要找标识符 1 的后继，第三根手指指向 0，0 比 3 更靠近 1，于是问 0；0 的手指指出后继是节点 1。正确性只要求后继指针对。手指可以旧，查找变慢，但不自动变错。论文把这写成实践里重要的退化：成员任意来去时，连 $O(\log N)$ 状态都难以及时对齐，但“每节点一条正确的后继”仍能保证查询被正确（尽管缓慢）地送达。

动态成员靠稳定化协议补上。后继正确，查找就正确；手指随后用后继去核对、去刷新，查找才又变快。每个节点另维持一份后继列表，记下环上最近的若干个后继。定理 7 与定理 8 说：在一份已经稳定的网上，后继列表长度取 $\Omega(\log N)$，然后让每个节点独立以 $1/2$ 的概率失效，则高概率下 find_successor 仍返回查询键的最近存活后继，期望步数仍是 $O(\log N)$。定理 6 说：稳定的 $N$ 节点网再加入至多 $N$ 个只有正确后继、没有手指的新节点，查找高概率仍是对数时间。这些是论文与技术报告里的装置与证明，不是加入、离开或在攻击下修补环的操作手册。稳定化自己也不声称能修好已经裂成多个不相交圈、或绕标识符空间多圈的病态环；那些情形不能由普通加入序列产生，论文把检测留给周期性采样，并写入未来工作。

论文量到了什么，以及它没有量到的东西#

仿真先量负载。一万个节点，键的总数从 $10^5$ 变到 $10^6$，步长 $10^5$，每个点重复二十次。键数增大，每节点键数的均值、第 1 百分位和第 99 百分位都大致线性张开；各种情况下都有节点一个键都不存。五十万键时均值为五十，观察到的最大值是 457，大约九倍于均值。原因之一是节点标识并未均匀铺满标识符空间：把空间切成 $N$ 个等长箱子，某一箱为空的概率大约 $(1-1/N)^N$，大 $N$ 时接近 $1/e$。虚拟节点把互不相关的若干标识绑到同一台物理机器上。实验给每个真实节点分配 $r$ 个虚拟节点，$r$ 取 1、2、5、10、20；第 99 百分位随 $r$ 下降、第 1 百分位从 0 升向均值。一万真实节点、每台二十个虚拟节点时，手指表大约膨胀二十倍的对数项，论文认为这点空间当时可以接受。路径长度按 $N=2^k$ 扫过 $k=3$ 到 $14$，均值大约 $\frac12\log_2 N$，第 1 与第 99 百分位同样对数增长；$2^{12}$ 个节点那张路径长度的概率密度被单独画出。

同时失效的实验仍用一万节点。随机抽走一部分节点，等稳定化结束，再问“键还能不能找到失效前的那个负责人”——这对应于上层不复制、也不在失效后恢复取值的系统。查找失败率几乎正好等于失效分数：多出来的失败并不显著。若环裂成两半，询问者与目标有一半时间不在同一片，失败率会靠近二分之一；曲线没有呈现出这种平台，论文据此说同时失效并未把查找结构撕成两截。持续抖动的实验改成五百个节点：查找按每秒一次的泊松过程到达，加入与失效也是泊松过程，每个节点平均三十秒做一次稳定化，仿真器每次刷新全部手指。这三十秒是仿真参数，不是一份超时配方。查询不重试，转发到已关闭节点即失败，于是测到的是状态不一致的最坏情景。论文用路径长度大约 $\frac12\log_2 500$ 来解释量级：失效若落在手指路径上，失败率大致是失效数乘上跳数；图上的点落在这个量级附近，略差一些，因为清掉一个失效节点可能不止一轮稳定化。

互联网原型只有十个物理站点，分布在加利福尼亚、科罗拉多、马萨诸塞、纽约、北卡罗来纳和宾夕法尼亚。中位时延随节点数缓慢上升。一百八十个节点时，一次典型查找大约五次双向交换：四次 Chord 跳，再加一次问后继；站点间典型往返约 60 毫秒，期望大约 300 毫秒，测到的中位是 285 毫秒。第 5 百分位低，是因为键在标识空间上靠近询问者，或一跳仍留在同一物理站点；第 95 百分位高，是因为跳到了高时延路径。教训被写成：查找时延随节点总数增长得很慢，与仿真里的可扩展性一致。

超过十个节点靠同一站点上的多份进程，地理多样性被刻意做小，时延曲线不能当成百万节点、每节点一机的公网测量。仿真器不重试，也不模拟上层数据尚未从旧后继搬到新后继的窗口；成功标准是“走到当前后继”，对取值来说偏乐观。论文没有测量对抗性覆盖网、日食式邻居垄断或伪造身份，也没有把网络地址转换写成一套可照做的穿越步骤。未来工作承认：稳定化看不见全局，裂开的环可能在局部看起来一致；恶意或出错的参与者可以出示不正确的环视图，在数据本身经过密码学认证的前提下，这威胁的是可用性而不是真实性。这些被列为未做的检测与修复，本页不把它们展开成攻击或部署配方。上层要的复制、缓存和命名，论文只示范“可以在后继列表上放副本、可以用数据的哈希当键”，并不量一套文件系统。同年稍后的 CFS 把存储层写成另一篇 SOSP 论文，那是另一份对象。

网络协议 在这里是手指消息的载体。原型选 TCP，查找是迭代的：发起者看见每一跳的往返，也承担每一跳的超时。递归转发会把时延测量和转发叠在同一台中间节点上，论文把它留在未来工作的服务器选择设想里，没有在十站点原型上对照测量。覆盖网跳数与底层 IP 跳数不是一回事：标识符距离减半，并不保证地理距离减半。Globe、Plaxton 那一类工作被拿来承认：它们在网络邻近性上比 Chord 更强；Chord 换到的是更简单、并且在并合成员变化下仍能陈述的正确性。

跨域连接#

• 概率论：定理 2 的 $O(\log N)$ 不是对任意标识符布置都成立的最坏情况，而是随机标识符（或 SHA-1 抗碰撞）下的高概率声明。每跳把剩余弧长至少减半，是几何图像；“再走 $\log N$ 步也够用”，来自剩下那一段里期望只有常数个节点、高概率不超过对数个。负载里空箱子的概率靠近 $1/e$，同样是均匀独立投点的推论，不是机器故障率。仿真把加入与失效写成泊松过程，稳定化间隔写成三十秒的均值，比较的是两种到达过程的相对速率，并不能把“高概率”读成公网上的实测频率。
• 图论：Chord 覆盖网是一张有向图：顶点是节点，边是后继与手指。每个顶点出度 $O(\log N)$，边长按二的幂跳过标识符弧，查找是一条朝后继前进的路径。定理 2 量的是这条路径的跳数，不是底层 IP 图的最短路。只保留后继边时图退化成一张环，直径变成 $N$；手指把直径压到对数。后继列表是沿环的一条短链，用来在独立失效模型里保住“仍能走到最近的活后继”。病态的多个不相交圈，是这张图的连通性已经离开论文所证明的那一类对象。
• 认识论：没有任何一个节点被允许声称自己看见了整张环。后继指针是关于“谁紧挨在我顺时针方向”的局部知识，论文把它定为正确性所要求的那一种真；手指是关于远处的近似知识，过期仍可用来赶路，但不能单独保证到达。迭代查找让发起者亲历每一跳给出的证词，递归查找则把中间判断交给别人。稳定化是一种把私人观察写成公共后继关系的手续：通知对方“我可能是你的前驱”，对方只在更近的前驱尚未出现时接受。裂环在局部可以看起来自洽，说明局部融贯不是全局知识。
• 信息不对称：Napster 把“键在哪”收成一份中心目录，询问者与目录之间的信息差距被设计成单向的：目录知道，客户端猜。Chord 把这份目录拆成 $N$ 份大小约 $\log N$ 的私有表，谁也不比谁多知道整个映射，但任意节点仍能在对数跳内把差距补到“找到后继”。一致性哈希 的 1997 年写法假定节点大体知道彼此，信息不对称被预先抹平；Chord 要处理的正是抹不平之后如何查询。GFS 与 Bigtable 重新引入少量知道得更多的主节点，是把不对称收回到可缓存的中心，和本页的对等表不是同一笔交易。
• 计算复杂性：这里的资源不是图灵机步数，而是消息条数与每节点状态。$O(\log N)$ 查找与 $O(\log N)$ 手指，说的是规模翻倍时热路径只加常数跳、表只加常数行，不需要为了规模去调一个像 CAN 那样预先固定的维数 $d$。定理给出的是带概率的渐近界，仿真看到的均值常数大约是 $\frac12$，因为随机距离里一半的比特为 1。把这条对数界读成复杂度课里的 P 与 NP，会把通信轮次误认成判定问题的时间类；它回答的是“环上定位要问几个人”，不是“这个问题算不算得起”。

参考文献#

• Stoica, I., Morris, R., Karger, D., Kaashoek, M. F. & Balakrishnan, H. Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications. Proc. ACM SIGCOMM, 2001, pp. 149–160. doi:10.1145/383059.383071（本文对象）
• Stoica, I. et al. Chord: A Scalable Peer-to-Peer Lookup Protocol for Internet Applications. IEEE/ACM Transactions on Networking 11(1), 2003, pp. 17–32.（期刊扩充版）
• Karger, D., Lehman, E., Leighton, T., Levine, M., Lewin, D. & Panigrahy, R. Consistent Hashing and Random Trees: Distributed Caching Protocols for Relieving Hot Spots on the World Wide Web. Proc. ACM STOC, 1997, pp. 654–663.（环上分配的前身；假定节点大体知道彼此）
• FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce / NIST, 1995.（原型所用 160 位标识的基哈希）
• Plaxton, C., Rajaraman, R. & Richa, A. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. Proc. ACM SPAA, 1997, pp. 311–320.（论文自承最接近的对数跳定位；邻近性更强、并发加入更复杂）
• Ghemawat, S., Gobioff, H. & Leung, S.-T. The Google File System. ACM SOSP, 2003, pp. 29–43. doi:10.1145/945445.945450（单主节点的块定位，与对等查找对照）
• Chang, F. et al. Bigtable: A Distributed Storage System for Structured Data. USENIX OSDI, 2006.（中心选主与 tablet 定位，与对等查找对照）

延伸阅读#

• Dabek, F., Kaashoek, M. F., Karger, D., Morris, R. & Stoica, I. Wide-area Cooperative Storage with CFS. ACM SOSP, 2001.（把 Chord 当定位层的存储；非本文对象）
• Ratnasamy, S., Francis, P., Handley, M., Karp, R. & Shenker, S. A Scalable Content-Addressable Network. Proc. ACM SIGCOMM, 2001.（同期 $d$ 维笛卡尔空间上的 DHT；状态不随 $N$ 变，查找随 $N^{1/d}$ 变）
• 与 一致性哈希 对读：1997 年管分配与迁移量；2001 年管分布式求值与手指跳数。
• 与 GFS、Bigtable 对读：中心元数据路径对对等环上的对数跳查找。