JumpBackHash: Say Goodbye to the Modulo Operation to Distribute Keys Uniformly to Buckets
Otmar Ertl
导言。 分布式数据处理和存储系统需要有效的方法来跨存储桶分发密钥。 虽然简单快捷,但传统的基于模块的映射在存储桶数量发生变化时不稳定,导致系统资源利用率激增,例如网络或数据库请求。 一致的哈希算法可以最大限度地减少重新映射,但要么明显较慢,需要浮点算术,要么基于标准库中很少可用的哈希函数家族。 这项工作引入了JumpBackHash,这是一种克服这些缺点的一致哈希算法。 方法。 JumpBackHash应用从一致的加权抽样中借用的主动指数的概念,这本身就会导致一致性。 它以反向顺序生成活动索引,从而避免浮点运算,使消耗的随机值最小化和使用标准的伪随机生成器,最后导致一个非常高效的算法。 成果。 理论分析显示,JumpBackHash有一个预期的恒定运行时。 预期值和消耗随机值数的方差与实验完全一致。 实证测试也证实了一致性。 结论。 JumpBackHash 提供了一个快速高效的解决方案,用于在分布式系统中跨存储桶均匀分配密钥。 作为Hash4j开源库的一部分,它的简单性,性能和生产就绪的Java实现的可用性使其成为基于模数的方法来改进分配和系统稳定性的可行替代品。
Introduction. Distributed data processing and storage systems require efficient methods to distribute keys across buckets. While simple and fast, the traditional modulo-based mapping is unstable when the number of buckets changes, leading to spikes in system resource utilization, such as network or database requests. Consistent hash algorithms minimize remappings but are either significantly slower, require floating-point arithmetic, or are based on a family of hash functions rarely available in...