Yashotantra Academy logo

3 · Partitioning & Data Stores

4. Consistent Hashing & Data Partitioning

Hash rings, virtual nodes, data rebalancing, and horizontal database sharding.

10 min read · 3 MCQs

The Failure of Modulo Hashing

Traditional horizontal partitioning computes $node = hash(key) \% N$. When the number of nodes $N$ changes (due to adding a server or a crash), almost every single key hashes to a different node, invalidating caches and triggering massive data rebalancing across the whole cluster.

Consistent Hash Rings

Consistent hashing maps both servers and data keys to a circular $2^{32}-1$ integer ring. A key is assigned to the first server encountered moving clockwise. Adding or removing a server only affects keys in its immediate neighboring segment ($k/N$ keys on average).

Virtual Nodes (VNodes)

To prevent hot spots and uneven data distribution (hash skew), each physical server is mapped to hundreds of pseudo-random positions on the ring called virtual nodes. This ensures uniform distribution and balances load proportionally to hardware capacity.

Chapter quiz

3 questions · pass mark 75%

  1. 1. What is the primary advantage of consistent hashing over standard modulo hashing?

  2. 2. Why are virtual nodes (VNodes) added to a consistent hash ring?

  3. 3. In consistent hashing, where is a key stored?