distributed - 一致散列：重新散列呢？

Question

您可能知道，在处理 DHT 时，一致的哈希是一个好主意。主要思想是在添加或删除新节点时不要遭受太多损失。

从原始论文：

当一台机器被添加到缓存集中或从缓存集中移除时，必须移动到新缓存的对象的预期比例是保持缓存间负载平衡所需的最小值。

解决方案很好，但是存在密钥分配不良的现象。为了解决这个问题，原始节点的副本是随机分布的。该解决方案效果很好。如果您想确定，请查看此图表。

好的，似乎工作得很好。但是，有件事我一直在想，没有人提到。

添加（或删除）一个节点时会发生什么？好吧，每个键，“之前”放置的节点都需要重新散列。这看起来不错，因为这些键不会是“所有”键。但是，如果我们决定放置一些副本，比如 20 个，那么 20 个节点会感到重新散列的痛苦。

更少的副本意味着更差的分布，但是更多的副本意味着在需要重新散列时更加痛苦。

您知道哪种解决方案适合这种情况？我错过了什么吗？

Answer 1

是的，我认为你看错了。我将使用术语“节点”表示机器，使用“对象”表示要缓存的事物。

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

重要的部分是大多数对象不受重新散列的影响。平均而言，只需要重新分配 1/nodes 对象；平均而言，每个节点只需要处理转移 1/nodes^2 个节点，这确实减少了这种影响。

Answer 2

看起来您正试图通过增加副本的数量来解决分布问题，而“更好的”散列函数可以解决问题。良好的散列函数确实提供了良好的分布（参见 MD5、SHA 等）。