分布式哈希表DHT

发表评论
391 views

哈希表 是一种数据结构，它以键值对来存储信息。

在分布式哈希表(distributed hash tables，简称 DHT)中，数据分布在计算机网络中，以便有效地协调以实现节点之间的有效访问和查找。

DHT 的主要优点在于去中心化、容错和可扩展性。节点无需中心协调，系统能够可靠地运作，即使节点发生故障或下线。并且，DHT 能够扩展以容纳数百万个节点。基于这些特性，使得 DHT 比中央服务器的结构更具有弹性。

分布式散列表本质上强调以下特性：

  • 离散性：构成系统的节点并没有任何中央式的协调机制。
  • 伸缩性：即使有成千上万个节点，系统仍然应该十分有效率。
  • 容错性：即使节点不断地加入、离开或是停止工作，系统仍然必须达到一定的可靠度。

DHT的结构可以分成几个主要的组件。其基础是一个抽象的键空间（keyspace），160位长的字符串集合。键空间分区（keyspace partitioning）将键空间分区成数个，并指定到在此系统的节点中。

延展网络则连接这些节点，并让他们能够借由在键空间内的任一值找到拥有该值的节点。

基本步骤

文件名称为filename且内容为data

存储：

  1. 键值k=SHA(filename)

  2. put(k,data)会在延展网络中被路由，抵达在键空间分区中被指定负责存储关键值k的节点（一般是多个）

  3. 节点保存(k,data)

取：

  1. 键值k=SHA(filename)

  2. get(k)会取找到存储关键值k的节点

  3. 此节点会相应请求，回传数据

路由算法的特点

基本上，就是一种映射key和节点的算法以及路由的算法。

其一为保证任何的路由路径长度必须尽量短，因而请求能快速地被完成； 其二为任一节点的邻近节点数目（又称最大节点度（Degree (graph theory)））必须尽量少，因此维护的花费不会过多。

Kademlia算法

（这个算法感觉比较像递归分块，把网络分成很多部分，然后与每个部分的部分节点保持联系）

Kademlia是一种通过 DHT 的协议算法，它是由Petar和David在2002年为P2P网络而设计的。Kademlia规定了网络的结构，也规定了通过节点查询进行信息交换的方式。 Kademlia网络节点之间使用UDP进行通讯。参与通讯的所有节点形成一张虚拟网（或者叫做覆盖网）。这些节点通过一组数字（或称为节点ID）来进行身份标识。节点ID不仅可以用来做身份标识，还可以用来进行值定位（值通常是文件的散列或者关键词）。

当我们在网络中搜索某些值（即通常搜索存储文件散列或关键词的节点）的时候，Kademlia算法需要知道与这些值相关的键，然后逐步在网络中开始搜索。每一步都会找到一些节点，这些节点的ID与键更为接近，如果有节点直接返回搜索的值或者再也无法找到与键更为接近的节点ID的时候搜索便会停止。

这种搜索值的方法是非常高效的：与其他的分布式哈希表的实现类似，在一个包含n个节点的系统的值的搜索中，Kademlia仅访问O(log(n))个节点。

Kademlia简称为Kad,它使用了一个精妙的算法，来计算节点之间的"距离" (这里的距离不是地理空间的距离，而是路由的跳数)，这个算法就是XOR操作(异或)，因为这个操作和距离的计算类似：

  • (A ⊕ B) == (B ⊕ A): XOR 符合“交换律”，具备对称性。A和B的距离从哪一个节点计算都是相同的。
  • (A ⊕ A) == 0: 反身性，自己和自己的距离为零。
  • (A ⊕ B) > 0: 两个不同的 key 之间的距离必大于零。
  • (A ⊕ B) + (B ⊕ C) >= (A ⊕ C): 三角不等式, A经过B到C的距离总是大于A直接到C的距离。（关键）

Kademlia使用160位的哈希算法（比如 SHA1），完整的 key 用二进制表示有160位，这样可以容纳2160个节点，可以说是不计其数了。

Kademlia把 key 映射到一个二叉树，每一个 key 都是这个二叉树的叶子。

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

对每一个节点，都可以按照自己的视角对整个二叉树进行拆分成最多160个子树。

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

Kademlia默认的散列值空间是 m=160（散列值有 160 bit），因此拆分出来的子树有 160 个。

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

K-桶

每个节点在完成子树拆分后，只需要知道每个子树里面的一个节点，就足以实现全遍历。但是考虑到健壮性（节点可能宕机或者退出），光知道一个显然是不够的，需要知道多个才比较保险。

所以 Kademlia论文中给出了一个K-桶（K-bucket）的概念。

Kademlia中使用了名为K-桶的概念来储存其他(临近)节点的状态信息，这里的状态信息主要指的就是节点ID, IP, 和端口。对于160bit的节点ID，就有160个K-桶，对于每一个K-桶i，它会储存与自己距离在区间 [2^i, 2^(i+1)) 范围内的节点的信息，每个K-桶中储存有k个其他节点的信息，在BitTorrent的实现中，k的取值为8。

下表反映了每个K-桶所储存的信息

K-桶 储存的距离区间 储存的距离范围 储存比率
0 [1, 2) 1 100%
1 [2, 4) 2-3 100%
2 [4, 8) 4-7 100%
3 [8, 16) 8-15 100%
4 [16,32) 16-31 75%
5 [32, 64) 32-63 57%
10 [1024, 2048) 1024-2047 13%
i [2^i, 2^i+1) / 0.75i-3

放在节点树上，即每个节点都更倾向于储存与自己距离近的节点的信息，形成储存的离自己近的节点多, 储存离自己远的节点少的局面。

对于一个节点而言，K-桶就代表着节点树上那些未知的节点(其实除了自己都是未知的)构成的子树，160个K桶分别是具有1到160层的子树，由小至大。对于节点ID，160个K-桶分别储存着节点ID前0到159个bit和自己一致的节点。

K-桶中的条目(其他临近节点的状态信息)排序的，每当收到一个消息(如查询)时，就要更新一次K桶。 首先计算自己与对方的距离，然后储存到对应的K-桶中，但如果K-桶已满(前面提到每个K-桶储存有k=8个条目)，则会倾向放弃储存，继续保持旧的节点信息(如果还有效的话). 除了距离外，Kademlia更倾向于与在线时间长，稳定的节点建立联系。

这是因为实践证明，累积在线时间越长的节点越稳定，越倾向于继续保持在线，即节点的失效概率和在线时长成反比。

这样还可以在一定程度上抵御攻击行为。因为当大量恶意的新节点涌入时，大家都会选择继续保持旧的节点信息，而不是接受新的。

除此之外，还需要定时检查K-桶中的节点是否任然在线，及时删去已失效节点。

K-桶其实就是路由表。对于某个节点而言，如果以它自己为视角拆分了 n 个子树，那么它就需要维护 n 个路由表，并且每个路由表的上限是 K。

四种消息

Kademlia协议共有四种消息。

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

因为每个节点都更倾向于储存距自己近的节点的信息，而整个网络又是一个二叉树，因此每次查询都会至少取得距离减半的结果，对于有N个节点的网络，至多只需要 log2N 次查询。

当进行 FIND VALUE 操作时，查询操作是类型的，每份数据都有一个同样是160bit的键，每份数据都倾向于储存在与键值距离较近的节点上。

当上传者上传一份数据时，上传者首先定位几个较为接近键值的节点，用STORE操作要求他们储存这份数据。

储存有数据的节点，每当发现比自己与键值距离更为接近的节点时，便将数据复制一份到这个节点上。

当一个新节点欲加入网络时，只需找到一个已在网络中的节点，借助它对自己的节点ID进行一次常规查询即可，这样便完成了对自己信息的广播，让距自己较近的节点获知自己的存在。而离开网络不必执行任何操作，一段时间后，你的信息会自动地从其他节点被删除。

定位节点

节点查询可以异步进行，也可以同时进行，同时查询的数量由α表示，一般是3。

（像dns的迭代查询方法）

  1. 由查询发起者从自己的k-桶中筛选出若干距离目标ID最近的节点，并向这些节点同时发送异步查询请求；
  2. 被查询节点收到请求之后，将从自己的k-桶中找出自己所知道的距离查询目标ID最近的若干个节点，并返回给发起者；
  3. 发起者在收到这些返回信息之后，更新自己的结果列表，再次从自己所有已知的距离目标较近的节点中挑选出若干没有请求过的，并重复步骤1；
  4. 上述步骤不断重复，直至无法获得比查询者当前已知的k个节点更接近目标的活动节点为止。
  5. 在查询过程中，没有及时响应的节点将立即被排除；查询者必须保证最终获得的k个最节点都是活动的。

举个例子：

节点 0要call节点13：

正常情况下，节点0拥有4个K-桶，K-桶0存的节点1，K-桶1存节点2-3，K-桶2存节点4-7，K-桶3存节点8-15

假设与节点0向连的是节点1，2，4，8 计算：1 XOR 13 = 12，2 XOR 13 = 15，4 XOR 13 = 9，8 XOR 13 = 5

选XOR结果最小的节点来连接，故，0和8连接

与节点8连接的是节点9，10，12 计算：9 XOR 13 = 4，10 XOR 13 = 7，12 XOR 13 = 1，

选择12与13相连

（实际是迭代的过程，图画的比较像递归查询）

定位资源

通过把资源信息与键进行映射，资源即可进行定位，哈希表是典型的用来映射的手段。由于以前的STORE消息，存储节点将会有对应STORE所存储的相关资源的信息。定位资源时，如果一个节点存有相应的资源的值的时候，它就返回该资源，搜索便结束了，除了该点以外，定位资源与定位离键最近的节点的过程相似。

考虑到节点未必都在线的情况，资源的值被存在多个节点上（节点中的K个），并且，为了提供冗余，还有可能在更多的节点上储存值。储存值的节点将定期搜索网络中与储存值所对应的键接近的K个节点并且把值复制到这些节点上，这些节点可作为那些下线的节点的补充。另外还有缓存技术。

加入网络
  1. 新节点A必须知道某个引导节点B，并把它加入到自己相应的K-桶中。
  2. 生成一个随机的节点ID,直到离开网络，该节点会一直使用该ID号。
  3. 向B（A目前知道的唯一节点）发起一个查询请求（FIND_NODE），请求的ID是自己（就是查询自己）
  4. B收到该请求之后，会先把A的ID加入自己的相应的 K-桶中。并且根据 FIND_NODE 请求的约定，B会找到K个最接近 A 的节点，并返回给 A
  5. A收到这K个节点的ID之后，把他们加入自己的 K-桶
  6. 然后A会继续向刚刚拿到的这批节点(还未发送过请求的节点)发送查询请求（协议类型 FIND_NODE），如此往复，直至A建立了足够详细的路由表。
  7. 这种“自我定位”将使得Kademlia的其他节点（收到请求的节点）能够使用A的ID填充他们的K-桶，同时也能够使用那些查询过程的中间节点来填充A的K-桶。这已过程既让A获得了详细的路由表，也让其它节点知道了A节点的加入
在p2p网络中的应用

Kademlia可在文件分享网络中使用。由于没有中央服务器存储文件的索引，这部分工作就被平均地分配到所有的客户端中去：

假如一个节点希望分享某个文件，它先把文件的内容散列成一组数字，这组散列数字必须和节点ID有同样的长度。

然后，该节点便在网络中搜索ID值与文件的散列值相近的节点，并把它自己的IP地址存储在那些搜索到的节点上，也就是说，它把自己作为文件的源进行了发布。正在进行文件搜索的客户端将使用Kademlia协议来寻找网络上ID值与希望寻找的文件的散列值最近的那个节点，然后取得存储在那个节点上的文件源列表。

由于一个键可以对应很多值，即同一个文件可以有多个源，每一个存储源列表的节点可能有不同的文件的源的信息，这样的话，源列表可以从与键值相近的K个节点获得。

文件名的搜索可以使用关键词来实现，文件名可以分割成连续的几个关键词，这些关键词都可以散列并且可以和相应的文件名和文件散列储存在网络中。搜索者可以使用其中的某个关键词，联系ID值与关键词散列最近的那个节点，取得包含该关键词的文件列表。由于在文件列表中的文件都有相关的散列值，通过该散列值就可利用上述通常取文件的方法获得要搜索的文件。