SWARM 学习 1——Kademlia 分布式路由表协议

@2020-08-19, AIbot

全文引用自, 经作者理解后重新整理

P2P 网络核心技术：Kademlia 协议

简介

Kademlia是分布式哈希表DHT(Distributed Hash Table)的一种, 它使用异或XOR方法来计算节点间的距离, 可以实现trackless的路由寻址。Kademlia分布式哈希表通过各节点各自独立的维护哈希表来实现分布式哈希表的维护。通过迭代的方法寻找其他不在本节点哈希表中的节点——具体实现方法见寻找方式小节

概念介绍

在Kademlia分布式哈希表协议中有如下三个关键概念：节点的身份NodeID、节点距离Node Distance、k桶——k-Bucket。和两个关键的步骤路由表Routing Table的构建、更新和节点寻找。

• 节点身份NodeID：节点通过唯一的字符串来表示自身的身份，冲突避免的哈希函数在此处大放异彩，原始的Kademlia协议使用SHA1算法生成节点的ID，它具有160bit；在IPFS和以太坊中该协议使用SHA2，3算法生成节点的ID，已经达到了256bit。下图1 介绍几点身份的计算结果





图1. 节点身份计算结果示意

• 节点距离Node Distance：节点的距离使用节点ID异或运算定义，换言之所谓距离Distance只是逻辑定义的概念并不表示实际物理世界两个节点之间的位置关系。下图2 展示两个4bit的节点距离计算方法





图2. 节点距离异或计算方法

• k桶——k-Bucket：k桶用于保存和当前节点连接的其他节点ID，k表示桶的容量一般为20也就是说常规操作一个桶中最多存储20个符合要求的节点。k桶的存储要求：k桶的数量与NodeID的比特数对应，原始协议160bit为例则一共有160个k桶；第i号k桶存储节点距离在$[2^{i-1}, 2^i -1]$之间的节点距离。利用最长前缀匹配法LCP（Longest Common Prefix）来快速确定节点所属的桶，前缀匹配的越少则距离越远，属于序号越大的桶；通过下图3 LCP子树划分可以更直观的感受。





图3. LCP子树划分

1. 路由表的构建，通过LCP划分的子树结果做如下运算$len(buckets)-int(lo{g}_2(diatance))$，即可得到该节点归属的k桶索引号，在k桶未满20之前直接存进去即可。路由表的更新，当前节点接收到它路由表中不存在的节点的查询请求后，会判断是否更新路由表；具体判断逻辑为:

• kbucket 未满，则直接添加

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

1. 节点寻找，见下一小节

节点寻找

假设现在的当前节点是 001，它想要查的目标节点是 101 节点。001 保存的 routing table 信息如下图4 当前节点路由表所示。





图4 当前节点路由表

我们先计算 001 与 101 节点的距离，001 ^ 101 等于 100，最高位的非零位的 index 是 2，因此，我们去 bucket 2 中查找是否有目标节点，发现没有，因此，我们向 bucket 2 中的节点依次发出查询请求，也即先向 110 发出查询请求；见图5-1 路由表查询和图5-2查询逻辑树。





图5-1 路由表查询





图5-2 查询逻辑树

110 节点的 Routing Table 信息如下图6. 110节点路由表





图6. 110节点路由表

节点 110 收到请求后，计算 110 ^ 101 结果是 011，匹配前缀数量是 1（非零位的 index 是 1），因此，去 bucket 1 中查找，bucket 1 中也没有 101，因此向 100 发送请求；见图7-1 和图7-2





图7-1





图7-2

节点 100 保存的 Routing Table 信息如下图8. 100节点路由表





图8. 100节点路由表哦

100 收到请求后，计算 100 ^ 101，结果是 001，最长匹配前缀数量 2（非零位的 index 是 0），因此去 bucket 0 中查找，见图9和图10 最终查找路径,其中绿色为最初的查找路径:001→110, 蓝色为以110为跳板的第二次查询路径:110→100, 红色是以100为跳板的第三次查询路径:100→101. 整个过程只是展示了一种成功的路径, 事实上在没得到找到的信号之前会广发英雄帖给相应bucket中的节点, 不同bucket中的节点不会接到查询请求(保证算法的N时间复杂度)





图9-1





图10. 最终查找路径

由 100 的 Routing Table 可知，目标节点 101 就正好在 bucket 0 中，直接返回,我们可以看到，整个检索过程是不断收敛的，查询复杂度是可以通过数学归纳法证明为 Log N的。