Kademlia

https://web.archive.org/web/20051211011605/http://www.cs.rice.edu/Conferences/IPTPS02/109.pdf
https://github.com/bmuller/kademlia

◇拓扑结构——二叉树

在映射之前，先做一下预处理。

  1. 先把 key 以二进制形式表示。
  2. 把每一个 key 缩短为它的【最短唯一前缀】。 然后
  3. 先把 key 以二进制形式表示，然后从高位到低位依次处理。
  4. 二进制的第 n 个数位就对应了二叉树的第 n 层
  5. 如果该位是1，进入左子树，是0则进入右子树（这只是人为约定，反过来处理也可以）
  6. 全部数位都处理完后，这个 key 就对应了二叉树上的某个【叶子】

◇距离算法——异或（XOR）

DHT算法都是采用某种逻辑上的距离，在Kademlia则采用简单的异或计算来衡量两节点间的距离，它和地理上的距离没有任何关系，但却具备几何公式的绝大特征：
（1）节点和它本身之间的异或距离是0
（2）异或距离是对称的：即从A到B的异或距离与从B到A的异或距离是等同的
（3）异或距离符合三角形不等式：给定三个顶点A B C，假如AC之间的异或距离最大,那么AC之间的异或距离必小于或等于AB异或距离和BC异或距离之和.
（4）对于给定的一个距离，距离A只存在有唯一的一个节点B，也即单向性，在查找路径上也是单向的，这个和地理距离不同。

◇路由机制

对每一个节点，都可以【按照自己的视角】对整个二叉树进行拆分。
　拆分的规则是：先从根节点开始，把【不包含】自己的那个子树拆分出来；然后在剩下的子树再拆分不包含自己的下一层子树；以此类推，直到最后只剩下自己。
　Kad 默认的散列值空间是 m=160（散列值有 160 比特），因此拆分出来的子树【最多】有 160 个（考虑到实际的节点数【远远小于】2160，子树的个数会明显小于 160）。
　对于每一个节点而言，当它以自己的视角完成子树拆分后，会得到 n 个子树；对于每个子树，如果它都能知道里面的一个节点，那么它就可以利用这 n 个节点进行递归路由，从而到达整个二叉树的【任何一个】节点

K-桶（K-bucket）

前面说了，每个节点在完成子树拆分后，只需要知道每个子树里面的一个节点，就足以实现全遍历。但是考虑到健壮性（请始终牢记：分布式系统的节点是动态变化滴），光知道【一个】显然是不够滴，需要知道【多个】才比较保险。
所以 Kad 论文中给出了一个“K-桶（K-bucket）”的概念。也就是说：每个节点在完成子树拆分后，要记录每个子树里面的 K 个节点。这里所说的 K 值是一个【系统级】的常量。由使用 Kad 的软件系统自己设定（比如 BT 下载使用的 Kad 网络，K 设定为 8）。
K 桶其实就是【路由表】。对于某个节点而言，如果【以它自己为视角】拆分了 n 个子树，那么它就需要维护 n 个路由表，并且每个路由表的【上限】是 K。
说 K 只是一个【上限】，是因为有两种情况使得 K 桶的尺寸会小于 K。
1. 距离越近的子树就越小。如果整个子树【可能存在的】节点数小于 K，那么该子树的 K 桶尺寸永远也不可能达到 K。
2. 有些子树虽然实际上线的节点数超过 K，但是因为种种原因，没有收集到该子树足够多的节点，这也会使得该子树的 K 桶尺寸小于 K。

K-桶（K-bucket）的刷新机制

刷新机制大致有如下几种：

  1. 主动收集节点
    　　任何节点都可以主动发起“查询节点”的请求（对应于协议类型 FIND_NODE），从而刷新 K 桶中的节点信息（下面聊“节点的加入”时，会提及这种）

  2. 被动收集节点
    　　如果收到其它节点发来的请求（协议类型 FIND_NODE 或 FIND_VALUE），会把对方的 ID 加入自己的某个 K 桶中。

  3. 探测失效节点
    　　Kad 还是支持一种探测机制（协议类型 PING），可以判断某个 ID 的节点是否在线。因此就可以定期探测路由表中的每一个节点，然后把下线的节点从路由表中干掉。
    　　“并发请求”与“α 参数”
    　　“K桶”的这个设计思路【天生支持并发】。因为【同一个】“K桶”中的每个节点都是平等的，没有哪个更特殊；而且对【同一个】“K桶”中的节点发起请求，互相之间没有影响（无耦合）。
    　　所以 Kad 协议还引入了一个“α 参数”，默认设置为 3，使用 Kad 的软件可以在具体使用场景中调整这个 α 因子。
    　　当需要路由到某个“子树”，会从该子树对应的“K桶”中挑选【α 个节点】，然后对这几个节点【同时】发出请求。

◇节点的加入
  1. 任何一个新来的节点（假设叫 A），需要先跟 DHT 中已有的任一节点（假设叫 B）建立连接。
  2. A 随机生成一个散列值作为自己的 ID（对于足够大的散列值空间，ID 相同的概率忽略不计）
  3. A 向 B 发起一个查询请求（协议类型 FIND_NODE），请求的 ID 是自己（通俗地说，就是查询自己）
  4. B 收到该请求之后，（如前面所说）会先把 A 的 ID 加入自己的某个 K 桶中。然后，根据 FIND_NODE 协议的约定，B 会找到【K个】最接近 A 的节点，并返回给 A。（B 怎么知道哪些节点接近 A 捏？这时候，【用 XOR 表示距离】的算法就发挥作用啦）
  5. A 收到这 K 个节点的 ID 之后，（仅仅根据这批 ID 的值）就可以开始初始化自己的 K 桶。
  6. 然后 A 会继续向刚刚拿到的这批节点发送查询请求（协议类型 FIND_NODE），如此往复（递归），直至 A 建立了足够详细的路由表。

◇节点的退出

　　与 Chord 不同，Kad 对于节点退出没有额外的要求（没有“主动退出”的说法）。
　　所以，Kad 的节点想离开 DHT 网络不需要任何操作（套用徐志摩的名言：悄悄的我走了，正如我悄悄的来）

保存数据

（以下只是大致原理，具体的协议实现可能会有差异）

  1. 当某个节点得到了新加入的数据（K/V），它会先计算自己与新数据的 key 之间的“距离”；然后再计算它所知道的其它节点与这个 key 的距离。
  2. 如果计算下来，自己与 key 的距离最小，那么这个数据就保持在自己这里。
  3. 否则的话，把这个数据转发给距离最小的节点。
  4. 收到数据的另一个节点，也采用上述过程进行处理（递归处理）。

获取数据

（以下只是大致原理，具体的协议实现可能会有差异）

  1. 当某个节点接收到查询数据的请求（key），它会先计算自己与 key 之间的“距离”；然后再计算它所知道的其它节点与这个 key 的距离。
  2. 如果计算下来，自己与 key 的距离最小，那么就在自己这里找有没有 key 对应的 value。有的话就返回 value，没有的话就报错。
  3. 否则的话，把这个数据转发给距离最小的节点。
  4. 收到数据的另一个节点，也采用上述过程进行处理（递归处理）。