P2P网络之Kademlia协议

最近研究P2P网络，在看Kademlia相关资料的时候发现很多文章细节不够详细，有些甚至概念颠倒，不知道是不是我理解的问题，反正是看不懂。所以在此结合源论文，整合多份资料，对Kademlia协议算法做一个比较全面的梳理。

Kademlia协议（简称 Kad）源于美国纽约大学 P. Maymounkov 和 D. Mazieres 在2002年发布的研究论文 《Kademlia: A peerto-peer information system based on the XOR metric》。Kad 是一种分布式哈希表（DHT）技术，与其他DHT实现技术比较，Kad通过独特的以异或算法（XOR）为距离度量基础，建立了一种全新的DHT拓扑结构，相比于其他算法，大大提高了路由查询速度。在BiTtorrent、emule以及BitComet 和 BitSpirit等下载软件中，都用到Kademlia核心算法。

Kademlia基础定义

在P2P网络中，每个节点（Node）都需要存储其它Node的路由信息，从而进行网络连接与交互。由指定的节点去访问网络中任意一节点，最简单的办法就是每个节点存储全量路由数据，显而易见这是不现实的。因此退而求其次，采用迭代查找的思路，通过将这些网络节点组织成一种特殊结构，每多查找一次离目标更近一步，这样我们很容易想到一种数据结构——二叉树。

基本原理：

• Kademlia中，每个节点通过唯一ID来标识，即节点ID（NodeID）用160位二进制表示，NodeID是加入网络时随机分配的。
• 每个节点保存着自己附近（nearest）节点的信息，但是在 Kademlia 中，这个距离不是指物理距离，而是指一种逻辑距离，通过XOR（异或）运算得知。XOR 是一种位运算，用于计算两个节点之间距离的远近。如：011 ⊕ 101 = 110 = 6。
• 在 Kad 网络中，整个网络空间可以被表示成一颗二叉树，而网络中的节点都被当作二叉树的叶子，并且每一个节点的位置都由其 ID 值的最短前缀唯一的确定，如图1所示。

图1 路由树

Kademlia节点路由表构造

1.节点路由树的构建

Step1：先把key（如节点ID）以二进制形式表示，然后从高位到地位依次按Step2~Step3处理。
Step2：二进制的第n位对应二叉树的第n层。
Step3：如果当前位是1，进入右子树，如果是0则进入左子树（认为设定，可以反过来）。
Step4：按照高位到地位处理完后，这个Key值就对应于二叉树上的某个叶子节点。

2.根据节点划分子树

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

拆分规则是从根节点开始，把不包含自己的子树拆分出来，然后在剩下的子树再拆分不包含自己的下一层子树，以此类推，直到最后只剩下自己。如图2所示，以节点ID为6（110）为视角进行拆分，可以得到3个子树（灰色圆圈）。而以节点101为视角拆分，则可以得到如下二叉树。以节点101的视角为例，展示了如何进行子树的划分。

图2 子树划分

3.K-bucket构造与原理

假设每个节点ID是N bits。每个节点按照自己视角拆分完子树后，一共可以得到N个子树，这些被切割的子树称为“Bucket”，而整个路由表的本质是一个Bucket数组，每个Bucket中的节点必然与本节点具有相同的最长公共前缀，由于节点只有160bit，最长公共前缀长度最大只有160，因此，路由表中的​Bucket数量最多也就160。根据以上规则，按110节点进行Buckets构造的路由表如图3所示。

图3 路由表示例

这样按节点拆分子树的目的，上文已经说了，是为了用较少的数据构造节点相关的“路由表”，因为如果让一个指定节点要访问所有P2P网络里的节点，那么最直接的方式就是该节点记录下所有节点的信息，但是基于存储数据量、网络稳定性等因素，不能采用这种方式。而通过划分子树的方式，只需要知道每个子树里的一个节点信息，理论上就可以遍历所有节点。而在实际使用过程中，考虑到健壮性（每个节点可能退出或者宕机），只知道一个节点可能不够的，需要多知道几个节点才比较保险。因此，在Kademlia论文中，提到K-桶的概念，也就是说，每个节点在完成拆分子树以后，要记录每个子树里面K个节点，也就是对每个Bucket内维护的节点树设置了一个数量为K的上限。这里K是为平衡系统性能和网络负载而设置的一个常数，但必须是偶数，可由软件系统自己设定（BT下载使用的Kad算法中，K设定为8）。K桶在这里实际上就是路由表。每个节点按照自己视角拆分完子树后，可以得到N个子树，那么就需要维护N个路由表（对应N个K-桶）。

图4 路由表结构

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

每一个这样的列表都称之为一个 K桶，并且每个 K桶内部信息存放位置是根据上次看到的时间顺序排列，最近（ least-recently）看到的放在头部，最后（most-recently）看到的放在尾部。每个桶都有不超过 k 个的数据项。

图5 路由表信息结构

由于每个K桶覆盖距离的范围呈指数关系增长，这就形成了离自己近的节点的信息多，离自己远的节点的信息少，从而可以保证路由查询过程是收敛。因为是用指数方式划分区间，经过证明，对于一个有N个节点的Kad网络，最多只需要经过logN步查询，就可以准确定位到目标节点。

4.K-桶分裂机制

路由表最多有160个桶，每个桶存储着某个距离范围的节点ID。但是维护160个桶，同时接收到FIND_NODE查找请求的节点，必须返回k个节点信息。如果维护160个桶，为了返回k个节点，可能需要遍历其中大部分桶。（对应的桶，没有足够的k个节点时，我们就需要遍历前后相邻的桶，去获取节点)。所以，为了优化这一过程，路由表初始时只有一个桶，这个桶里的节点ID的距离范围是[0, 2^160]。桶内只有自己的节点ID。

当我们接收到新的节点信息时，它将根据与新的节点的距离，尝试将其插入到合适的桶中。如果找到对应的桶，如果桶还没满，我们直接插入到桶。如果对应的桶满了，则根据下面的情况分别处理：

（1）如果本机节点在桶内，就要将桶一分为二

（2）如果本机节点不在桶内，如果桶内的节点全部有效，直接丢弃新的节点

5.K-桶更新机制

当节点接收到外界RPC消息时，触发更新机制。如当节点y（发送者）向节点x（接收者）发送一个RPC消息时，则接收者x会进行如下操作，来更新发送者y（ID）对应的K-桶中（IP）信息：

Step1：计算自己和发送者y的距离：d(x,y) = x⊕y，注意：x 和y 是ID 值；

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

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

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

⑴ 如果该K 桶的记录项小于k 个，则直接把y 的(IP address,UDP port,Node ID)信息插入队列尾部

⑵ 如果该K桶的记录项大于k个，则选择头部的记录项（假如是节点z）进行RPC_PING操作

① 如果z没有响应，则从K-桶中移除z的信息，并把y的信息插入队列尾部

② 如果z有响应，则把z的信息移到队列尾部，同时忽略y的信息。

为了防止 K 桶老化，所有在一定时间之内无更新操作的 K 桶，都会分别从自己的 K 桶中随机选择一些节点执行 RPC_PING 操作。

Kademlia 协议及操作

1.操作类型

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

（1）PING操作的作用是探测一个节点，用以判断其是否仍然在线。

（2）STORE操作的作用是通知一个节点存储一个<key,value>对，以便以后查询需要。

（3）FIND_NODE操作使用一个160bit 的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 值。

2.节点查找

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

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

Step1：计算到 t 的距离： d(x,y)=x⊕y

Step2：从 x 的第 [log2 d] 个 K 桶中取出 α 个节点的信息（log2 d是以2为底d的对数，[]是取整符号），同时进行 FIND_NODE 操作。如果这个 K 桶中的信息少于 α 个，则从附近多个桶中选择距离最接近 d 的总共 α 个节点。
Step3：对接受到查询操作的每个节点，如果发现自己就是 t，则回答自己是最接近 t 的；否则测量自己和 t 的距离，并从自己对应的 K 桶中选择 α 个节点的信息给 x。
Step4：x 对新接受到的每个节点都再次执行 FIND_NODE 操作，此过程不断重复执行，直到每一个分支都有节点响应自己是最接近 t 的。
Step5：通过上述查找操作，x 得到了 k 个最接近 t 的节点信息。
注意：这里用“最接近”这个说法，是因为 ID 值为 t 的节点不一定存在网络中，也就是说 t 没有分配给任何一台电脑。这里 α 也是为系统优化而设立的一个参数，就像 K 一样。在 BitTorrent 实现中，取值为 α=3。

当α=1时，类似于逐跳查询过程。如图6所示，要找粉色节点ID时，上下对照逐跳过程，可知最终未能找到该节点。

图6 节点查找过程

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

N₁ = find_node_n(0)(t)

N₁ = find_node_n(1)(t)

...

N_l = find_node_n(l-1)(t)

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

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

3.资源查找

当节点 x 要查询<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下载工具，下载的某个资源的人越多时，下载速度越快的原因。

4.保存资源

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

Step1：发起者首先定位K个距离目标key值最近的节点

Step2：然后发起者对这K个节点发起STORE请求

Step3：接收到STORE请求的节点将保存<key, value>数据

Step4：同时，执行STORE操作的K个节点每小时重发布自己所有的<key, value>对数据

Step5：最后，为了限制失效信息，所有<key, value>对数据在发布24小时后过期。

5.节点参与

（1）节点加入

如果节点 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 为例，其路由表的生成过程为：

Step1：最初，u的路由表为一个单个的K-桶，覆盖了整个160bit的 ID 空间；

Step2：当学习到新的节点信息后，则u 会尝试把新节点的信息，根据其前缀值插入到对应的K桶中：
⑴如果该K-桶没有满，则新节点直接插入到这个K桶中；
⑵ 如果该K-桶已经满了
①如果该K桶覆盖范围包含了节点u的ID，则把该K-桶分裂为两个大小相同的新K桶，并对原K桶内的节点信息按照新的K-桶前缀值进行重新分配；
②如果该K桶覆盖范围没有包节点u的ID，则直接丢弃该新节点信息；
Step3：上述过程不断重复，最终会形成表1 结构的路由表。达到距离近的节点的信息多，距离远的节点的信息少的结果，保证了路由查询过程能快速收敛。

图7 K-桶分裂过程

（上图为论文所中所示例子，阐述了这种变化过程。初始时，本机节点（ID为00..00）的路由树如图①所示，只有一个Tree node，即一个覆盖全部ID空间的K-桶。当获得一个新的联系节点时，这唯一的Bucket已经满了（主要由设置的k决定），并且K-桶覆盖的ID范围中包含本机ID即00..00的值（最右侧），此时便分裂为如图②的两个桶。当下一次包含ID 00..00的K桶满了之后，继续进行分裂，如图③-④所示。可以看出分裂只能在包含00..00 ID的桶进行，其他桶满了不会进行分裂。）

2.节点退出

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

 

参考文章：

https://segmentfault.com/a/1190000023417884

https://blog.csdn.net/shangsongwww/article/details/89190141

https://codethechange.stanford.edu/guides/guide_kademlia.html