BiTtorrent的DHT算法 --- Kademlia 协议原理简介(2)

图4：α＝1时的查询过程

整个路由查询过程是递归操作的，其过程可用数学公式表示为：

这个递归过程一直持续到Nl＝t，或者Nl的路由表中没有任何关于t 的信息，即查询 失败。

由于每次查询都能从更接近t的K桶中获取信息，这样的机制保证了每一次递归操作都能够至少获得距离减半（或距离减少1bit）的效果，从而保证整个查询过程的收敛速度为O(logN)，这里N为网络全部节点的数量。

当节点x要查询对时，和查找节点的操作类似，x选择k个ID值最接近key值的节点，执行FIND_VALUE操作，并对每一个返回的新节点重复执行FIND_VALUE操

作，直到某个节点返回value值。

一旦FIND_VALUE操作成功执行，则对数据会缓存在没有返回value值的最接近的节点上。这样下一次查询相同的key时就会更加快速的得到结果。通过这样的方式，热门对数据的缓存范围就逐步扩大，使系统具有极佳的响应速度，如图5所示。

图5：缓存原则

七、数据存放

存放对数据的过程为：

1、 发起者首先定位k个ID值最接近key的节点； 2、 发起者对这k个节点发起STORE操作

3、 执行STORE操作的k个节点每小时重发布自己所有的对数据。 4、 为了限制失效信息，所有对数据在初始发布24小时后过期。

另外，为了保证数据发布、搜寻的一致性，规定在任何时候，当节点w发现新节点u比w上的某些对数据更接近，则w把这些对数据复制到u上，但是并不会从w上删除。

八、节点加入和离开

如果节点u要想加入Kad网络，它必须要和一个已经在Kad网络的节点，比如w，取得联系。

u首先把w插入自己适当的K桶中，然后对自己的节点ID执行一次FIND_NODE操作，然后根据接收到的信息更新自己的K桶内容。通过对自己邻近节点由近及远的逐步查询，u完成了仍然是空的K桶信息的构建，同时也把自己的信息发布到其他节点的K桶中。 在Kad网络中，每个节点的路由表都表示为一颗二叉树，叶子节点为K桶，K桶存放的是有相同ID前缀的节点信息，而这个前缀就是该K桶在二叉树中的位置。这样，每个K桶都覆盖了ID空间的一部分，全部K桶的信息加起来就覆盖了整个160bit的ID空间，而且没有重叠。

以节点u为例，其路由表的生成过程为：

1． 最初，u的路由表为一个单个的K桶，覆盖了整个160bitID空间，如图6最上面的路由表；

2． 当学习到新的节点信息后，则u会尝试把新节点的信息，根据其前缀值插入到对应的K桶中：

① 如果该K桶没有满，则新节点直接插入到这个K桶中； ② 如果该K桶已经满了，

⑴ 如果该K桶覆盖范围包含了节点u的ID，则把该K桶分裂为两个大小相同的新K桶，并对原K桶内的节点信息按照新的K桶前缀值进行重新分配

⑵ 如果该K桶覆盖范围没有包节点u的ID，则直接丢弃该新节点信息

3． 上述过程不断重复，最终会形成表1结构的路由表。达到距离近的节点的信息多，距离远的节点的信息少的结果，保证了路由查询过程能快速收敛。

图6：节点000的路由表生成演化

在图7 中，演示了当覆盖范围包含自己ID 值的K 桶是如何逐步分裂的。

图7：节点0100的K桶分裂过程

当K桶010满了之后，由于其覆盖范围包含了节点0100的ID，故该K桶分裂为两个新的K桶：0101和0100，原K桶010的信息会根据其其前缀值重新分布到这两个新的K桶中。注意，这里并没有使用160bit的ID值表示法，只是为了方便原理的演示，实际Kad网络中的ID值都是160bit的。

节点离开Kad网络不需要发布任何信息，Kademlia协议的目标之一就是能够弹性工作在任意节点随时失效的情况下。为此，Kad要求每个节点必须周期性的发布全部自己存放的对数据，并把这些数据缓存在自己的k个最近邻居处，这样存放在失效节点的数据会很快被更新到其他新节点上。