Maglev哈希算法：Rust实现

根据Google 论文 描述的Maglev一致性哈希算法的实现

什么是一致性哈希？

一般来说，哈希可以松散地定义为将一组键分配到一组桶中。通常，哈希算法的目标是确保所有桶分配到相同数量的键，并且键在桶中均匀分布。

当尝试使用哈希将键分配到一组作为桶的分布式服务器时，传统哈希算法的保证是不够的。问题是，调整桶的大小可能会严重改变键的分配。在分布式系统中，由于桶是服务器，服务器可能会崩溃，因此在容错系统中使用传统哈希意味着需要大量的网络调用来重新安排桶并将分布式系统带到稳定状态。

一致性哈希算法旨在确保在调整桶大小时对键的分布造成的干扰最小。正如维基百科所说

当哈希表调整大小时，平均只需要重新映射 n/m 个键，其中 n 是键的数量，m 是槽的数量。

Maglev哈希是如何工作的？

对于每个桶（服务器），我们为键生成一个偏好列表。偏好列表本质上就是数组（0..M -1）的随机排列，对于 M 个键。

然后使用这个偏好列表将桶分配给每个键。分配通过循环每个偏好列表进行，选择尚未分配的键，并将其分配给当前偏好列表的所有者。