186

任何人都可以解释 DHT 的工作原理吗？

没什么太重的，只是基础。

4

4 回答 4

252

好的，它们基本上是一个非常简单的想法。DHT 为您提供类似字典的界面，但节点分布在网络中。DHT 的诀窍是通过散列该键找到存储特定键的节点，因此实际上您的哈希表存储桶现在是网络中的独立节点。

这提供了很多容错性和可靠性，并可能带来一些性能优势，但它也引发了很多令人头疼的问题。例如，当一个节点因故障或其他原因离开网络时会发生什么？以及当节点加入时如何重新分配密钥以使负载大致平衡。想一想，无论如何，您如何均匀分配密钥？当一个节点加入时，如何避免重新散列所有内容？（请记住，如果您增加存储桶的数量，您必须在普通哈希表中执行此操作）。

解决其中一些问题的一个示例 DHT 是由 n 个节点组成的逻辑环，每个节点负责 1/n 的密钥空间。将节点添加到网络后，它会在环上找到一个位于其他两个节点之间的位置，并负责其兄弟节点中的一些密钥。这种方法的美妙之处在于环中的其他节点都不会受到影响。只有两个兄弟节点必须重新分配密钥。

例如，假设在三节点环中，第一个节点的密钥为 0-10，第二个节点为 11-20，第三个节点为 21-30。如果第四个节点出现并将自己插入节点 3 和 0 之间（记住，它们在一个环中），它可以负责 3 的一半密钥空间，所以现在它处理 26-30，节点 3 处理 21 -25。

还有许多其他的覆盖结构，例如使用基于内容的路由来找到存储密钥的正确节点。在环中定位密钥需要一次在环中搜索一个节点（除非您保留本地查找表，在数千个节点的 DHT 中存在问题），这是 O(n) 跳路由。其他结构 - 包括增强环 - 保证 O(log n) 跳路由，并且一些声称以更多维护为代价的 O(1) 跳路由。

阅读维基百科页面，如果你真的想更深入地了解，请查看哈佛的这个课程页面，它有一个非常全面的阅读清单。

于 2008-09-27T20:59:46.060 回答
11

DHT 向用户提供与普通哈希表相同类型的接口（通过键查找值），但数据分布在任意数量的连接节点上。维基百科有一个很好的基本介绍，如果我写得更多，我基本上会反刍 -

http://en.wikipedia.org/wiki/Distributed_hash_table

于 2008-09-27T20:12:16.000 回答
8

我想补充一下 HenryR 的有用答案，因为我刚刚了解了一致的哈希。正常/朴素哈希查找是两个变量的函数，其中一个是存储桶的数量。一致散列的美妙之处在于我们从等式中消除了桶的数量“n”。

在朴素散列中，第一个变量是要存储在表中的对象的键。我们将把键称为“x”。第二个变量是桶的数量，“n”。因此，要确定对象存储在哪个桶/机器中，您必须计算：hash(x) mod(n)。因此，当您更改存储桶的数量时，您也更改了几乎每个对象的存储地址。

将此与一致散列进行比较。让我们将“R”定义为哈希函数的范围。R只是一些常数。在一致性哈希中，对象的地址位于 hash(x)/R。由于我们的查找不再是存储桶数量的函数，因此当我们更改存储桶数量时，我们最终会减少重新映射。

http://michaelnielsen.org/blog/consistent-hashing/

于 2016-04-28T21:45:47.780 回答
2

DHT 的核心是哈希表。键值对存储在 DHT 中，可以使用键查找值。键是值的唯一标识符，范围从区块链中的块到地址和文档。

DHT 与普通哈希表的区别在于 DHT 上的存储和查找分布在多个（可能是数百万）节点或机器上。DHT 的这一特性使其看起来像用于存储和检索的分布式数据库。参与节点之间没有主从层次结构或集中控制。所有节点都被视为对等点。

DHT 为参与节点提供自由，使节点可以随时加入或离开网络。由于这个原因，DHT 广泛用于点对点 (P2P) 网络。事实上，DHT 研究背后的部分动机源于其在 P2P 网络中的使用。

DHT的特点

  1. 去中心化：因为没有中央权威或协调

  2. 可扩展：系统可以轻松扩展到数百万个节点

  3. 容错：DHT 复制所有节点上的数据存储。因此，即使一个节点离开网络，也不应该影响网络中的其他节点。

让我们看看如何在 Chord 等流行的 DHT 协议中进行查找。考虑一个循环的节点的双向链表。每个节点都有一个指向上一个和下一个节点的引用指针。有问题的节点旁边的节点称为后继节点。在所讨论的节点之前的节点称为前驱节点。

就 DHT 而言，每个节点都有一个唯一的 k 位节点 ID，这些节点按照节点 ID 的升序排列。假设这些节点排列在一个称为标识符环的环形结构中。对于每个节点，后继节点顺时针方向的距离最短。对于大多数节点，这是其 ID 最接近但仍大于当前节点 ID 的节点。要找出适合特定密钥的节点，首先使用一致的哈希技术（如 SHA-1）将密钥 K 和所有节点哈希到恰好 k 位。

SHA1

从环中的任何点开始，顺时针遍历，直到找到节点 ID 更接近密钥 K，但可能大于 K 的节点。该节点负责存储和查找该特定密钥。

DHT 中的基本查找

在迭代式查找中，每个节点 Q 查询其后继节点的 KV（键值）对。如果查询到的节点没有目标key，则返回一组可以更接近目标的节点S。查询节点 Q 然后查询 S 中离自己较近的节点。这一直持续到返回目标 KV 对或没有更多节点要查询时。

这种查找非常适合所有节点都具有完美正常运行时间的理想场景。但是如何处理节点有意或因故障离开网络的情况呢？这就需要一个健壮的加入/离开协议。

流行的 DHT 协议和实现

  1. 弦
  2. 卡德利亚
  3. 阿帕奇卡桑德拉
  4. Koorde TomP2P
  5. 伏地魔

参考：

  1. https://en.wikipedia.org/wiki/Distributed_hash_table
  2. https://steffikj19.medium.com/dht-demystified-77dd31727ea7
  3. https://www.linuxjournal.com/article/6797
于 2021-03-27T17:11:38.203 回答