Kad协议实现踩坑记

Posted by szh on 2019-06-05

前言

之前看了 Kademlia 协议的论文,正赶上刚学了 Golang,就打算自己实现一个 DHT 玩玩。一路上遇见了不少坑,这篇文章记录了在实现过程中遇到的一些困难以及解决方式。

论文中的坑

  • 论文中对 K 桶(路由表)的实现给出了两种方式,一种是在文章开头提到的对所有异或距离范围为[2^i,2^i+1)的节点开一个桶,由于节点和资源 ID 为 160 位,一共要开 160 个桶。第二种方式是在文章中介绍 Routing Table 时提到的基于 Split 的方式,大概意思是一开始只有一个桶,之后随着节点的加入不断分裂桶进而形成一棵二叉搜索树,按节点 ID(注意此处不是异或距离)插入,等到桶满了之后,如果这个桶盛放节点的范围包含了这个节点本身,就分裂桶,否则开始 Ping。这里介绍的就比较含糊,并没有细讲怎么分裂桶。而且论文随后提到这种方式可能会导致二叉树不平衡,然后又引入了一个新的分裂规则,这里因为英文读不通一直没法理解。

  • 论文中,新节点插入桶时遇到桶满的情况先后提出了两种差别非常大的解决方法,一种是在文章开头提到的,在桶满的时候 Ping 桶中最长时间没联系的节点,如果没通就把这个节点换成新插入节点;另一种是说在桶满的时候把新节点放进一个等待队列中,等到明确发现原来桶中某个节点失效时,从等待队列中找出来最近联系的节点加入桶中。

  • 对于第一点的两种方式,需要两种数据结构,直接对所有范围开桶是最简单的方法,只要一个数组,而第二种方式需要二叉树,为了支持 Split,还需要自己实现一个链表。对第二点的两种方式,第二种比第一种多了一个队列。根据论文所说,第一种方式的通信开销比较大;而第二种方式,我认为可能会降低第一轮查找的成功率,由于路由表的惰性更改,在有实际查询需要时,第一轮发出请求的节点会比第一种方式“老”

我选择的实现方式

  • 对于路由表的数据结构,我选择了不分裂的 K 桶和惰性更新的组合,不分裂 K 桶除了在空间上稍微大一点(一开始就需要 160 个指针,不过微不足道)在实现难度和操作时间开销方面均优于分裂的方式。对于惰性更新,并没有进行实际性能测试,这里有待进一步实验测试