分布式哈希表（DHT）的简单基本解释

Question

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

没什么太重，只是基础。

Answer 1

好吧，从根本上说，这是一个非常简单的想法。 DHT为您提供类似字典的界面，但节点分布在整个网络中。 DHT的技巧是通过散列该密钥来找到存储特定密钥的节点，因此实际上您的散列表桶现在是网络中的独立节点。

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

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

例如，假设在三节点环中，第一个节点具有键0-10，第二个节点具有键20-20和第三个节点21-30。如果第四个节点出现并在节点3和0之间插入（请记住，它们处于一个环中），它可以负责说3个键空间的一半，所以现在它处理26-30和节点3处理21 -25。

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

阅读维基百科页面，如果您真的想深入了解，请查看 coursepage ，有一个非常全面的阅读清单。

Answer 2

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

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

Answer 3

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

在幼稚哈希中，第一个变量是要存储在表中的对象的键。我们将密钥称为“x”。第二个变量是桶的数量，“n”。因此，要确定对象存储在哪个桶/机器中，您必须计算：hash（x）mod（n）。因此，当您更改存储桶的数量时，还会更改几乎每个对象的存储地址。

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

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

Answer 4

查看此维基百科文章 或者 powerpoint slide

Answer 5

查看亚马逊的Dynamo，它解释了一个基于圆一致散列的简单而新颖的DHT实现。