Consistent Hashing

When an interviewer asks "how do you add a cache server without cold-starting the whole cluster?", the answer is consistent hashing. It is the classic technique behind distributed caches (Memcached clients), databases (Cassandra, DynamoDB), and shard routing.

The core idea

Naive sharding maps a key with hash(key) mod N, where N is the number of nodes. It's even and simple — until N changes. Add or remove one node and N changes, so almost every key remaps to a different node, invalidating the whole cache and forcing massive data movement. Consistent hashing solves this: when a node joins or leaves, only about 1/N of the keys move, not all of them.

Beginner — the hash ring

Imagine the hash output space bent into a ring (0 to 2^32-1, wrapping around). Each node is hashed to a point on the ring. Each key is hashed to a point too, then assigned to the first node found clockwise from its position. Because keys and nodes share one ring, adding a node only steals the slice of keys between it and its predecessor — everything else stays put.

Intermediate — why removals are cheap too

Remove a node and its keys simply roll clockwise to the next node; no other key is affected. Add a node and it takes over a contiguous arc from its clockwise successor. In both cases only the neighbors' keys move, roughly 1/N of the total — the defining benefit.

Advanced — virtual nodes

Plain consistent hashing has a flaw: with few nodes, the ring is uneven, so some nodes own big arcs and become hotspots, and a removed node dumps all its load onto one neighbor. The fix is virtual nodes (vnodes): each physical node is placed at many points on the ring (e.g., 100–200 hashes). This smooths the distribution, spreads a departing node's load across many others, and lets you weight powerful machines by giving them more vnodes. Nearly every production system uses vnodes.

Worked example

A cache cluster of 4 nodes uses hash(key) mod 4. You add a 5th node → N goes 4→5 and roughly 80% of keys now map elsewhere, so the cache is almost entirely cold and the database gets slammed. Switch to consistent hashing with virtual nodes: adding the 5th node moves only about 1/5 (20%) of keys, the rest keep hitting warm cache, and load stays even.

When to use

Use consistent hashing whenever nodes join/leave frequently and you want to minimize disruption: distributed caches, sharded databases and key-value stores, load distribution across a dynamic pool, and P2P systems.

Tricks and mnemonic

Remember "mod N breaks on N-change; the ring keeps ~(N-1)/N of keys home." And: vnodes = many small arcs = even load.

Fast revision of consistent hashing.

• Problem: hash(key) mod N remaps almost ALL keys when N changes → cold cache, huge data movement.
• Consistent hashing: place nodes and keys on a ring; each key goes to the first node clockwise.
• Adding/removing a node moves only about 1/N of keys — everything else stays put.
• Virtual nodes (vnodes): each physical node sits at many ring points → even load, smooth failover, weighting.
• Without vnodes, distribution is lumpy and a failed node dumps all load on one neighbor.
• Used in Cassandra, DynamoDB, and distributed cache clients (Memcached).

Cover the answer, recall, then check. 8 cards.

Q1. What problem does consistent hashing solve?
A1. Minimizing key remapping (and cache invalidation) when nodes are added or removed.

Q2. Why is hash(key) mod N bad when N changes?
A2. Changing N remaps almost every key to a different node, cold-starting caches and moving huge amounts of data.

Q3. How is a key assigned to a node on the ring?
A3. Hash the key onto the ring, then walk clockwise to the first node encountered.

Q4. Roughly what fraction of keys move when a node is added/removed?
A4. About 1/N of the keys — only the affected arc.

Q5. What are virtual nodes?
A5. Placing each physical node at many ring points to even out distribution and failover.

Q6. What goes wrong without virtual nodes?
A6. Uneven arcs cause hotspots, and a departing node dumps its whole load onto one neighbor.

Q7. Name two systems that use consistent hashing.
A7. Cassandra and DynamoDB (also distributed cache clients).

Q8. Can virtual nodes weight a more powerful machine?
A8. Yes — give it more virtual nodes so it owns a larger share of the ring.

Worked Example

Problem: Four cache servers route keys with server = hash(key) % N. When you add a 5th server, why do nearly all keys remap, and how does consistent hashing avoid that?

Solution: With hash(key) % N, the assignment depends on N. Changing N from 4 to 5 changes hash(key) % N for almost every key (only keys where hash%4 == hash%5 survive). The result is a near-total cache miss storm — a cache stampede onto the database.

Consistent hashing instead maps both servers and keys onto a hash ring (0 … 2³²−1). A key is served by the first server clockwise from its position. Adding a server inserts one new point on the ring, so only the keys in the arc between the new server and its predecessor move — about K/N keys, not all of them.

To keep load even, each physical server is placed at many points via virtual nodes.

Answer: mod-N remaps almost all keys; consistent hashing moves only ≈ K/(N+1) keys.