1、简介

Kademlia 是分布式散列表（DHT，Distributed Hash Table）的一种，类似的还有 Chord，Pastry 等。DHT 技术是去中心化 P2P 网络中最核心的一种路由寻址技术，可以在无中心服务器（trackerless）的情况下，在网络中快速找到目标节点。现在随着区块链技术的火热，这个 P2P 网络的底层技术也被越来越多的人了解。

这篇文章主要介绍 Kademlia 技术原理，以及其在 IPFS，以太坊等项目中的实现。

先从直观上来看一下 P2P 网络中节点之间连接的方式

图（1）是早的 BtTorrent 网络，需要一个中心服务器也就是种子服务器，来帮助各个 Peers 节点找到彼此进行文件下载。

图（2） 是实现了 Kademlia 协议的 P2P 网络，每个节点维护一个路由表，仅记录离自己最近的一些节点信息，通过迭代查找，来连接网络中其他的节点。

2、背景知识

网上有太多关于 Kademlia 协议原理的文章，我就不详细介绍了，这里我只列出 Kademlia 中最关键的几个部分：

• Node ID 在 P2P 网络中， 节点是通过唯一 ID 来进行标识的，在原始的 Kad 算法中，使用 160-bit 哈希空间来作为 Node ID。

• Node Distance 每个节点保存着自己附近（nearest）节点的信息，但是在 Kademlia 中，这个距离不是指物理距离，而是指一种逻辑距离，通过运算得知。

• XOR 异或运算 XOR 是一种位运算，用于计算两个节点之间距离的远近。把两个节点的 Node ID 进行 XOR 运算，XOR 的结果越小，表示距离越近。

• K-Bucket 用一个 Bucket 来保存与当前节点距离在某个范围内的所有节点列表，比如 bucket0, bucket1, bucket2 ... bucketN 分别记录[1, 2), [2, 4), [4, 8), ... [2^i, 2^(i+1)) 范围内的节点列表

• Bucket 分裂 如果初始 bucket 数量不够，则需要分裂（具体跟实现有关）

• Routing Table 记录所有 buckets，每个 bucket 限制最多保存 k 个节点，如下图：

• Update 在节点 bootstrap 过程中，需要把连接上的 peer 节点更新到自己的 Routing table 中对应的 bucket 中

• LookUp 查找目标节点，找到与目标节点最近（nearest/closest）的 bucket，如果已在 bucket 中，则直接返回，否则向该 bucket 中的节点发送查询请求，这些节点继续迭代查找

• 收敛 & 时间复杂度 查找会最终收敛至目标节点，整个查询过程复杂度是 Log N

下面详细介绍每个部分：

1、Node ID

Kademlia 中使用 SHA1 哈希来计算 Node ID，SHA1 是一个 160 bit 的哈希空间，整个 ID 长度是 160 个位， 也就是 20 个字节。

IPFS 中都使用 SHA256 来计算 Node ID，ID 长度是 256 位的哈希空间， 也即 32 个字节。

Ethereum 使用 sha3，也是 256 位哈希空间， 32 字节。

2、Node Distance 与 XOR

直接对两个 Node ID 进行 XOR 运算，就可以得出他们之间的距离。

比如，当前节点的 NodeID 是 1101，它与另一个节点 1010 的距离计算如下：

结果是：0101，用十进制数来表示就是 5，也就是他们距离相差 5。

注：为了简化，这里的节点 ID 我们假设只有 4 bits 长度。

Kademlia 中，根据当前节点的 Node ID 与它保存的其他 peer 节点 Node ID 的匹配的最多的前缀 bit 个数来构建一颗二叉树（Binary Tree），

这里前缀匹配的 bit 数也叫 LCP，Longest Common Prefix，的从上面的运算我们可以观察到，当前节点 1101 与 1000 的前缀只有最高位是匹配的。因此，其

LCP 就是 1。Kademlia 中根据 LCP 来划分子树。当前节点的每个 LCP 都是一个子树。

比如：假设节点的 ID 是 0011，那么它可以划分为 LCP = 0, 1, 2, 3 一共 4 个子树，如下：

所以，对于一个 160 bit 空间的 Node ID 来说，一共会有 160 个子树，也就是 160 个 buckets。每个 bucket 可以通过 XOR 的结果来索引。

Kad 协议要求每个节点知道其各子树的至少一个节点，只要这些子树非空。在这个前提下，每个节点都可以通过 ID 值来找到任何一个节点。

3、K-Bucket & Routing Table

从上图中可以看到，每个子树就是一个 K-Bucket，而且，子树中也包含许多 leaf 节点，每个 leaf 节点都表示一个 Peer。

Kademlia 中把子树中包含的 leaf 节点数量被设置为最多 k 个。这样可以有效控制整棵树的膨胀。

routing table 使用 K-Bucket list 来保存上述信息。

4、K-Bucket 更新

由于在真实的分布式网络中，由于网络的波动等因素，节点可能是频繁加入和退出网络的，而 kBucket 中保存的是相对静态的信息，因此需要随着一些条件的变化来进行相应的更新，最典型的需要更新 kbucket 的场景就是，当连上一个新的节点，或者有查询原本不在 kbucket 中的节点时。

kademlia 通过记录 kbucket 中每个节点的最近访问时间戳来判断节点的活跃度。

当需要更新一个 kbucket，时 取决于两个因素：

• kbucket 未满，则直接添加

• kbucket 已满，则判断是否存在剔除失效节点，存在，则用新节点替换，不存在，则抛弃新节点。

5、Peer finding

想要直观理解 Kademlia 算法的查找过程，我们可以通过一个例子来体会：

小明想要加撩公司里的美女小芳，但是不知道她微信号，那么他就从自己的微信好友（同事）中挑出 k 个最可能认识她的人，然后依次问他们有没有她的微信号，假如其中一个叫小华的认识小芳，那么他就会直接告诉小明，这样小明就不用继续问其他人了。假如不认识，那么小华就会给告诉小明他微信好友中最有可能认识小芳的 k 个人的联系方式，然后小明继续问这 k 个人，然后整个过程就一直循环迭代下去，直到最终有一个人肯定知道小芳的微信号。

Kademlia 查找就是这样一个过程。

K-Bucket 详解

下面，我们更具体的例子来深入理解 kBucket 构建，分裂及更新等过程，最后，我们再详细解析 Peer LookUp 过程。

1）构建与更新

假设当前节点 A 的 Node ID 是 110，初始状态时，没有连接任何其他节点，因此，只有一个 空 bucket，里面没有任何元素。

当一个新节点 B 连上当前节点 A 时，A 先计算距离 d = A ^ B，由于距离 d 就是我们 bucket 数组的索引，因此可以直接找到对应的 bucket[d]，

然后进行如下判断：检测其是否已经存满 k 个节点

• 如果未满，则直接添加进 kbucket 即可
• 如果已满，检测 bucket 列头元素是否能够 ping 通，如果 ping 通，则抛弃新节点，无法 ping 通，则用新节点替换失效节点

Kademlia 算法在不同的项目中会有不同的实现，区别主要在于 kbucket 数据结构及其相关方法。

比如，典型的 Kademlia 实现是，先根据 ID 空间预先分配 kbucket 数量的空间（比如 160 位，就分配 160 个 buckets 空间，256 位就直接分配 256 个 buckets 空间，这样，后续计算 distance 的时候可以直接 distance 作为 bucket 索引），还有就是 IPFS 这种，也是原始 Kademlia 论文中提到的，动态分配 buckets，如果节点少的时候，就只有一个 bucket，当节点不断增加之后，原 bucket 不断分裂，具体就是，每次满了 k 个元素，原 bucket 就分裂成 2 个。这样的话，对于内存空间是一个优化。而以太坊中的实现又略有不同，它使用固定数量的 buckets，但是却限定在 17 个，而不是 256 个，它通过一个 log 映射表来把新节点均匀分布在各个 buckets 中。

核心常量：

• Alpha 3
• K 20
• nBuckets 160

Alpha 是查询的并发数，也就是最多返回节点的数量，比如，发出一个查询，最终返回结果中包含 Alpha 个节点信息（包括了目标节点）。如果 Alpha 是 1， 那么只返回目标节点。

K 就是每个 bucket 中最多能保存的节点数量（通常是 20 ），从另外一个方面也可以把其理解成资源的副本。也就是说，一个资源，在一个分布式网络中，一共有 k 个节点保存了它的副本。

nBuckets 就是 Routing Table 中 bucket 的数量。

2）查找 LookUp

假设现在的当前节点是 001，它想要查的目标节点是 101 节点。

001 保存的 Routing Table 信息如下

我们先计算 001 与 101 节点的距离，001 ^ 101 等于 100，最高位的 index 是 2，因此，我们去 bucket 2 中查找是否有目标节点，发现没有，因此，我们依次向 bucket 2 中的节点发出查询请求，也即先向 110 发出查询请求，

即

110 节点的 Routing Table 信息如下：

节点 110 收到请求后，计算 110 ^ 101 结果是 011，匹配前缀数量是 1，因此，去 bucket 1 中查找，bucket 1 中也没有 101，因此向 100 发送请求，

即

节点 100 保存的 Routing Table 信息如下

100 收到请求后，计算 100 ^ 101，结果是 001，最长匹配前缀数量 2，因此去 bucket 0 中查找，

即

有 100 的 Routing Table 可知，目标节点 101 就正好在 bucket 0 中，直接返回!

我们可以看到，整个检索过程是不断收敛的，查询复杂度是可以证明是 Log N

全文完