Pastry：前缀表、叶集与邻近集，不是环上的手指

破除误解#

误解二：对等查找就是某款文件共享软件去掉中心目录，Pastry 是那条产品史的一章。 论文只承诺键到数值最近的节点，并在沿途把 forward 与 deliver 交给上层。PAST 用文件名与所有者的哈希当键、把副本放在数值最近的 $k$ 台；SCRIBE 用主题名的哈希当汇合点。那是另外两份对象。相关工作拿 Napster 的中心库、Gnutella 的广播、Freenet 的不保证找回对照，拿 Plaxton 的前缀定位当尚未充分自组织的前身。把本页读成某个品牌覆盖网的兴衰，会把三张表换成另一套产品年表。

误解三：$\lceil\log_{2^{b}} N\rceil$ 是一张在公网上量过的毫秒发票，仿真曲线可以直接当成十万节点因特网时延。 跳数实验把节点随机撒在边长一千的平面上，邻近度量是平面距离，不是 IP 毫秒。一千到十万节点、二十万次随机对的平均跳数贴着 $\log_{16} N$ 走；十万节点时跳数最多是五，与 $\lceil\log_{16} 100000\rceil$ 一致。相对一张“谁都认识谁”的虚构全表，Pastry 路径在邻近度量上大约长百分之三十到四十。论文自己写明因特网节点并不均匀铺在欧氏平面上，三角不等式也不总成立；基本转发不受影响，局部性可能变差。这些是仿真器里的跳数与路径拉长，不是公网查找时延。

误解四：邻近集是路由正确性的保险，叶集只是多记几台近邻。 邻近集 $M$ 按邻近度量记下离自己最近的若干台，论文写明它通常不参与转发，用途是维持局部性、在加入的第二阶段贡献“附近还有谁”的信息。叶集 $L$ 才进入路由手续：键落在叶集覆盖的数值区间里，就直接交给叶集里数值最近的那台。第三种少见情形——前缀格子空了或对端已不可达——才在叶集、路由表、邻近集的并里找一个前缀不更短、且数值更近的下一跳。两张表不能对调。

节点标识、前缀表、叶集与路由#

协议的心脏是把一百二十八位标识和键读成以 $2^{b}$ 为底的数字串，然后按前缀走近目标。$b$ 是配置参数，正文里的典型值是四，于是每一位是十六进制数字。标识被假定均匀铺在 $0$ 到 $2^{128}-1$ 的圆环上，例如取节点公钥或 IP 地址的密码学哈希。随机指派的后果被写成高概率命题：相邻标识在地理、归属和管辖上往往分散，于是上层可以把副本放在数值最近的 $k$ 台，而不把它们挤进同一处。正常运行时，送到数值最近节点的步数少于 $\lceil\log_{2^{b}} N\rceil$。$b=4$、一百万节点时，路由表平均大约七十五项、期望跳数是五；十亿节点时平均大约一百零五项、期望跳数是七。这是论文写下的表规模与跳数交换，不是一份要读者去调参的集群配方。

每台节点维持三份状态。路由表 $R$ 按行切开：第 $n$ 行的 $2^{b}-1$ 个格子，各指向一个与自己共享前 $n$ 位、但第 $n+1$ 位取其余某个值的节点。格子里只记一台；候选有多个时，选按邻近度量更近的那台。没有合适节点就留空。标识均匀时，平均只有 $\lceil\log_{2^{b}} N\rceil$ 行真正有人。论文图 1 用假想节点 10233102 讲完这件事：$b=2$、叶集长度八，数字按四进制写；阴影格是自己的那一位。

叶集 $L$ 记下数值上最近的 $|L|/2$ 个更大标识和 $|L|/2$ 个更小标识。邻近集 $M$ 记下按邻近度量最近的 $|M|$ 台。两者典型取值是 $2^{b}$ 或 $2\times 2^{b}$。主实验取 $b=4$、$|L|=16$、$|M|=32$。叶集用于转发；邻近集通常不用于转发。

转发手续按论文表 1。键 $D$ 落到本机叶集覆盖的数值区间里，就交给叶集里 $|D-L_i|$ 最小的那台——可以是自己。否则看本机与 $D$ 已经共享的前缀长度 $l$，若路由表第 $l$ 行、对应 $D$ 下一位的格子非空，就把消息交给那台，前缀至少再长一位。格子空了或对端不可达，则在叶集、路由表、邻近集的并里找一个前缀不短于 $l$、且数值比自己更靠近 $D$ 的节点。每一步要么让前缀变长，要么前缀同样长但数值距离变小，于是手续收敛。分析把第三种情形的概率写成：在表准确、没有刚发生的失效时，$|L|=2^{b}$ 低于百分之二，$|L|=2\times 2^{b}$ 低于千分之六；一旦发生，高概率只再多一跳。大量同时失效时，跳数在最坏情况下可以到与 $N$ 成线性——论文标明这是宽松上界，并把渐变退化留给第三节的实验。最终送达的保证绑在叶集上，不绑在前缀格子是否填满。

上层接口很少。pastryInit 返回本机标识；route(msg,key) 把消息送到数值最近的活节点。应用提供 deliver、forward 和 newLeafs：本机就是最近者时投递；转出前可改内容或下一跳，下一跳置空则停；叶集变化时通知上层。转发是覆盖网上的递归移交，不是 Chord 原型里那种发起者自己一连串去问。网络协议 在这里是格子里的 IP 地址所承载的那一层。邻近度量可以是 IP 跳数或地理距离，由应用提供测距函数。三角不等式被假定成立；论文承认它对某些因特网度量不成立，基本转发不受影响，局部性声明可能变弱。

加入被写成如何把三张表填成论文所要求的形状，不是一份接入现网的操作手册。新节点 $X$ 被假定已经知道一台按邻近度量靠近自己、且已在网内的 $A$。$X$ 请 $A$ 转发一条键等于 $X$ 标识的加入消息，消息落到当前数值最靠近 $X$ 的 $Z$。$A$ 的邻近集、$Z$ 的叶集，以及路径上第 $i$ 个节点的第 $i$ 行前缀表，构成 $X$ 的底稿。第二阶段再向第一阶段填进表里的节点要一份状态，换成更近的格子。邻近集在这一步传播“附近还有谁”，不管对方前缀。加入的消息条数是 $O(\log_{2^{b}} N)$，常数大约 $3\times 2^{b}$。并发用时间戳乐观处理：期间状态已变就重来。这些是论文对自己装置的声明，不是超时配方。

离开被定义成标识空间上的紧邻再也联络不上。叶集向失效一侧仍活的远端成员要一份表，除非连续 $\lfloor|L|/2\rfloor$ 个相邻标识一起失效，可以惰性修好。路由表项在转发时发现不可达才换：先问同一行，再撒到下一行。邻近集被周期探测。第二节末尾把任意错误行为点到为止：确定性路径会让同一查询反复走到不肯正确转发的节点；论文说可以在合法下一跳里做随机化选择，并把细节标成超出本文范围。本页不把这句话展开成攻击或部署步骤。

局部性没有全局方向，不保证源到宿的最短路。前缀表每一格在前缀约束下选邻近度量更近的代表，于是每一步在标识空间里走近目标，同时在邻近空间里走当时看起来最短的一截。两条几何图像被写在纸上：消息一旦从 $A$ 走到距离为 $d$ 的 $B$，随后不能再走进距 $A$ 小于 $d$ 的节点；连续各行的候选按 $N/2^{bl}$ 变稀，每一步期望走得更远。复制场景里，$k$ 个数值近邻因随机标识而往往散开；路径仍朝数值最近者走，并倾向于先碰到离客户端较近的那一台。前缀优先可能错过前缀不同却更近的副本。启发式用本地叶集估计密度，接近那 $k$ 个近邻时改走数值最近。第三节把这件事量成百分比，而不是写成副本布局手册。

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

原型用 Java 写，跑在一台四路 Compaq AlphaServer ES40 上，主存六吉字节。为了把规模做到十万，所有 Pastry 节点进同一台 Java 虚拟机，仿真器维护节点之间的距离。每个节点在 $[0,1000]$ 的平面上随机取坐标。论文写明这不是因特网的簇状分布，三角不等式也不总成立，并提到正在用更写实的拓扑继续做；本页只采用已经画进这篇 Middleware 文本的平面模型。

第一组实验扫规模。$b=4$、$|L|=16$、$|M|=32$，节点数从一千到十万，二十万次随机选一对再走一条消息。平均跳数按预测随规模上升。十万节点时跳数分布被单独画出：两跳约百分之一点五六，三跳约百分之十六，四跳约百分之六十四点五，五跳约百分之十七点五，六跳为零。最大值五，正是 $\lceil\log_{16} 100000\rceil$。第二组实验拿“每台都有全表”的虚构方案当尺子。Pastry 路径在邻近度量上大约长百分之三十到四十；十万节点时前缀表大约七十五项，全表则近十万项。未优化的 Java 实现声称每秒处理超过三千条消息。这是单机仿真吞吐量，不是公网发票。

加入手续对局部性的影响，用五千个节点一个接一个加入来量。只取路径上对应的那一行、取整份状态但不做第二阶段、以及论文实际用的两阶段办法，被画在同一张图上。五千节点、$b=4$ 时，第二、三行本来就不会填满。实际办法下，每一行平均不到一项不是按邻近度量的最佳选择。少交换信息会让次优或缺失急剧变多。

副本实验把 $k$ 取五，网络一万节点，$b=3$、$|L|=8$，十万次随机起点与随机键。不用启发式时，先到达按邻近度量最近那台约百分之六十八，落在最近两台之内约百分之八十七；加上用本地叶集估计密度的启发式，两个数字升到约百分之七十六与百分之九十二，距“估计完美”的对照大约两个百分点。这是“先碰到哪一台副本”的仿真，不是就近调度产品。

失效实验从五千节点里静默抽走百分之十，先关掉表修复再做二十万次查找，然后打开修复再走同样的键与起点。修复后，用过的格子里缺失项被补回，局部性接近失效前。平均跳数从 $2.73$ 升到不修复时的 $2.96$，修复后回到 $2.74$。每个失效节点平均五十七次远程调用。这些是仿真计数，不是超时配方。

没有十个地理站点上的查找中位毫秒，没有把平面换成一份可复核的因特网拓扑再重画全部图，也没有把网络地址转换写成一套可照做的穿越步骤。恶意参与者如何垄断邻居、如何批量伪造身份，第二节末尾只把随机化下一跳和“细节超出本文”写到为止，本页也不补。上层要的持久存储与发布订阅，在 PAST 与 SCRIBE 里，不在这三张表的路由手续里。Kademlia 后来用对称异或和发起者并行问询另写一页；Chord 用环、后继和手指另写一页。三份对象不能兑成一句“都是对数跳的分布式哈希表”。

跨域连接#

• 概率论：$\lceil\log_{2^{b}} N\rceil$ 不是对任意标识布置都成立的最坏情况发票，而是标识均匀、表准确、没有刚发生的失效时的期望步数。第三种转发——前缀格子用不上、改走“前缀不短且数值更近”——在 $|L|=2^{b}$ 时低于百分之二，在 $|L|=2\times 2^{b}$ 时低于千分之六。最终送达要求连续 $\lfloor|L|/2\rfloor$ 个相邻标识不同时失效；相邻标识因随机哈希而往往分散，于是这事件被写成可以压得很低，不是公网故障率。加入路径上第 $i$ 行的候选集合按 $N/2^{bl}$ 变稀，是把均匀投点改写成“每一步期望走得更远”的几何图像。
• 图论：覆盖网是一张有向图。前缀表给出按数字位分层的出边：第 $n$ 行是“前 $n$ 位已同、下一位取其余值”的袋，每袋通常一条、并按邻近度量挑选。叶集是数值环上左右各半的短链，直径在这一截上被压成一跳。邻近集是按另一种度量——平面距离或 IP 跳数——剪出来的星，通常不出现在转发路径上。查找是一条前缀单调变长、或前缀持平但数值距离下降的路径。Chord 的图是环加二的幂弦；Kademlia 的图是按异或分层的桶。直径的对数声明依赖表大致准确；大量同时失效时，论文给出的宽松上界是线性于 $N$ 的退化，而不是把图撕成两半。
• 认识论：没有任何一个节点被允许声称自己看见了整份映射。前缀表是关于“下一位数字通向哪一类人、并且我这边看起来近”的局部知识；叶集是关于“数值上谁紧挨着我”的、被当成正确性所要求的那种真；邻近集是关于“物理上谁在我附近”的证词，用来改善局部性，不能单独保证到达。forward 把中间判断交给沿途节点，应用可以改下一跳或就地停住；这与 Chord 原型里发起者亲历每一跳的迭代风格不是同一种作证方式。确定性路径会让同一查询反复采信同一份错误证词，论文因此把合法下一跳上的随机化写成一种补救，而不是写成已经量过的抗任意错误方案。
• 信息不对称：Napster 把“键在哪”收成一份中心目录。Pastry 把这份目录拆成每台大约 $\lceil\log_{2^{b}} N\rceil\times(2^{b}-1)$ 项的前缀表，外加常数大小的叶集与邻近集。谁也不比谁多知道整个映射，但任意节点仍能在对数跳内把差距补到“数值最近者”。一致性哈希 的 1997 年写法假定节点大体知道彼此，信息不对称被预先抹平；Pastry 要处理的正是抹不平之后，局部前缀如何仍然够用。邻近度量把另一笔不对称写进表里：我离谁近，不必等于谁离我近，选格时用的是本机视角。Kademlia 后来用对称异或把“谁出现在我的桶里”与入站查询的发送方对齐；Pastry 不靠对称性学习，而靠加入时沿途借表、再加第二阶段比较距离。
• 计算复杂性：这里的资源是覆盖网跳数、每节点状态和加入时交换的消息，不是图灵机步数。$b$ 把表项数 $\lceil\log_{2^{b}} N\rceil\times(2^{b}-1)$ 与跳数 $\lceil\log_{2^{b}} N\rceil$ 绑在同一把尺子上：一百万节点、四位一组时大约七十五项、五跳。加入是 $O(\log_{2^{b}} N)$ 条消息，常数大约 $3\times 2^{b}$。CAN 被拿来对照：状态不随 $N$ 增长，跳数却按 $N^{1/d}$ 走。把这条对数界读成复杂度课里的 P 与 NP，会把通信轮次误认成判定问题的时间类；它回答的是“按前缀走近一个键要问几个人”，不是“这个问题算不算得起”。

参考文献#

• Rowstron, A. & Druschel, P. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. Proc. IFIP/ACM Middleware, LNCS 2218, 2001, pp. 329–350. doi:10.1007/3-540-45518-3_18（本文对象）
• 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（数值差转发、不把邻近写进手指；论文直接对照）
• 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（对称 XOR 与 $k$-bucket；自承第一阶段像前缀路由）
• 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. G., Rajaraman, R. & Richa, A. W. Accessing Nearby Copies of Replicated Objects in a Distributed Environment. Theory of Computing Systems 32, 1999, pp. 241–280.（前缀定位的前身；论文指出其尚未充分自组织）
• Ratnasamy, S., Francis, P., Handley, M., Karp, R. & Shenker, S. A Scalable Content-Addressable Network. Proc. ACM SIGCOMM, 2001.（同期 $d$ 维空间；状态不随 $N$ 变，查找随 $N^{1/d}$ 变）
• FIPS 180-1. Secure Hash Standard. U.S. Department of Commerce / NIST, 1995.（标识可由 SHA-1 一类哈希从公钥或地址派生）

延伸阅读#

• Druschel, P. & Rowstron, A. PAST: A large-scale, persistent peer-to-peer storage utility. Proc. HotOS VIII, 2001.（把 Pastry 当定位层的存储；非本文对象）
• Rowstron, A. & Druschel, P. Storage management and caching in PAST, a large-scale, persistent peer-to-peer storage utility. Proc. ACM SOSP, 2001.（PAST 的存储与缓存；非本文对象）
• 与 Chord 对读：环加后继加手指，对前缀表加叶集加邻近集。
• 与 Kademlia 对读：对称 XOR 加 $k$-bucket 加发起者并行问询，对前缀步进加数值收尾。
• 与 一致性哈希 对读：1997 年管分配与迁移量；2001 年管抹不平全局知识之后，局部前缀如何仍能对数跳定位。