简介

现在很多 P2P 网络的实现都采纳 DHT 的形式实现查找，其中 Kademlia（简称 Kad）算法因为其简略性、灵活性、安全性成为支流的实现形式。上面咱们就来详细分析这个利用于比特币和以太坊 P2P 网络中的 Kad 算法。

Kademlia 协定（以下简称 Kad）是美国纽约大学的 P. Maymounkov 和 D. Mazieres 在 2002 年公布的一项钻研后果 Kademlia: A peerto-peer information system based on the XOR metric。

简略的说，Kad 是一种分布式哈希表（DHT）技术，不过和其余 DHT 实现技术比拟，如 Chord、CAN、Pastry 等，Kad 通过独特的以异或算法（XOR）为间隔度量根底，建设了一种全新的 DHT 拓扑构造，相比于其余算法，大大提高了路由查问速度。

在 2005 年 5 月驰名的 BiTtorrent 在 4.1.0 版实现基于 Kademlia 协定的 DHT 技术后，很快国内的 BitComet 和 BitSpirit 也实现了和 BitTorrent 兼容的 DHT 技术，实现 trackerless 下载方式。

另外，emule 中也很早就实现了基于 Kademlia 相似的技术（BT 中叫 DHT，emule 中也叫 Kad，留神和本文简称的 Kad 区别），和 BT 软件应用的 Kad 技术的区别在于 key、value 和 node ID 的计算方法不同。

节点间隔

• Kademlia 中要害值（Key）用 160 位二进制示意，节点 ID（NodeID）也用 160 位二进制示意，NodeID 是退出网络时随机调配的。
• Kademlia 次要采纳了异或（XOR）机制 NodeID 与 NodeID 或节点与 Key 之间的间隔。

Kad 网络中每个节点都有一个 160bit 的 ID 值作为标志符，Key 也是一个 160bit 的标志符，每一个退出 Kad 网络的节点都会被调配一个 160bit 的节点 ID（node ID），这个 ID 值是随机产生的。

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 的间隔

这里所说的间隔是逻辑上的间隔，与地理位置无关，所以有可能两个节点之间计算失去的逻辑间隔很近，但实际上天文上的间隔却很远。

例如：节点 A 的 ID（011）和节点 B 的 ID（101）间隔：011 ⊕ 101 = 110 = 6。

网络节点树

在 Kad 网络中，所有节点都被当作一颗二叉树的叶子，并且每一个节点的地位都由其 ID 值的最短前缀惟一的确定。
由节点组成 kad 网络节点树的过程如下：

• Step1：先把 key（如节点 ID）以二进制模式示意，而后从高位到位置顺次按 Step2~Step3 解决。
• Step2：二进制的第 n 位对应二叉树的第 n 层。
• Step3：如果以后位是 1，进入右子树，如果是 0 则进入左子树（认为设定，能够反过来）。
• Step4：依照高位到位置解决完后，这个 Key 值就对应于二叉树上的某个叶子节点。

当咱们把所有节点 ID 都依照上述步骤操作后，会发现，这些节点造成一颗二叉树。

节点树拆分

每一个节点都能够从本人的视角来对二叉树进行拆分，把这颗二叉树合成为一系列间断的，不蕴含本人的子树。最高层的子树，由整颗树不蕴含本人的树的另一半组成；下一层子树由剩下局部不蕴含本人的一半组成；依此类推，直到宰割残缺颗树。

拆分规定是从根节点开始，把不蕴含本人的子树拆分进去，而后在剩下的子树再拆分不蕴含本人的下一层子树，以此类推，直到最初只剩下本人。如上图所示，以节点 ID 为 6（110）为视角进行拆分，能够失去 3 个子树（灰色圆圈）。而以节点 101 为视角拆分，则能够失去如下二叉树。以节点 101 的视角为例：

Kad 默认的散列值空间是 m =160（散列值有 160bit），所以拆分当前的子树最多有 160 个。而思考到理论网络中节点个数远远没有 2^160 个，所以子树的个数显著小于 160 个。

对于每个节点，当依照本人的视角对二叉树进行拆分当前，会失去 n 个子树。对于每个子树，如果都别离晓得外面 1 个节点，那么就能够利用这 n 个节点进行递归路由，从而能够达到整个二叉树的任何一个节点。

Kad 协定确保每个节点晓得其各子树的至多一个节点，只有这些子树非空。在这个前提下，每个节点都能够通过 ID 值来找到任何一个节点。这个路由的过程是通过所谓的 XOR（异或）间隔失去的。

K- 桶（K-bucket）机制

假如每个节点 ID 是 N bits。每个节点依照本人视角拆分完子树后，一共能够失去 N 个子树。下面说了，只有晓得每个子树里的一个节点就能够实现所有节点的遍历。然而，在理论应用过程中，思考到健壮性（每个节点可能推出或者宕机），只晓得一个节点是不够的，须要之多多几个节点才比拟保险。

所以，在 Kad 论文中旧有一个 K - 桶（K-bucket）的概念。也就是说，每个节点在实现拆分子树当前，要记录每个子树外面 K 个节点。这里 K 是一个零碎级常量，由软件系统本人设定（BT 下载应用的 Kad 算法中，K 设定为 8）。

K 桶在这里实际上就是路由表。每个节点依照本人视角拆分完子树后，能够失去 N 个子树，那么就须要保护 N 个路由表（对应 N 个 K - 桶）。

Kad 算法中就应用了 K - 桶的概念来存储其余邻近节点的状态信息，这些信息由 (IP address,UDP port,Node ID) 数据列表形成（Kad 网络是靠 UDP 协定替换信息的）。

每一个这样的列表都称之为一个 K 桶，并且每个 K 桶外部信息寄存地位是依据上次看到的工夫顺序排列，最近（least-recently）看到的放在头部，最初（most-recently）看到的放在尾部。每个桶都有不超过 k 个的数据项。

不过通常来说当 i 值很小时，K 桶通常是空的（也就是说没有足够多的节点，比方当 i = 0 时，就最多可能只有 1 项）；而当 i 值很大时，其对应 K 桶的项数又很可能会超过 k 个（当然，笼罩间隔范畴越广，存在较多节点的可能性也就越大），这里 k 是为均衡零碎性能和网络负载而设置的一个常数，但必须是偶数，比方 k = 20。在 BitTorrent 的实现中，取值为 k = 8。

因为每个 K 桶笼罩间隔的范畴呈指数关系增长，这就造成了离本人近的节点的信息多，离本人远的节点的信息少，从而能够保障路由查问过程是收敛。因为是用指数形式划分区间，通过证实，对于一个有 N 个节点的 Kad 网络，最多只须要通过 logN 步查问，就能够精确定位到指标节点。这个个性和 Chord 网络上节点的 finger table 划分间隔空间的原理相似。

K- 桶更新机制

次要有以下 3 种：

1. 被动收集节点： 任何节点都能够发动 FIND_NODE（查问节点）的申请，从而刷新 K - 桶中的节点信息。
2. 被动收集节点： 当收到其余节点发送过去的申请（如：FIND_NODE、FIND_VALUE），会把对方的节点 ID 退出到某个 K - 桶中。
3. 检测失效节点： 通过发动 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 桶列表中。

所以，通过把在线工夫长的节点留在 K 桶里，Kad 就明显增加 K 桶中的节点在下一时间段依然在线的概率，这对应 Kad 网络的稳定性和缩小网络保护老本（不须要频繁构建节点的路由表）带来很大益处。

这种机制的另一个益处是能在肯定水平上进攻 DOS 攻打，因为只有当老节点生效后，Kad 才会更新 K 桶的信息，这就防止了通过新节点的退出来泛洪路由信息。

为了避免 K 桶老化，所有在肯定工夫之内无更新操作的 K 桶，都会别离从本人的 K 桶中随机抉择一些节点执行 RPC_PING 操作。

上述这些 K 桶机制使 Kad 弛缓了流量瓶颈（所有节点不会同时进行大量的更新操作），同时也能对节点的生效进行迅速响应。

Kademlia 协定操作类型

Kademlia 协定包含四种近程 RPC 操作：PING、STORE、FIND_NODE、FIND_VALUE。

1. PING 操作的作用是探测一个节点，用以判断其是否依然在线。
2. STORE 操作的作用是告诉一个节点存储一个 <key,value> 对，以便当前查问须要。
3. FIND_NODE 操作应用一个 160 bit 的 ID 作为参数。本操作的接受者返回它所晓得的更靠近指标 ID 的 K 个节点的 (IP address, UDP port, Node ID) 信息。这些节点的信息能够是从一个独自的 K 桶取得，也能够从多个 K 桶取得（如果最靠近指标 ID 的 K 桶未满）。不论是哪种状况，接受者都将返回 K 个节点的信息给操作发起者。但如果接受者所有 K 桶的节点信息加起来也没有 K 个，则它会返回全副节点的信息给发起者。
4. FIND_VALUE 操作和 FIND_NODE 操作相似，不同的是它只须要返回一个节点的 (IP address, UDP port, Node ID) 信息。如果本操作的接受者收到同一个 key 的 STORE 操作，则会间接返回存储的 value 值。

为了避免伪造地址，在所有 RPC 操作中，接受者都须要响应一个随机的 160 bit 的 ID 值。另外，为了确信发送者的网络地址，PING 操作还能够附带在接受者的 RPC 回复信息中。

节点查找

Kad 技术的最大特点之一就是可能提供疾速的节点查找机制，并且还能够通过参数进行查找速度的调节。

如果节点 x 要查找 ID 值为 t 的节点，Kad 依照如下递归操作步骤进行路由查找：

1. 计算到 t 的间隔：d(x,y)=x⊕y
2. 从 x 的第 [ln d] 个 K 桶中取出 α 个节点的信息（ln d 是以 2 为底 d 的对数，[] 是取整符号），同时进行 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。

资源查找

当节点要查问 <key, value> 数据对时，和定位节点的过程相似。

• Step1： 首先发起者会查找本人是否存储了 <key, value> 数据对，如果存在则间接返回，否则就返回 K 个间隔 key 值最近的节点，并向这 K 个节点 ID 发动 FIND_VALUE 申请
• Step2： 收到 FIND_VALUE 申请的节点，首先也是查看本人是否存储了 <key, value> 数据对，如果有间接返回 value，如果没有，则在本人的对应的 K - 桶中返回 K - 个间隔 key 值最近的节点
• Step3： 发起者如果收到 value 则完结查问过程，否则发起者在收到这些节点后，更新本人的后果列表，并再次从其中 K 个间隔 key 值最近的节点，筛选未发送申请的节点再次发动 FIND_VALUE 申请。
• Step4： 上述步骤一直反复，直到获取到 value 或者无奈获取比发起者以后已知的 K 个节点更靠近 key 值的流动节点为止，这时就示意未找到 value 值。

如果上述 FIND_VALUE 最终找到 value 值，则 <key, value> 数据对会缓存在没有返回 value 值的最近节点上，这样下次再查问雷同的 key 值时就能够放慢查问速度。

所以，越热门的资源，其缓存的 <key, value> 数据对范畴就越广。这也是为什么咱们以前用 P2P 下载工具，下载的某个资源的人越多时，下载速度越快的起因。

保留资源

当节点收到一个 <key, value> 的数据时，它的存储过程如下：

• Step1： 发起者首先定位 K 个间隔指标 key 值最近的节点
• Step2： 而后发起者对这 K 个节点发动 STORE 申请
• Step3： 接管到 STORE 申请的节点将保留 <key, value> 数据
• Step4： 同时，执行 STORE 操作的 K 个节点每小时重公布本人所有的 <key, value> 对数据
• Step5： 最初，为了限度生效信息，所有 <key, value> 对数据在公布 24 小时后过期。

节点退出和来到

如果节点 u 要想退出 Kad 网络，它必须要和一个曾经在 Kad 网络的节点（种子节点），比方 w，取得联系。其步骤如下：

• Step1： 新节点 A 首先须要一个种子节点 B 作为疏导，并把该种子节点退出到对应的 K - 桶中
• Step2： 首先生成一个随机的节点 ID 值，直到来到网络，该节点会始终应用该 ID
• Step3： 向节点 B 发动 FIND_NODE 申请，申请定位的节点时本人的节点 ID
• Step4： 节点 B 在收到节点 A 的 FIND_NODE 申请后，会依据 FIND_NODE 申请的约定，找到 K 个间隔 A 最近的节点，并返回给 A 节点
• Step5： A 收到这些节点当前，就把它们退出到本人的 K - 桶中
• Step6： 而后节点 A 会持续向这些刚拿到节点发动 FIND_NODE 申请，如此往返，直到 A 建设了足够具体的路由表。

节点来到 Kad 网络不须要公布任何信息，Kademlia 协定的指标之一就是可能弹性工作在任意节点随时生效的状况下。为此，Kad 要求每个节点必须周期性的公布全副本人寄存的 <key,value> 对数据，并把这些数据缓存在本人的 k 个最近街坊处，这样失效节点寄存的数据会很快被更新到其余新节点上。

参考：
https://shuwoom.com/?p=813
https://blog.csdn.net/shangso…