Consistent Hashing

Pradeep P
2 days ago
3 min read

Series: Modern System Design · Layer 1 — The building blocks

Layer 1 · Post 19 of 21

← Previous: Amdahl's Law → Next: Cache Stampede

Layer 1 — The building blocks · Post 92 of 119

Place keys and nodes on a ring so adding or removing a node moves only a fraction of the keys.

What you'll learn

Why hash(key) % N is a disaster when N changes
The ring, virtual nodes, and what "consistent" actually means
Where this shows up in caches, Dynamo-style stores, and load balancers

The idea in one minute

Sharding (Post 15) needs a function: key → node. The naive function is hash(key) % number_of_nodes.

When you add node number 9, almost every key changes remainder. The whole cache misses. The whole dataset remaps. You wanted +1 capacity; you caused a stampede (next post) and a data shuffle.

Consistent hashing puts both keys and nodes on a circle (the hash space). A key belongs to the first node clockwise (or counterclockwise — pick one). Add a node: it lands on the ring and steals only the arc until the next node. Remove a node: its arc goes to its neighbor. Expected move is about 1/N of the keys, not ~100%.

Ring 0 -------- hash space -------- 2^32-1
        n1        n2         n3
         \        |          /
          keys sit on the ring;
          each key walks clockwise to a node

"Consistent" means: the mapping stays as stable as possible when the node set changes. It does not mean strong consistency of data.

Why it matters

Any system that partitions work — cache shards, Kafka-like assignment, CDN, load balancing — either remaps everything on membership change or uses a stable hash. Interviewers use this to see if you have felt a cache cluster resize.

It is also how you talk about hot keys: the ring can still dump a popular key on one node. Consistent hashing is not load balancing of traffic; it is stable assignment of keys.

How it works

Hash to a large ring. SHA-1 / Murmur / xxHash of the key and of the node name. 32-bit is enough to sketch; production uses 64+ or a well-known library.

Virtual nodes (vnodes). One physical server appears as many points on the ring (e.g. 100–200). That smooths imbalance: a new box takes many small arcs instead of one unlucky giant slice. Dynamo called this out; Cassandra token ranges are the same idea.

Replication. For N replicas, walk clockwise to the next distinct physical nodes. That is how Dynamo-style stores place copies. Fail a node: its neighbors already have the data (or can stream it).

Lookups. Binary search on sorted vnode positions, or a library (jump hash, Maglev, Rendezvous / HRW). Jump hash is simpler when nodes are 0..N-1 and you only add at the end. Maglev is Google's table for load balancers: almost-even, almost-stable.

What it does not do. It does not move bytes for you. After remap, the new owner has a cold cache or must copy from the old owner. You still need a transfer protocol.

A simple example

Eight Redis cache nodes, hash(url) % 8. You add a ninth for Black Friday. Suddenly 8/9 of URLs hash to a different box. Every box is empty for most keys. Origin databases see almost all traffic at once. That is a cache stampede caused by the hash function, not by TTL.

With consistent hashing, the new node takes ~1/9 of keys. 8/9 stay warm. You still want to pre-warm or rate-limit the new arcs, but you did not throw away the whole cache.

Common mistakes

Implementing the ring in the app on Friday. Use a known library or the datastore's partitioner. Off-by-one on the circle is a silent wrong-shard bug.

Too few vnodes. One unlucky physical node owns 40% of the ring. Then you "have consistent hashing" and still a hot partition.

Hashing a changing string. hash(userId + region) that you later drop region from remaps everything. Hash the shard key you will keep.

Confusing this with cryptographic "consistency." Interviewers will let you recover if you say "stable mapping," not "linearizable."

How this shows up in real systems

Dynamo, Cassandra, Riak, DynamoDB (partition key): ring / token ranges.
Redis Cluster: hash slots (16384); a discrete cousin of the same idea.
Akamai / CDNs, some load balancers: Maglev, consistent hash for session stickiness.
Kubernetes: hash(key) % replicas on some controllers — know when a restart reshuffles.

Recap

% N remaps almost everything when N changes; a ring remaps about 1/N.
Virtual nodes keep the arcs even; they do not fix a single hot key.
Next: what happens when the cache is empty all at once anyway — cache stampede.