谁能解释一下 DHT 的工作原理？
没什么太重的，只是基础知识。
好的，它们基本上是一个非常简单的想法。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) 跳路由。
阅读维基百科页面，如果你真的想更深入地了解，请查看哈佛的这个课程页面，它有一个非常全面的阅读列表。
DHT 为用户提供与普通哈希表相同类型的接口（通过键查找值），但数据分布在任意数量的连接节点上。维基百科有一个很好的基本介绍，如果我写得更多，我基本上会反省 -
我想添加到 HenryR 的有用答案中，因为我刚刚了解了一致性哈希。普通/简单的散列查找是两个变量的函数，其中一个是桶的数量。一致性哈希的美妙之处在于我们从等式中消除了桶“n”的数量。
在朴素哈希中，第一个变量是要存储在表中的对象的键。我们将键称为“x”。第二个变量是桶的数量，“n”。因此，要确定对象存储在哪个桶/机器中，您必须计算：hash(x) mod(n)。因此，当你改变桶的数量时，你也改变了几乎每个对象存储的地址。
将此与一致性哈希进行比较。让我们将“R”定义为哈希函数的范围。R 只是一些常数。在一致性哈希中，对象的地址位于 hash(x)/R。由于我们的查找不再是桶数的函数，因此当我们更改桶数时，我们最终会减少重新映射。
DHT 的核心是哈希表。键值对存储在 DHT 中，可以通过键查找值。键是值的唯一标识符，范围可以从区块链中的块到地址和文档。
DHT 与普通哈希表的区别在于 DHT 上的存储和查找分布在多个（可能是数百万个）节点或机器上。DHT 的这一特性使其看起来像用于存储和检索的分布式数据库。参与节点之间没有主从层次结构或集中控制。所有节点都被视为对等节点。
DHT 为参与节点提供了自由，使得节点可以随时加入或离开网络。由于这个原因，分布式哈希表被广泛用于对等（P2P）网络。事实上，DHT 研究背后的部分动机源于它在 P2P 网络中的使用。
DHT的特点
去中心化：因为没有中央权威或协调
可扩展：系统可以轻松扩展到数百万个节点
容错：DHT 在所有节点上复制数据存储。因此，即使一个节点离开网络，也不应影响网络中的其他节点。
让我们看看在流行的 DHT 协议（如 Chord）中查找是如何发生的。考虑一个循环双向链表的节点。每个节点都有一个指向其上一个和下一个节点的引用指针。有问题的节点旁边的节点称为后继节点。在所讨论的节点之前的节点称为前驱。
就 DHT 而言，每个节点都有一个唯一的 k 位节点 ID，这些节点按照节点 ID 的递增顺序排列。假设这些节点排列在一个称为标识符环的环结构中。对于每个节点，后继者的距离最短（顺时针方向）。对于大多数节点，这是 ID 最接近但仍大于当前节点 ID 的节点。要找到适合特定密钥的节点，首先使用一致的哈希技术（如 SHA-1）将密钥 K 和所有节点哈希到恰好 k 位。
从环中的任意一点开始并顺时针遍历，直到找到节点 ID 更接近密钥 K 但可以大于 K 的节点。该节点负责存储和查找该特定密钥。
In an iterative style of lookup, each node Q queries its successor node for KV (key-value) pair. If the queried node does not have the target key, it will return a set of nodes S that can be closer to the target. The querying node Q then queries the nodes in S which are closer to itself. This continues until either the target KV pair is returned or when there are no more nodes to query.
This lookup is very suitable for an ideal scenario where all the nodes have a perfect uptime. But how to handle scenarios when nodes leave the network either intentionally or by failure? This calls for the need for a robust join/leave protocol.
Popular DHT protocols and implementations
- Chord
- Kademlia
- Apache Cassandra
- Koorde TomP2P
- Voldemort
References:
