Consistent Hashing and Data Partitioning Explained
On this page
What data partitioning is
When data outgrows one node, split it: each node owns a partition (also called a shard). Three schemes are common, and the difference shows when you add or remove a node.
Why hash modulo N breaks when nodes change
node = hash(key) mod N spreads keys evenly. But change N and nearly every key's result changes. Going from 4 nodes to 5, a key keeps its node only if hash mod 4 equals hash mod 5, which happens for about 1 key in 5. The other 80 percent move. For a cache, that's an instant mass miss; for a database, a giant data migration.
How consistent hashing works
Map both nodes and keys onto the same ring of hash values. A key belongs to the first node clockwise from it. Adding a node takes over only the keys between it and its predecessor; removing one hands its keys to its successor. On average only K / N keys move (K keys, N nodes), close to the minimum possible. In a simulation with 100,000 keys growing from 3 to 4 nodes, modulo hashing moved 75 percent of keys and a hash ring moved 22 percent (the System Design Interview course includes the code).
Virtual nodes fix the ring's unevenness: each physical node appears at many points (often 100+), so each owns many small arcs. Load evens out, a departing node's keys spread across many others, and bigger machines can take more points. Dynamo-style stores place a key's replicas on the next N distinct physical nodes clockwise (Day 13).
Fixed hash slots, as in Redis Cluster
A different route to the same goal: hash keys into a fixed number of slots, far more than nodes, and assign slots to nodes. Redis Cluster uses 16,384 slots; many databases use thousands of logical shards. Adding a node moves whole slots, never rehashing keys. It's simpler to reason about and gives an explicit map you can inspect and rebalance.
Range partitioning
Instead of hashing, give each node a contiguous key range (A to F, G to M...). Range queries ("all orders from customer 42 between June and July") stay on one or few nodes, and data is sorted. HBase, Bigtable, Spanner, CockroachDB and MongoDB's ranged sharding work this way, splitting ranges as they grow.
The risk is hot spots: keys that increase over time, such as timestamps, put all new writes in the last range. Common fixes: prefix with something well-distributed, or hash part of the key.
| Scheme | Rebalancing cost | Range queries | Hot-spot risk |
|---|---|---|---|
| Hash mod N | Most keys move | Scatter to all nodes | Low |
| Consistent hashing | ~1/N of keys move | Scatter | Low (with virtual nodes) |
| Fixed slots | Whole slots move | Scatter | Low |
| Range | Split and move ranges | Efficient | High with monotonic keys |
Hot keys: what partitioning can't fix
No partitioning scheme splits the load of one very popular key: it lives on one node. Caching it, replicating it to several nodes, or splitting it into sub-keys (Day 14 of the Kafka course) handles that separately.
Check yourself
Changing N changes the remainder for almost every key, so going from 4 to 5 nodes moves about 80 percent of keys to a different node. Consistent hashing moves only about 1/N of the keys.
Each physical node owns many small ranges spread around the ring, so load is more even, and when a node leaves its keys spread across many nodes instead of all landing on one neighbor. Nodes can also take more or fewer virtual nodes to match their capacity.
When range queries over the key are important, as long as the key isn't monotonically increasing or is made to spread writes.
Keys hash into 16,384 fixed slots, and slots are assigned to nodes. Adding a node moves whole slots, which keeps rebalancing explicit and simple.
All requests for one key go to the partition that owns it. Fixing it needs caching, splitting the key into sub-keys, or replicas for reads.