Kademlia 协议

Kademlia[1]协议是一种分布式散列表(Distributed Hash Table, DHT) 技术。它可以被用来构建 P2P 网络,相比其他的散列表技术,提高了路由的查询速度。

在 Kademlia 协议中,利用异或来定义了节点之间的距离。这个距离是一个逻辑距离,而不是两个节点实际上的物理距离。在 Kademlia 协议中,每个节点都有一个随机生成的长度为160 bit的ID,而两个节点之间的距离就是把它们的 ID 异或后得到的值。

结合异或本身的性质,可以得到距离的一些特点[2]

  • $A \bigotimes B = B \bigotimes A$:A 到 B 和 B 到 A 的距离是一样的
  • $A \bigotimes A = 0$:节点自身和自身的距离是0
  • $A \bigotimes B > 0$:任意两个不同节点之间的距离大于0
  • $(A \bigotimes B) + (B \bigotimes C) \ge (A \bigotimes C)$:A 经过 B 到达 C 的距离大于 A 直接到达 C 的距离

K-bucket

在 Kademlia 协议中,定义了 K 桶(K-bucket),这里的 K 表示一个桶的容量。K 桶存储了其他邻居节点的信息,K 桶是每个节点在自己的视图下进行划分得到的。以下图为例,节点11(对应二进制为1011),它存储了包含自己id共16个节点的路由信息,然后将节点 ID 以前缀树的方式进行维护,然后通过以其他节点和自己的最长公共前缀来划分 K 桶,图中的每一个框都是一个 K 桶。

kademlia_routing_table_in_tree

第 $n$ 个 K 桶理论上维护的节点到当前节点的距离理论上为 $[2^{n -1 }, 2^n)$,但是每个 K 桶是存在容量限制的,距离本地节点较远的节点只维护 K 个。在查询某个节点的时候,可以求出另外一个节点和本地节点的 ID 的最长公共前缀长度来确认节点应该所在的 K 桶,如果节点不在路由表中,则可以去询问 K 桶中的节点。

在实际的代码实现中,go-lib-p2p-kbucket 使用了最长公共前缀长度来作为 K 桶的序号,查询邻居节点时利用最长公共前缀来定位节点所应该在的 K 桶,然后查找最近的 K 个节点来得到结果。而 python-kademlia 则没有利用这种方式,它将维护的 K 桶并非按照距离/最长公共前缀长度来维护,而是维护每个 K 桶的节点序号范围,在查找邻居的时候交替从目标 K 桶的左右 K 桶获取元素来得到 K 个最近的节点。

路由表更新机制

(待续,抽空写)

广播方法

参考文章