分布式哈希表(DHT)的简单基本说明 [英] Simple basic explanation of a Distributed Hash Table (DHT)
问题描述
有人可以解释DHT的工作原理吗?
Could any one give an explanation on how a DHT works?
没有什么太重的，只是基础.
Nothing too heavy, just the basics.
推荐答案
好吧，从根本上讲，这是一个非常简单的想法. DHT为您提供类似于字典的界面，但是节点分布在网络中. DHT的窍门在于，通过散列该密钥可以找到要存储特定密钥的节点，因此实际上，您的散列表存储桶现在是网络中的独立节点.
Ok, they're fundamentally a pretty simple idea. A DHT gives you a dictionary-like interface, but the nodes are distributed across the network. The trick with DHTs is that the node that gets to store a particular key is found by hashing that key, so in effect your hash-table buckets are now independent nodes in a network.
这提供了很多的容错性和可靠性，并可能带来一些性能上的好处，但同时也带来了很多麻烦.例如，当某个节点因故障或其他原因离开网络时会发生什么?以及在节点加入时如何重新分配键，以便大致平衡负载.想一想，您如何均匀地分配密钥?当节点加入时，如何避免重新哈希所有内容? (请记住，如果您增加存储桶的数量，则必须在普通哈希表中执行此操作.)
This gives a lot of fault-tolerance and reliability, and possibly some performance benefit, but it also throws up a lot of headaches. For example, what happens when a node leaves the network, by failing or otherwise? And how do you redistribute keys when a node joins so that the load is roughly balanced. Come to think of it, how do you evenly distribute keys anyhow? And when a node joins, how do you avoid rehashing everything? (Remember you'd have to do this in a normal hash table if you increase the number of buckets).
解决这些问题的一个示例DHT是n个节点的逻辑环，每个节点负责1/n的键空间.将节点添加到网络后，它会在环上找到一个位于其他两个节点之间的位置，并负责其兄弟节点中的某些密钥.这种方法的优点在于，环中的其他节点均不受影响.只有两个同级节点必须重新分配密钥.
One example DHT that tackles some of these problems is a logical ring of n nodes, each taking responsibility for 1/n of the keyspace. Once you add a node to the network, it finds a place on the ring to sit between two other nodes, and takes responsibility for some of the keys in its sibling nodes. The beauty of this approach is that none of the other nodes in the ring are affected; only the two sibling nodes have to redistribute keys.
例如，假设在三节点环中，第一个节点具有键0-10，第二个11-20和第三个21-30.如果出现第四个节点并将其自身插入节点3和0之间(请记住，它们成环)，则它可以负责说说3的密钥空间的一半，因此现在它处理26-30，而节点3处理21 -25.
For example, say in a three node ring the first node has keys 0-10, the second 11-20 and the third 21-30. If a fourth node comes along and inserts itself between nodes 3 and 0 (remember, they're in a ring), it can take responsibility for say half of 3's keyspace, so now it deals with 26-30 and node 3 deals with 21-25.
还有许多其他这样的覆盖结构，它们使用基于内容的路由来找到要在其上存储密钥的正确节点.在环中定位密钥需要一次在一个环上搜索一个节点(除非您保留本地查找表，这在成千上万个节点的DHT中是有问题的)，这就是O(n)跳路由.其他结构-包括增强环-可以保证O(log n)跃点路由，并且有些人主张以O(1)跃点路由为代价，需要更多的维护.
There are many other overlay structures such as this that use content-based routing to find the right node on which to store a key. Locating a key in a ring requires searching round the ring one node at a time (unless you keep a local look-up table, problematic in a DHT of thousands of nodes), which is O(n)-hop routing. Other structures - including augmented rings - guarantee O(log n)-hop routing, and some claim to O(1)-hop routing at the cost of more maintenance.
Read the wikipedia page, and if you really want to know in a bit of depth, check out this coursepage at Harvard which has a pretty comprehensive reading list.
这篇关于分布式哈希表(DHT)的简单基本说明的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
