KAD(Kademlia)算法介绍

概述

在去中心化底层网络中大部分使用P2P网络，特别是运用于区块链技术中。通常为了维护整个网络会用到分布式哈希表DHT（Distributed Hash Table），而Kademlia协议是其中一种DHT技术。

Kademlia协议（简称Kad）是美国纽约大学的PetarP Maymounkov和David Mazieres. 在2002年发布的一项研究结果《Kademlia: A peerto -peer information system based on the XOR metric》。 Kad 通过独特的以异或算法（XOR）为距离度量基础，建立了一种 全新的 DHT 拓扑结构，相比于其他算法，大大提高了路由查询速度。

两个Go语言实现的Kademlia库 go-libp2p-kad-dht go-libp2p-kbucket

Kademlia介绍

节点状态表示

在 Kad 网络中，所有节点都被当作一颗二叉树的叶子，并且每一个节点的位置都由其 ID 值的最短前缀唯一的确定，每个节点都有一个160bit的ID值作为标志符。 整个网络节点状态可以使用二叉树表示。

规则如下：

ID值以二进制形式表示；二进制的第 n 个 bit 就对应了二叉树的第 n 层；如果该位是 1，进入左子树，是 0 则进入右子树；最后二叉树上的叶子节点对应某个节点。
每个节点是160位的二进制表示，所以最多有160层，而实际并没有这么多层，因为采用最短唯一前缀，所以叶子节点会在任意层数出现。如下所示：

拆分二叉树

对于任意一个节点，都可以把这颗二叉树分解为一系列连续的，不包含自己的子树。最高层的子树，由整颗树不包含自己的树的另一半组成；下一层子树由剩下部分不包含自己的一半组成；依此类推，直到分割完整颗树。如上图所示：

虚线包含的部分就是节点0011的各子树，从每个分叉点拆分出不属于自己的那部分的整个子树。

对于每一个节点而言，当它以自己的视角完成子树拆分后，会得到 n 个子树；对于每个子树，如果它都能知道里面的一个节点，那么它就可以利用这 n 个节点进行递归路由，从而到达整个二叉树的任何一个节点 。拆分二叉树也是为下面讲到的K桶作准备。

节点查询步骤

下图中，节点 0011 通过连续查询来找到节点 1110 的例子。只有第一步查询时的节点101是已知的，其他节点都是逐步反馈得到的。

节点距离

Kad算法采用异或操作来计算节点之间的距离。通过异或操作，我们可以得到该距离算法有一下特点：

(A ⊕ B) == (B ⊕ A)：对称性，A到B的距离和B到A的距离是相等的。
(A ⊕ A) == 0：节点自身与自身的距离是0。
(A ⊕ B) > 0 ：任意两个节点之间的距离一定大于0。
(A ⊕ B) + (B ⊕ C) >= (A ⊕ C)：三角不等，A经过B到C的距离总是大于等于A直接到C的距离
这里所说的距离是逻辑上的距离，与地理位置无关，所以有可能两个节点之间计算得到的逻辑距离很近，但实际上地理上的距离却很远。

查询加速
Kademlia使用异或(^)来定义距离。两个节点ID的异或（或者节点ID和关键字的异或）的结果就是两者之间的距离。
对于每一个二进制位来说，如果相同，异或返回0，否则，异或返回1。异或距离满足三角形不等式：任何一边的距离小于（或等于）其它两边距离之和。

异或距离使得Kademlia的路由表可以建在单个bit之上，即可使用位组（多个位联合）来构建路由表。
位组可以用来表示相应的K桶，它有个专业术语叫做前缀，对一个m位的前缀来说，可对应2^m-1个K桶。
（m位的前缀本来可以对应2^m个K桶）另外的那个K桶可以进一步扩展为包含该节点本身ID的路由树。
一个b位的前缀可以把查询的最大次数从logn减少到logn/b。
这只是查询次数的最大值，因为自己K桶可能比前缀有更多的位与目标键相同，(这会增加在自己K桶中找到节点的机会，假设前缀有m位，很可能查询一个节点就能匹配2m甚至更多的位组)，所以其实平均的查询次数要少的多。
节点可以在他们的路由表中使用混合前缀，就像eMule中的Kad网络。
如果以增加查询的复杂性为代价，Kademlia网络在路由表的具体实现上甚至可以是有异构的。

K桶机制

每个节点在完成子树拆分后，要记录每个子树里面的 K 个节点。这里所说的 K 值是一个系统级的常量(必须是偶数)。
由使用 Kad 的软件系统自己设定（比如BT下载使用的 Kad 网络，K 设定为 8）。
K-桶其实就是路由表。对于某个节点而言，如果以它自己为视角拆分了 n 个子树，那么它就需要维护 n 个路由表，并且每个路由表的节点上限是 K。

对每一个 0≦i≦160，每个节点都保存有一些和自己距离范围在区间[2^i~2^(i+1))内的一些 节点信息，这些信息由一些(IP address,UDP port,Node ID)数据列表构成。
每一个这样的列表都称之为一个 K 桶 ，每个桶都有不超过 k 个的数据项。如下所示：

在go-libp2p-kbucket代码中，K桶的数据结构定义如下：

type bucket struct {
list *list.List
}

func newBucket() *bucket {
b := new(bucket)

b.list = list.New()
return b
}

K桶更新机制

K桶更新方式主要有以下几种：

• 主动收集节点：任何节点都可以发起FIND_NODE（查询节点）的请求，从而刷新K-桶中的节点信息。
• 被动收集节点：当收到其他节点发送过来的请求（如：FIND_NODE、FIND_VALUE），会把对方的节点ID加入到某个K-桶中。
• 检测失效节点：通过发起PING请求，判断K-桶中某个节点是否在线，然后清理K-桶中哪些下线的节点。

被动更新举例
当节点 x 收到一个 PRC 消息时，发送者 y 的 IP 地址就被用来更新对应的 K 桶，具体步 骤如下：

1. 计算自己和发送者的距离：d(x,y) = x⊕y，注意：x 和 y 是 ID 值，不是 IP 地址。

2. 通过距离 d 选择对应的 K 桶进行更新操作。

3. 如果 y 的 IP 地址已经存在于这个 K 桶中，则把对应项移到该 K 桶的尾部。

4. 如果 y 的 IP 地址没有记录在该 K 桶中 ：

   1. 如果该 K 桶的记录项小于 k 个，则直接把 y 的(IP address,UDP port,Node ID) 信息插入队列尾部
   2. 果该K桶的记录项大于k个，则选择头部的记录项（假如是节点z）进行RPC_PING操作 ：
      1. 如果 z 没有响应，则从 K 桶中移除 z 的信息，并把 y 的信息插入队列尾部。
      2. 如果 z 有响应，则把 z 的信息移到队列尾部，同时忽略 y 的信息。

从上面可看到，更新原则是将最新的节点插入到队列尾部，并不会剔除掉在队列中的已在线的节点。

用户在线时长与继续在线的概率关系，如下图所示：

根据K桶更新原则，在线时间长的节点具有较高的可能性继续保留在K桶列表中，因此：

通过把在线时间长的节点留在 K 桶里，Kad 就明显增加 K 桶中的节点在下一时间 段仍然在线的概率，
这对应 Kad 网络的稳定性和减少网络维护成本（不需要频繁构建节点的 路由表）带来很大好处，同时能在一定程度上防御 DOS 攻击，
因为只有当老节点失效后，Kad 才会更新 K 桶的信息，这就避免了通过新节点的加入来泛洪路由信息。

协议操作类型

Kademlia 协议包括四种远程 RPC 操作：PING、STORE、FIND_NODE、FIND_VALUE。

• PING 操作的作用是探测一个节点，用以判断其是否仍然在线。
• STORE 操作的作用是通知一个节点存储一个<key,value>对，以便以后查询需要。
• FIND_NODE 操作使用一个 160bit 的 ID 作为参数。
  本操作的接受者返回它所知道的更 接近目标 ID 的 K 个节点的(IP address,UDP port,Node ID)信息。
  这些节点的信息可以是从一个单独的 K 桶获得，也可以从多个 K 桶获得（如果最接近目 标 ID 的 K 桶未满）。
  不管是哪种情况，接受者都将返回 K 个节点的信息给操作发起者。
  如果接受者所有 K 桶的节点信息加起来也没有 K 个，则它会返回全部节点的信息给发起者。
• FIND_VALUE 操作和 FIND_NODE 操作类似，不同的是它只需要返回一个节点的(IP address,UDP port,Node ID)信息。
  如果本操作的接受者收到同一个 key 的 STORE 操作，则 会直接返回存储的 value 值。

路由查找机制

Kad能够快速地进行节点查找，当进行节点查找时，此时并不知道查询的节点是否存在。例如，节点x需要查找节点t。

Kad 按照如下递归操作步骤进行路由查找：

1. 计算到 t 的距离：d(x,t) = x⊕t

2. 从 x 的第[㏒ d]个 K 桶中取出 α 个节点的信息（[]是向上取整），同时进行FIND_NODE操作。
   如果这个 K 桶中的信息少于 α 个，则从附近多个桶中选择距离最接近 d 的总共 α 个节点。

3. 对接受到查询操作的每个节点，如果发现自己就是 t，则回答自己是最接近 t 的；
   否则测量自己和 t 的距离，并从自己对应的 K 桶中选择 α 个节点的信息给 x。

4. x对新接受到的每个节点都再次执行 FIND_NODE 操作，此过程不断重复执行，直到每一个分支都有节点响应自己是最接近 t 的。

5. 通过上述查找操作，x 得到了 k 个最接近 t 的节点信息。

注意：这里用“最接近”这个说法，是因为 ID 值为 t 的节点不一定存在网络中，也就是说 t 没有分配给任何一台电脑。

这里 α 也是为系统优化而设立的一个参数，就像 K 一样。在 BitTorrent 实现中，取值为 α＝3。

查询过程如下所示：

由于每次查询都能从更接近 t 的 K 桶中获取信息，这样的机制保证了每一次递归操作都能够至少获得距离减半，因此时间复杂度为：O(logN)。

节点加入

节点加入通常需要种子节点来引导加入，下面w就是种子节点。
如果节点 u 要想加入 Kad 网络，它必须要和一个已经在 Kad 网络的节点(比如 w)取得联系。
u 首先把 w 插入自己适当的 K 桶中，然后对自己的节点 ID 执行一次 FIND_NODE 操作，然后根据接收到的信息更新自己的 K 桶内容。
通过对自己邻近节点由近及远的逐步查询，u 完成了空的 K 桶信息的构建，同时也把自己的信息发布到其他节点的 K 桶中。

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

1. u 的路由表为一个单个的 K 桶，覆盖了整个 160bit ID空间，下图中最上面的路由表；

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

   1. 如果该 K 桶没有满，则新节点直接插入到这个 K 桶中；

   2. 如果该 K 桶已经满了：

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

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

3. 上述过程不断重复，最终会形成如下结构的路由表。达到距离近的节点的信息多，

距离远的节点的信息少的结果，保证了路由查询过程能快速收敛。

节点离开

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

引用

维基百科Kademlia
知乎Kademlia协议详解
《Kademlia: A peerto -peer information system based on the XOR metric》