P2P网络之Kademlia协议

2022年5月17日11:12:29P2P网络评论276阅读模式

最近研究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所示。

P2P网络之Kademlia协议

图1 路由树

Kademlia节点路由表构造

1.节点路由树的构建

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

2.根据节点划分子树

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

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

P2P网络之Kademlia协议

图2 子树划分

3.K-bucket构造与原理

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

P2P网络之Kademlia协议

图3 路由表示例

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

P2P网络之Kademlia协议

图4 路由表结构

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

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

P2P网络之Kademlia协议

图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时,上下对照逐跳过程,可知最终未能找到该节点。

P2P网络之Kademlia协议

图6 节点查找过程

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

N1 = find_noden(0)(t)

N1 = find_noden(1)(t)

...

Nl = find_noden(l-1)(t)

这个递归过程一直持续到 Nl =t,或者 Nl 的路由表中没有任何关于 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 结构的路由表。达到距离近的节点的信息多,距离远的节点的信息少的结果,保证了路由查询过程能快速收敛。

P2P网络之Kademlia协议

图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