Kademlia分布式哈希表

1. 背景介绍

1.1 DHT是一种分布式存储、路由技术

设想一个场景：有一所1000人的学校，现在学校突然决定拆掉图书馆（不设立中心化的服务器），将图书馆里所有的书都分发到每位学生手上（所有的文件分散存储在各个节点上）。那么所有的学生，共同组成了一个分布式的图书馆。

图书馆

关那么现在的关键问题就是这两个：

1. 如何分配存储内容到各个节点，新增/删除内容如何处理？（每个同学手上都分配哪些书）
2. 一个节点如果想获取某个特定的文件，如何找到存储文件的节点/地址/路径？（如何寻找需要的书籍）
   针对这两个问题，有一种非常朴素的思想：向网络中每个节点都发送查询请求；每个节点都“帮忙”转发其他节点查询请求。这种思想叫做泛洪查询。
   泛洪查询
   显然，这种查询的效率非常低，也会造成所谓的“泛洪风暴”。那么有没有改进方法呢？当然有的，这种方法叫做Gossip，本质上一种克制的泛洪。
   我们先看一个理论，六度分隔理论：你和任何一个陌生人之间所间隔的人不会超过五个。也就是说，最多通过五个人你就能够认识任何一个陌生人。以下就是关于Gossip的详细介绍。

• Gossip 类似于疾病的传染，被感染节点随机选择 k 个邻接节点（fan-out）散播消息，假设把 fan-out 设置为2，每次最多往2个节点散播
• 每次散播消息都选择尚未发送过的节点进行散播

• 收到消息的节点不再往发送节点散播，比如 A -> B，那么 B 进行散播的时候，不再发给 A

  
  Gossip

1.2 从哈希表到分布式哈希表

哈希表这种数据结构，通常会包含K个bucket（k桶）。“桶”用来存储多个键值对，可以看做一个动态数组。对某个KEY进行查找时：先通过Hash函数，计算出散列值，然后取模，得到对应的Bucket编号

哈希表
那么分布式哈希表呢？还是拿图书馆举例：假设《分布式算法》这本书的书名的hash值是 00010000，那么这本书就会被要求存在学号为00010000的同学手上。（要求hash算法的值域与node ID的值域一致。）万一00010000今天没来上学（节点没有上线或彻底退出网络），那《分布式算法》这本书岂不是谁都拿不到了？那算法要求这本书不能只存在一个同学手上，而是被要求同时存储在学号最接近00010000的k位同学手上，即00010001、00010010、00010011…等同学手上都会有这本书。
分布式哈希表

1.3 节点路由

问题描述：由于手上只有一部分同学的通讯录（Bootstrap节点），你很可能并没有00010000的手机号（IP地址）。那如何联系上目标同学，向他发出请求呢？
算法思想：如果一个同学离你越近，你手上的通讯录里存有ta的手机号码的概率越大。
当你知道目标同学Z与你之间的距离，你可以在你的通讯录上先找到一个你认为与同学Z最相近的同学B，请同学B再进一步去查找同学Z的手机号。
那么，一种合适的举例算法就非常重要。这里我们采用汉明距（XOR）作为距离度量：学号（Node ID）之间的异或距离（XOR distance）。0⊕0=0，1⊕0=1，0⊕1=1，1⊕1=0（相异取真）。比如 01000000 与 00000001 距离为 01000001（换算为十进制即为26+1，即65）

1.4 为什么需要DHT

DHT技术主要是为了解决P2P网络发展中遇到的种种问题。在 P2P 网络的发展过程中，出现过3种不同的技术路线：

1. 中央服务器模式：每个节点都需要先连接到中央服务器，然后才能查找到自己想要的文件在哪里。中央服务器成为整个 P2P 网络的【单点故障】，典型代表：Napster
2. 广播模式：要找文件的时候，每个节点都向自己相连的【所有节点】进行询问；被询问的节点如果不知道这个文件在哪里，就再次进行“广播”如此往复，直至找到所需文件
3. DHT模式：承载海量数据。由于数据是海量的，每个节点只能存储整个系统的一小部分数据。需要把数据【均匀分摊】到每个节点

2. DHT简介

2.1 DHT需要解决的问题

1. 去中心化带来的问题：如何设计高效的存储、内容路由算法。
2. 数据量大带来的问题：如何设计高效的存储、内容路由算法。
3. 节点动态变化的问题：参与DHT的计算节点会频繁变化，每时每刻都有新的节点上线、旧的节点下线。
4. 高效查询困哪的问题：如何快速定位节点，同时又不消耗太多网络资源？

2.2 DHT设计思路

1. 散列算法的选择：DHT 通常是直接拿数据的散列值作为 key，数据本身作为 value。那么。散列函数产生的“散列值范围”（keyspace）要足够大，以防止太多的碰撞。那么我们更进一步， 让keyspace足够大，使得“随机碰撞”的概率小到忽略不计。这样有助于简化DHT的系统设计。通常的 DHT 都会采用大于等于 128 比特的散列值
2. 同构的node ID与data key：给每一个node分配唯一的ID，将分布式系统与实际物理网络解耦。逻辑上相邻的节点，可能实际上相距很远。这样设计，有以下好处：

• 散列值空间足够大的时候，随机碰撞忽略不计，因此也就确保了 node ID 的唯一性
• 可以简化系统设计——比如简化路由算法

3. 拓扑结构设计：Key-based routing（key 本身已经提供了足够多的路由信息）
   当某个分布式系统具有自己的拓扑结构，它本身成为一个覆盖网络（Overlay Network）所谓的覆盖网络，通俗地说就是“网络之上的网络”。由于前面分布式系统与实际物理网络解耦的设计，使得DHT在设计拓扑结构和路由算法时，只需要考虑 node ID，而不用考虑其下层网络的属性。
4. 路由算法设计：由于 DHT 中的节点数可能非常多，而且这些节点是动态变化的。因此就不可能让每一个节点都记录所有其它节点的信息。所以，每个节点通常只知道少数一些节点的信息。这样就需要设计某种路由算法，尽可能利用已知的节点来转发数据。

3. Kademlia DHT算法

3.1 简介

Kademlia是分布式哈希表（Distributed Hash Table, DHT）的一种。而DHT是一类去中心化的分布式系统。在这类系统中，每个节点（node）分别维护一部分的存储内容以及其他节点的路由/地址，使得网络中任何参与者（即节点）发生变更（进入/退出）时，对整个网络造成的影响最小。DHT可以用于构建更复杂的应用，包括分布式文件系统、点对点技术文件分享系统、合作的网页高速缓存、域名系统以及实时通信等。
Kademlia算法在2002年由Petar Maymounkov 和 David Mazières 所设计，以异或距离来对哈希表进行分层是其特点。Kademlia后来被eMule、BitTorrent等P2P软件采用作为底层算法。
Kademlia的优点在于：

• 对于任意一个有[ 2(n−1) ,2𝑛)个节点的网络，最多只需要n步搜索即可找到目标节点；
• K-bucket的更新机制一定程度上保持了网络的活性和安全性。

3.2 Kademlia DHT拓扑结构：二叉树

Kademlia采用了“node ID 与 data key 同构”的设计思路。Kademlia 采用某种算法把 key 映射到一个二叉树，每一个 key 都是这个二叉树的叶子。在映射之前，先做以下预处理。

1. 先把 key 以二进制形式表示，然后从高位到低位依次处理
2. 二进制的第 n 个 bit 就对应了二叉树的第 n 层
3. 如果该位是 1，进入左子树，是 0 则进入右子树

4. 把每一个 key 缩短为它的最短唯一前缀。

   
   拓扑结构
   

   Kad 使用 160比特 的散列算法（比如 SHA1），完整的 key 用二进制表示有 160 个数位（bit）。实际运行的 Kad 网络，即使有几百万个节点，相比 keyspace（2^160）也只是很小很小很小的一个子集。其次，由于散列函数的特点，key 的分布是高度随机的。因此任何两个 key 都不会非常临近。所以，使用“最短唯一前缀”来处理 key 的二进制形式，得到的结果就会很短

3.3 二叉树拆分

二叉树拆分：对每一个节点，都可以按照自己的视角对整个二叉树进行拆分。
拆分规则：先从根节点开始，把不包含自己的那个子树拆分出来；然后在剩下的子树再拆分不包含自己的下一层子树；以此类推，直到最后只剩下自己。

拆分

Kademlia 默认的散列值空间是 m = 160（散列值有 160 bits），因此拆分出来的子树最多有 160 个（考虑到实际的节点数远远小于2^160，子树的个数会明显小于 160）。对于每一个节点而言，当它以自己的视角完成子树拆分后，会得到 n 个子树；对于每个子树，如果它都能知道里面的一个节点，那么它就可以利用这 n 个节点进行递归路由，从而到达整个二叉树的任何一个节点。

3.4 距离定义：XOR

DHT将其他的peer节点，按照与自己的距离，划分到不同的k桶（k-bucket）当中
以0000110为基础节点，如果一个节点的ID，前面所有位数都与它相同，只有最后1位不同，这样的节点只有1个——0000111，与基础节点的异或值为0000001，即距离为1；对于0000110而言，这样的节点归为“k-bucket 1”
如果一个节点的ID，前面所有位数相同，从倒数第2位开始不同，这样的节点只有2个：0000101、0000100，与基础节点的异或值为0000011和0000010，即距离范围为3和2；对于0000110而言，这样的节点归为“k-bucket 2”；
如果一个节点的ID，前面所有位数相同，从倒数第i位开始不同，这样的节点只有2^(i-1) 个，与基础节点的距离范围为[2^(i-1), 2^i）；对于0000110而言，这样的节点归为“k-bucket i”
将整个网络的节点梳理为一个按节点ID排列的二叉树，树最末端的每个叶子便是一个节点，则下图就比较直观的展现出，节点之间的距离的关系

节点距离

3.5 K-Bucket

每个节点在完成子树拆分后，只需要知道每个子树里面的一个节点，就足以实现全遍历。但是考虑到健壮性，只知道一个节点显然是不够的，需要知道多个才比较保险。
所以 Kademlia 论文中给出了一个K-桶（K-bucket）的概念：每个节点在完成子树拆分后，要记录每个子树里面的 K 个节点。这里所说的 K 是一个常量，由使用 Kademlia的软件自行设定（比如 BitTorent 下载软件使用的 Kademlia网络，K 设定为 8）。
这个K-桶其实就是路由表。对于某个节点而言，如果以它自己为视角拆分了 n 个子树，那么它就需要维护 n 个路由表，并且每个路由表的上限是 K。
K 只是一个上限，因为有两种情况使得 K 桶的尺寸会小于 K：

1. 距离越近的子树就越小。如果整个子树可能存在的节点数小于 K，那么该子树的 K 桶尺寸永远也不可能达到 K。
2. 有些子树虽然实际上线的节点数超过 K，但是因为种种原因，没有收集到该子树足够多的节点，这也会使得该子树的 K 桶尺寸小于 K。

（以K=2举例，每个子树只保留2个节点，既：每层路由表中只保存两个节点的路由信息）

子树拆分

每个节点只维护一部分的路由表，这个路由表按照距离分层，即k-bucket1, k-bucket 2, k-bucket 3
虽然每个k-bucket中实际存在的节点数逐渐增多，但每个节点在它自己的每个k-bucket中只记录k个节点的路由信息（IP地址与端口号）。
由于节点的ID有160位，所以每个节点的路由表总共分160层，既：节点共有160个k-bucket。整个网络最多可以容纳2^160个节点，但是每个节点最多只维护160 * k 行路由信息。

K桶

3.5 Kad DHT的Peer交流机制

Kademlia算法中，每个节点只有4个指令：

• PING：测试一个节点是否在线
• STORE：要求一个节点存储一份数据
• FIND_NODE：根据节点ID查找一个节点
• FIND_VALUE：根据KEY查找一个数据，实则上跟FIND_NODE非常类似
  K-桶的刷新机制大致有如下几种，该机制保证了任意节点加入和离开都不影响整体网络

1. 主动收集节点：任何节点都可以主动发起“查询节点”的请求（对应于协议类型 FIND_NODE），从而刷新 K 桶中的节点信息
2. 被动收集节点：如果收到其它节点发来的请求（协议类型 FIND_NODE 或 FIND_VALUE），会把对方的 ID 加入自己的某个 K 桶中。
3. 探测失效节点：Kad 还是支持一种探测机制（协议类型 PING），可以判断某个 ID 的节点是否在线。因此就可以定期探测路由表中的每一个节点，然后把下线的节点从路由表中干掉。

那么一个节点加入DHT的流程就如下所描述：

1. 任何一个新来的节点（假设叫 A），需要先跟 DHT 中已有的任一节点（假设叫 B）建立连接。
2. A 随机生成一个散列值作为自己的 ID（对于足够大的散列值空间，ID 相同的概率忽略不计）
3. A 向 B 发起一个查询请求（协议类型 FIND_NODE），请求的 ID 是自己（通俗地说，就是查询自己）
4. B 收到该请求之后，会先把 A 的 ID 加入自己的某个 K 桶中。然后，根据 FIND_NODE 协议的约定，B 会找到K个最接近 A 的节点，并返回给 A。
5. A 收到这 K 个节点的 ID 之后，开始初始化自己的 K 桶。
6. 然后 A 会继续向刚刚拿到的这批节点发送查询请求（协议类型 FIND_NODE），如此往复，直至 A 建立了足够详细的路由表。

4. DHT应用举例

回到我们最初找书的案例当中，假设有1000名学生，Kademlia取m=8，K=4
场景：学生A尚未加入DHT网络，但他想从网络中获取《分布式系统设计》这本书

举例

1. 学生A加入网络，自行随机生成一个ID，例： 00000110
2. 建立路由表（细节忽略）
3. 计算《分布式系统设计》书的Hash，假设是：00010000
4. 假设学生Z的ID就是00010000，那么意味着这本书在Z那里，或者与Z临近的K个同学那里
5. 计算Z与A的距离：XOR得出结果00010110，从第5位开始不同，离范围在[2^4, 2^5)。所以Z可能在k-bucket 5中
6. A查看自己的路由表，k-bucket 5中有无Z
   · 如果有，那么直接联系Z，获取书籍
   · 如果没有，在A的k-bucket 5中随机找一个学生B（B学号的第五位一定是与Z相同的，既B与Z的距离小于2^4，距离缩短了一半以上）。B将会重复相同的流程（步骤5-6）递归。

5. 总结

• Kademlia的这种查询机制，每次要么找到，要么将搜索范围减半。网络中节点2^n个，最多只需要n步搜索即可找到目标节点。DHT网络中，通常n=160
• K-bucket的更新机制一定程度上保持了网络的活性和安全性：每个节点的K-bucket都不相同，并且只包含了少部分节点的信息
• 拓扑结构简单、距离算法也很简单
• 天生支持并发
• 节点退出无需任何操作，适合波动大的分布式网络