theory - 分布式哈希表(DHT)的简单基本解释

Question

谁能解释一下 DHT 的工作原理吗？

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

Answer 1

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

这提供了很多容错性和可靠性，并且可能带来一些性能优势，但它也带来了很多麻烦。例如，当节点因故障或其他原因离开网络时会发生什么？当节点加入时如何重新分配 key 以使负载大致平衡。想一想，如何均匀地分配 key 呢？当节点加入时，如何避免重新散列所有内容？ (请记住，如果增加存储桶的数量，则必须在普通哈希表中执行此操作)。

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

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

还有许多其他类似的覆盖结构，它们使用基于内容的路由来查找存储 key 的正确节点。在环中定位 key 需要每次在环上搜索一个节点(除非您保留本地查找表，这在数千个节点的 DHT 中会出现问题)，这是 O(n) 跳路由。其他结构(包括增强环)保证 O(log n) 跳路由，有些结构声称以更多维护为代价实现 O(1) 跳路由。

阅读维基百科页面，如果您确实想深入了解，请查看此 coursepage哈佛大学有一个非常全面的阅读 list 。