Kademlia：XOR 距离上的 k-bucket，不是环上的手指

破除误解#

误解二：对等查找就是某款文件共享软件去掉中心目录，Kademlia 是那条产品史的一章。 论文只承诺键到靠近该键的节点，再用四个远程过程调用读写不透明的键值对。它不规定文件名怎么切词，不保证匿名，也不把用户可读的种子、块清单或内容标识写成协议的一部分。相关工作拿 Pastry、Tapestry 和 Plaxton 的前缀路由对照，拿 Chord 的不对称度量对照，拿 Saroiu、Gummadi 与 Gribble 对已有文件共享系统的在线时长测量当生存时间假设的经验来源。把本页读成某个品牌覆盖网的兴衰，会把 XOR 与 $k$-bucket 换成另一套产品年表。

误解三：$\lceil\log n\rceil$ 是一张在公网上量过的毫秒发票，仿真曲线可以直接当成百万节点时延。 证明草稿要证的是多数操作耗时 $\lceil\log n\rceil+c$（$c$ 为小常数），并且已存进系统的键值对能以压倒性概率被找回。论文没有给出像 Chord 原型那样的十站点往返毫秒表。它真正画出来的图，是 Gnutella 节点“再活一小时”的条件概率：横轴是已经在线的分钟数（图上画到约 2500 分钟），纵轴是“活过 $x$ 分钟的节点里，还有多大比例继续活过 $x+60$ 分钟”。那条曲线来自他们引用的华盛顿大学技术报告，用来替 $k$-bucket 偏好老联系人辩护，不是一份公网查找时延。

误解四：GFS 和 Kademlia 都是“分布式存储论文”，有没有中心只是实现细节。 GFS 用单主节点记住块在哪；客户端先问主，再跟 chunkserver 说话。Kademlia 的软件是链进应用的协议：每个节点维持自己的 160 个距离区间，功能对等，没有逻辑根。分布式系统 里最贵的往往是谁必须出现在热路径上：Google 那篇把热路径上的元数据做成可缓存的中心；Kademlia 把热路径做成发起者对若干桶内联系人的并行对话。把它们并成一句“都是把数据拆到多台机器上”，会把查找装置读丢。

XOR 度量、$k$-bucket 与发起者查找#

协议的心脏是距离，不是环上的后继指针。节点标识按 Chord 那一类办法构造，正文为了陈述干净，假定加入时各自随机抽一个 160 位数。发出的每条消息都带上自己的节点标识，收件人因此可以决定要不要把对方记进桶里。键同样是 160 位。给定 $x$ 与 $y$，距离是按位异或再读成整数。论文先核这是一个合法、尽管非欧的度量：$d(x,x)=0$；$x\neq y$ 时 $d(x,y)>0$；对一切 $x,y$ 有 $d(x,y)=d(y,x)$；三角不等式来自 $d(x,z)=d(x,y)\oplus d(y,z)$ 以及非负整数上 $a+b\ge a\oplus b$。单向性让同一键的查找收敛；对称性让入站查询的发送方分布，与自己路由表里已有的那类节点同分布。论文据此对照 Chord：没有对称性，收件人从查询里学不到对自己有用的路由信息。

节点状态按距离区间切开。对每个 $0\le i<160$，节点保存一份三元组列表——IP 地址、UDP 端口、节点标识——对象是距离落在 $[2^i,2^{i+1})$ 里的其他节点。这些列表叫做 $k$-bucket。每只桶按最近一次见到的时间排序：最久未见的在队头，刚见过的在队尾。$i$ 很小时桶常常空着，因为那样近的标识根本不存在；$i$ 很大时列表可以长到系统级复制参数 $k$。$k$ 的选取标准写在纸上：任意给定的 $k$ 个节点在一小时内一起失效的概率要非常低，例子取 $k=20$。任何消息——请求或应答——到来时，收件人更新发送方所在的那只桶。对方已在桶里，就挪到队尾；不在且桶未满，就插到队尾；桶已满，则向队头那个最久未见的节点发 PING。若它不应答，就驱逐它、把新来者插到队尾；若它应答，就把它挪到队尾、丢掉新来者。论文把这写成“最久未见驱逐，但活着的节点从不被移出”。偏好老联系人，直接接在下一节那张 Gnutella 条件概率图上。设计上的另一句是：不能靠涌进大批新标识把别人的路由表冲掉，新联系人只有在老联系人离开之后才进得了已满的桶。这句话是论文对自己装置的声明，不是一份覆盖网攻击配方。

四个远程过程调用构成协议。PING 探测对方是否在线。STORE 让对方存下一对键值。FIND_NODE 带一个 160 位目标，收件人返回自己知道的、最靠近该目标的 $k$ 个三元组；它们可以来自一只桶，也可以在最近那只桶未满时从多只桶拼齐，除非它认识的节点总数还不到 $k$。FIND_VALUE 几乎相同，唯一例外是：若收件人曾经为这个键收过 STORE，它直接返回存着的值。所有调用都要求收件人回显一个 160 位随机 RPC 标识，论文把它写成对地址伪造的一点阻力；PING 也可以捎在应答上，让收件人多一重对发送方网络地址的确认。网络协议 在这里是这些调用的载体：联系人三元组里写的是 UDP 端口，不是 Chord 原型里的 TCP 会话。

最重要的手续是：给定一个标识，找出最靠近它的 $k$ 个节点。发起者先从自己最近的非空 $k$-bucket 里取出 $\alpha$ 个节点（若那只桶不够 $\alpha$ 条，就在已知联系人里取最近的 $\alpha$ 个），并行、异步地向他们发 FIND_NODE。$\alpha$ 是系统级并发参数，例子取 3。论文把后续步骤叫做 recursive step：发起者不必等上一轮 $\alpha$ 个应答全部回来，就可以根据已经学到的更近联系人继续发。在已听说的、最靠近目标的 $k$ 个节点里，选出尚未问过的 $\alpha$ 个再问。应答来得慢的先移出考虑，除非后来又回来。若一整轮没有找出比当前最近者更近的节点，发起者就把 FIND_NODE 补发给这 $k$ 个最近者里尚未问过的每一位。查找在发起者已经询问并得到这 $k$ 个最近节点的应答时结束。$\alpha=1$ 时，消息条数和察觉失效的时延接近 Chord；Kademlia 的额外余地是每只桶里有最多 $k$ 个可替换联系人，可以按往返时延挑选，也可以并行发出以免死等超时。对等查找文献后来把“发起者自己一连串去问、中间节点不接管请求”叫做迭代风格；本页按这个装置来读，不把论文里的 recursive 一词读成把查询转发出去。

多数操作叠在这次查找上。要存一对键值，先找到最靠近该键的 $k$ 个节点，再向他们发 STORE。每个节点每小时再发布一次自己存着的键值对；原发布者每 24 小时再发布一次，否则键值对在首次发布 24 小时后过期，用来限制陈旧信息。若节点 $w$ 观察到新节点 $u$ 更靠近自己手里的某些键，就把这些对复制给 $u$，自己并不删掉。取值用 FIND_VALUE，任一节点返回值就停；成功后，请求方把该对存到自己见过的、最靠近该键、却没有返回值的那个节点上。单向性使得以后的查找很可能先碰到缓存。为避免缓存过密，过期时间与“自己和最靠近该键的节点之间隔着多少节点”成指数反比。桶通常靠过路请求保持新鲜；若某只桶的区间在一小时内没有做过节点查找，就在该区间里随机抽一个标识做一次查找。加入者 $u$ 必须先认识已经在场的 $w$：把 $w$ 插入相应的桶，对自己的标识做一次查找，再刷新所有比最近邻居更远的桶。

讨论节把 XOR 路由写成与 Pastry、Tapestry 以及 Plaxton 第一阶段很像。那三份一次跳 $b$ 位时，还要在“前缀已同、下一位数字不同”的节点里再找一遍，次级表 $O(2^b)$，主表 $O(2^b\log_{2^b}n)$。Kademlia 把桶表配成每跳走近 $b$ 位，期望不超过 $(2^b-1)\log_{2^b}n$ 只桶真正有条目。当时的实现取 $b=5$。这是论文写下的表配置，不是一份要读者去调参的集群配方。

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

生存时间假设接在一张图上。图的横轴是已经在线的分钟数，纵轴是条件比例：在活过 $x$ 分钟的 Gnutella 节点里，还有多大一份继续活过 $x+60$ 分钟。数据来自 Stefan Saroiu、P. Krishna Gummadi 与 Steven D. Gribble 2001 年 7 月的华盛顿大学技术报告 UW-CSE-01-06-02，不是作者自己再爬一遍覆盖网。曲线的形状被用来支持那句装置选择：节点在线越久，再活一小时的可能性越高，因此桶里应留下仍然活着的老联系人。证明草稿把新节点写成最不可靠的那一档，并取它们在一小时后仍在线的概率为 $1/2$；键值对发布在最靠近该键的 $k$ 个节点上、且每小时再发布一次，于是一小时后它仍在这 $k$ 个最近者之一上的概率写成 $1-2^{-k}$。新加入、标识更靠近该键的节点会为了填桶去联系自己的近邻，从而接到应存的键值对，这条概率不因此被破坏。若最靠近该键的 $k$ 个节点都失效、而键值对又没有缓存在别处，系统会丢掉它——论文把失败条件写明，并不假装复制参数能取消失效。

查找步数是证明对象，不是测出来的毫秒。覆盖 $[2^i,2^{i+1})$ 的桶指标为 $i$；节点深度 $h$ 取 $160-i$，其中 $i$ 是非空桶的最小指标。标识随机，高度以压倒性概率落在 $\log n$ 的常数邻域内。假定只要区间里存在节点，每只 $k$-bucket 至少有一个联系人：若最近节点深度为 $h$ 且最高的 $h$ 只桶都不空，查找每步把距离缩短大约一位，于是 $h-\log k$ 步找到最近者；空桶只让最后几步不再减半，最近节点仍在同一界内返回。找到之后并行度从 $\alpha$ 切到 $k$，收齐其余 $k-1$ 个最近者不大可能超过常数加 $\log k$。能打破不变量的方式是：区间里至少有 $k+1$ 个节点，而桶里那 $k$ 个在没有查找、也没有刷新的情况下全部失效。$k$ 正是为“一小时（最大刷新间隔）内同时失效”的概率足够小而选的。XOR 对称使来往请求碰到的标识与桶区间兼容，实际失效比“$k$ 个节点在一小时内离开”更少。单只桶坏了只加一跳，不自动让查找答错。要让一次查找失败，路径上 $k$ 个节点必须各自丢掉同一只桶里的 $k$ 个联系人且中间没有刷新；桶互不重叠时概率写成 $2^{-k^2}$。这些是纸上的界，带“压倒性概率”和弱在线时长假设，不是公网测量。

没有十个地理站点上的查找中位毫秒，没有把 $N$ 扫到上万再画负载百分位，也没有把网络地址转换写成一套可照做的穿越步骤。实现节只把 $b=5$ 的桶表配置写下来，并声称可以按往返时延在桶内挑选、用 $\alpha$ 换带宽以换无超时等待的故障恢复。未来工作与攻击面被点到为止：地址伪造靠 RPC 标识回显“提供一些阻力”；基本的拒绝服务被写成“新节点灌不进已满且仍活的桶”。恶意参与者如何垄断邻居、如何批量伪造身份，论文没有展开成步骤，本页也不补。上层要的命名、文件系统和内容分发，不在四个 RPC 里。

跨域连接#

• 概率论：桶的大小 $k=20$ 不是工程口诀，而是“任意给定的 $k$ 个节点在一小时内一起失效的概率要非常低”。新节点再活一小时被写成 $1/2$，一小时后键值对仍在 $k$ 个最近者之一上被写成 $1-2^{-k}$；路径上 $k$ 个节点各自丢掉整只桶、且桶互不重叠时，失败概率写成 $2^{-k^2}$。图 1 的纵轴是条件概率——活过 $x$ 分钟的人里还有多少继续活过 $x+60$ 分钟——横轴以分钟计。这是用已有文件共享系统的在线时长来约束失效模型，不能把 $1/2$ 读成公网上每一个新节点的实测频率。
• 图论：160 位标识是一棵满二叉树的叶子。节点必须在自己不在的那些子树里各留联系人；$k$-bucket 是按 XOR 最高有效位切开的出边袋，每袋最多 $k$ 条。查找是发起者在这张有向图上走的路径：每一步选当前已知、XOR 更近的顶点，并行问 $\alpha$ 个。Chord 的图是环加二的幂弦；Kademlia 的图是按异或分层的树状邻域。直径的对数声明依赖“该在的区间里至少有一条边”，空桶不自动把图撕成两半，但会让某几步不再把距离减半。
• 认识论：没有任何一个节点被允许声称自己看见了整份映射。每条消息都带发送方标识，于是每一次对话都是一份可被对方写入私有桶的证词；论文把“发出的每条消息都在传达或加固有用的联系人信息”写成拓扑的性质。发起者自己问完 $k$ 个最近者才停，是把“谁靠近目标”的判断留在提问者手里；中间节点只回答自己知道的 $k$ 个三元组，并不接管查询。桶里的老联系人被当成比新面孔更可靠的证人，依据是条件存活曲线，不是中心目录的盖章。
• 信息不对称：Chord 的不对称度量让“谁出现在我的手指里”和“我出现在谁的手指里”不必互为对方；Kademlia 用对称 XOR 把这笔差距抹平，查找流量本身成为配置信息的来源。代价是谁也不持有全局表，询问者必须用对数轮对话把“键在哪”从私有桶拼出来。GFS 把不对称收回到可缓存的中心，和本页的对等桶不是同一笔交易。一致性哈希 的 1997 年写法假定节点大体知道彼此；Kademlia 要处理的是抹不平之后，局部桶如何仍然够用。
• 计算复杂性：这里的资源是消息轮次与每节点状态，不是图灵机步数。$\lceil\log n\rceil+c$ 说的是规模的对数跳，外加收齐 $k$ 个最近者的常数邻域；把底换成 $2^b$、当时实现取 $b=5$，期望桶数不超过 $(2^b-1)\log_{2^b}n$。$\alpha$ 把“等一个超时”换成“并行问常数个”。把这条对数界读成复杂度课里的 P 与 NP，会把通信轮次误认成判定问题的时间类；它回答的是“按 XOR 走近一个标识要问几个人”，不是“这个问题算不算得起”。

参考文献#

• Maymounkov, P. & Mazières, D. Kademlia: A Peer-to-peer Information System Based on the XOR Metric. Proc. IPTPS, LNCS 2429, 2002, pp. 53–65. doi:10.1007/3-540-45748-8_5（本文对象）
• 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（不对称环度量与刚性手指，论文直接对照）
• Rowstron, A. & Druschel, P. Pastry: Scalable, Distributed Object Location and Routing for Large-scale Peer-to-Peer Systems. Proc. IFIP/ACM Middleware, 2001.（论文自承最像其第一阶段；第二阶段改用数值差，复制也用第二度量）
• Zhao, B. Y., Kubiatowicz, J. & Joseph, A. Tapestry: An Infrastructure for Fault-tolerant Wide-area Location and Routing. Tech. Rep. UCB/CSD-01-1141, U.C. Berkeley, April 2001.（前缀路由的同期对照）
• Plaxton, C., Rajaraman, R. & Richa, A. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. Proc. ACM SPAA, 1997, pp. 311–320.（对数跳定位的前身；论文指出其对高故障环境更不针对性）
• Saroiu, S., Gummadi, P. K. & Gribble, S. D. A Measurement Study of Peer-to-Peer File Sharing Systems. Tech. Rep. UW-CSE-01-06-02, University of Washington, July 2001.（图 1 的 Gnutella 在线时长来源）
• FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce / NIST, 1995.（160 位键的示例基哈希）
• Ghemawat, S., Gobioff, H. & Leung, S.-T. The Google File System. ACM SOSP, 2003, pp. 29–43. doi:10.1145/945445.945450（单主节点的块定位，与对等桶对照）

延伸阅读#

• 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}$ 变）
• 与 Chord 对读：环加后继加手指，对 XOR 加 $k$-bucket 加发起者并行问询。
• 与 一致性哈希 对读：1997 年管分配与迁移量；2002 年管对称度量下的局部桶如何仍能对数跳定位。
• 与 GFS 对读：中心元数据路径对对等树上的 XOR 查找。