分布式散列表协议 —— Kademlia 详解

概述

散列表是一种由键值对组成的列表。你可以把它看作一部字典,只需要经过少数的几步就能通过某种信息找到需要的信息,查询速度很快。

分布式散列表就是由一个网络内所有的节点共同维护的一种散列表,这类散列表通常十分巨大,或者压根不可能由单个机器或者某机组机器维护。

Kademlia 协议由 Petar Maymounkov 和 David Mazières 设计。它可以在容易出错的环境(比如节点会毫无征兆地下线)中建立一张分布式散列表。

为什么需要分布式散列表?

当散列表不是很大的时候只需要存储在一个机器上即可,但是有时哈希表会十分大,大到不是几组机器能够维护。亦或者有些哈希表是无法进行集中式存储的,比如 BitTorrent 的 DHT 网络。

以 BitTorrent 网络为例,每个文件都有一个文件 ID,文件 ID 是一个长度为 160 的二进制数。每个 BitTorent 节点也会有一个相同长度的节点 ID。文件 ID 和 节点 ID 之间是“多对多”的关系,想使用散列表集中式地存储这些信息几乎是不可能的,原因如下。

  • 文件 ID 的取值空间十分巨大,即 $2^{160} \approx 1.46 \times 10^{48}$。这个值有多大?全球一共有 70 亿人,每个人每秒下载 1,000,000 个文件, 大概需要 $6 \times 10^{16}$ 亿年才能下载完。
  • 节点 ID 的取值空间也和文件 ID 的取值空间同样巨大。
  • 节点 ID 和文件 ID 之间是多对多的关系,我们假设每个节点指对应两个文件 ID,那么共需要存储 $2^{161}$ 个项目,这几乎不可能。

由此可见,仅从空间成本上来看就是不可能的事情,更不要说节点随时会下线和故障等头疼的问题。

分布散列表是由所有节点共同维护一个散列表,每个节点维护一部分,这样网络内就形成了一张巨大的散列表。

前置知识

Kademlia 协议要求每个节点都有一个长度为 160 bit 的节点 ID。

”异或“距离

Kademlia 协议使用”异或“算法来计算两个 ID 之间的距离,下面是一个例子。

假设节点ID 是 4 位二进制。

A 的 ID 为 0101
B 的 ID 为 1111

那么两者的距离就是 1010,换算成十进制就是 9。

    0 1 0 1
⊕  1 1 1 1
--------------
    1 0 1 0

二进制二叉树

每个节点都有一个长度固定的节点 ID,那么就可以将系统中的全部节点放到一个二叉树内,下面是一个例子。

假设节点 ID 的长度为 3 位二进制,则二叉树的每个叶子节点都代表了一个节点。

             *
           /   \
          /     \
      0  /       \  1
        /         \
       /           \
      *              *
    /  \           /  \
 0 /    \ 1     0 /    \ 1
  /      \       /      \
 O        O      O       O

信息的存储和查询

在 Kademlia 协议中,每个信息都有一个唯一的 ID,而发布这个信息的节点会将这个信息存储到距离距离信息 ID 最近的若干的节点中。可以认为是用全部已知节点 ID 和信息 ID 进行异或运算得到已知节点和信息之间的逻辑距离,然后选出若干个最近的节点,将信息存储到这些节点上。

查询某个信息时,过程可以认为是用全部的已知节点 ID 和被查询的信息 ID 进行异或运算得到已知节点和信息的逻辑距离,然后选择出若干的最近的节点,然后向这些节点发起信息查询请求。

路由表

Kademlia 协议依靠路由表和其它节点通信,下面介绍一下路由表的建立过程。

前面我们提到网络中的节点都可以放到同一个二进制二叉树中,而路由表的制作过程实际上就是二叉树的拆分过程。我们假设节点 ID 为 11(二进制),看看二叉树的拆分过程。

首先将不包含自身的最大子树取出。

+--------------+
|             *|
|           /  | \
|          /   |  \
|      0  /    |   \  1
|        /     |    \
|       /      |     \
|      *       |       *
|    /  \      |     /  \
| 0 /    \ 1   |  0 /    \ 1
|  /      \    |   /      \
| O        O   |  O        O
+--------------+

重复上述步骤,直到剩余的部分只有自己这一个节点。本例中只需要拆分两次。

+--------------+
|            * |
|           /  | \
|          /   |  \
|      0  /    |   \  1
|        /     |    \
|       /      |     \
|              | +-------+
|      *       | |      *|
|    /  \      | |    /  |\
| 0 /    \ 1   | | 0 /   | \ 1
|  /      \    | |  /    |  \
| O        O   | | O     |  O
+--------------+ +-------+

此时我们从左到右一共有了三颗子树,其中第三颗子树只有我们自己。此时三颗子树就对应了三个 K-桶(K-Bucket)。

编号覆盖前缀距离区间已经联系上的节点
1110
2101
30?[2, 3]
K-桶列表

这就是我们的路由表了,此时我们可以通过下列步骤查询距离某个 key 最近的节点,假设我们要寻找的 key 为 00(二进制),我们自己的节点 ID 为 11(二进制)。

  1. 使用异或运算计算出自身和目标 key 的距离,计算结果为 2(十进制)。
  2. 查询 K-桶的距离区间,发现 3 号 K-桶中的节点距离目标 key 最近。
  3. 按照某种策略(见后文)选出三号 K-桶中的某个节点(假设为节点 01),然后向其发送查询请求。
  4. 节点 01 也会使用相同的方式建立自己的路由表,收到查询请求后它会执行下列步骤。
    1. 使用异或运算计算出自身和目标 key 的距离,显然距离为 1(十进制)。
    2. 查询自身的 K-桶的距离区间,发现某个 K-桶的距离区间恰好为 1,并且此 K-桶内只有一个节点。
    3. 节点 01 发现自己已经存储了节点 00 的联系信息,于是将联系信息返回给节点 11。
  5. 节点 00 收到了节点 01 的响应,得知了节点 00 的联系信息,查询结束。

这只是一个简单的例子,有很多错误,还有很多情况没有考虑到,但已经能够体现查询原理了。

三个协议过程

Kademlia 由三个 RPC 过程组成,分别为 PING、STORE、FIND_NODE 和 FIND_VALUE。

RPC(Remote Procedure Call),即远程过程调用。可以简单地认为是一方向另一方发送某个指令,接收方执行对应的指令并将结果返回给发送方。

PING

用来测试节点是否在线。

STORE

请求目标节点存储一个键值对。

FIND_NODE

查询距离目标键值最近的若干的节点。

这个才是重点,本文将在这里详细描述查询过程。

此过程的参数是一个 160 bit 的节点 ID,即要查询目标节点的 ID。此过程结束后返回若干个三元组 < IP, UDP port, Node ID >,每个三元组都是某个节点的联系信息。

当一个节点收到 FIND_NODE 请求时,它会查询自己的 K-桶列表并返回 k 个距离目标节点最近的节点,如果此节点已知的节点不足 k 个则返回全部已知的节点。

当一个节点想要查询某个节点时,它会执行下列步骤。

  1. 查询自己的 k 桶列表并选出若干个距离目标最近的节点,然后向这些节点发送 FIND_NODE 请求。
  2. 当这些 FIND_NODE 请求返回时我们会得到许多个节点,记录这些新的节点。
  3. 从新得到的节点中挑选出若干个距离目标节点更近(相对于所有旧的节点)的节点,向这些节点发送 FIND_NODE 请求。如果没有找到距离更近的节点则查询结束
  4. 重复步骤 2,3,直到查询结束。

上面的步骤依然是简化的版本,但步骤已经完整了,只是跳过了一些细节,比如每次选择多少个节点发送请求。

FIND_VALUE

基本和 FIND_NODE 差不多,只不过如果收到请求的节点存有被请求的值得时候应该将其值返回。

信息的再发布

有两种情况可能会导致已经存在的信息却不能被查询到。

  • 存储了这些信息的全部节点下线。
  • 有许多距离更近的节点加入到了网络中,查询信息时则会向这些节点发起请求,而不是距离更远的但是之前已经存储了信息的节点。

为了缓解这一情况,每个节点会以一小时为周期,每个周期内重新发布一次信息。但是这么做的代价很大。假设有 A 个节点存储了同一个信息,那么每个周期内,每个节点都会先发起一次 FIND_NODE 请求,然后每个节点都会向其它最多 A-1 个节点发起 STORE 请求。这样网络中就会充斥着大量的请求,并且很多是无用的请求。

好在我们有优化方法,即当某个节点在本周期内收到 STORE 请求时,下一个周期内就不进行对该信息的再发布。

典型应用

BitTorrent 协议簇中的分布式散列表(DHT)协议及由此构成的属于 BitTorrent 网络内部的 DHT 网络。正是有了 DHT 网络,我们才能够在没有 .torrent 文件的情况下凭借磁力链接下载文件。我们有时候在 BitTorrent 客户端中粘贴一段十六进制字符串就能进行下载也是 DHT 网络的功劳。

参考资料

Kademlia: A Peer-to-peer information system based on the XOR Metric

本文作者:ADD-SP
本文链接https://www.addesp.com/archives/5338
版权声明:本博客所有文章除特别声明外,均默认采用 CC-BY-NC-SA 4.0 许可协议。
暂无评论

发送评论 编辑评论


				
上一篇
下一篇