DHT 深入解析：Kademlia、Chord 与 Pastry 的内部构造
首页介绍了 DHT 的概念。这里更进一步：真实路由表的结构、Kademlia 的查找流程、与 Chord、Pastry 的对比、如何应对 churn（节点频繁进出）、真实系统中的应用规模与抗攻击能力，以及理论与现实之间的技术局限与实用性差距。
路由表:「捷径清单」的设计
DHT 的核心是每个节点持有的小型路由表。Chord 维护指针表，即「距自己 2^k 处的负责节点」的列表（m 条，m 为哈希位数）；Kademlia 则按距离区间维护收纳节点的 k-桶。两者的共同点是「远处知之粗略、近处知之精细」，因而每一跳都能把到目标的距离至少减半。表的规模保持在 O(log n)，即便百万节点的网络，每个节点管理的知识也微乎其微。
在 Kademlia 中，针对 160 位的节点 ID 空间（原论文采用 SHA-1），最多设置 160 个桶。桶 i 存放与自身距离落在 2^i 到 2^(i+1)-1 之间的节点，每桶最多 k 个（原论文 k=20）。节点 ID 由哈希函数分配，因此节点在 ID 空间上均匀分布，并不会在特定距离区间内聚集；分裂桶的目的是提高自身周边的路由精度，因此靠近自己的桶保持细粒度，远处的桶保持粗粒度。当桶已满又发现新节点时，Kademlia 会向桶内最久未更新的节点发送 Ping：若其应答则保留旧节点、丢弃新节点；只有无应答时才会淘汰旧节点。这种带存活检查的「老节点优先」淘汰策略，自然体现了「存活越久的节点越可能继续存活」这一经验法则。
每个距离区间对应一个桶：第 i 个桶保存与自身 ID 距离在 2^i 到 2^(i+1)-1 之间的节点，每桶最多 k 个（原论文 k=20）。距离越远区间越粗，越近越细。
Kademlia 的查找:XOR 距离与 α 并行查询
Kademlia 把节点间「距离」定义为 ID 的 XOR（异或）。该度量是对称的（A 到 B 与 B 到 A 相等），具有类似三角不等式的性质，并与桶结构完美契合。查找键的节点从自己的桶中选出距目标最近的 α 个节点（通常 3 个）并行发问，用回复中「更近的节点」信息继续追问。因每一步距离必然缩短，查找在 O(log n) 步内收敛。
- 从自己的 k-桶中按距离目标键由近到远选出 α 个节点，并行发送 FIND_NODE（若为取值则发送 FIND_VALUE）。
- 把回复中「更近的节点」候选合并进已知的最近邻列表。
- 从尚未查询过的节点中再次选出最近的 α 个，重复上一步。
- 当最近的 k 个节点在最近一轮中不再更新时，即视为收敛，结束查找。
- 若是 FIND_VALUE，则一旦中途有节点被发现持有该值，立即结束。
即便在百万节点规模下，距离空间也会在每一跳大致减半，因此只需数轮往返即可抵达目标节点。α 越大，单轮的通信量越大，但受节点无响应（超时）造成的延迟影响越小，因此实现中会把 α 当作延迟与带宽之间的权衡来调优。
与 Chord 的对比:环形结构与 XOR 距离
DHT 的另一代表 Chord 把节点与键放在同一个环（0 到 2^m-1 的圆环）上，把键的负责者定义为「ID 大于等于该键且最接近的节点」（即 successor）。指针表指向自身之后 2^0、2^1、……、2^(m-1) 处的位置，因此查找总是沿环顺时针方向逐跳收缩，是单方向的串行过程。与 Kademlia 的差异整理如下。
| 维度 | Kademlia | Chord |
|---|---|---|
| 距离定义 | ID 的 XOR（对称、类树形） | 环上的单方向距离（非对称） |
| 查找并行度 | 默认对 α 个节点并行查询 | 基本为串行跳转（是否并行取决于实现） |
| 维护方式 | 普通查找即可顺带刷新路由表 | 需周期性运行 stabilize 以维持后继列表 |
| 容错能力 | 桶内保留多个候选，替换灵活 | 通过 successor list 保留多个后继节点 |
| 代表性应用 | BitTorrent Mainline DHT、IPFS、Ethereum discv5 | 以学术/研究实现为主，大规模生产落地较少 |
Kademlia 在实际部署中更占优势，除了并行查找降低延迟之外，还因为它不需要专门的维护协议（相当于 Chord 的 stabilize/fix_fingers）：普通的查询流量本身就能让路由表保持新鲜。
Pastry:前缀路由与近邻感知设计
在 DHT 研究文献中，与 Kademlia、Chord 并列被频繁引用的还有 Rowstron 与 Druschel（2001 年，微软研究院 / 莱斯大学）提出的 Pastry。Chord 与 Kademlia 按数值「距离」路由，而 Pastry 继承自更早的覆盖网络研究（Plaxton 树与 Tapestry），按节点 ID 的前缀匹配（与目标共享的开头位数）进行路由。
节点 ID 通常为 128 位，以每 b=4 位为一个十六进制数字的字符串处理。路由表呈网格状：行对应共享前缀的长度，列对应 16 种可能的下一位十六进制数字。第 r 行的条目指向与自身共享前 r 位、但第 r+1 位不同的节点。除此之外，每个节点还持有按 ID 数值最接近自己的节点集合，即叶集（大致相当于 Chord 的 successor list），以及按物理网络近邻性选出的邻居集。
路由本身很简单：节点收到消息后，若路由表中存在与目标共享前缀比自身多至少一位的条目，则转发给它；若没有，则转发给叶集中数值上最接近该键的节点。由于每一跳共享前缀至少增加一位，跳数为 O(log₁₆ n)，常数因子比 Chord 或 Kademlia 的 O(log₂ n) 更小。
Pastry 最大的特点是在构建路由表时考虑近邻性。当某个表项存在多个共享相同前缀的候选节点时，Pastry 不会仅凭 ID 运算决定，而是选择实测往返延迟（RTT）最小的节点。这样不仅减少了逻辑跳数，也让每一跳在物理网络上同样趋于就近。原论文的仿真报告显示，实际延迟与直接通信延迟之比（Relative Delay Penalty）可被控制在一个较小的常数范围内。这与 Chord、Kademlia 完全依赖 ID 空间运算来决定路径的做法形成了鲜明对比。
| 维度 | Kademlia | Chord | Pastry |
|---|---|---|---|
| 路由依据 | ID 的 XOR 距离 | 环上的单方向距离 | ID 前缀匹配 |
| 近邻性（RTT）考量 | 通常没有（部分扩展会加入） | 没有 | 在构建路由表时明确纳入考量 |
| 跳数量级 | O(log₂ n) | O(log₂ n) | O(log₁₆ n)（取决于进制基数） |
| 冗余结构 | k-桶（同一距离区间内多个候选） | successor list | 叶集 + 邻居集 |
| 代表性应用 | BitTorrent、IPFS、Ethereum discv5 | 以学术实现为主 | PAST、SCRIBE、Squirrel 等（均为研究原型） |
基于 Pastry 构建的研究系统包括：通过复制与缓存保存文件的大规模分布式存储系统 PAST；沿 Pastry 路由路径反向构建树结构、实现主题式发布订阅的 SCRIBE；以及作为 Web 缓存设计的 Squirrel。基于 Java 的 FreePastry 是这一研究方向广泛参考的实现。
值得注意的是，Pastry 与 Chord、CAN、Tapestry 一样，至今仍频繁出现在分布式系统课程与 DHT 相关论文中，作为「标准比较对象」，但它几乎没有像 BitTorrent 的 Mainline DHT、IPFS 或 discv5 那样的大规模生产部署。前缀路由与近邻感知的路由表构建思路影响了后续研究，但 Pastry 本身正是「在研究中被广泛引用、却始终未被大规模实际采用」的 DHT 代表，与 Kademlia 一脉所走的道路截然不同。
与 churn 的搏斗:桶刷新与重新发布
P2P 的现实是与 churn 的搏斗，即节点以分钟到小时为周期频繁更替。测量研究表明，节点在线时长服从重尾分布：大量短命节点与少数长寿节点并存。Kademlia「优先把长寿节点留在桶中」的策略，正是基于「活得久的节点接下来也更可能活着」的经验法则。周期性的值重新发布（republish）和桶刷新，同样是防止知识因 churn 而腐坏的机制。
- 桶刷新：在原始 Kademlia 论文中，若某个桶在一段时间内（约一小时）未被查询过，则会在该桶对应的距离范围内随机选取一个 ID 发起查找，主动维持路由表的新鲜度。
- 值的重新发布（republish）：存储的值带有有效期（原论文为 24 小时），持有该值的节点会在过期前重新执行 FIND_NODE 以确认当前的负责节点集合，并重新分发该值，避免因负责节点更替而丢失数据。
- k=20 这个数字的含义：k 越大，单个桶的冗余度越高，越能承受多个节点同时离线，但维护通信量也随之增加。BitTorrent 的 Mainline DHT（BEP 5）采用 k=8，比原论文的默认值更小；实际部署中通常会根据网络规模、churn 率与用途来调整 k。
真实系统中的应用
Kademlia 系 DHT 并不止步于学术方案，而是多个大规模 P2P 系统的底层基础设施。
| 系统 | ID / 哈希 | k（桶大小） | 主要用途 |
|---|---|---|---|
| BitTorrent Mainline DHT（BEP 5） | 160 位（SHA-1） | 8 | 无需追踪器的节点发现，据报道规模达数百万至数千万节点 |
| IPFS（libp2p Kademlia） | 256 位（SHA-256） | 20 | 为内容寻址对象查找持有者（provider）记录 |
| Ethereum discv5 | 256 位（Keccak-256） | 16 | 节点发现与 ENR（Ethereum Node Record）的分发，基于 UDP |
即便同样自称「Kademlia」，各系统在 ID 长度、k、α 等参数以及消息格式上也各不相同。设计或实现 DHT 时，不应直接照搬原论文的默认值，而应根据预期节点规模、churn 率与可接受的延迟重新审视这些参数。
抗攻击能力:女巫攻击、Eclipse 攻击与 S/Kademlia 的对策
公开型 DHT 允许任何人以节点身份加入，因而结构性地易受女巫攻击（一方伪造大量节点 ID）以及Eclipse 攻击（用恶意节点包围目标节点周边）的影响。由于 Kademlia 的路由表完全是基于距离的机械化结构，攻击者只要能大量生成接近目标键的 ID，就可能主导通往该键的查询路径。
- S/Kademlia（Baumgart & Mies，2007 年）是代表性对策，它将节点 ID 的生成与哈希求解成本（crypto puzzle）绑定，从而提高批量获取 ID 的代价。
- S/Kademlia 还提出了互不相交的多路径查找（disjoint paths lookup）：不走单一路径，而是沿 d 条相互独立的路径并行逼近目标，即使部分路径经过恶意节点，也能通过多数结果收敛到正确答案。
- DHT 的通信任何人都可观测，因此查询请求的源 IP 地址也可能暴露节点的使用情况，这是需要留意的隐私问题。
常见误解：有人认为「DHT 是可以存储任意数据的分布式数据库」，但实际的 Kademlia 系 DHT 是针对每个键存储相对较小的值（如节点信息或指向元数据的指针）而优化的，并不适合存放大容量数据本身。另一个误解是「用了 DHT 就意味着匿名」，但 DHT 的通信本身会暴露 IP 地址，要实现匿名性还需要NAT 穿透与攻击与防御中提到的额外设计。
DHT 的技术局限与实用性:理论与现实的差距
迄今介绍的每一种设计在纸面上都拥有漂亮的 O(log n) 保证，但真正运营或实现 DHT 时，会遇到理论模型未曾涵盖的若干现实制约。
- 查找耗时的长尾分布：O(log n) 的跳数保证，前提是路由表中始终只包含存活节点。而现实中节点往往没有发送明确的离线通知就突然下线，路由表中始终会残留一定比例的失效条目。对这些条目的查询需要等待超时后才会回退到下一个候选，因此即便平均跳数接近理论值，查找耗时的分布仍会出现不可忽视的长尾。
- 可达性的高墙：DHT 协议默认「任何节点都可被直接联系」，但现实中相当一部分互联网主机处于NAT或防火墙之后，无法从外部直接访问。针对 BitTorrent Mainline DHT 的测量研究表明，被观测节点中不可达的比例达到不可忽视的规模；多数实现的应对办法是把 Kademlia 节点状态分类为「good（有响应）」「questionable（存疑）」「bad（无响应）」，只把确认可达的节点推荐给其他节点。
- 查询表达能力有限：DHT 本质上只支持「按键精确查找（get）」，不支持范围查询、全文搜索、排序或连接等数据库式操作。若要在其上叠加这些功能，要么需要前缀哈希树之类的额外结构，要么最终还是要依赖中心化的索引服务器。
- 一致性保证薄弱：多数 DHT 实现不提供事务或线性一致性。在 churn 剧烈的情况下，并发的 put/get 可能产生竞争，副本之间也可能短暂出现不一致。因此 DHT 更适合存放「体量小、变化不频繁、即使略微过时代价也很小」的数据（节点信息、指向元数据的指针），而非被设计为保存权威真值的存储。
正因存在这些局限，生产系统通常不会把 DHT 当作唯一的真值来源，而是作为辅助性的发现层使用。IPFS 用 DHT 查找「谁持有某项内容」的 provider 记录，而非存储内容本身；以太坊的 discv5 只负责节点发现，共识则完全交由分布式共识中讨论的另一套协议层处理。DHT 是「给定一个键，谁负责它」这一狭窄却可靠问题的成熟答案。一旦对它期待更多，比如协调或一致性状态，理论与现实之间的差距就会显现出来。