dht分布式散列表和kad介绍

1. 如何实现散列表

• 在散列表这种数据结构中，会包含 N 个 bucket（桶）。对于某个具体的散列表，N（桶的数量）通常是【固定不变】的。于是可以对每个桶进行编号，从 0 到 N-1。

• “桶”是用来存储“键值对”的，你可以把它通俗理解成一个动态数组，里面可以存放【多个】“键值对”。

• 当使用某个 key 进行查找，会先用某个散列函数计算这个 key 的散列值。得到散列值通常是一个整数，然后用散列值对 N（桶数）进行“取模”运算（除法求余数），就可以算出对应的桶编号。（注：取模运算是最常用的做法，但不是唯一的做法）

2. 分布式散列表 DHT

2.1 P2P 技术路线

• 中央服务器 Napster ->单点故障
• 广播 Gnutella 早期版本 ->广播风暴
• DHT

2.2 DHT 难点

• 无中心

  需要提供一系列机制来实现节点之间的通讯。

• 海量数据

  每个节点只能存储（整个系统的）一小部分数据。需要把数据【均匀分摊】到每个节点。

• 节点动态变化

  统散列表所含的【桶数】是固定不变滴。为啥捏？因为传统散列表在针对 key 计算出散列值之后，需要用“散列值”和“桶数”进行某种运算（比如：取模运算），从而得到桶的编号。如果桶的数量出现变化，就会影响到上述“取模运算”的结果，然后导致数据错乱。

• 高效查询

2.3 DHT 难点解决

• 散列算法的选择

  DHT业务数据的散列值作为Key,业务数据为Value, 所以要避免碰撞

• 同构的 nodeID 和 data key

  DHT 属于分布式系统的一种。既然是分布式系统，意味着存在【多个】节点

  很多 DHT 的设计会让“node ID”采用跟“data key”【同构】的散列值。这么搞的好处是
  1、当散列值空间足够大的时候，随机碰撞忽略不计，因此也就确保了 node ID 的唯一性 2、可以简化系统设计——比如简化路由算法

• “拓扑结构”的设计

  作为分布式系统，DHT 必然要定义某种拓扑结构；有了拓扑结构，自然就要设计某种“路由算法”。如果某个 DHT 采用前面所说的——“node ID”与“data key”【同构】——那么很自然的就会引入“Key-based routing”。

  请注意，这【不是】某个具体的路由算法，而只是某种【风格】。采用这种风格来设计路由机制，好处是：key 本身已经提供了足够多的路由信息。

• “路由算法”的权衡

  由于 DHT 中的节点数可能非常多（比如：几十万、几百万），而且这些节点是动态变化的。因此就【不可能】让每一个节点都记录所有其它节点的信息。实际情况是：每个节点通常只知道少数一些节点的信息。

  在确定了路由算法之后，还需要做一个两难的权衡——“路由表的大小”。
  路由表越大，可以实现越短（跳数越少）的路由；缺点是：（由于节点动态变化）路由表的维护成本也就越高。
  路由表数越小，其维护成本越小；缺点是：路由就会变长（跳数变多）。

• 距离算法

  某些 DHT 系统还会定义一种“距离算法”，用来计算：“节点之间的距离”、“数据之间的距离”、“节点与数据的距离”。

  写到这里，某些聪明的读者就会明白：为啥前面要强调——“node ID”与“data key”【同构】。当这两者【同构】，就可以使用【同一种“距离算法”】；反之，如果这两者不同构，多半要引入几种不同的“距离算法”。

• 数据定位

  • 保存数据

    当某个节点得到了新加入的数据（K/V），它会先计算自己与新数据的 key 之间的“距离”；然后再计算它所知道的其它节点与这个 key 的距离。

    如果计算下来，自己与 key 的距离最小，那么这个数据就保持在自己这里。否则的话，把这个数据转发给距离最小的节点。收到数据的另一个节点，也采用上述过程进行处理（递归处理）。

  • 获取数据

    当某个节点接收到查询数据的请求（key），它会先计算自己与 key 之间的“距离”；然后再计算它所知道的其它节点与这个 key 的距离。

    如果计算下来，自己与 key 的距离最小，那么就在自己这里找有没有 key 对应的 value。有的话就返回 value，没有的话就报错。否则的话，把这个数据转发给距离最小的节点。收到数据的另一个节点，也采用上述过程进行处理（递归处理）。

3. Chord 协议

• 概述

Chord 诞生于2001年。第一批 DHT 协议都是在那年涌现的，另外几个是：CAN、Tapestry、Pastry。

• 拓扑结构——环形

  当初设计“一致散列”主要是为了解决“节点动态变化”这个难点（前面有提及）。为了解决这个难点，“一致散列”把散列值空间（keyspace）构成一个【环】。对于 m 比特的散列值，其范围是 [0, 2m-1]。你把这个区间头尾相接就变成一个环，其周长是 2m。然后对这个环规定了一个移动方向（比如顺时针）。

假设有某个节点A，距离它最近的是节点B（以顺时针方向衡量距离）。那么称 B 是 A 的【继任】（successor），A 是 B 的【前任】（predecessor）。

数据隶属于【距离最小】的节点。以 m=6 的环形空间为例：
数据区间 [5,8] 隶属于节点8
数据区间 [9,15] 隶属于节点15
......
数据区间 [59,4] 隶属于节点4（注：“6比特”的环形空间，63之后是0）

• 路由机制

  • 基本路由（简单遍历）

    当收到请求（key），先看 key 是否在自己这里。如果在自己这里，就直接返回信息；否则就把 key 转发给自己的继任者。以此类推。
    　　这种玩法的时间复杂度是 O(N)。对于一个节点数很多的 DHT 网络，这种做法显然非常低效。

  • 高级路由（Finger Table）

    “Finger Table”是一个列表，最多包含 m 项（m 就是散列值的比特数），每一项都是节点 ID。 每一个节点都有个路由表

假设当前节点的 ID 是 n，那么表中第 i 项的值是：successor( (n + 2i) mod 2m ) 当收到请求（key），就到“Finger Table”中找到【最大的且不超过 key】的那一项，然后把 key 转发给这一项对应的节点。有了“Finger Table”之后，时间复杂度可以优化为 O(log N)。`跳跃式查询`

• 节点的加入

  • 任何一个新来的节点（假设叫 A），需要先跟 DHT 中已有的任一节点（假设叫 B）建立连接。
  • A 随机生成一个散列值作为自己的 ID（对于足够大的散列值空间，ID 相同的概率忽略不计）
  • A 通过跟 B 进行查询，找到自己这个 ID 在环上的接头人。也就是——找到自己这个 ID 对应的“继任”（假设叫 C）与“前任”（假设叫 D）
  • 　接下来，A 需要跟 C 和 D 进行一系列互动，使得自己成为 C 的前任，以及 D 的继任。这个互动过程，大致类似于在双向链表当中插入元素

• 节点的【正常】退出

  • 如果某个节点想要主动离开这个 DHT 网络，按照约定需要作一些善后的处理工作。比如说，通知自己的前任去更新其继任者……
    　　这些善后处理，大致类似于在双向链表中删除元素

• 节点的【异常】退出

  • 作为一个分布式系统，任何节点都有可能意外下线（也就是说，来不及进行善后就挂掉了）

    假设 节点A 的继任者【异常】下线了，那么 节点A 就抓瞎了。咋办捏？为了保险起见，Chord 引入了一个“继任者候选列表”的概念。每个节点都用这个列表来包含：距离自己最近的 N 个节点的信息，顺序是【由近到远】。一旦自己的继任者下线了，就在列表中找到一个【距离最近且在线】的节点，作为新的继任者。然后 节点A 更新该列表，确保依然有 N 个候选。更新完“继任者候选列表”后，节点A 也会通知自己的前任，那么 A 的前任也就能更新自己的“继任者候选列表”。

4. Kademlia（Kad）协议

• 拓扑结构——二叉树

  • 散列值的预处理

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

    1. 先把 key 以二进制形式表示。
    2. 把每一个 key 缩短为它的【最短唯一前缀】。

- 散列值的映射

    完成上述的预处理后，接下来的映射规则是：

    1. 先把 key 以二进制形式表示，然后从高位到低位依次处理。
    2. 二进制的第 n 个数位就对应了二叉树的第 n 层
    3. 如果该位是1，进入左子树，是0则进入右子树（这只是人为约定，反过来处理也可以）
    4. 全部数位都处理完后，这个 key 就对应了二叉树上的某个【叶子】

• 距离算法——异或（XOR）

  接下来要聊的是 Kad 最精妙之处——采用 XOR（按比特异或操作）算法计算 key 之间的“距离”。这种搞法使得它具备了类似于“几何距离”的某些特性（下面用 ⊕ 表示 XOR）

  (A ⊕ B) == (B ⊕ A)	XOR 符合“交换律”，具备对称性。相比之下，Chord 的距离算法不对称
  (A ⊕ A) == 0	反身性，自身距离为零
  (A ⊕ B) > 0	【不同】的两个 key 之间的距离必大于零
  (A ⊕ B) + (B ⊕ C) >= (A ⊕ C)	三角不等式

• 路由机制

  • 二叉树的拆分

    对每一个节点，都可以【按照自己的视角】对整个二叉树进行拆分。

    拆分的规则是：先从根节点开始，把【不包含】自己的那个子树拆分出来；然后在剩下的子树再拆分不包含自己的下一层子树；以此类推，直到最后只剩下自己。

    Kad 默认的散列值空间是 m=160（散列值有 160 比特），因此拆分出来的子树【最多】有 160 个（考虑到实际的节点数【远远小于】2160，子树的个数会明显小于 160）。

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

• K-桶（K-bucket）

  每个节点在完成子树拆分后，只需要知道每个子树里面的一个节点，就足以实现全遍历。但是考虑到健壮性（请始终牢记：分布式系统的节点是动态变化滴），光知道【一个】显然是不够滴，需要知道【多个】才比较保险。

  所以 Kad 论文中给出了一个“K-桶（K-bucket）”的概念。也就是说：每个节点在完成子树拆分后，要记录每个子树里面的 K 个节点。这里所说的 K 值是一个【系统级】的常量。由使用 Kad 的软件系统自己设定（比如 BT 下载使用的 Kad 网络，K 设定为 8）。

  K 桶其实就是【路由表】。对于某个节点而言，如果【以它自己为视角】拆分了 n 个子树，那么它就需要维护 n 个路由表，并且每个路由表的【上限】是 K。说 K 只是一个【上限】，是因为有两种情况使得 K 桶的尺寸会小于 K。

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

• K-桶（K-bucket）的刷新机制

  • 主动收集节点　 　

    任何节点都可以主动发起“查询节点”的请求（对应于协议类型 FIND_NODE），从而刷新 K 桶中的节点信息

  • 被动收集节点

    如果收到其它节点发来的请求（协议类型 FIND_NODE 或 FIND_VALUE），会把对方的 ID 加入自己的某个 K 桶中。

  • 探测失效节点

    Kad 还是支持一种探测机制（协议类型 PING），可以判断某个 ID 的节点是否在线。因此就可以定期探测路由表中的每一个节点，然后把下线的节点从路由表中干掉。

• “并发请求”与“α 参数”

  “K桶”的这个设计思路【天生支持并发】。因为【同一个】“K桶”中的每个节点都是平等的，没有哪个更特殊；而且对【同一个】“K桶”中的节点发起请求，互相之间没有影响（无耦合）。

  所以 Kad 协议还引入了一个“α 参数”，默认设置为 3，使用 Kad 的软件可以在具体使用场景中调整这个 α 因子。

  当需要路由到某个“子树”，会从该子树对应的“K桶”中挑选【α 个节点】，然后对这几个节点【同时】发出请求。这么做有啥好处捏？俺在本文末尾聊“性能”和“安全性”时会具体介绍。

• 节点的加入

  • 任何一个新来的节点（假设叫 A），需要先跟 DHT 中已有的任一节点（假设叫 B）建立连接。
  • A 随机生成一个散列值作为自己的 ID（对于足够大的散列值空间，ID 相同的概率忽略不计）
  • A 向 B 发起一个查询请求（协议类型 FIND_NODE），请求的 ID 是自己（通俗地说，就是查询自己）
  • B 收到该请求之后，（如前面所说）会先把 A 的 ID 加入自己的某个 K 桶中。然后，根据 FIND_NODE 协议的约定，B 会找到【K个】最接近 A 的节点，并返回给 A。（B 怎么知道哪些节点接近 A 捏？这时候，【用 XOR 表示距离】的算法就发挥作用啦）
  • A 收到这 K 个节点的 ID 之后，（仅仅根据这批 ID 的值）就可以开始初始化自己的 K 桶。
  • 然后 A 会继续向刚刚拿到的这批节点发送查询请求（协议类型 FIND_NODE），如此往复（递归），直至 A 建立了足够详细的路由表。

• 节点的退出

  与 Chord 不同，Kad 对于节点退出没有额外的要求（没有“主动退出”的说法）。
  　　所以，Kad 的节点想离开 DHT 网络不需要任何操作（套用徐志摩的名言：悄悄的我走了，正如我悄悄的来）

5. 参考资料

• https://colobu.com/2018/03/26/distributed-hash-table/
• https://program-think.blogspot.com/2017/09/Introduction-DHT-Kademlia-Chord.html