A survey and comparison of consistent hashing algorithms

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.

I. Introduction

With an arbitrary amount of data as input, hashing algorithms are deterministic operations that generate a fixed-length result known as a hash value or digest. Hashing techniques can be used in distributed systems to distribute objects among nodes so that all nodes evenly divide the load, and clients can quickly identify which node is in charge of a particular object. By using the key to determine the index of the bucket where the data is stored, hashing techniques can be used to build associative arrays that enable data to be accessed using any key rather than a numeric index. In a Distributed Hash Table (DHT), each bucket might be located on a different node in a computer network. Due to the necessity to move data to a new node, dynamically enlarging a hash table like this usually comes at a high cost and might result in unbalanced data placement. Consistent hashing solutions have been created to solve these problems and exhibit low reallocation costs (in terms of data that need to be transferred to a different node). The goal of this paper is to analyze the state of the art to determine the most effective consistent hashing algorithm. For this study, the most relevant consistent hashing algorithms proposed since the first papers on this matter published by