Lec 18 P2P 与 Chord 查找协议

论文：Chord: A Scalable Peer-to-Peer Lookup Service for Internet Applications, SIGCOMM 2001. Ion Stoica, Robert Morris, David Karger, M. Frans Kaashoek, Hari Balakrishnan（MIT LCS）

1. 问题背景

P2P（Peer-to-Peer）系统是没有中心控制、没有层级结构的分布式系统，每个节点运行的软件在功能上是对等的。这类系统的特性很多（冗余存储、持久性、就近选择、匿名、搜索、认证、层级命名……），但其核心操作几乎都归结为一件事：

高效地定位存储了某个数据项的节点。

Chord 把这个核心问题抽象为一个极简的接口——只提供一个操作：给定一个键 $k$，Chord 将其映射到一个节点

即返回负责存储该键的节点的 IP 地址。具体存什么、怎么认证、怎么缓存、怎么复制，全部交给上层应用决定。

Chord 与其它 P2P 查找协议相比，有三个突出特点：简单性、可证明的正确性、可证明的性能。

其中 $N$ 是系统中的节点数。

与既有系统的对比：

• Napster 有中心目录（单点故障）；
• Gnutella 用广播查询（不可扩展）；
• DNS 依赖特殊的根服务器且命名结构受行政边界约束。
• Chord 没有特殊节点、键空间是扁平的、且在路由信息部分过期时性能也只是优雅降级而非崩溃——这是它能在频繁加入/离开的动态环境中工作的关键。

2. 系统模型与设计目标

Chord 以库的形式与应用链接，向应用暴露两件事：(1) lookup(key) 返回负责该键的节点 IP；(2) 当本节点负责的键集合发生变化时通知上层（以便迁移数据）。

它通过解决以下难题来简化 P2P 系统设计：

• 负载均衡（Load balance）：作为一个分布式哈希函数，把键均匀散布到各节点。
• 去中心化（Decentralization）：完全分布式，没有任何节点比其它节点更重要。
• 可扩展性（Scalability）：查找代价随节点数对数增长，无需任何参数调优。
• 可用性（Availability）：自动调整内部表以反映节点的加入与失效，即使系统持续变化也能找到负责键的节点。
• 灵活命名（Flexible naming）：键空间扁平，不对键的结构施加任何约束。

典型应用：协作镜像（Cooperative Mirroring）、分时存储（Time-Shared Storage）、分布式索引（支持类 Gnutella/Napster 的关键词搜索）、大规模组合搜索（如密码破解）。

3. 一致性哈希（Consistent Hashing）

Chord 的底层是 (consistent hashing / 一致性哈希) 的一个变体。

用基础哈希函数（如 (SHA-1)）给每个节点和键分配一个 $m$ 比特的标识符：

• 节点标识符 = $\text{hash}(\text{节点 IP})$
• 键标识符 = $\text{hash}(\text{key})$

所有标识符按模 $2^m$ 排列在一个标识符环（identifier circle）上。$m$ 要足够大，使两个节点或键碰撞的概率可忽略（实现中用 160 比特）。

键 $k$ 被分配给标识符等于或顺时针紧随 $k$ 的第一个节点，记为

关于 "with high probability"：论文用 (SHA-1) 作为确定性哈希，严格说 "高概率" 不再适用。但构造一组在 SHA-1 下碰撞的键相当于 "反演/解密" SHA-1，被认为是困难的。因此把结论表述为 "基于标准困难性假设成立"。

为何最终不用虚拟节点：所需虚拟节点数取决于系统规模 $N$，而 $N$ 难以预先确定。论文为简化表述放弃虚拟节点，代价是单节点负载以高概率至多超出均值 $O(\log N)$ 倍。

4. 可扩展的键定位（Scalable Key Location）

4.1 朴素方案的问题

只要每个节点知道自己的后继（successor），就能沿环传递查询直到命中——正确但低效，最坏需遍历全部 $N$ 个节点。为加速，Chord 引入额外路由信息：finger table。

关键设计哲学：finger table 是为了快，successor 指针是为了对。只要后继指针正确，查找的正确性就有保证；finger 过期只影响速度。

4.2 Finger Table

两个重要特征：

1. 每个节点只存储少量其它节点的信息，且对环上离自己近的节点了解更多，对远的了解少（finger 间距呈指数 $2^{i-1}$ 增长）。
2. 一个节点的 finger table 通常不足以直接确定任意键的后继。

// 找 id 的后继
n.find_successor(id):
    n' = find_predecessor(id)
    return n'.successor

// 找 id 的前驱（join 操作也会用到，故显式实现）
n.find_predecessor(id):
    n' = n
    while id ∉ (n', n'.successor]:
        n' = n'.closest_preceding_finger(id)
    return n'

// 返回 finger table 中最接近且先于 id 的节点
n.closest_preceding_finger(id):
    for i = m downto 1:
        if finger[i].node ∈ (n, id):
            return finger[i].node
    return n

直觉证明（距离减半论证）：设节点 $p$ 是 $id$ 的直接前驱，目标 $p$ 落在当前节点 $n$ 的第 $i$ 个 finger 区间内。该区间非空，故 $n$ 会 finger 到区间内某节点 $f$：

• $n$ 与 $f$ 的距离 $\ge 2^{\,i-1}$；
• 但 $f$ 与 $p$ 同在第 $i$ 个区间内，故二者距离 $\le 2^{\,i-1}$。

于是 $f$ 到 $p$ 的距离至多是 $n$ 到 $p$ 距离的一半。初始距离至多 $2^m$，故 $m$ 步内必到达。进一步在随机化假设下，$O(\log N)$ 次转发后剩余距离缩到 $2^m / N$，期望落入 1 个节点，再 $O(\log N)$ 步即命中。

实测路径长度 $\approx \frac{1}{2}\log_2 N$：把节点到查询的距离写成二进制，每个为 1 的比特需要跟一次 finger，为 0 则跳过。随机距离下期望约一半比特为 1，故平均跳数约为 $\frac{1}{2}\log_2 N$。

5. 节点加入（基础版本）

动态网络中，加入/离开必须保持"能定位每个键"的能力。Chord 维护两条不变式：

为支持加入/离开，每个节点额外维护一个 predecessor（前驱）指针，可逆时针绕环行走。

单节点 $n$ 加入时（已知一个现有节点 $n'$）需完成三项任务：

1. 初始化 $n$ 的 predecessor 和 finger table（向 $n'$ 查询）；
2. 更新现有节点的 finger 与 predecessor，使之反映 $n$ 的加入；
3. 通知上层软件，迁移 $n$ 现在负责的键。

// n 加入网络，n' 是网络中任意已知节点
n.join(n'):
    if (n'):
        init_finger_table(n')
        update_others()
        // 从后继处迁移 (predecessor, n] 区间的键
    else:                       // n 是网络中唯一节点
        for i = 1 to m: finger[i].node = n
        predecessor = n

初始化 finger table 的优化：朴素地对 $m$ 个 finger 各做一次 find_successor 需 $O(m\log N)$。利用"第 $i$ 个 finger 往往也是第 $i{+}1$ 个 finger"的性质，可把需要真正查找的 finger 数降到 $O(\log N)$，总时间 $O(\log^2 N)$。实践中还可直接向邻居要一份完整 finger table 作为提示。

6. 并发操作与失效（生产级机制）

基础版的"激进维护所有 finger"在大规模并发加入下难以维持。论文把正确性与性能目标分离：

• 用一个轻量的 stabilization（稳定化）协议专门保证 successor 指针最终正确 → 保证查找正确；
• 再用 successor 指针去校正 finger → 让查找又快又对。

6.1 Stabilization

n.join(n'):
    predecessor = nil
    successor = n'.find_successor(n)   // 此时还未让网络知道 n

// 每个节点周期性运行：验证后继，并告知后继自己的存在
n.stabilize():
    x = successor.predecessor
    if x ∈ (n, successor):
        successor = x
    successor.notify(n)

// n' 认为它可能是 n 的前驱
n.notify(n'):
    if predecessor is nil or n' ∈ (predecessor, n):
        predecessor = n'

// 周期性刷新随机一项 finger
n.fix_fingers():
    i = random index (>1) into finger[]
    finger[i].node = find_successor(finger[i].start)

6.2 失效与复制（Successor List）

节点失效的核心威胁是后继指针断裂（最坏情况下 find_predecessor 只靠后继也能推进）。解决办法：

successor-list 同时方便上层做数据复制：把某键的数据副本存在该键之后的 $k$ 个节点上；节点掌握 $r$ 个后继的来去，从而通知上层何时传播新副本。

7. 仿真与实验结果

迭代式 vs 递归式：迭代式由发起节点主导全部通信（仿真采用）；递归式由中间节点逐跳转发。递归式更利于"server selection"式的延迟优化。

8. 局限与未来工作

• 环分裂（partition）无专门修复机制：分裂后的子环对稳定化可能"看起来局部一致"。检测思路：节点周期性请别人 lookup 自己，若结果不是自己则可能有分裂；或让节点长期记忆一组随机遇到过的节点。
• 恶意/有 bug 的参与者可呈现错误的环视图。若数据本身经密码学认证，则这只威胁可用性而非真实性。要求节点 ID 由其 IP 的 SHA-1 派生，可增加"插入紧邻目标键的节点来劫持数据"这类攻击的难度。
• 降低跳数：把 finger 间距从 $2$ 的幂改为 $(1+1/d)$ 的整数次幂，可把跳数降到 $O(\log_{1+1/d} N)$，代价是 finger 数增加到约 $O(d\log N)$。
• 降低延迟：每个 finger 项指向区间内前 $k$ 个节点，测量网络时延后转发给最低延迟者（递归式更有效）。

9. 一句话总结

Chord 用一致性哈希 + 指数间距的 finger table + 稳定化协议，在完全去中心、节点频繁来去的环境中，以每节点 $O(\log N)$ 状态、每次查找 $O(\log N)$ 消息的代价，提供了一个"给键 → 找负责节点"的、可证明正确且性能可证明、并优雅降级的查找原语。

附：核心符号速查