跳转到内容
Jason's Study

Pastry — 用 nodeId 的前缀一位一位逼近目标

是什么

Pastry 是一套让一群没有中心服务器的机器自己组织起来、按 nodeId 前缀一位一位接近目标的协议。日常类比：你在一座有 10 万间办公室的大楼里找编号 7B3F 的房间，第一层楼牌按”首字母分区”，到了 7 区再看二层楼牌”第二位 B”，到了 7B 区再看下一位——四步就走到，不用一间一间敲。

具体一点。Pastry 把两件东西揉到同一个 ID 空间里：

  • nodeId：每台机器拿自己 IP 算 hash，得到一个 128 位 的 ID（论文按 b=4 位一组拆成 32 个十六进制数字）
  • key：每条数据也算同样长度的 hash，落到同一个 ID 空间

规则：编号 k 的数据，由”nodeId 在数值上离 k 最近的那台机器”负责存。

而每次路由消息，Pastry 让消息每跳至少多匹配一位 nodeId 前缀——10 万节点最多 5 跳到位。

为什么重要

不理解 Pastry，下面这些事都没法解释：

  • 为什么和 Chord 同一年提出的 DHT 还能各自开花——前缀路由比环形 finger table 多了”邻近性”的设计空间
  • 为什么 Kademlia（BitTorrent / Ethereum DHT 的底层）的路由表长得很像 Pastry——前缀分桶 + XOR 距离是它的近亲
  • 为什么 FreePastry 这套 Java 实现成了分布式系统课的标准教具——把抽象的 DHT 概念落到一份能跑的代码
  • 为什么”邻近性感知”在 2001 年就被写进协议——作者意识到 ID 距离 ≠ 网络距离，必须分开优化

核心要点

Pastry 的全部魔力来自三张表：

  1. 路由表（routing table）：log_{2^b} N 行 × 2^b - 1 列。第 i 行的每个格子放一个”和我共享 i 位前缀、第 i+1 位是某个特定值”的节点。例如本节点 nodeId = 65A1...，第 0 行有 15 列，分别放 nodeId 以 0、1、2 … F（除了 6）开头的节点；第 1 行放 60、61 … 6F（除了 65）开头的节点。关键：每格如果有多个候选，挑 RTT 最近的那个——这就是邻近性感知。

  2. leaf set：L 个 nodeId 在数值上最近的邻居（上下各 L/2，典型 L=16）。前缀路由走到最后一跳时，目标 key 已经”非常接近”本节点 nodeId，就直接在 leaf set 里查最接近的那个，省去用前缀继续逼近。

  3. neighborhood set：M 个网络距离最近的节点（典型 M=32）。不参与路由决策，只用来初始化新加入节点的路由表 + 替换故障表项时挑邻近候选。

三张表加起来：每节点存 O(log N) 行 + 常数大小的 leaf/neighborhood set，路由 O(log_{2^b} N) 跳——b=4 时，10 万节点约 4 跳，100 万节点约 5 跳。

实践案例

案例 1：路由一条消息走一遍

假设 ID 用 4 位十六进制（实际 128 位，缩短演示），本节点 nodeId = 65A1，要把 key = D46A 路由出去。

本节点 65A1 的路由表（节选）：
  第 0 行 (共享 0 位前缀)：
    0... → N0xxx     1... → N1xxx     ...     D... → ND2F4    F... → NF118
  第 1 行 (共享 1 位前缀 6)：
    60... → N60xx    61... → N61xx   ...     6F... → N6F23

第 1 跳：本节点查”第 0 行 + 目标首位 D” → 把消息交给 ND2F4。

到了 ND2F4，它和目标 D46A 共享首位 D，看自己第 1 行”第二位 = 4”那一格 → 转给 ND4xx 中的某个，例如 ND41C。

到了 ND41C，发现它和 D46A 共享 D4，再看第 2 行”第三位 = 6”那一格 → 转给 ND469。

ND469 看自己的 leaf set，发现自己就是数值上最接近 D46A 的节点之一，路由完成。4 跳。

案例 2：节点加入

新节点 X（nodeId = 65A0）想加入网络。

  1. X 知道某个已在线节点 A（启动种子，可以是 DNS 提供）
  2. X 让 A 把 65A0 路由一遍，路径上每个节点把自己的对应行复制给 X——X 拿到一份”接近正确”的路由表
  3. 路径终点（数值上最接近 65A0 的节点）把自己的 leaf set 复制给 X
  4. X 用 expanding ring IP 多播或种子节点的 neighborhood set 找到自己 RTT 最近的几个节点，填进 neighborhood set
  5. X 通知所有需要把 X 加进自己路由表的节点

整个过程交换的消息数 O(log N)，比”全网广播自己来了”省得多。

案例 3：节点失效与恢复

leaf set 里某个节点 D 不响应了：

  • 检测：周期性心跳超时
  • 修复：从 leaf set 的另一端拿一个候选，或者向更远的 leaf set 节点询问它知道的节点

路由表某格 R 失效了：

  • 同行其他格里的节点知不知道一个 nodeId 也匹配 R 那一格的节点？问它们
  • 如果整行都没人，向上一行（共享前缀更短）的节点求助

容错的关键：所有表项都是软状态，丢了能重建。

踩过的坑

  1. leaf set 数值最近 ≠ 网络最近：leaf set 是按 nodeId 数值选的，最后一跳可能反而走到地球另一端。这是 Pastry 为简单牺牲的代价；后来的 Kademlia 用并发查询缓解。

  2. proximity 仅在路由表生效：邻近性感知只决定每格选谁，不改变前缀路由的路径长度——给的是常数因子优化，不是更小的复杂度。

  3. 128 位 vs 160 位：Pastry 用 128 位，Chord 用 SHA-1 的 160 位。后来 SHA-1 被发现不够安全，Pastry 的 128 位反而显得短——但论文当时关心的是空间够大不冲突，不是密码学强度。

  4. base b 的取舍：b 越大每跳前进越多（路由表更宽），但路由表也越大。论文推荐 b=4（每行 15 列）。b=1 退化成”二进制 trie”，路由像 Chord 但没了 finger table 的精妙。

案例 4：和 Chord 同跳数比较

10 万节点（N = 10^5）：

  • Chord（m = 160）：finger table 160 项，路由 log2(N) ≈ 17 跳
  • Pastry（b = 4）：路由表约 4 行 × 15 列 = 60 项，路由 log_{16}(N) ≈ 4 跳

Pastry 跳数更少，但每跳决策时要在 15 个候选里挑——总消息数差不多。真正的差别在 latency：Pastry 选邻近候选，每跳走”近的物理路径”；Chord 不挑路径，跳数虽多但每跳可能走得很远。论文里实测 Pastry 平均路由时延小于 IP 直连时延的 2 倍。

适用 vs 不适用场景

适用：

  • 大规模 P2P 存储 / 多播 / 协作 cache
  • 需要”加节点 / 删节点平滑”的场景（影响 O(K/N) 个 key）
  • 对”网络邻近性”敏感的应用——选个就近的副本胜过纯 ID 距离

不适用：

  • 强一致性场景——Pastry 是最终一致，节点加入期间可能短暂找错
  • 抗 Sybil 攻击——任何人造一堆 nodeId 就能”占据”目标 key 的负责区
  • 跨 NAT / 移动网络——直连假设在 2001 年还成立，2026 年的实际部署常需打洞 / relay

历史小故事（可跳过）

  • 2001 年：分布式 hash 表概念刚成型。同一年 SIGCOMM 出了 Chord（圆环 + finger table），Middleware 出了 Pastry（前缀路由 + 邻近性），SIGCOMM 还有 CAN（多维空间）和 Tapestry（前缀路由的另一支）——DHT 四大门派同年开宗。
  • 2002–2005 年：FreePastry（Rice 大学，Java）成为最广用的开源 DHT 实现；微软的 SimPastry 用 C# 做仿真。基于 Pastry 的 PAST、SCRIBE、SQUIRREL 论文连发。
  • 2002 年：Kademlia 论文出现，用 XOR 距离统一了”前缀路由”和”距离度量”，被 BitTorrent / Ethereum 采纳，成为今天最广用的 DHT 算法。
  • 之后：DHT 没成为通用基础设施，但思想活在 Cassandra（一致性哈希）、IPFS（Kademlia）、各类区块链节点发现里。

学到什么

  1. ID 距离和网络距离要分开建模——Pastry 用”路由决策按 ID、候选填充按网络”两层设计把它们解耦
  2. 前缀路由是 trie 的分布式版——和数据结构课上的 trie 一脉相承，每跳”消化”一位前缀
  3. DHT 不是单一答案——Chord、Pastry、CAN、Kademlia 同年并立，证明”分布式查找”这道题的解空间很广
  4. 软状态 + 周期修复比”强一致 + 主动同步”更适合 P2P——节点不可靠是常态，协议接受不精确并最终收敛

延伸阅读

  • 论文 PDF：Pastry — Middleware 2001（22 页，可读性好）
  • FreePastry 项目首页：freepastry.org（Rice 大学维护的 Java 参考实现）
  • 教学讲解：MIT 6.824 分布式系统课关于 DHT 的一讲（YouTube 公开课）
  • chord-2001 —— 同年的 DHT 兄弟，圆环 + finger table 的另一种解法
  • dynamo —— 一致性哈希的工业落地，思想可追溯到 Pastry / Chord

关联

  • chord-2001 —— Chord — 让上万台机器排成圈，查任何 key 都只走 log N 步
  • dynamo —— Amazon Dynamo 用一致性哈希做无主存储，思想直系
  • akamai-2002 —— Akamai 把网站搬到离用户 10 毫秒的地方；同样关心”网络邻近性 ≠ ID 距离”

反向链接

  • akamai-2002 —— Akamai 2002 — 把网站搬到离用户 10 毫秒的地方
  • chord-2001 —— Chord — 让上万台机器排成圈，查任何 key 都只走 log N 步
  • dynamo —— Dynamo — 让购物车永远能写入的分布式存储
  • kademlia-2002 —— Kademlia — 用 XOR 当距离的 P2P 路由表