绪论
chord 系统只提供查询服务：给定一个 key，把它映射到一个节点上，这个节点可以保存这个 key 对应的 value。任意节点查询这个 key 时，如果之前保存对应的 value 的节点没有下线，则都能取回。
在 chord 里面的每一个节点都会分配一个唯一标识 ID，这样 ID 按顺序就组成了一个环形。同样对于需要保存的信息，比如文件，每个文件也会分配一个唯一 Key ID。Key 为 k 的文件应该由标识同样是 k 或者第一个 ID 大于 k 的节点保存，这个节点记为 successor(k)。关键是这个系统内的任一个节点，向系统提交文件时，chord 怎么保证文件存到它应去的节点？获取文件时，chord 怎么从查到文件在哪个节点并取回来？
性能
在性能方面，稳定状态的 N 个节点的 chord 系统，每个节点只维护 \(O\lparen \log{N} \rparen \) 个其它节点的信息，查询只需要 \(O\lparen \log{N} \rparen \) 次通信，每次节点加入或退出时不会造成超过 \(O\lparen {\lparen \log{N} \rparen}^2 \rparen \) 次通信。
chord 作为一致性哈希，满足下面两条：
定理 1.1：对于任何 N 个节点和 K 个 key，有很高的概率每个节点只负责 \(\lparen 1+\epsilon \rparen \dfrac{K}{N} \) 个 key，其中 \(\epsilon\) 界限为 \(O\lparen \log{N} \rparen \)，可以增加 \(O\lparen \log{N} \rparen\) 个虚拟节点来让 \(\epsilon\) 任意小。也就是负载均衡。
定理 1.2：当第 N+1 个节点加入或离开时，很高的概率只有 \(O\lparen \dfrac{K}{N} \rparen\) 个 key 要重新映射到其它节点。
Finger 表
每个节点内部需要保存一张 finger 表，提供和其它节点通信时需要的路由信息。本质上 finger 表让节点对附近的节点知道得较详细，对越远的节点了解得越少。假如节点 ID 为 n，ID 标识的二进制位数为 m，则 finger 表最多包含 m 行。对于每行记录的内容则是 ID 为 \(n + 2^{i-1}\) 时它所映射到的节点 \(successor\lparen n+2^{i-1} \rparen \)，其中 \(1 \leqslant i \leqslant m \)。表的第一行实际就是节点 n 的下一个节点（后继节点）。
所以 finger 存的数据类型为 Vec<Node>。将 \(successor\lparen n+2^{i-1} \rparen \) 记为 n.finger[i].node，n.finger[i].start 就是 \(\lparen n+2^{i-1} \rparen \mod 2^m, 1 \leqslant i \leqslant m\)。
算法
注意接下来的伪代码部分，如果有调用其它节点的函数，那就相当于 RPC 或者发送请求消息。另外注意上面描述 finger 说它的行号是从 1 开始，但在下面的代码里面第 1 行在数组里面的索引是 0。
查找
定理 2：在 N 个节点的网络中，找到一个
successor(x)需要联系 \(O\lparen \log{N} \rparen\) 个节点。
/// 查找 Key 为 id 的内容应该保存在哪个节点里面，实际就是这个 id 的前继节点的后继节点
fn find_successor(&Node, id) -> Node {
let n = self.find_predecessor(id);
n.successor
}
/// 找到 id 的前继节点（标识比 id 要大但又最近 id 的节点），这样 id 就属于 『这个节点，它的下一个节点』 之间
fn find_predecessor(&Node, id) -> Node {
let mut n = self.clone();
// 一步步找到靠近 id 节点作为 id 的前继
while id not isin n.id ..= n.sucessor.id {
n = n.cloest_preceeding_in_finger(id);
}
n
}
/// 从自己的 finger 表的节点中，到 id 的前继
fn cloest_proceeding_in_finger(&Node, id) -> Node {
// 倒查 finger 表，从远往近搜索
for i in (m-1)..0 {
if self.finger[i].node.id isin (self.id, id) {
return self.finger[i].node;
}
}
return self.clone();
}
节点加入或离开
节点有加入或离开时，只要下面 2 条规则不变就总能找到 key 对应的节点：
-
每个节点的后继节点被正确维护（保持环形）。
-
节点
successor(k)就是负责 key 为 k 的点。
定理 3；任何节点加入或离开 N 个节点的网络，很高概率要通讯 \(O \lparen {\lparen \log{N} \rparen }^2 \rparen \) 次来重新建立 finger 表。
为了简化加入和离开的处理，每个节点要维护一个 predecessor，也就是每个节点拥有自己前继节点的联系方式。
新节点加入
新节点为 n，它的 ID 为 I，且已知节点 X 为 bootstrap（这是个特殊的、所有节点都能和它联系的节点，所有节点都通过它加入到网络中）。
- 初始化 finger 表和 predecessor
最简单的方法是通过 X 执行 1 次 find_predecessor 和对 finger 中的 m 行分别执行 find_successor。
有两种方式能加快这一过程。
-
可以判断
finger[i].node是否还是finger[i+1].node来加快（判断finger[i].node这个节点的 ID 是否大于等于 \(I + 2^{i+1-1}\)）。 -
作为实现上的优化，n 通过 X 得到它的 successor 后，可以复制它的 successor 的 finger 表，然后通过这张表再去执行
find_successor。
-
更新已有节点的 finger 表
-
检查 n 的后继节点，看是否存在一些 key 对应的数据要转移给这个新加入的节点 n。
/// 新节点加入，bootstrap 可以是任意一个可以通讯的节点
fn join(&mut Node, bootstrap: Option<Node>) {
if bootstrap.is_some() {
self.init_finger_talbe(bootstrap.unwrap());
self.update_others();
} else {
// 自己是第一个节点时，自己就是 bootstrap
for i in 0..m {
self.finger[i].node = self.clone();
}
self.predessor = self.clone();
}
}
/// 初始化 finger 表
fn init_finger_talbe(&mut Node, bootstrap: Node) {
self.finger[0].node = bootstrap.find_sucessor(self.finger[0].start);
self.successor = self.finger[0].node.clone();
// 注意这两行，更新原有的前后两个节点的数据，使新节点加入后仍然是一个环
self.predecessor = self.successor.predecessor.clone();
self.successor.prdecessor = self.clone();
for i in 1..(m-1) {
// 注意区间开闭
if self.finger[i].start isin self.id=..self.finger[i-1].node.id {
self.finger[i].node = self.finger[i-1].node;
} else {
self.finger[i].node = bootstrap.find_successor(self.finger[i].start);
}
}
}
// 更新其它节点的 finger 表
fn update_others(&Node) {
for i in 0..(m-1) {
// 逆时针找到最近的节点 p，看 p 的 finger 表中的第 i 项是否就是新加入的这个 self 节点
// 所以是减去一段距离
let mut p = self.find_predecessor(n-2^i);
p.update_finger_table(self, i);
}
}
/// 检查是否需要将自己的 finger 表中的第 i 项改为节点 s
fn update_finger_table(&mut Node, s: Node, i: usize) {
if s isin self.id=..self.finger[i].node.id {
self.finger[i].node = s;
let p = self.predessor;
// 自己的前继节点是否也需要更改
p.update_finger_talbe(s, i);
}
}
稳定化
上面这种节点加入算法只是在单个节点加入时的情况。多个节点加入时，如果又都插入到 2 个节点之间（也就是插入到原有环的相邻的 2 个节点之间）时，由于修改已有 2 个点的前继和后继顺序可能错乱，导致这个环在这里是断开的。这样在这个区间的查询可能会得不到结果，上层应用需要隔一段时间后重试。
解决多个节点同时加入的办法是每个节点周期性地去平稳网络。
fn join(&mut Node, bootstrap: Node) {
self.predecessor = None;
self.successor = bootstrap.find_sucessor(self.id);
}
/// 每个节点都周期性执行，校正自己的后继节点，并通知它让它的前继指向自己
fn stablize(&mut node) {
let x = self.sucessor.predecessor.clone();
if x is in self.id .. self self.sucessor.id {
self.successor = x;
}
self.successor.notify(self.clone());
}
/// notifier 发来通知，认为它是 self 节点的前继
fn notify(&mut Node, notifier: Node) {
if self.predecessor == None || notifier.id isin self.predecessor.unwrap().id .. self.id {
self.predecessor = Some(notifier);
}
}
/// 每个节点周期性执行，校正 finger 表
fn fix_fingers(&mut Node) {
// 可以等于 1
let i = random(1, m);
self.finger[i].node = self.find_successor(self.finger[i].start);
}
节点离开
为了防止节点突然断开，导致节点找不到它原来后继的后继，就不能成环了。所以需要每个节点在 stablize 操作中维护一个 successor_list 数组（知道它后面的连续多个后继），长度为 \(O\lparen \log{N} \rparen\)。另外在最开始提到，key 为 k 的文件应该由标识同样是 k 或者 k 之后的第一个节点保存，这时候如果这个节点下线，就再也取不回这个文件了，所以可以通过某些确定性的方式，让多个节点来保存副本。可以是让原本负责的节点加上它后面连续多个后继节点来保存，也可以对 k 再做几次哈希（假如是用哈希算法来决定 k 的话），让这个文件同时有多个 key。
后续
之后打算基于 Rust 的 Actor 框架 riker 来实现 chord，完成后会再写一篇关于实现的博客。