Tapestry：邻接表、代理路由与就近副本，不是把对象搬到键上

破除误解#

误解二：对等查找就是某款文件共享软件去掉中心目录，Tapestry 是那条产品史的一章。 报告要的原语更窄：用位置无关的名字给消息寻址，并请求把它送到按网络时延或地理邻近定义的最近副本。驱动应用是 OceanStore，不是某品牌覆盖网的兴衰。相关工作拿 Globe、广域 SLP、服务发现与 anycast 对照，也拿同期的 Pastry、Chord、CAN 对照。把本页读成 Napster 之后的下一款客户端，会把邻接表和软状态指针换成另一套产品年表。

误解三：Tapestry 就是 1997 年 Plaxton、Rajaraman 与 Richa 那张静态网，动态插入只是工程补丁。 第二节把 Plaxton 网格写成前身：名字是与位置无关的随机定长比特，例如四十个十六进制位表示一百六十比特；邻接表按后缀一位一位走近目的地，一致时逻辑跳数至多 $\log_b N$，表规模 $b\log_b N$。Plaxton 还证明定位加转发的网络距离与底层距离成比例。缺口有三条：唯一根要用构造时的全局知识；根是单点故障，远处客户端若沿途碰不到中间指针，根一不可达，对象就从他们眼里消失；网格静态，插入也要重算根函数。Tapestry 用代理路由给出唯一活根，用盐值再哈希给出多个根，用软状态租约让指针可丢可补，用第四节的增量算法把新节点织进去。前身与后继不能兑成同一页。

误解四：$\log_b N$ 跳和相对时延惩罚是一张在公网上量过的毫秒发票。 第五节跑在分组级仿真器上，拓扑跳是单位距离，量的是定位相对时延惩罚：Tapestry 走过的距离比上直达该对象的底层距离。拓扑包括 AS-Jan00、1999 年的 MBone、TIERS 五千点和 Transit-stub 五千点；有中间位置指针时比值相对平稳，拿掉指针则跳数冲向根。纠删实验把四千零九十六个 Tapestry 节点铺在五千点 Transit-stub 上，不是十个真实机房。覆盖网相对时延惩罚拿跳数比 IP 跳数。这些是仿真器里的跳数与比值，不是公网查找中位毫秒。

邻接表、代理路由与软状态指针#

协议的心脏是把节点与对象的名字读成同一底 $b$ 的数字串，然后按已经对齐的后缀再补一位。技术报告从右往左解析数字，并写明方向是任意的；后来的文本有时改成从左对齐前缀，本页跟这份四月报告走。第 $n$ 个到达的节点与目的标识至少共享长度为 $n$ 的后缀；下一跳看第 $n+1$ 级表里与目的地下一位相符的那一格。节点 $N$ 的邻接表第 $j$ 级有 $b$ 格；第 $j$ 级第 $i$ 格记下按网络距离最近、后缀为 “$i$” 接上 $\mathrm{suffix}(N,j-1)$ 的那台。报告举节点 325AE：第四级第九格是距离它最近、以 95AE 结尾的节点。每一格还为故障准备两台次级邻居。假定表一致，名字空间大小 $N$、底为 $b$ 时，任一现存节点至多 $\log_b N$ 逻辑跳可达，表规模 $b\log_b N$。每个目的节点是一棵生成树的根。报告图 1 用四位十六进制、从 0325 走到 4598 画完这一趟。

定位把“对象在哪”写成沿途可修的指针，而不是把对象搬到键的数值近邻上。服务器 $S$ 发布对象 $O$，就是朝 $O$ 的根发一条消息；每一跳存一份映射 $\langle\mathrm{Object\text{-}ID}(O),\mathrm{Server\text{-}ID}(S)\rangle$。指针指向存放处，不是对象本身。Plaxton 在通往根的节点上只保留离自己最近的那一份副本；Tapestry 把多份位置都存下来，好让应用自己定义选择算子——除距离外还可带新鲜度，也可以要求送到最近的 $N$ 份互异对象。查询同样先朝根走：半路遇到映射就转向该服务器；一路都没有，根上保证能找到。根与对象没有语义姻亲，它只是那份映射的担保人。

Plaxton 用全局全序选根，并承认要靠全局知识从稀疏名字空间里挑一台还在的机器。Tapestry 的代理路由先假装根的名字就等于对象标识 $I$，朝 $I$ 走；稀疏空间里这台机器多半不存在，于是会撞上空格。空格处在仍有的邻居指针里做一次确定性挑选。路由停在这样一张表上：除了自己，这一级再没有非空格。那台机器就是该对象的代理根。空格只能在全网都没有合格节点时出现，于是共享同一后缀的节点空格图案相同，从任一处出发会走到同一台代理根。相对 Plaxton 的静态捷径，代理路由可能多走几跳。报告把它收成优惠券收集：十六进制时，“空格出现而当前后缀下还剩超过 $b/2$ 台”的概率低于 $b/e^{b}$，约 $1.8\times 10^{-6}$；从第一次空格到只剩一台，期望大约 $\log_b(b^{2})=2$ 跳。

根仍可以是单点。Tapestry 给每个对象派多个根：把一小段全局恒定的盐值——报告举例 $1,2,3$——接到对象标识后面再哈希。发布与查找走同一套哈希，得到一组可并行去问的根。盐值被说成若干张独立的 Plaxton 平面：有 $s$ 个根时，即便发生完全分区，数据仍经某一根可达的概率被写成约 $1-(1/2)^{s}$。指针带软状态租约，存放处按间隔重新发布；对象被删或服务器不可达，沿途缓存会超时。软状态的谱系被点到 IGMP 与 MBone 会话公告。故障由上一跳发现并绕开。每台节点还维持反向指针，供插入时通知、也供用 UDP 心跳声明自己仍可当下一跳。探测用 TCP 超时；主邻居失效后改走次级。多数故障被认为会较快修好，于是先标为无效，并留一段“再给一次机会”的窗口——报告举例一天。这些是报告对自己装置的声明，不是超时配方。网络协议 在这里是格子里的地址所承载的那一层。

动态插入被写成如何在没有全局知识时把邻接表填成“还算像样”的形状，报告不声称得到理想拓扑。新节点 $N$ 被假定已经知道一台按网络距离靠近自己的网关 $G$。$N$ 从 $G$ 起朝自己的新标识走，第 $i$ 跳与 $N$ 共享长度为 $i$ 的后缀；$N$ 拷下这一级表，再拿主邻居与次级邻居比距离，直到再挖下去没有显著改进——报告举例百分之十五的距离下降。下一跳空了就停，改走到当前代理根，并把本该由新标识承接的数据挪到 $N$。随后沿代理根的反向指针按层退回；第三节称代理多走的跳数高概率不超过两跳，于是退三跳应能通知到相关空格。填空格会改变此后的代理路径，于是要么显式删除旧指针再发布，要么等软状态自己换新。离开可以沿反向指针主动告知，也可以交给软状态。报告写明当前不适合传感器网那种持续剧烈变化的环境。

软状态若当真按固定间隔重发全部指针，带宽会先把方案顶住。报告用一百万节点、一万亿个对象做一次纸面账：一次发布按四十跳计，每机约一千四百兆字节；若间隔定为一天，摊下来约一百二十九千比特每秒。于是第四节改成显式更新加软状态垫底：映射扩成三元组 $\langle$对象，服务器，上一跳$\rangle$，并用纪元号做指针版本。节点离开时通知相关服务器带新纪元重发，在与旧路会合处沿上一跳反向删掉旧指针。对象从 $A$ 迁到 $B$ 时，$A$ 先留下转发指针，$B$ 带新纪元发布。不一致窗口里，客户端若被指到旧处，至多多付一次往返，然后可继续朝根走。热点监测把“某源查询超过阈值、建议在源头附近加副本”交给上层。这些是纸上的装置与权衡，不是集群复制手册。

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

定位实验要核对的，是 Plaxton 已经证明过的那件事在仿真拓扑上是否还看得见：带着中间位置指针去定位并走到对象，相对底层直达，开销应是一个不大的线性因子。分组级仿真器采用单位距离跳。四份拓扑都呈同一趋势：有局部性指针时，定位相对时延惩罚保持在较小且相对平稳的因子上；没有指针，路径被拉去根。正文画出 TIERS 五千点与 Transit-stub 五千点两张。这是跳数比，不是公网毫秒。

稳定性被写成用冗余换方差。Silverback 把对象纠删成例如三十二片，拼回需要最快到达的十六片。实验在四千零九十六个 Tapestry 节点、五千点 Transit-stub 上跑，每跳时延用无记忆分布绕平均值一跳单位；一半服务器被标成高负载，响应多加六跳单位。把同时发出的片段请求从阈值往上加，到达十六片的时间与方差都下降；再给链路百分之二、百分之四的故障并计入超时重传，多出来的请求带来的改善更明显。聚合带宽随请求数近似线性涨。多根实验给随机放置的对象派五个随机标识：对不紧挨根的客户端，并行能明显压低时延；从一根加到两根的那一刀最陡；一根、两根的曲线更锯齿，五根并行把长跳的随机性抹平。这些是仿真计数，不是归档产品的部署参数。

压力实验把简化的 Tapestry 定位——关掉热点管理器与多根——和中心目录放在 ns-2 的一百个节点上。查询负荷按万维网形状来：百分之十五的对象吃掉百分之九十的查询。背景流量制造丢包。沿服务器到根的复制让 Tapestry 在零星丢包下退化得比较缓；中心目录在丢包升高后被隔开，TCP 重传与指数退避再把它拉差。另一组给路由器加上故障意识：下一跳可靠程度低过阈值就把分组复制到备用邻居。覆盖网开销用相对时延惩罚：Tapestry 路由距离比上 IP 路由距离，在四份拓扑上扫不同的标识底，画的是第九十百分位。

没有十个地理站点上的查找中位毫秒，没有把单位跳拓扑换成一份可复核的因特网时延矩阵再重画全部图。恶意参与者如何垄断邻居、如何批量伪造身份，报告把拜占庭与“把通向恶意服务器的路当成损坏目录丢掉”写到设计动机与未来工作为止；本页不补成步骤。网络地址转换如何穿越，不在对象里。Java 实现被写成正在收尾，分组仿真器是 C 的；那是 2001 年四月的进度，不是一份已上线覆盖网的发票。上层要的持久存储、纠删归档与应用层组播，在 OceanStore、Silverback 与 Bayeux 里。Pastry、Chord 与后来的 Kademlia 各有专页；三份对象不能兑成一句“都是对数跳的分布式哈希表”。

跨域连接#

• 概率论：名字被假定由哈希铺得大致均匀，于是每多对齐一位后缀，仍合格的候选大约按底 $b$ 变稀，查询与发布的路径才被期望很快相交。代理路由多出来的跳数被收成优惠券收集：$b$ 格的表用大约 $b^{2}$ 个随机项即可高概率填满；十六进制时，空格出现而当前后缀下还剩超过 $b/2$ 台的概率低于 $b/e^{b}$，约 $1.8\times 10^{-6}$，从第一次空格到只剩一台的期望大约两跳。多根公式 $1-(1/2)^{s}$ 是完全分区下“至少一张平面仍可达”的模型，不是公网分区率。
• 图论：覆盖网是一张有向图。邻接表给出按后缀分层的出边：第 $j$ 级是“已对齐 $j-1$ 位、下一位取各个数字”的袋，每袋先填按邻近度量最近的一台，再挂两台次级。反向指针是入边的显式记忆。每个目的标识是一棵生成树的根；代理路由在缺节点时仍把任意标识确定地映到一台活根。Chord 的图是环加二的幂弦；Kademlia 的图是按异或分层的桶。Tapestry 的局部性来自“每一格在后缀约束下选邻近度量更近的代表”，不是来自标识数值与地理距离的天然对应。
• 认识论：没有任何一个节点被允许声称自己看见了整份映射。邻接表是关于“下一位后缀通向哪一类人、并且我这边看起来近”的局部知识；根上的指针是关于“对象至少在这里能被找到”的担保，中间跳上的指针是可过期的证词。Plaxton 的全局全序是一种不允许局部修订的根知识；代理路由把这门知识改写成沿途空格上的确定性挑选。软状态说的是：目录允许暂时不一致，只要不一致的量与持续时间可被租约和显式纪元钉住。多根是同一对象上的多份独立证词，并不要求先证明所有平面一致。
• 信息不对称：中心目录把“对象在哪”收成一份谁都能问的清册，也把可用性钉在这本清册还能不能被问到上。Tapestry 把清册拆成沿发布路径放下的指针：离对象近的查询往往不必走到根。一致性哈希 的 1997 年写法假定节点大体知道彼此，信息不对称被预先抹平；本页要处理的是抹不平之后，局部后缀加一份软状态指针是否仍然够用。邻近度量把另一笔不对称写进表里：我离谁近，不必等于谁离我近。Pastry 用加入时沿途借表来填前缀；Tapestry 还要把“对象仍在原处”的消息沿树根方向做软状态扩散。
• 玻尔兹曼统计力学：报告把“用统计换稳定性”写成与摩尔定律冗余同一方向的选择：不再抠每一周期、每一比特，而靠许多相互作用的部件在失效仍属常态时给出更均匀的行为。纠删片段实验是这一句的仿真版——阈值十六、总共三十二，多要几片是在用额外带宽换到达时间的均值与方差。多根并行是同一思想在定位平面上的重复：一两条平面会把某次长跳写成锯齿，五根把那次长跳藏进更平滑的曲线。这里的“系综”是随机标识、多路径与多副本，不是把覆盖网写成热平衡，更不是一份靠堆副本去掩盖错误配置的操作单。

参考文献#

• Zhao, B. Y., Kubiatowicz, J. & Joseph, A. D. 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. Proc. ACM SPAA, 1997, pp. 311–320.（静态定位；报告指出全局知识、单根与不能自组织）
• 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.（同一结果的期刊稿）
• Rowstron, A. & Druschel, P. Pastry: Scalable, decentralized object location and routing for large-scale peer-to-peer systems. 报告相关工作所引的 2001 年稿；会议录后见 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. 报告相关工作所引的 2001 年稿；会议录后见 Proc. ACM SIGCOMM, 2001, pp. 149–160. doi:10.1145/383059.383071（环与手指；逻辑近不必是网络近）
• Ratnasamy, S., Francis, P., Handley, M., Karp, R. & Shenker, S. A Scalable Content-Addressable Network. 报告相关工作所引的 2001 年稿；会议录后见 Proc. ACM SIGCOMM, 2001.（$d$ 维坐标）
• Kubiatowicz, J. et al. OceanStore: An Architecture for Global-Scale Persistent Storage. Proc. ACM ASPLOS, 2000.（驱动应用；非本文对象）
• Deering, S. Host Extensions for IP Multicasting. RFC 1112, 1989.（软状态 announce/listen 的谱系）
• Rekhter, Y. & Li, T. An Architecture for IP Address Allocation with CIDR. RFC 1518, 1993.（最长前缀转发的对照）
• Robshaw, M. J. B. MD2, MD4, MD5, SHA and Other Hash Functions. RSA Laboratories TR-101, 1995.（标识可由哈希铺匀）

延伸阅读#

• Zhao, B. Y., Huang, L., Stribling, J., Rhea, S. C., Joseph, A. D. & Kubiatowicz, J. D. Tapestry: A Resilient Global-Scale Overlay for Service Deployment. IEEE JSAC 22(1), 2004, pp. 41–53.（后出期刊重述；非本文对象）
• Hildrum, K., Kubiatowicz, J. D., Rao, S. & Zhao, B. Y. Distributed Object Location in a Dynamic Network. Proc. ACM SPAA, 2002.（动态网上的定位证明；非本文对象）
• Zhuang, S. Q., Zhao, B. Y., Joseph, A. D., Katz, R. H. & Kubiatowicz, J. D. Bayeux: An Architecture for Scalable and Fault-tolerant Wide-area Data Dissemination. 报告所引的 2001 年稿；后见 Proc. NOSSDAV, 2001.（应用层组播；非本文对象）
• 与 Pastry 对读：数值最近者加叶集，对就近副本指针加代理根。
• 与 Chord 对读：环加后继加手指，对后缀邻接表加软状态目录。
• 与 Kademlia 对读：对称 XOR 加发起者并行问询，对沿树根放下的指针。
• 与 一致性哈希 对读：1997 年管分配与迁移量；2001 年管没有全局成员表之后，局部后缀如何仍能把消息送到近处的那一份。