阅读量:

DHT 详解

DHT 介绍

DHT（分布式哈希表）是一种用于在分布式环境中存储和查找数据的技术。它基于哈希函数将数据映射到一个大型的分布式网络中的节点上。每个节点负责维护一部分数据的索引，并通过协作来实现高效的数据存储和查找。

DHT具有以下几个核心概念：

哈希函数：DHT使用哈希函数将数据键（key）映射到整个网络中的特定节点。哈希函数将任意长度的输入映射为固定长度的输出，通常是一个数字或字符串。
节点：DHT网络由多个节点组成，每个节点都有一个唯一的标识符（通常是一个哈希值）和一个网络地址。节点可以加入和离开网络，并且负责存储和处理与其标识符相关联的数据。
数据存储和定位：当一个节点要存储数据时，它会将数据的键通过哈希函数转换为一个标识符，并找到该标识符在网络中最接近的节点。该节点负责存储该数据项。当需要查找数据时，节点通过哈希函数找到负责该数据项的节点，并从该节点获取数据。
路由表：每个节点都维护一个路由表，其中包含其他节点的信息。路由表根据标识符的空间划分为不同的区域，使节点能够快速定位到其他节点。通过路由表，节点可以有效地进行消息传递和数据查找。

DHT的优点包括高度可扩展性、去中心化、容错性和灵活性。它可以应用于各种分布式系统场景，如对等网络（P2P）文件共享、内容分发网络（CDN）、分布式存储系统等。

DHT是一个广泛的概念，有许多不同的实现和变体，例如Chord、Kademlia、CAN等。每个实现方式都有其独特的算法和协议，但它们共享相似的基本原则和目标。

Chord 算法

基本要素

Chord 算法的核心在于环形链表和跳表。Chord算法将节点 IP 和资源 Key 使用统一用某个哈希函数（如SHA-1）计算出一个 m 位的 ID 号。将计算出的 ID 号对 2^m 取模后按顺序排列在环上，该环被称为 identifier space。

对于一个资源 Key ，用哈希函数计算后的 ID 号为 k，该 Key 由环上第一个 ID 号大于 k 的节点负责维护这个资源。

环上的每个节点都维护着自身的后继节点，如下图中，N1 节点保存着 N8 节点的信息，N8 节点保存着 N14 节点的信息，以此类推就构成了一个环形链表结构。

如下图， K10 这个资源就由 N14 这个节点进行负责（14 > 10）。

资源定位

当节点想要查询一个节点的位置时，根据现有结构，他需要依次遍历每一个后继节点，直到查找到资源为止。

如下图中，节点 N8 想要查找到资源 K54，那么它需要执行 N8 -> N14 -> N21 -> N32 -> N38 -> N42 -> N51 -> N56才能找到 N54 对应的资源。

查询优化

为了解决链表结构查询资源缓慢的问题，Chord 引入了前置节点（Chord 环变成了环形双向链表）和finger table，finger table 实际上就是一个跳表。

在 finger table 中，在每个节点 N 上都维护了最多有 m 项（m为 ID 的位数）的路由表（称为 finger table），用来定位资源。

如图所示，节点 N8 存储了节点 N14、N21、N32、N42的节点信息。

节点 N8 需要查询资源 K54 的信息时，将 K54 和自身跳表中的信息进行比较，发现 N42 是距离 K54 距离最近的节点，因此 N8 会直接找 N42 去请求数据，N42 再去重复下面的操作，直到找到 K54 为止。

数据冗余

在上面的介绍中，资源 k 只会被存储在单一节点 N 上。这种存储方式会导致当节点 N 宕机时，资源 k 无法被其他节点查询到。

为了解决这种问题，资源数据需要进行冗余存储，以防止节点宕机。

其冗余策略为，节点 N 在存储资源时，不仅要本机存储，同时也会存放在自己的后继节点中。只存放在后继节点的话安全性依然有不足的情况，因此还可在自身 finger table 中选择节点进行数据存储。

节点变更

当节点需要加入时，新节点必须要知道整个 Chord 网络中的一个节点信息，新节点和已知节点进行通信，用以知道自身应该加入的位置（参考链表增加节点的流程）。

当节点需要退出时，需要将自身存储资源移交给前置和后继节点。

Kademlia 算法

Kademlia 算法（后面简称 Kad）的核心在于二叉树搜索。Kad 算法中，资源 ID 和节点 ID 同样是统一编码，在 Kad 算法中 ID 长度为 160bit，可容纳 2 ^ 160 - 1 个资源，这个数量级基本上是整个宇宙中原子的数量。

在 Kad 算法中使用 XOR （异或）来计算节点 Key 和节点 ID 之间的逻辑距离。

节点树

在 Kad 算法中，所有节点都可被当作一个二叉树的叶子节点，每一个叶子节点的位置由ID号来确定，如图所示：

节点树拆分

每一个节点都可以从自己的视角来对二叉树进行拆分，把这颗二叉树分解为一系列连续的，不包含自己的子树。最高层的子树，由整颗树不包含自己的树的另一半组成；下一层子树由剩下部分不包含自己的一半组成；依此类推，直到分割完整颗树。

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

下图中，以 1000 节点视角做拆分，可把整个二叉树拆分为四颗子树：

Kad 网络中默认的散列值空间是 m=160（散列值有160bit），所以拆分以后的子树最多有160个。而考虑到实际网络中节点个数远远没有2^160个，所以子树的个数明显小于160个。对于每个节点，当按照自己的视角对二叉树进行拆分以后，会得到n个子树。对于每个子树，如果都分别知道里面1个节点，那么就可以利用这n个节点进行递归路由，从而可以达到整个二叉树的任何一个节点。在拆分子树时，如果 n 选择的较大，会导致大量的桶为空，因为找不到合适匹配的节点；如果n选择的较小，则不能精确匹配节点，一般而言，n 为 log(N)，N 为整个 Kad 网络中的节点数量。

但是考虑到健壮性（节点可能宕机或者退出），光知道一个显然是不够的，需要知道多个才比较保险。因此 Kad 论文中给出了一个K-桶（K-bucket）的概念：每个节点在完成子树拆分后，要记录每个子树里面的 K 个节点。这里所说的 K 值是一个系统级的常量，一般为 20。K桶实际上就是一个路由表，一个 K桶就是一张路由表，K桶中路由表的条数最大为 K。

Kad 依赖下面的方式选择 K 桶中的 K 个节点：

当 K 桶中容量未满时，只要属于这个 K 桶的节点都加入 K 桶；
当 K 桶已满，且 K 桶中存在离线节点，则踢出离线节点，将新节点加入 K 桶；
当 K 桶中全都是活跃节点，则将新加入节点保留在额外的附属列表中（作为缓存），当 K 桶中有节点停止响应时，才从附属列表取出节点加入 K 桶。

协议消息

Kademlia协议共有四种消息。

PING: 测试节点是否仍然在线；
STORE: 请求节点存储一个键值对；
FIND_NODE: 消息请求的接收者将返回自己桶中离请求键值最近的K个节点；
FIND_VALUE: 与FIND_NODE一样，不过当请求的接收者存有请求者所请求的键的时候，它将返回相应键的值。

每一个RPC消息中都包含一个发起者加入的随机值，这一点确保响应消息在收到的时候能够与前面发送的请求消息匹配。

资源存储与查询

存储资源

节点在存储资源时，需要在网络中找到最多 k 个距离最近的节点，向这些节点发起 STORE 请求，由这些节点负责资源的存储。在查找这 k 个距离最近节点时， Kad 网络采用递归查询的方式进行查询。

首先初始节点从距离最近的 k 桶中选择 α 个（一般为 3）距离资源 ID 最近的节点，向这 α 个节点发起 FIND_NODE 请求；
收到 FIND_NODE 请求的节点会从查询自身 k 桶中距离节点 ID 比自身更近的所有节点，如果没有比自身更近的节点，则返回空；
初始节点收到 FIND_NODE 响应后将它加入列表中，然后再从已知最近的节点中选择尚未发送给 FIND_NODE 消息的节点继续发送 FIND_NODE 节点信息，直到再没有新节点返回为止；
然后再从已知的所有节点中选出 k 个最近的节点用以存储资源信息。

查询资源

进行 FIND_VALUE 时和 FIND_NODE 类似，不过在 FIND_VALUE 的过程中，如果当前节点有该资源 ID 的信息，那么则直接返回资源信息。

由于在 Kad 网络中不能保证强数据一致性，因此会导致返回结果不同，因此下面有几种方式用以增强数据一致性：

查询数据时选择半数相同的数据作为返回值；
存储数据时带上时间，查询数据时选择最新的数据作为返回结果。

参考：