Consistent Hashing

Consistent hashing is a popular algorithm and databases such as DynamoDB, Cassandra, ScyllaDB, and Riak use this algorithm to scale systems. In this lesson, we will explain the algorithm.

What is consistent hashing?

Consistent hashing is a hashing algorithm in which only $k/n$ keys are remapped if the number of nodes changes. Here $k$ is the number of keys and $n$ is the number of slots, i.e., nodes.

In traditional hashing algorithms, a change in the number of slots requires many keys to be remapped. In the consistent hashing algorithm, the remap is tolerable, which is why databases have adopted this strategy.

Let’s discuss.

The hash ring

In general hashing, the keys are mapped to a one-dimension space. Assuming the hash key range is $0$ to $2^{32}-1$, the keyspace is a one-dimensional array.