AnchorHash

AnchorHash: A Scalable Consistent Hash中描述的一致性哈希算法。

一致性哈希（CH）是许多网络应用程序的核心构建块，从数据中心负载均衡到分布式存储。不幸的是，现有的CH解决方案在任意变化下无法确保完全一致性，或者无法在保持合理的内存占用和更新时间的同时进行扩展。我们提出了AnchorHash，这是一种可扩展且完全一致性的哈希算法。AnchorHash实现了高键查找率、低内存占用和低更新时间。我们正式建立了其强大的理论保证，并展示了具有每个资源仅几字节内存占用的先进实现。此外，广泛的评估表明，它优于现有算法，并且它可以在单个核心上扩展到1亿个资源，同时仍然实现每秒超过1500万个键的查找率。

要点

• 对所有资源均匀分配负载
• 当资源添加和删除时，最佳键重新平衡
• 小内存占用
• 它真的，真的快！

AnchorHash在任意工作集变化下持续地将键哈希到资源中。它通过低内存占用、快速键查找（每秒10到1000万次查找）和最佳的干扰以及资源间的均匀负载平衡来实现这一点。

优化

此实现默认使用SSE4.2指令在x86_64平台上快速执行内部桶哈希——使用Fowler–Noll–Vo哈希作为后备。可以通过禁用simd crate功能手动禁用SIMD优化的哈希。

此实现还在64位架构上编译时使用Daniel Lemire的快速范围映射算法，该算法在Fast Random Integer Generation in an Interval中提出。可以通过禁用fastmod crate功能手动禁用此功能。

本实现使用16位整数以最大化缓存局部性，为小容量实例提供显著的速度提升。这限制了可寻址资源的总数为65,535。

基准测试

此crate包含覆盖哈希算法、范围映射优化和整体AnchorHash实现的基准测试 - cargo bench运行它们。