COMP5313 Week 11 P2P 查找与分布式哈希表（Chord/CAN）总结

Posted on Edited on In Word count in article: 3.1k Reading time ≈ 11 mins.
COMP5313 Week 11 详细总结，结合课程 handout 与论文 Balakrishnan et al. “Looking up data in P2P systems” (CACM 2003)，系统梳理 P2P 查找问题、分布式哈希表（DHT）、Chord 一致性哈希环与 finger table、CAN 多维路由，附完整 finger table 与 lookup 路由例子，并明确标注考点与 optional（不考）。

Week 11 总结：P2P 查找问题与分布式哈希表（Chord / CAN）

课程：COMP5313/COMP4313 — Large Scale Networks, S1 2026 结合两份材料：① 课程 handout 11_peer_to_peer_handout.pdf；② 论文 H. Balakrishnan, M. F. Kaashoek, D. Karger, R. Morris, I. Stoica, Looking up data in P2P systems, CACM 46(2), 2003。

考点标注：⚠️ 高频/每年必考　✅ 考点　🚫 optional / 不考。 主线：把 Week 10 的「去中心化搜索」搬进分布式系统——在没有中心服务器的网络里，仅用局部邻居信息，快速、可靠地找到负责某个 key 的节点。

〇、考点速览

内容 是否考
P2P 系统简介（overlay、结构化/非结构化、Napster、Gnutella） 🚫 不考（仅用于引出 lookup）
查找问题 Lookup Problem ✅ 考点
分布式哈希表 DHT 与 lookup(key) ✅ 考点
Chord：一致性哈希环 + successor 规则 ✅ 考点
Chord：finger table 构造 + lookup 路由 ⚠️ 高频必考
Chord：时间/空间复杂度 \(O(\log n)\) ✅ 考点
Chord：successor list 容错、join、stabilization 🚫 论文深度，不考
CAN：\(d\) 维 zones、贪心路由、复杂度 ✅ 考点（细节不必过深）
Chord vs CAN 对比 ✅ 考点
Pastry / Tapestry / Kademlia / Viceroy / Freenet 🚫 课上未讲，不考

一、P2P 系统简介　🚫 optional（不考）

老师明确说本节 optional，不考，只用于引出 lookup problem；下面从简。

  • Overlay network（覆盖网络）：P2P 把节点组织成一个逻辑网络。overlay 的节点是物理网络节点的子集，每条 overlay 逻辑链路对应物理网络中的一条路径。每个节点只能直接给它在 overlay 中的邻居发消息。Overlay 让 P2P 独立于物理网络，用于索引与节点发现。
  • 两类 P2P：
    • 非结构化（unstructured）：不对 overlay 强加结构，如 Gnutella、Kazaa。
    • 结构化（structured）：overlay 组织成特定拓扑，有协议保证任何节点都能高效查找，如 Chord、CAN。
  • 三种查找方式（演化）：中心化（Napster）→ 洪泛（Gnutella）→ 结构化对称（DHT）。详见下一节的对比表。

二、查找问题 Lookup Problem　✅ 考点

定义：在大型 P2P 系统中，给定一个数据项的 key，不依赖任何中心服务器或层级结构，仅用局部邻居信息找到负责存储它的节点，并且要求路径短、消息数少。

这是所有 P2P 系统的核心问题，本质上与 Milgram 实验 / 去中心化搜索一致：每一步只把请求转发给一个「看起来更接近目标」的邻居。论文把已有方案分为三类：

方案 代表 查找机制 代价 / 问题 是否考
中心化 Napster 中心服务器存目录，查询问服务器 单点故障、扩展性差 🚫
洪泛 flooding Gnutella 把请求转发给所有邻居 健壮但消息量大、最坏 \(O(n)\) 🚫
结构化对称 Chord、CAN（DHT） 节点对称、维护少量邻居、按规则路由 可保证数据存在即能找到，\(O(\log n)\) 量级 ✅

结构化 DHT 的最大优点：可证明的保证——只要数据已存入，就一定能被找到，且开销远小于洪泛。

三、分布式哈希表 DHT　✅ 考点

普通哈希表：存 key-value 对，两种操作 put(key, value)、value = get(key)，用哈希函数把 key 映射到 bucket。

DHT：把一张哈希表分区到很多机器上，每个节点负责一部分 key。与普通哈希表的关键区别是多了一个核心操作：

\[\texttt{lookup(key)} \;\rightarrow\; \text{当前负责该 key 的节点身份（如 IP 地址）}\]

完整流程： 1. 发布者把文件名用 SHA-1 之类的普通哈希转成 key； 2. 调用 lookup(key) 得到负责该 key 的节点； 3. 在该节点上 put/get 实际数据。

DHT 必须解决两件事（论文）： 1. 负载均衡地把 key 映射到节点：所有 key 和节点都用 \(m\) 位 ID 表示；每个 key 存在 ID 与它「接近」的节点上（不同方案对「接近」定义不同：Chord 看环上后继距离，CAN 看坐标距离）。 2. 正确转发查询：任何收到 key 查询的节点，都要能把它转给更接近负责节点的下一跳。

四、Chord DHT　⚠️ 核心高频

4.1 标识符与环结构　✅ 考点

  • 每个节点有唯一 id、每个文件有 key，都用 \(m\) 位编码，因此 ID 空间大小为 \(2^m\)。
  • \(n\) 个节点排成一个有 \(2^m \ge n\) 个 slot 的环，id 沿顺时针递增。

4.2 一致性哈希与 successor 规则　✅ 考点

  • Successor 规则：key \(k\) 存在 id 满足 \(\min\{\,\text{node.id} : \text{node.id} \ge k\,\}\) 的节点上，即「顺时针方向第一个 id \(\ge k\) 的节点」，称该节点 负责（responsible for） key \(k\)；若没有正好 \(\ge k\) 的，则回绕到环首的最小 id 节点。
  • 一致性哈希（consistent hashing）的关键性质：当节点加入/离开时，平均只有 \(K/N\) 个 key 需要重新分配（\(K\) 为 key 总数，\(N\) 为节点数），且只影响邻近区间——新节点只从它的 successor 手里接管自己那段 key。
    • 对比普通取模哈希 \(h(k)\bmod N\)：一旦 \(N\) 变化，几乎所有 key 的归属都会改变。这正是 Chord 用一致性哈希而非取模的原因。

4.3 朴素查找：\(O(n)\)

若每个节点只知道自己的 successor，要找 key \(k\) 就沿环逐个询问后继，直到某节点 id \(\ge k\)。最坏要走遍几乎所有节点 → 时间 \(O(n)\)。需要 finger table 加速。

4.4 Finger Table　⚠️ 每年必考

为加速查找，每个节点 \(i\) 维护一张 \(m\) 项的 finger table，第 \(j\) 项指向负责 key \((i + 2^{\,j-1}) \bmod 2^m\) 的节点：

\[\text{finger}[j] = \text{successor}\big((i + 2^{\,j-1}) \bmod 2^m\big), \qquad j = 1, 2, \dots, m\]

  • 直觉：finger 指向环上相距 \(1, 2, 4, 8, \dots\)（2 的幂）处的负责节点，像一个 skiplist，提供由近及远的多尺度跳跃边。
  • 与 Week 10 的联系：finger 的 \(1,2,4,8,\dots\) 这些不同距离尺度的跳跃边，正对应 Week 10 小世界模型里不同尺度的 weak ties / 长程边——近处精细定位、远处大跨度逼近目标。
  • 项数 \(= m = \log_2(2^m)\)，与 \(\log n\) 同量级。

完整例子：\(m=4\)（ID 空间 \(0\text{–}15\)），在线节点 \(\{1,3,5,8,9,11,14,15\}\)。

节点 1 的 finger table：

\(j\) start \(=(1+2^{j-1})\bmod 16\) successor（负责节点）
1 2 3
2 3 3
3 5 5
4 9 9

节点 8 的 finger table：

\(j\) start \(=(8+2^{j-1})\bmod 16\) successor
1 9 9
2 10 11
3 12 14
4 \(16\equiv 0\) 1

4.5 Lookup 路由　⚠️ 每年必考

路由规则：Go as far as possible, but never pass the target（不越过目标，尽量走远）： 1. 若 key 落在「我」与「我的 successor」之间，直接交给 successor； 2. 否则，转发给 finger table 中 id 不超过 key 的最大节点； 3. 重复，直到到达负责节点。

完整路由 trace（同上环，查 key 13，从节点 1 发起）：

当前节点 finger table key 13 ∈ (当前, succ]? 不超过 13 的最大 finger 下一跳
1 [3, 3, 5, 9] (1, 3] 否 9 9
9 [11, 11, 14, 1] (9, 11] 否 11 11
11 [14, 14, 15, 3] (11, 14] 是（succ=14 负责 13） — 14（命中）

路径 \(1 \to 9 \to 11 \to 14\)。可见每跳都把到目标的距离大幅缩短。

handout 另一例（更大的环）：从节点 1 查 key 26 → \(1\to18\to20\to21\to28\)；从节点 28 查 key 12 → \(28\to4\to9\to11\to14\)。

4.6 时间复杂度：\(O(\log n)\)　✅ 考点

halving 论证（handout）：假设 id 在空间中近似均匀分布。

  • 第 1 步：finger 把查询送到目标所在的半个环；
  • 第 2 步：缩小到四分之一个环；
  • 第 \(i\) 步后：可能的目标节点从 \(n\) 个减半到 \(n/2^i\) 个。

因此约 \(\log_2 n\) 步后只剩 1 个候选 → 查找时间 \(O(\log n)\)。

4.7 空间复杂度：\(O(\log n)\)　✅ 考点

每个节点维护： - finger table，大小 \(m = O(\log n)\)； - （为应对失效/离开）其后 \(r\) 个 successor 与前 \(r\) 个 predecessor 的 id。

综合每节点状态为 \(O(\log n)\)。

4.8 容错、加入与稳定化　🚫 论文深度，不考

以下为论文细节，老师未要求，不考，了解即可：

  • Successor list：每节点记其后 \(r\approx\log N\) 个后继；即便很多 finger 指向失效节点，查询仍能在 ID 空间上前进。仅当某节点紧邻的 \(r\) 个后继同时失效才会出错；因 id 随机、失效独立，概率约 \(1/N\)。
  • 节点加入：新节点 \(n\) 让任一已有节点帮它 lookup(n) 定位，只需更新 \(n\) 与其前驱的 successor 即可保证查找正确；finger table 后台修复（只影响性能不影响正确性）；并从 successor 接管对应 key。
  • 稳定化协议（stabilization）：每节点周期性问其 successor「你的前驱是谁」，据此修正指针，保证并发加入/失效下的正确性。

五、CAN（Content Addressable Network）DHT　✅ 考点

老师说 CAN 细节不必过深，重点是思想与复杂度。

  • 结构：用一个 \(d\) 维笛卡尔坐标空间（如二维 \([0,1]\times[0,1]\)）实现 DHT。空间被划分成若干超矩形 zone，每个节点负责一个 zone，并由其 zone 的边界标识。
  • key 映射：key 映射到坐标空间中的一个点，存到包含该点的 zone 所属节点。
  • 邻居：两个节点相邻 ⟺ 它们的 zone 共享一个 \((d-1)\) 维超平面（二维时即共享一条边）。每个节点维护其所有邻居的路由表，邻居数约 \(2d\)。
  • 贪心路由（greedy）：查询沿「从发起者到目标点的直线」推进——每步转发给坐标上最接近目标的邻居（平局任意打破），直到到达包含目标点的 zone。
  • 复杂度：
    • 每节点状态（邻居数）：\(O(d)\)；
    • 查找时间：\(O(d\cdot n^{1/d})\)。直觉：每个维度上约有 \(n^{1/d}\) 段，平均要跨越 \(\tfrac{d}{4}n^{1/d}\) 段，故为 \(O(d\,n^{1/d})\)。二维时约 \(O(\sqrt n)\)。
  • 加入：新节点随机选坐标点 \(P\)，让负责 \(P\) 的节点把其 zone 一分为二，交一半给新节点；新节点据邻居信息初始化路由表。
  • 离开/失效：把 zone 交给邻居，若能合并成合法 zone 则合并，否则邻居暂时兼管；后台运行 zone 重分配算法避免碎片化（🚫 细节不考）。

六、Chord vs CAN 对比　✅ 考点

维度 Chord CAN
结构 一维环形 ID 空间 \(2^m\) \(d\) 维笛卡尔坐标空间，分 zones
key 归属 顺时针第一个 id \(\ge k\) 的节点（successor） 包含 key 坐标点的 zone
路由信息 finger table（\(1,2,4,\dots\) 跳） 约 \(2d\) 个相邻 zone 的邻居
路由策略 不越过目标尽量走远 贪心选坐标最近邻、直线逼近
查找时间 \(O(\log n)\) \(O(d\,n^{1/d})\)
每节点空间 \(O(\log n)\) \(O(d)\)

小结：Chord 用 \(O(\log n)\) 空间换 \(O(\log n)\) 时间；CAN 用很小的 \(O(d)\) 空间换较慢的 \(O(d\,n^{1/d})\) 时间。调大维度 \(d\) 可缩短路径，但邻居维护更复杂。

七、论文提到的其他 DHT　🚫 课上未讲，不考

论文是综述，还比较了多种结构化对称 DHT，老师未讲、不考，仅供了解 DHT 设计谱系：

  • 前缀/树形路由：Pastry、Tapestry、Kademlia——每个节点按 ID 前缀记录路由表（如知道前缀 0、1、00、01… 的某个节点），逐位匹配前进，期望 \(O(\log N)\) 跳。Kademlia 用 XOR 距离（单向且对称，故无需 leaf set / 稳定化）。
  • 其他：Viceroy、Chord 的 de Bruijn 变体（每节点仅记约两个邻居仍达 \(O(\log N)\)）、Freenet（非结构化对称、动态构建路由表）。
  • 论文讨论的设计维度（distance function、operation cost、fault tolerance、proximity routing）同样不考。

八、考点重点（务必掌握）

  • ⚠️ Chord finger table 构造：\(\text{finger}[j]=\text{successor}((i+2^{\,j-1})\bmod 2^m),\ j=1\dots m\)；会画出某节点全部 finger 边。
  • ⚠️ Chord lookup 路由：按「不越过目标尽量走远」走出路径，数出经过的 finger 边与跳数。
  • ✅ 复杂度：Chord 时间/空间均 \(O(\log n)\)（halving 论证）；CAN 时间 \(O(d\,n^{1/d})\)、空间 \(O(d)\)。
  • ✅ 概念：lookup problem 定义；DHT 比普通哈希表多 lookup(key)；一致性哈希环 + successor 规则（及「只移动 \(K/N\) 个 key」性质）；CAN 的 \(d\) 维 zone 与贪心路由。
  • 🚫 不考：P2P/overlay 简介、Napster/Gnutella、Chord 的 successor list / join / stabilization 细节、CAN 节点重分配、以及论文中 Pastry/Tapestry/Kademlia/Viceroy/Freenet 等其他系统。