Catalog My learning Blog
Distributed Systems Explained: CAP, Clocks and Replication · Phase 2 · Lesson 11 · 4 min read

Consistent Hashing and Data Partitioning Explained

On this page
  1. What data partitioning is
  2. Why hash modulo N breaks when nodes change
  3. How consistent hashing works
  4. Fixed hash slots, as in Redis Cluster
  5. Range partitioning
  6. Hot keys: what partitioning can't fix
  7. Check yourself

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).

Keys and nodes sit on a hash ring; each key belongs to the next node clockwise, and adding a node takes over only its own arc.
Keys and nodes sit on a hash ring; each key belongs to the next node clockwise, and adding a node takes over only its own arc.

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.

SchemeRebalancing costRange queriesHot-spot risk
Hash mod NMost keys moveScatter to all nodesLow
Consistent hashing~1/N of keys moveScatterLow (with virtual nodes)
Fixed slotsWhole slots moveScatterLow
RangeSplit and move rangesEfficientHigh 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.