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

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

没什么太重,只是基础.

1> HenryR..：

---

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

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

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

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

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

阅读维基百科页面,如果你真的想深入了解一下,请查看哈佛大学的这篇文章,它有一个非常全面的阅读清单.

---

+1好答案.你在第三段("解决其中一些问题的一个例子DHT是n个节点的逻辑环")中的含义是Consistent Hashing.这是一个非常有趣的主题,用于Apache Cassandra,一个由Facebook创建的分布式数据库.链接到纸(值得一读):http://www.cs.cornell.edu/projects/ladis2009/papers/lakshman-ladis2009.pdf

---

一个非常容易理解的基于环的查找协议是Chord:http://pdos.csail.mit.edu/papers/chord:sigcomm01/

2> Peter..：

---

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

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

3> thebiggestle..：

---

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

在幼稚哈希中,第一个变量是要存储在表中的对象的键.我们称之为"x"键.第二个变量是桶的数量,"n".因此,要确定对象存储在哪个桶/机器中,您必须计算:hash(x)mod(n).因此,当您更改存储桶的数量时,还会更改几乎每个对象的存储地址.

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

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