在一致性哈希算法中，是否存在可靠的公平变化方式？

Question

我正在寻找类似于一致性哈希的东西，但需要保证分布尽可能公平（不仅仅是对于随机密钥的平均值） - 是否有这样的东西，如果有在哪里可以找到？

编辑：在我的特定情况下，密钥集在前期已知（且“较小”）。这些密钥将始终存在，并且在任何给定时间必须分配到恰好一个节点。

- SoftMemes

---

+1，对我来说这似乎是一个非常合理的问题：“是否存在一种已知算法具有算法X的所有属性，以及额外的属性Y？”显然，提问者已经独自做了足够的研究，找到了算法X。 - Steve Jessop

我甚至没有看到在常见问题解答中有任何研究要求 - 我认为存在于那些过分关注“家庭作业”的人们心中的想象中的常见问题解答正在污染其他一切。我们中的一些人非常乐意成为有趣问题的“研究助手”。 - andrew cooke

我认为你所要求的实际上是不可行的。对于n个节点，有n^2种可能的可用性场景；我怀疑是否可能设计一种算法，在所有这些场景下公平地分配责任。 - Nick Johnson

@Nick，公平且确定地完成这个任务并不是问题，只需在节点之间进行循环调度即可。然而，在节点进入或离开时仍保持键的移动最小化的属性，这就更加困难了。 - SoftMemes

Answer 1

听起来你需要一个最小完美哈希。

- Jim Mischel

---

不完全是。在我的情况下，我确实希望发生碰撞（多个键被分配给同一节点），并且我对节点数量变化时应该发生什么有特定要求。 - SoftMemes

Answer 2

这并不是对一致性哈希提供的保证的准确描述。首先，“平均”没有捕捉到以下事实：为了在圆上随机放置大量虚拟节点和一个良好的哈希函数族（例如，一个对数独立的哈希函数族），负载不平衡非常不可能很大（我相信通常的不平衡应该是分配给特定机器的键数的平方根数量级）。其次，只要密钥不依赖于随机选择的哈希函数（忽略敌手），它们就不必是随机的。

由于您想要始终公平的哈希，随机化是无济于事的，因为随机数生成器可能具有与this one难以区分的结果。除非离线已知密钥，否则没有确定性算法可以静态地分配节点首选项而不可能出现不平衡。

如果您关心平方根不平衡的项目数量足够少，则可以进行老式的有状态负载平衡。

- magic

---

在一个箱子中的变异（标准差）是该箱子中数值数量的平方根（假设为“随机” - 泊松 - 统计）。 - andrew cooke

在一致性哈希的描述上达成了共识，但是在这种情况下，我需要更强的保证，同时我仍然非常希望不需要显式共享状态（而是能够仅从桶和数据中推导出分配）。在我的情况下，键的集合实际上是预先已知的，我应该在原始问题中包含这一点（将进行更新）。 - SoftMemes