请问有人可以解释下DHT是如何工作的吗？
不用太深入，只讲基本概念即可。
4个回答
262
好的，它们基本上是一个相当简单的想法。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）跳路由。
阅读维基百科页面，如果想要深入了解，请查看哈佛大学的这个课程页面，其中有一个相当全面的阅读列表。
- HenryR
6
26+1 很好的回答。你在第三段所指的（“一个解决这些问题的例子是n个节点的逻辑环形DHT”）是一致性哈希算法。这是一个非常有趣的主题，在Facebook创建的分布式数据库Apache Cassandra中使用。链接到论文（值得阅读）：http://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf - santiagobasulto
5一个相当易于理解的基于环的查找协议是 Chord：http://pdos.csail.mit.edu/papers/chord:sigcomm01/ - ThomasWeiss
你能详细说明一下键值是如何存储在节点上的吗？它会是哈希表或数据库的某种形式吗？ - Wand Maker
@HenryR，"节点环"不就是一种树形结构吗？ - Pacerier
1伊利诺伊大学每学期都会在其分布式系统课程中教授和使用Chord协议，如果有人需要更多阅读材料，请访问https://courses.engr.illinois.edu/ece428/sp2018/lectures.html。 - Siddhartha
这太棒了@HenryR，真的帮助我理解DHT的直觉。 - carozimm
11
DHTs提供与普通哈希表相同的用户接口（通过键查找值），但数据分布在任意数量的连接节点上。如果写更多，我基本上会重复维基百科的良好基础介绍 -
- Pete
8
我想作为HenryR有用答案的补充，因为我刚刚对一致性哈希有了深入的理解。普通/天真的哈希查找是两个变量的函数，其中之一是桶的数量。一致性哈希的美妙之处在于我们从方程式中消除了桶的数量“n”。
在天真的哈希中，第一个变量是要存储在表中的对象的密钥。我们将密钥称为“x”。第二个变量是桶的数量“n”。因此，要确定对象存储在哪个存储桶/机器中，您必须计算：hash（x）mod（n）。因此，当您更改桶的数量时，您还会更改几乎每个对象存储的地址。
与一致性哈希相比较。让我们定义“R”为哈希函数的范围。R只是某个常数。在一致性哈希中，对象的地址位于hash（x）/ R处。由于我们的查找不再是桶的数量的函数，因此当我们更改桶的数量时，我们需要重新映射的对象就会减少。
在天真的哈希中，第一个变量是要存储在表中的对象的密钥。我们将密钥称为“x”。第二个变量是桶的数量“n”。因此，要确定对象存储在哪个存储桶/机器中，您必须计算：hash（x）mod（n）。因此，当您更改桶的数量时，您还会更改几乎每个对象存储的地址。
与一致性哈希相比较。让我们定义“R”为哈希函数的范围。R只是某个常数。在一致性哈希中，对象的地址位于hash（x）/ R处。由于我们的查找不再是桶的数量的函数，因此当我们更改桶的数量时，我们需要重新映射的对象就会减少。
- thebiggestlebowski
2
1你仍然需要进行模运算，不是吗？假设你有3个服务器。
hash(x)/R得到的结果是34500。你仍然需要执行34500 % 3的操作。 - Pacerier你的博客文章不够清晰，你应该列出一个逐步快照的工作示例，其中包括添加和删除节点以及添加和删除行。 - Pacerier
4
一个 DHT 的核心是一个哈希表。键值对被存储在 DHT 中，可以通过键查找值。这些键是唯一的标识符，对应的值可以是区块链中的块、地址或文档。
DHT 与普通哈希表不同的地方在于，它的存储和查找是分布在多个（可以是数百万个）节点或机器上的。这种特性使得 DHT 看起来像用于存储和检索的分布式数据库。在参与节点之间不存在主从层次结构或集中控制。所有节点都被视为同等地位。
DHT 提供了自由给参与节点，以便它们可以随时加入或离开网络。因此，DHT 在点对点（P2P）网络中被广泛使用。事实上，研究 DHT 的部分动机源于其在 P2P 网络中的使用。
DHT 的特征包括：
这种查找非常适合理想情况下所有节点都具有完美的运行时间的场景。但是如何处理节点故障或意外离开网络的情况呢？这就需要一个强大的加入/离开协议。
流行的DHT协议和实现：
1. Chord 2. Kademlia 3. Apache Cassandra 4. Koorde TomP2P 5. Voldemort
参考资料：
DHT 与普通哈希表不同的地方在于，它的存储和查找是分布在多个（可以是数百万个）节点或机器上的。这种特性使得 DHT 看起来像用于存储和检索的分布式数据库。在参与节点之间不存在主从层次结构或集中控制。所有节点都被视为同等地位。
DHT 提供了自由给参与节点，以便它们可以随时加入或离开网络。因此，DHT 在点对点（P2P）网络中被广泛使用。事实上，研究 DHT 的部分动机源于其在 P2P 网络中的使用。
DHT 的特征包括：
去中心化：由于没有中央机构或协调，因此系统是去中心化的。
可扩展的：系统可以轻松扩展到数百万个节点。
容错的：DHT将数据存储在所有节点上进行复制。因此，即使一个节点离开网络，它也不应影响网络中的其他节点。
让我们看看像Chord这样的流行DHT协议中查找是如何进行的。考虑一个循环双向链表节点。每个节点都有指向其前面和后面节点的引用指针。紧接着该节点的下一个节点称为“后继节点”。而在该节点之前的节点称为“前驱节点”。
在DHT方面，每个节点都有k位的唯一节点ID，这些节点按其节点ID的增加顺序排列。假设这些节点按照称为标识符环的环形结构排列。对于每个节点，后继节点沿顺时针方向距离最短。对于大多数节点，这是其ID最接近但仍大于当前节点ID的节点。要找到适合特定密钥的节点，请先使用一致性哈希技术（如SHA-1）对密钥K和所有节点进行精确到k位的哈希。
这种查找非常适合理想情况下所有节点都具有完美的运行时间的场景。但是如何处理节点故障或意外离开网络的情况呢？这就需要一个强大的加入/离开协议。
流行的DHT协议和实现：
1. Chord 2. Kademlia 3. Apache Cassandra 4. Koorde TomP2P 5. Voldemort
参考资料：
- Steffi Keran Rani J
网页内容由stack overflow 提供, 点击上面的可以查看英文原文，
原文链接
原文链接