algorithm - 一致性哈希是否有保证的公平变化？

Question

我正在寻找类似Consistent Hashing之类的东西，但要保证分配最终尽可能公平（不仅仅是随机密钥的平均） - 有没有这样的事情，如果有，我在哪里可以找到它？

编辑：在我的具体情况下，这组键是预先知道的（和“小”）。确切地说，这些密钥将始终存在，并且必须在任何给定时间点分别分配给每个节点。

Answer 1

在我看来，您正在寻找一个最小的完美哈希。

Answer 2

不只是平均随机键

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

由于您想要始终公平的散列，随机化将无济于事，因为 RNG 的结果可能与这个无法区分。没有确定性算法可以静态地将节点偏好分配给密钥而不会出现不平衡的可能性，除非密钥是离线已知的。

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