Consistent hashing is a technique for distributing data across a network of nodes in a way that minimizes reorganization when nodes join or leave the network. It is extensively applied in modern distributed systems as a fundamental mechanism for routing and data placement. Similarly, distributed storage systems rely on consistent hashing for scalable and fault-tolerant data partitioning. This paper introduces BinomialHash, a consistent hashing algorithm that executes in constant time and requires minimal memory. We provide a detailed explanation of the algorithm, present a pseudocode implementation, and formally establish its strong theoretical guarantees. Finally, we compare its performance against state-of-the-art constant-time consistent hashing algorithms, demonstrating that our solution is both highly competitive and effective, while also validating the theoretical boundaries.

Consistent hashing is used in distributed systems and networking applications to spread data evenly and efficiently across a cluster of nodes. In this paper, we present MementoHash, a novel consistent hashing algorithm that eliminates known limitations of state-of-the-art algorithms while keeping optimal performance and minimal memory usage. We describe the algorithm in detail, provide a pseudo-code implementation, and formally establish its solid theoretical guarantees. To measure the efficacy of MementoHash, we compare its performance, in terms of memory usage and lookup time, to that of state-of-the-art algorithms, namely, AnchorHash, DxHash, and JumpHash. Unlike JumpHash, MementoHash can handle random failures. Moreover, MementoHash does not require fixing the overall capacity of the cluster (as AnchorHash and DxHash do), allowing it to scale indefinitely. The number of removed nodes affects the performance of all the considered algorithms. Therefore, we conduct experiments considering three different scenarios: stable (no removed nodes), one-shot removals (90% of the nodes removed at once), and incremental removals. We report experimental results that averaged a varying number of nodes from ten to one million. Results indicate that our algorithm shows optimal lookup performance and minimal memory usage in its best-case scenario. It behaves better than AnchorHash and DxHash in its average-case scenario and at least as well as those two algorithms in its worst-case scenario.

When a cluster is scaled, a well-known hashing technique called consistent hashing permits only a small number of resources to be remapped. In a variety of settings, including distributed databases, cloud infrastructures, and peer-to-peer networks, it performs key functions as a data router and load balancer. The literature does not offer a full review and comparative assessment of consistent hashing algorithms, despite the fact that research on these algorithms in relation to various usage scenarios has been conducted. Consequently, in a rather neutral setting, this study surveys and empirically compares the most widely used consistent hashing algorithms for distributed databases and cloud infrastructures, published from 1997 to 2021. All algorithms have been implemented in Java and benchmarked on common hardware to perform the comparison. We found Jump, Anchor, and Dx to outmatch the other algorithms on all the considered metrics. The measured values match the asymptotic curves. Although, some asymptotically faster algorithms have been shown to be slower in practice due to the number of memory accesses.