分布式哈希表与Kademlia算法

公司的一台服务器上有一批重要内部文件, 公司的员工都可以访问这台服务器，找到想要的文件或者增加文件。

我作为一个怀疑心重的运维，总觉得公司明天会火灾或者给恐怖袭击，到时候这台服务器就爆炸了，里面的文件就跟着去了。

于是我想出一个办法，将这批内部文件分发给公司的员工，每位员工在自己的电脑保存一部分的文件，这样就降低了风险。

但这样带来了几个问题

1. 怎样找到文件，我要怎样才能知道文件A在哪位员工的电脑？
2. 怎样分配文件，我新增了一个文件Z，文件Z存储到哪位员工的电脑？
3. 文件A在员工A的电脑里，员工A的电脑出故障了，这时候就无法拿不到文件A了？

Kademlia协议

哈希表，大家应该都知道，是一种<key, value>的数据结构，通过key可以在O(1)的时间复杂度找到value。

我们一般在单台服务器上使用哈希表。而分布式哈希表(Distribute Hash TABLE, 缩写DHT)，是由许多服务器连接在一起，每台服务器保存一部分的<key, value>，去中心化的一种数据结构。每台服务器都可以读和写整个哈希表。

kademlia DHT是其中一种DHT的实现协议。现在结合刚开始的场景和问题，详细讲解下kademlia。

对于每个文件，分配一个160 bit的file_id，可以使用sha1对文件的内容生成。

我们使用key来保存file_id，value来保存存放该文件的员工电脑的ip和port。现在我们要找文件A, 只需要sha1(文件A)得到key，在分布式哈希表里找到对应的value，我们就可以通过得到的ip和port，连接到存放文件A的电脑，就可以得到文件了。

问：每台电脑保存着分布式哈希的一部分<key, value>，我去哪台电脑得到文件A key/value。

答：kademlia是这样解决的，对于每台员工的电脑，同样分配一个独一无二的160 bit的node_id, 160 bit随机的id，基本可以保证世界上，不会存在同样的node id。<key, value>会存放在node_id和key"距离接近"的电脑里。

问："接近"是如何定义的？还有，我目前只有自己电脑的node_id, 又怎样连接上key "接近"的node_id对应的电脑？

答: kademlia使用两个node_id异或(xor)的结果，来衡量距离的远近。例如电脑0001(0001⊕0000=1)就比电脑0011(0011⊕0000=11)更靠近电脑0000。

同时每台电脑都保存这一个路由表，路由表里保存着其他电脑的node_id和它们的ip和port，我们可以通过这个路由表和路由算法来找到目标node_id的电脑。

kademlia将路由表里的node_id映射到一颗二叉树的叶子，每个node_id在树中的位置由这个node_id的最短唯一前缀决定。

上面的图，就展示了本机node_id=0011...(后面省略16个bit), 和它当前知道的其他电脑node_id，所组成的一颗二叉树。

然后我们对每一个节点，按照自己的视角对二叉树进行拆分。上面的图，就是以node_id=0011...(黑色实心点)的视角拆分后的结果。
拆分规则是，先从根节点开始，把不包含自己的那个子树拆分出来；然后在剩下的子树再拆分不包含自己的下一层子树；以此类推，直到最后只剩下自己。
因为node_id由160bit组成，因此拆分出来的子树最多有160课。（本机一般知道的其他node_id个数远远小于2的160次方，子树的棵树会明显小于160课，上面的图里就只有四颗子树)

每一颗子树就是路由表里一个桶(bucket), 每个桶都有一个编号，编号由桶里node_id和本机node_id的共同bit前缀位数i决定，例如，0号桶里的node_id和本机node_id的共同bit前缀i=0。也可以观察到，每个桶里的node_id和本机node_id的异或结果在[2^(160-i-1), 2^(160-i)]。

现在有了路由表，那我们怎样利用路由表来寻找节点。

对于每一个节点而言，当它以自己的视角完成子树拆分后，会得到n个子树；对于每个子树，如果它都能知道里面的一个节点，那么它就可以利用这n个节点进行递归路由，从而到达整个二叉树的【任何一个】节点

上面是论文里的图。本机的node_id=0011..., 构建后路由表后，现在要定位node_id=1110...的电脑，0011...⊕1110...的结果在[2^159, 2^160]范围内，我们可以在0桶内取出一个node_id, 上面的图取出了101...。本机发送rpc请求给node_id=101...的电脑，node_id=101...的电脑，计算101...⊕1110...的结果在[2^158, 2^159]范围内，于是在1桶内（注意，这里是101...的路由表，不是本机的路由表)取出node_id=1101...的信息返回给本机, 本机继续发送rpc请求给node_id=1101...的电脑。可以看到每一次rpc请求得到的node_id和目标node_id 1110...的异或结果会越来越小，这个过程一直递归执行下去，直到我们得到目标node_id或者距离目标node_id最近的node_id。

可以观察到这一个过程，每一次rpc调用，得到的node_id，与目标node_id的共同前缀，最少都会增加一位，node_id有160位，所以这一过程最多160次。每次都可以将范围定位缩小到一半子树，这是一个logN的过程。

路由表的细节

kademlia每个节点维护着一个路由表。路由表可以划分为160个桶，0<=桶的编号i<160, 每个桶保存着和当前节点node id距离在2^i到2^(i+1)范围的其他节点信息<IP地址, UDP端口，Node IP，NODE ID>。每个桶的节点按上次可见的时间排序从小到大排序，最老的在桶的头部，最新的桶的尾部。

路由算法里，我们知道，每个桶里只需要有一个节点，我们就可以递归到达任一个其他节点。但是网络和节点是不可靠的（节点断开网络)，kadelima提供了一个系统级的参数k, 设置每个桶最多可以保存的节点数，所以每个桶也叫k-桶。

当一个节点收到其他节点的消息（请求或者响应），它会把消息发送者的节点信息保存在对应的桶里。

• 如果已经存在于桶里，将发送者的节点移到桶的尾部。
• 如果不存在，桶也没满，将发送者的节点加入到桶的尾部。

• 如果桶已满，尝试去ping桶内最老的节点

  • 如果最老的节点没响应，那将最老的节点移出桶，将发送者的节点加入到桶的尾部
  • 如果最老的节点有响应，那将最老的节点移到桶的尾部，忽略发送者的节点。

为什么要使用这样的方式更新桶？

1. 一个节点在线时间越久，下一个小时仍然在线的概率越大，所以老节点有响应，就继续保留老节点在桶里。
2. 另一个好处是对抗dos攻击，攻击者无法伪造，来清空我们桶里已有的节点信息，攻击我们。因为只有老的节点移出桶后，新的节点才能插入进去。

桶，一般都会在被请求或被响应时，得到请求者或响应者的节点id, 从而得到更新。但也有可能出现，一个桶内的节点长时间没有更新的情况，桶内的节点可能都已经下线了。为了解决这种问题，每个桶都有一个最后更新时间，过去一个小时没有得到更新的桶会强制更新。更新方法是，选择一个在该桶范围内的随机节点id，发起对该节点的FIND_NODE查找。这一过程是一个递归的过程，响应者会不断返回k个离随机节点id最近的节点id，桶就能够得到更新。

刚开始，我们的路由表里什么信息都没有，我们无法使用上面的路由算法去查找文件。我们需要加入到整个网络中，这就要求我们知道一些已经常驻在网络上的节点信息，例如我作为公司的运维，就开了一台阿里云的机器，所有的员工都知道这台机器的ip和端口，员工可以向这台阿里云的机器发起一个，查找自己的节点id的请求，员工电脑会收到响应，就可以利用响应里的节点信息更新自己的路由表。同时自己的节点id也会插入到阿里云机器和其他员工电脑的路由表。

我们知道路由表最多有160个桶，每个桶存储着某个距离范围的节点id。但是维护160个桶，同时接收到FIND_NODE查找请求的节点，必须返回k个节点信息。如果维护160个桶，为了返回k个节点，可能需要遍历其中大部分桶。（对应的桶，没有足够的k个节点时，我们就需要遍历前后相邻的桶，去获取节点)

所以，为了优化这一过程，路由表初始时只有一个桶，这个桶里的节点id的距离范围是[0, 2^160]。桶内只有自己的节点id。
当我们接收到新的节点信息时，它将根据与新的节点的距离，尝试将其插入到合适的桶中。插入的规则如下：

1. 如果找到对应的桶，如果桶还没满，我们直接插入到桶。

2. 如果对应的桶满了

   1. 如果本机节点在桶内，就要将桶一分为二
   2. 如果本机节点不在桶内，如果桶内的节点全部有效，直接丢弃新的节点

下图，设定k=5且节点全部有效在线, 每个桶最多能容纳5个节点。

可以看出，如果桶1满了，这时候是不能再分裂的，桶的分裂永远只能在桶0发生。最后可以分裂后的桶的数目，最多是160个，这时候和我们最开始定义的160个桶的路由表是一样的。

你可以继续模拟，当桶0再次满了的时候，桶再次分裂的情景。

回到最开始的问题

现在我们已经解决了问题1和2，如何查找文件和存储文件。但细想下，160bit的node_id和file_id相等的可能性是很低的，就拿bt来举例，此时全世界有数百万的客户端正在下载，但是相比2^160这个天文数字，几百万是一个很小的数字。同时问题3，如果我们只在一台电脑存储文件，这台电脑下线后，我们就无法找到文件了。

所以kademlia为了整个系统的健壮性，使用k个里目标id最近的节点，来保存文件。这样一个节点离线后，还可以从其他节点拿到文件。

记住，整个DHT网络是动态变化，节点可以随时离开网络，新的节点也可以随时加入网络。

文件(key)的高效重新发布

因为网络是动态变化的，下面两种场景可能会造成定位文件所在的节点时失败。

1. 存储文件的k个节点全部都下线了。
2. 新加入网络的节点node_id比网络里原有的k个节点，离file_id的距离更近。当查找文件时，通过路由算法，定位到的是新加入到网络的节点，这时候这些节点里，没有存储着这些文件。

为了解决上面的问题，存储着文件的节点必须定期地（每小时)向网络重新发布文件，以保证离目标文件file_id最近的k个节点，保存着文件。

最简单的实现方法是，当前存储着文件的k个节点，每个都分别发起查找请求，找到离目标文件file_id最近的k个节点，然后分别向这k个节点，发起存储文件的请求。当这是一种很耗时的实现方法。

下面有两种优化策略：

1. 当一个节点收到存储请求时，它会知道其他k-1个节点也收到了请求。收到请求的该节点这时候就不会重发布文件，而是将重发布时间更新到当前时间的一小时后，这样可以减少这个重发布过程的查找和存储请求数。
2. 第二个优化在于在重新发布key之前避免进行节点查询。(这点没搞懂，大家可以看看kademlia的论文，看懂的可以告诉我）（原始论文里提到的为了处理高度不平衡树，桶分裂时做了一些优化，从而引出了这里的第二优化。但我看了下bittorrent的源码和stackoverflow的一些讨论，bittorrent没有做处理高度不平衡树的优化，stackoverflow的回答也指出，不采用论文里的优化手段，只使用普通的桶分裂方法，路由表里的节点最终也可以均匀分布)

Kademlia rpc

kademlia协议定义了四个rpc方法

• ping：探测一个节点是否在线
• store: 存储<key, value>到节点
• find_node: 160-bit的目标node_id作为参数，发送rpc请求，接收者从对应的k-桶里取出k个节点信息<IP地址，UDP端口，Node ID>。如果对应的k-桶里没有k个节点，可以从相邻的k-桶取。接收者必须返回k个节点信息。（除非所有k-桶加起来的节点个数都小于k)

• find_value: 160-bit的目标文件file_id作为参数，发送rpc请求

  • 如果接收者保存了key=file_id对应的value，返回value
  • 接收者的响应和find_node一样，返回离file_id最近的k个节点信息

查找过程的细节

kademlia协议需要实现的最重要的过程是定位距离给定node_id最近的k个节点。kademlia采用了递归的算法来处理节点查找。α是并发请求的参数，设定了同时发送rpc请求的并发数，一般是3

下面的实例图是bt dht查找过程。

一个节点在自己的路由表里，找到离目标node_id最近的α个节点，同时发送find_node请求。接收者收到请求后，会从自己的路由表里拿出k个里目标id最近的节点信息，返回给发送者。

发送者维护着一个结果列表，列表里的节点按与目标id的距离，从近到远排序，一旦接收到响应后，（注意：这里不需要等待之前的α个请求全部响应，之前我以为要等，看了下论文里提到）

In the recursive step,the initiator resends the FIND_NODE to nodes it has learn about from previous RPCS. (This recursion can begin before all α of the previous RPCs have returned).

还看了下bittorrent客户端里的代码实现，只要收到一个请求的返回，就可以更新结果列表，然后从列表的前k个节点，向第一个还没请求过的节点，发送FIND_NODE请求。

上面这一过程，当结果列表的前k个节点都已经被请求过，说明返回的节点，已经没有比这k个节点，离目标id更近了，就可以终结整个FIND_NODE过程，前k个节点作为结果。

kademlia里大部分的操作的实现，都基于上面的查找过程。
例如本机新创建文件后，本机需要通过上面的查找过程，定位里目标文件file_id最近的k个节点，然后向这k个节点发送STORE请求。
查找文件，也是以目标文件file_id作为目标id, 这个查找过程基本和上述一样，除了当找到目标文件时，提前终止查找过程。同时为了缓存, 一旦查找成功，需要将文件存储到当前找到的里目标file_id最近且没有存储的节点。这样做的好处是，设想下，某一个会议期间，老板通知大家要打开同一个文件，这时候，请求的压力都集中到几台电脑，有了上面的缓存过程，请求的压力就可以分散到更多的电脑。这可以解决整个网络，热点资源的压力瓶颈问题。
同时这一缓存过程，可能会使热点的文件缓存到整个网络。为了避免过分缓存，我们会为<key, value>设置过期时间，这个时间与节点ID和目标file_id的距离成指数反比。注意：缓存不会执行上面key重新发布过程，过期时间到了，缓存便会被删除。

个人觉得，kademlia论文里对某些实现，讲解的不是很详细。对kademlia的代码实现，出于具体项目和工程上的考虑，也各有不同。推荐阅读下bittorrent源码，go-libp2p-kad-dht源码。emule论坛里也有很多高质量的讨论。

Kademlia: A Peer-to-peer Information System Based on the XOR Metric
Kademlia Wiki
The Kademlia Protocol Succinctly
Bit torrent techtalks_dht