1. 介绍
P2P System（对等系统）：节点关系平等，可用于存储冗余、数据持久、临近节点选取、匿名、搜索、认证、层次名称管理，核心操作是寻找特定数据的节点位置。
Chord：基于对等应用的分布式查找协议
- 仅支持的操作：给定一个key，将它映射到节点
- 基于一致性散列，在节点加入/离开时，改动很小
- 集群有$N$个节点，每个节点只需维护$O(logN)$的路由消息，节点加入/离开时的信息交互不超过$O(log^2N)$
- 协议简单（路由只需经过$O(logN)$个节点），正确性和性能都可证明
2. 系统模型
Chord解决以下问题：
- 负载均衡：Chord的一致性散列可直接实现
- 去中心化：Chord是完全分布式的，提高了健壮性，并让P2P应用更松散
- 可扩展性：Chord查询的时间根据节点数量增长，不需调整参数
- 可用性：当节点加入/离开时，Chord内部表会自动调整，每个key总能找到对应的节点
- 灵活命名：Chord的key是flat的，提供了灵活性
使用Chord：通过库链接到客户端和服务端，提供lookup(key)以返回节点地址，并通知上层应用key位置的变化
Chord可提供的基础功能：
- 合作镜像：类似SVN，可用于版本控制
- 时间共享存储：将数据存在别的服务器，以提高可用性
- 分布式索引
- 大型组合搜索：加密密钥，进行key到节点的映射
一个基于Chord的分布式存储架构如下：FS提供灵活命名，Block store提供存储，Chord提供路由查询
3. 基本的Chord协议
3.1. 概述
协议基于一致性散列，实现负载均衡，节点加入/离开时，只需移动$O(1/N)$的数据。
为提高扩展性，节点不需知道所有节点的路由信息，只需要$O(logN)$节点信息，查询也只需要经过$O(logN)$的节点。而路由信息更新只需要传输$O(log^2N)$条信息。
而Chord算法协议的核心就是一致性散列。
3.2. 一致性散列
使用基本的散列函数（如SHA-1），将节点和key散列成一个$m$位长的标识符，$m$必须足够大（冲突概率足够小），整个散列空间也为$m$位，组成一个$0 \sim 2^{m}-1$的环。
具体散列和路由规则略。（因为很熟悉了）
论文中略去了虚拟节点。一般情况下，对于每个IPv4地址一个节点，32个虚拟节点是适合的。
定理1：$N$个节点和$K$个key，高概率下：
- 每个节点接管最多$(1+\epsilon)K/N$个key
- 当节点加入/离开，$O(K/N)$个键需要被其它节点接管
3.3. 可扩展的key位置
协议中，每个节点只需要知道它在环上的后继节点。通过不停地路由到后继节点，即可找到正确的节点位置。此外Chord维护了额外信息加速路由。
假定：
- $m$为散列空间的位数
- 每个节点$n$维护$m$个后继节点（简称finger table）
则定义有finger table，记录后继节点：
- 表中的第$i$项（$n.finger[i]$）为：
- $start$：即$(n+2^{i-1}) \% 2^m$
- $interval$：即区间$[n.finger[i].start, n.finger[i+1].start)$
- $node$：比节点$n$大$2^{i-1}$的第一个后继节点，记为$s$。即$s=successor(n.finger[i].start)$ ($1\le i \le m$)
根据某个标识符$id$（散列值）查找后继者的伪码如下所示，基本思路是：
- 先找$id$的最近前驱节点$n’$
- 然后找到该节点$n’$的最近后继节点
对于远程调用和远程引用，使用RPC；对于本地调用和本地引用，直接本地执行
定理2：大概率下，在$N$节点的集群，找到某个$id$的后继节点，需要和$O(logN)$个节点进行通信。
3.4. 节点加入
Chord需要保证每个key都能被定位，因此需要维护2个不变量：
- 每个节点维护的后继者都是正确的
- 对于每个key $k$，节点$successor(k)$负责$k$
最好，finger table也保证正确，以加快查找
定理3：大概率下，在$N$节点的集群，单节点的加入或离开需要传输$O(log^2 N)$条消息，以重建路由不变量和finger table
为维护不变量，每个节点维护一个前驱指针（可反向遍历节点），当节点$n$加入时，并执行3个任务：
- 初始化节点$n$的前驱指针和finger table
- 更新已存在节点的finger table和前驱指针，反映节点$n$的加入
- 通知上层应用将数据迁移到新节点
3.4.1. 初始前驱和fingers
在$n.init _ finger _ table(n’)$中实现。
最初实现可通过$m$个RPC填充所有的fingers，复杂度为$O(mlogN)$。
不过可以检查第$i$项是否也是第$i+1$项（可检查$finger[i].interval$是否不含有节点，若不含，则成立）以减少RPC次数，从而降低到$O(log^2 N)$。
不过，实际优化中，新节点可直接查询最近的节点，获取整个finger table和前驱节点信息，从而降低时间复杂度为$O(logN)$
3.4.2. 更新已存在节点的fingers
在$n.update _ others()$实现，将$n$插入到其它节点的fingers中。
$n$成为节点$p$的finger第$i$项，需要满足：
- $p$需要在$n$之前，且差距至少为$2^{i-1}$
- $p$的原有finger第$i$项在$n$之后
伪码中，可以看出，它是一个沿时钟反向的递归流程。
实现可以达到：
- 需要修改$O(logN)$个节点的finger table
- 整个更新时间复杂度为$O(log^2 N)$（可优化到$O(logN)$）
3.4.3. 迁移key
即通知上层应用迁移数据，具体实现需要看上层。
4. 并发操作和失效
4.1. 稳定协议
稳定协议：保证节点的后继节点指针（即$node.successor$）是最新的，用于验证和修正finger table。
当并发节点加入/离开时，可能出现下面3种情形：
- 当前的finger table依旧正确（查找依旧正常，为$O(logN)$）
- 当前后继者指针是正确的，finger table不准确（查询可以正确，但较慢）
- 两者都不正确（查询会失败，可通知上层等待重试）
下述伪码可以替代第3节的伪码，用于支持并发的操作：
- 节点加入时，调用$n.join(n’)$，只会获取后继指针
- 周期性调用$n.stablelize()$，验证后继者是否正确，并告知新的后继者，调用$n.notify(succ)$以更新前驱指针
- 周期性调用$n.fix _ finger()$以更新自己的finger table，每次更新一项（随机指定），最终能完全更新完毕
实质上，只要有正确的后继指针，则就可以查找成功（前驱和后继都可以），finger table只是加速查询罢了
定理4：一旦节点能处理某个查询，未来，对于该查询则都能处理。
定理5：最后的节点加入后，一段时间内，所有节点的后继指针都会是正确的。
定理6：已有一个稳定的$N$节点的集群，当另有$N$个节点加入集群且fingers为空（但有正确的后继指针），那么大概率下，查询依旧能保证在$O(logN)$下完成。
推论：只要调整fingers的时间小于网络扩大一倍的时间，也能保证$O(logN)$的查询
4.2. 错误和复制
当节点$n$失效，则其它包含$n$的finger table对应的节点需要找到$n$的后继者；此外，失效不能扰乱处理中的查询，尽管系统在重新稳定化。
恢复的关键：保持正确的后继指针。
实现：
- 维护“后继者列表”（successor-list），包含自己在环上最接近的$r$个继承者（在$n.stablize()$中维护）
- 若节点发现后继者指针不正确（即节点可能失效了），则选择列表中的第一项作为后继者
- 稳定化后一段时间，finger table会被修正
节点失效，并在稳定化之前，其它节点依旧可以向失效节点发送请求，作为查找后继节点（$find _ successor()$）的一部分。这种情况下，需要在节点失效后，选取另一条路由路径，这就要一个备用节点列表：
- 可在finger table中查找备用节点
- 若失效节点在finger table中处于较小索引位置，也可用”后继者列表”选出备用节点
定理7：若后继者列表长度$r=O(logN)$，集群有$N$个节点且初始稳定，每个节点失效的可能性为$O(1/2)$，则大概率下，$find_ successor()$会返回最接近的活跃后继者。
定理8：若后继者列表长度$r=O(logN)$，集群有$N$个节点且初始稳定，每个节点失效的可能性为$O(1/2)$，则大概率下，$find _ successor()$在失效发生下的时间复杂度为$O(log N)$
