consistent hashing is the distributed hashing technique that distributes data across multiple servers in the cluster. It is used to efficiently rebalancing of the distribution of data across cluster when nodes are added ore removed (minimize data movement). It maps data and nodes on to hash ring. NoSQL database like Cassandra is the best example of use of consistent hashing.
When we have fixed size cluster of nodes, below simple hashing works great,
serverIndex = hash(key) % N, where N is the total number of nodes in the cluster
However when nodes removed or added dynamically int the cluster (typical up scaling or down scaling scenario), this mechanism fails to rebalance the data and yields wrong nodes for accessing data. This is where consistent hashing plays the key role.
Hash function used here is different from the modular one mentioned in the previous case where rehashing problem is there. So data keys are hashed on to this hash ring using uniformly distributed hash function. To retrieve the data using keys , we need to connect to the proper node where key can be found. Going, clockwise you can see k1 is stored on n1, k2 is stored on n2 , k3 in stored on n3 and k4 is tored on n4.
Adding or removing the nodes from the ring, has minimal effect on redistribution of the keys. Rebalancing of keys is done efficiently with minimal effect on rest of the keys. However this basic approach has pitfall of odd distribution of partitions to the nodes considering dynamic scaling scenarios of upscaling and downscaling.
2 real nodes (R1 & R2)
5 virtual nodes each (V1–V10)
Partitions (P1–P10) clearly marked, showing which real node they belong to
Sample keys (K1–K5 in red) placed on the ring, mapping to their next clockwise virtual node (and thus to a real node).
As the number of virtual nodes increases, the distribution of keys becomes more balanced. This is because the standard deviation gets smaller with more virtual nodes, leading to balanced data distribution. Thus it is easy to scale horizontally.
With virtual nodes each physical node is responsible for multiple partitions