一致性哈希算法：重新哈希会发生什么？

Question

3

如您所知，一致性哈希在处理DHT时是一个很好的想法。其主要思想是在添加或删除节点时不会遭受太多损失。

从原始论文中可以看到：

“当将机器添加到缓存集合中或从其中删除时，必须移动到新缓存中的对象的期望分数是最小的，以使负载在缓存之间保持平衡。”

该解决方案非常好，但存在密钥分布不良的现象。为了解决这个问题，原始节点的副本被随机分布。这个解决方案非常有效。如果您想确信，请查看此 chart。

好的，似乎运行良好。但是，有件事我一直在考虑，却没有人提及。

当添加（或删除）一个节点时会发生什么？嗯，需要重新哈希位于该节点之前的每个键。这似乎很好，因为那些键不会是“所有”键。但是，如果我们决定放置一些副本，比如20个，那么20个节点将感受到重新哈希的痛苦。

“较少的副本意味着分布较差，但更多的副本意味着重新哈希时会更加痛苦。”“您知道什么解决方案适合这种情况吗？我有遗漏吗？”

- santiagobasulto

1

为什么这是个问题呢？键重新散列的总比例保持不变：已经散列的总数的约1/N。无论它在1个节点还是20个节点上发生，因为散列是确定性的（可以实时计算），所以这并不重要。 - ShreevatsaR

重新散列正是一致性哈希算法旨在解决的问题。哈希桶的数量是固定的。当节点数量发生变化时，只有桶与节点之间的映射关系会发生改变。 - jaggi

2个回答

-1

看起来你正在尝试通过增加副本数量来解决分布问题，而更好的哈希函数可能会解决这个问题。良好的哈希函数确实提供了良好的分布（例如MD5、SHA等）。

- Jérôme Verstrynge

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- aaronsuperglue · Accepted Answer

是的，我认为你的看法有误。我将使用术语“节点”表示机器，“对象”表示要缓存的东西。

平均而言，几乎每个节点都会受到新添加的影响。这并不是坏事；它将重新哈希的负载分散到所有可用的节点上。

重要的是，大多数对象不会受到重新哈希的影响。平均而言，只有1/节点的对象需要重新分配；平均而言，每个节点只需要处理转移1/节点^2个节点，这真的可以减少其影响。