JumpBackHash: Say Goodbye to the Modulo Operation to Distribute Keys Uniformly to Buckets
Fuente:
arXiv
Enregistré dans:
| Auteur principal: | |
|---|---|
| Format: | Preprint |
| Publié: |
2024
|
| Sujets: | |
| Accès en ligne: | |
| Tags: |
Ajouter un tag
Pas de tags, Soyez le premier à ajouter un tag!
|
| _version_ | 1866914142893375488 |
|---|---|
| author | Ertl, Otmar |
| author_facet | Ertl, Otmar |
| contents | 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 standard libraries. This work introduces JumpBackHash, a consistent hash algorithm that overcomes those shortcomings.
Methodology. JumpBackHash applies the concept of active indices borrowed from consistent weighted sampling, which inherently leads to consistency. It generates the active indices in reverse order, which avoids floating-point operations, enables the minimization of consumed random values and the use of a standard pseudorandom generator, and finally leads to a very efficient algorithm.
Results. Theoretical analysis shows that JumpBackHash has an expected constant runtime. The expected value and the variance of the number of consumed random values perfectly agree with the experiments. Empirical tests also confirm the consistency.
Conclusion. JumpBackHash offers a fast and efficient solution for uniformly distributing keys across buckets in distributed systems. Its simplicity, performance, and the availability of a production-ready Java implementation as part of the Hash4j open source library make it a viable replacement for the modulo-based approach for improving assignment and system stability. |
| format | Preprint |
| id |
arxiv_https___arxiv_org_abs_2403_18682 |
| institution | arXiv |
| publishDate | 2024 |
| record_format | arxiv |
| spellingShingle | JumpBackHash: Say Goodbye to the Modulo Operation to Distribute Keys Uniformly to Buckets Ertl, Otmar Data Structures and Algorithms Databases Distributed, Parallel, and Cluster Computing 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 standard libraries. This work introduces JumpBackHash, a consistent hash algorithm that overcomes those shortcomings. Methodology. JumpBackHash applies the concept of active indices borrowed from consistent weighted sampling, which inherently leads to consistency. It generates the active indices in reverse order, which avoids floating-point operations, enables the minimization of consumed random values and the use of a standard pseudorandom generator, and finally leads to a very efficient algorithm. Results. Theoretical analysis shows that JumpBackHash has an expected constant runtime. The expected value and the variance of the number of consumed random values perfectly agree with the experiments. Empirical tests also confirm the consistency. Conclusion. JumpBackHash offers a fast and efficient solution for uniformly distributing keys across buckets in distributed systems. Its simplicity, performance, and the availability of a production-ready Java implementation as part of the Hash4j open source library make it a viable replacement for the modulo-based approach for improving assignment and system stability. |
| title | JumpBackHash: Say Goodbye to the Modulo Operation to Distribute Keys Uniformly to Buckets |
| topic | Data Structures and Algorithms Databases Distributed, Parallel, and Cluster Computing |
| url | https://arxiv.org/abs/2403.18682 |