CAN：笛卡尔分区与贪心转发，状态不随规模涨

破除误解#

误解二：对等查找就是某款文件共享软件去掉中心目录，CAN 是那条产品史的一章。 引言拿 Napster 的中心索引和 Gnutella 的有范围泛洪当反例，问题被收成：文件传送本身可扩展，难的是找到那台对等端。论文承诺的接口只是哈希表。OceanStore、Farsite、Publius 被写成可能的用户，不是本页要交付的产品。Freenet 一类系统在人人守规矩时仍可能找不到已有内容；CAN 在正常运行时给每个键一个确定的“家”，任何节点都知道这个家在坐标上的位置、以及怎么朝它走。把本页读成某个品牌覆盖网的兴衰，会把分区与贪心换成另一套产品年表。

误解三：$(d/4)N^{1/d}$ 是一张在公网上量过的毫秒发票，仿真曲线可以直接当成二十六万节点因特网时延。 这条式子写的是应用层跳数：空间被切成 $n$ 个相等区时的平均路径长度，不是 IP 毫秒。论文反复提醒，坐标相邻的两台在底层可能隔着许多英里、许多 IP 跳。查找总时延是跳数乘上每一跳的时延；他们要压的是相对底层 IP 路径的那一截拉长。仿真跑在 GT-ITM 生成的 Transit-Stub 拓扑上。累积实验把二十六万余节点的“裸 CAN”画成约一百九十八跳、路径时延约二十三秒；把维度、区超载与往返时延加权一齐打开后，跳数大约五、路径时延约一百三十五毫秒。这些是仿真器里的跳数与时延比，不是十个机房里的中位查找发票。

误解四：坐标空间就是地理或 IP 拓扑，贪心等于沿地图走最短路。 第二节第一句就把空间写成完全逻辑的，与任何物理坐标无关。随机加入时，伯克利的节点完全可能把欧洲的节点当成邻居，去斯坦福的路径会绕远。后文用往返时延加权、区超载时挑选更近的对端、以及仍标成进行中的地标分箱，去补这一截；累积对照故意关掉了地标。贪心是笛卡尔距离上的下一步，不是底层最短路。网络协议 在这里是邻居表里那串 IP 地址所承载的那一层。

笛卡尔空间、分区与贪心转发#

协议的心脏是一张 $[0,1]^d$ 上的虚拟坐标空间。任意时刻，整张空间被当时仍在的节点动态切开，每台拥有互不重叠的一区。论文图 1 用二维、五台节点画完这件事。存 $(K,V)$ 时，用均匀哈希把 $K$ 映到点 $P$，交给拥有 $P$ 的那一区；取回时任何节点用同一哈希得到 $P$，再朝该区走。空间本身不规定文件名怎么切词，也不提供匿名。

每台维持一份坐标路由表：每个紧邻的 IP 地址及其区的范围。$d$ 维里，两台相邻当且仅当它们的区在 $d-1$ 维上重叠、沿一维紧挨。图 2 里节点 5 是节点 1 的邻居，节点 6 不是，因为后两者沿 $X$ 与 $Y$ 都只是顶角相碰。消息里带着目的坐标。本机在邻居里挑坐标上最靠近目的地的一台，贪心交出。两点之间往往有多条路：一台邻居垮了，可以改走当时次优的那条。若某一方向上的邻居全没了，而修复还没补上空洞，贪心可能暂时走不动；论文写的退路是在覆盖网上做受控的扩展环搜索，找到一台比自己更靠近目的地的节点，再恢复贪心。本页不把这句话展开成泛洪或部署步骤。

均匀切成 $n$ 个区时，平均路径长度是 $(d/4)n^{1/d}$ 跳，每台大约 $2d$ 个邻居。$d$ 固定，节点数可以涨，每台状态不必涨，平均跳数按 $O(n^{1/d})$ 走。这是应用层跳，不是 IP 跳。脚注把 Plaxton 与 Chord 的 $O(\log n)$ 跳、$O(\log n)$ 邻居写成另一组交换：CAN 也能靠让 $d$ 随 $n$ 涨去对齐，但正文选择不这么做。

加入被写成如何给新人切出一区，不是一份接入现网的操作手册。新人先要认识网内任意一台；功能不依赖发现细节，正文借用 YOID 的假设：域名解析到若干引导节点，再拿到若干随机在网节点的地址。新人在空间里随机挑一点 $P$，把 JOIN 交给任意在网节点，沿 CAN 转发直到拥有 $P$ 的那台。该台把本区切成两半，留下一半、交出一半，并把该半区上的键值对一并移交。切哪一维按固定次序轮转，二维时先 $X$ 后 $Y$，好让离开时还能并回去。新人的邻居集是原占有者邻居集的一个子集，外加原占有者自己；原占有者删掉不再相邻的项。随后双方的邻居靠立即更新加周期刷新学会这次重切。一次加入只搅动坐标空间里很小一块，$O(d)$ 台，不随 $N$ 涨。图 2 与图 3 用节点 7 加入画完邻居集怎么改。

离开时，正常手续是把本区及键值库交给一名邻居。若某邻居的区能与本区并成一个合法区，就合并；否则交给当前区体积最小的邻居，由它暂时照看两块。节点或网络故障靠接管：邻居久收不到更新，就认为对端死了，启动与本区体积成比例的定时器，并用带体积的 TAKEOVER 消息在失效节点的邻居之间比出体积更小的活着的一方。键值对在故障路径上会丢，直到原插入者按周期刷新。多台相邻同时失效、本机够不到失效者半数以上邻居时，论文要求先搜到空洞另一侧，再安全接管。后台还有一套把“一台多区”收回“一台一区”的重切；附录用概念上的二分剖分树解释，实现只靠本地邻接。这些是论文对自己装置的声明，不是超时配方，也不写成攻击步骤。

第三节把时延拆成跳数与每一跳的时延，并列出一批旋钮。加维使邻居略增、路径按分析式变短；图 4 从数百到约一百万节点扫 $d=2$ 到 $5$，曲线贴着 $O(d\,n^{1/d})$。现实（reality）是 $r$ 张独立坐标空间，每台在每张上各占一区；同一键值各存一份，四张现实时要四台同时不可达才丢。转发看所有现实上的邻居，交给坐标上最靠近目的地的那台。同一邻居预算下，加维比加现实更能压跳数；现实另换数据可用性。往返时延加权按笛卡尔进度除以到该邻居的往返时延选下一跳。Transit-Stub 上随机两端的底层平均时延约一百一十五毫秒；表 1 里未加权的每跳贴着这个数，加权后二维降到 $88.3$ 毫秒，五维降到 $70.9$ 毫秒。区超载让一区最多 $MAXPEERS$ 台对等端，正文设想三或四；邻居表仍按邻区各记一台。表 2 里一区四台把每跳从 $116.4$ 毫秒降到 $64.4$ 毫秒。多哈希把同一键映到 $k$ 个点，可并行问。更均匀的切开：JOIN 落到的那台先比自己与邻居的区体积，切开最大的那块。六万五千五百三十六节点、三维时，没有这步则大约百分之四十的节点分到体积 $V=V_T/n$，最大到 $8V$；加上之后将近百分之九十落在 $V$，最大掉到 $2V$。热点用沿途缓存与向邻居复制来写，并要求存活时间；这是纸上的装置，不是复制手册。地标分箱按到一组知名机器的往返时延排序，把空间切成 $m!$ 份；正文标成进行中，累积对照不再使用。

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

仿真器采用 GT-ITM 的 Transit-Stub：两层路由域，传输域把下层桩域连起来。节点规模在图里从数百扫到约一百万；累积对照取 $n=2^{18}$，即二十六万余台。恢复算法的大规模与 ns 小规模实验被指到 2001 年 1 月的 ICSI 技术报告，不在这篇会议文本的图里。

图 4 核对分析式；图 5 固定二维扫现实数；图 6 在约十三万节点上表明同一邻居预算下加维更能压跳数。表 1 与表 2 量的是每一跳。图 9 量区体积分布；图 7 量多哈希并行下用户先看到答案的时间。

第四节把旋钮一齐拧开，对照“裸 CAN”。裸配置取 $d=2$、$r=1$、每区不对等超载、单哈希、不用往返时延加权、不用均匀切开、不用地标；全开配置取 $d=10$、$r=1$、每区最多四台对等端、单哈希、打开往返时延加权与均匀切开，仍关掉地标。二十六万余节点上，裸路径约 $198.0$ 跳、邻居约 $4.57$、对等端为零、底层 IP 时延 $115.9$ 毫秒、CAN 路径时延 $23{,}008$ 毫秒；全开后路径约 $5.0$ 跳、邻居约 $27.1$、对等端约 $2.95$、用来对照的 IP 时延 $82.4$ 毫秒、CAN 路径时延 $135.29$ 毫秒。论文把总邻居数读成大约三十，偏高但未必不合理；最大一刀来自加维，把一百九十八跳压到大约五。脚注解释 $82.4$ 不是物理网变快了，而是超载与加权会走向更近的那份副本。他们把这一趋势外推成：再悲观地按 $n^{1/10}$ 涨，系统再扩大约 $2^{10}$、接近十亿节点，路径时延才走到底层的四倍左右——这是外推，不是十亿节点实验。图 10 换链路时延分布，系统大到十三万时，时延拉伸在所有画出的拓扑上都不超过三；随机时延涨得最快，因为新补上的边不必是低时延边。

没有十个地理站点上的查找中位毫秒，没有把 Transit-Stub 换成一份可复核的因特网时延矩阵再重画全部图。恶意参与者如何既当客户端又当服务器和路由器、如何做拒绝服务，第六节写成开放问题，本页不补成步骤。网络地址转换如何穿越，不在对象里。可变内容与关键词搜索被标成未来工作。实现项目被写成仿真之后才开始的文件共享索引，不是一份已上线覆盖网的发票。Chord 用环与手指另写一页；Pastry 用前缀与叶集另写一页；Tapestry 用后缀邻接与软状态指针另写一页；Kademlia 用异或与发起者问询另写一页。四份对象不能兑成一句“都是对数跳的分布式哈希表”。

跨域连接#

• 概率论：键被假定由均匀哈希铺到坐标空间里，于是区体积才被当成该节点将要承担的存储与请求负荷的代理量。随机 JOIN 落到哪一点，决定了谁被切开；均匀切开旋钮是在这一随机投点之上，再于局部邻居里挑体积最大者，把最大区从 $8V$ 压到 $2V$。多台现实上同一坐标同时不可达，被写成副本同时失效的合取，不是公网故障率。哈希到 $k$ 个点、查询并行发出，用户感知时延吃的是最小值，不是 $k$ 条路径的平均。这些概率图像都停在仿真与纸面模型里，没有被写成一份已校准的失效分布。
• 图论：覆盖网是一张有向图。每个区是一个顶点，出边指向几何上相邻的区，度数大约 $2d$，不随 $N$ 涨。查找是一条在笛卡尔度量上单调走近目的点的路径；环面边界让空间没有墙。Chord 的图是环加二的幂弦；Pastry 与 Tapestry 的图按数字位分层；Kademlia 的图按异或分层。CAN 的直径声明是 $O(d\,N^{1/d})$，不是对数。多条几何近路同时存在，于是单条边失效不必把图撕开；某一方向的出边全断时，正文才允许暂时改用扩展环去接回一条更近的边。现实把 $r$ 张独立的同构图叠在同一批顶点上，转发时在并集里挑。
• 认识论：没有任何一个节点被允许声称自己看见了整张哈希表。坐标邻居是关于“紧挨我的区由谁看守”的局部知识；贪心是一种只凭局部真值做的下一步判断。引导节点知道一份它相信仍活着的部分名单，不是全局成员表。Plaxton 要把对象映到节点，原文指出需要全局拓扑知识才能保持映射一致；CAN 用“随机点所在的那一区负责切开”代替那份全局知识。软状态更新是可过期的证词：久不来，就当那份邻接不再真。接管比较的是区体积，不是关于谁更可信的全局裁决。
• 信息不对称：Napster 把“键在哪”收成一份中心目录。Gnutella 用有范围的广播去问，信息不对称被换成视野边界。CAN 把目录拆成每台 $O(d)$ 项的邻接，谁也不比谁多知道整个映射，但任意节点仍能沿坐标把差距补到拥有该点的那一区。一致性哈希 的 1997 年写法假定节点大体知道彼此，信息不对称被预先抹平；本页要处理的是抹不平之后，局部几何是否仍然够用。往返时延加权把另一笔不对称写进表里：我离谁近，不必等于谁离我近，选下一跳用的是本机测到的时延。地标分箱试图让逻辑邻居与底层邻近对齐，正文承认某些排序更常见，空间会变得疏密不均。
• 计算复杂性：这里的资源是覆盖网跳数、每节点状态和加入时被搅动的节点数，不是图灵机步数。$d$ 把邻居数 $2d$ 与跳数 $(d/4)N^{1/d}$ 绑在同一把尺子上：钉住 $d$，状态与 $N$ 脱钩，跳数不再是对数。加入只影响 $O(d)$ 台。Plaxton 与 Chord 用对数邻居换对数跳；CAN 用固定维度换另一组渐近。把 $(d/4)N^{1/d}$ 读成复杂度课里的 P 与 NP，会把通信轮次误认成判定问题的时间类；它回答的是“沿坐标走近一个键要问几个人”，不是“这个问题算不算得起”。

参考文献#

• Ratnasamy, S., Francis, P., Handley, M., Karp, R. & Shenker, S. A Scalable Content-Addressable Network. Proc. ACM SIGCOMM, 2001. doi:10.1145/383059.383072（本文对象）
• 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（论文脚注所引的对数跳、对数邻居对照）
• 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.（前缀定位；论文指出其全局知识与自组织缺口）
• 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（前缀表与叶集；非本文对象）
• 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.（就近副本指针；非本文对象）
• 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；非本文对象）
• Kubiatowicz, J. et al. OceanStore: An Architecture for Global-Scale Persistent Storage. Proc. ACM ASPLOS, 2000.（论文所引的可能用户；其定位层基于 Plaxton）
• Zegura, E., Calvert, K. & Bhattacharjee, S. How to Model an Internetwork. Proc. IEEE INFOCOM, 1996.（仿真所用的 Transit-Stub / GT-ITM）
• Francis, P. Yoid: Extending the Internet Multicast Architecture. Unpublished, ACIRI, April 2000.（引导发现的借用假设）

延伸阅读#

• Ratnasamy, S., Francis, P., Handley, M., Karp, R. & Shenker, S. A Scalable Content-Addressable Network. ICSI Technical Report, January 2001.（会议文本所引、含恢复仿真的技术报告；非本文对象）
• Ratnasamy, S., Handley, M., Karp, R. & Shenker, S. Application-Level Multicast Using Content-Addressable Networks. Proc. NGC, LNCS 2233, 2001, pp. 14–29.（把 CAN 当定位层的应用层组播；非本文对象）
• 与 Chord 对读：环加后继加手指，对笛卡尔分区加贪心邻居。
• 与 Pastry 对读：前缀步进加数值叶集，对区体积与 $2d$ 邻接。
• 与 Tapestry 对读：对象仍在原处、沿途放指针，对键值进拥有该点的那一区。
• 与 Kademlia 对读：对称 XOR 加发起者并行问询，对覆盖网上的递归贪心移交。
• 与 一致性哈希 对读：1997 年管分配与迁移量；2001 年管没有全局成员表之后，局部几何如何仍能把键送到它的家。