Consistent Hashing

01The problem: sharding a growing system

Imagine you’re designing a ticketing system like TicketMaster. At the start it’s simple: one database holds all event data, clients make requests to fetch event information, and everything works smoothly.

Success brings load. As the platform hosts more events, a single database can no longer keep up, so you distribute the data across multiple databases — a process called sharding. That immediately raises the question everything else hangs on:

02First attempt: simple modulo hashing

The most straightforward way to place data across databases is modulo hashing:

1. Take the event ID and run it through a hash function, turning it into a number.
2. Take that number modulo the number of databases (%).
3. The result tells you which database stores that event.

# any hash function works here — md5, murmur, etc.
database_id = hash(event_id) % number_of_databases

With three databases:

hash(1234) % 3 = 1  →  Database 1
hash(5678) % 3 = 0  →  Database 0
hash(9012) % 3 = 2  →  Database 2

This works great — until the cluster changes size.

Problem 1 · Adding a database remaps almost everything

To add a fourth database you naively switch the code to modulo 4:

database_id = hash(event_id) % 4

You push to production and database activity goes through the roof — and not just on the new instance, on all of them. Changing the divisor didn’t only affect data destined for the new node; it changed where almost every event maps.

The result is a mass redistribution across all instances: a huge spike in database load, users unable to reach data or seeing slow responses.

Problem 2 · Removing a database does the same thing

Now suppose a database goes down — hardware failure, a bug, anything. You remove it from the pool and redistribute its data over the survivors. But the divisor changes from % 3 to % 2, and you hit the exact same redistribution problem: data that had no reason to move gets shuffled anyway.

03Consistent hashing: the hash ring

The mechanism is three steps:

1. Create a hash ring with a fixed number of points. To keep it simple, say 0–100.
2. Place the database nodes on the ring. With four databases you might place them at 0, 25, 50, and 75.
3. To locate an event, hash its ID as before — but instead of taking a modulo, find that value on the ring and walk clockwise until you hit a database. That’s where it lives.

Adding a database (DB5)

Add a fifth database at position 90. Now:

• Only events hashing to the range 75–90 need to move.
• Those events were previously walking clockwise to DB1 (at 0).
• Every other event stays exactly where it was.

Where modulo forced almost all data to move, here you relocate only about 60% of DB1’s events (the 15-unit slice from 75–90 out of DB1’s 25-unit span) — roughly 15% of all events. There is no mass redistribution.

Removing a database

If DB2 (at position 25) fails:

• Only events that mapped to DB2 need to move.
• They now walk clockwise to DB3 (at position 50).
• Everything else stays put.

04Virtual nodes

One problem remains. When DB2 failed above, all of its events landed on its single clockwise neighbor, DB3. Now DB3 carries 2× the load of DB1 and DB4. We’d prefer the departed node’s load to spread evenly rather than dump onto one neighbor.

For example, instead of only hashing "DB1" to position 0, you hash its variants to positions like 20, 35, 65. Do this for every database and the ring becomes a fine-grained mix of small arcs owned by different physical nodes.

The more virtual nodes per database, the smoother the distribution. And it helps on the way in, too:

05Addressing hot spots

Even with virtual nodes distributing data evenly, hot spots can still occur.

Strategies real systems use:

06Data movement in practice

Consistent hashing tells you where data should live — it doesn’t teleport terabytes when a node dies. In practice, most distributed databases pair consistent hashing with replication so failures need no data movement at all.

• DynamoDB replicates each partition across three availability zones. When a primary fails, a replica is promoted via a consensus algorithm like Raft — no data moves.
• Cassandra works similarly, replicating data to N consecutive nodes on the ring so reads can be served from surviving replicas.

Real data movement happens only during planned membership changes — adding capacity, or permanently replacing a node to restore the replication factor. Even then, consistent hashing guarantees only a bounded fraction of keys must be re-replicated, never the whole dataset.

07Consistent hashing in the real world

Although the example scaled a database, consistent hashing applies to any scenario where you distribute data across a cluster — databases, caches, message brokers, or even a pool of application servers.

• Apache Cassandra — distributes data across the ring.
• Amazon DynamoDB — uses it under the hood for partition placement.
• CDNs — decide which edge server should cache specific content.

08When to use it in an interview

Most modern distributed systems handle sharding and data distribution for you. When you design a system on DynamoDB or Cassandra, you usually just need to mention that these use consistent hashing (or a form of it) under the hood to scale. Most interviews stop there.

In those deep infrastructure interviews, be ready to explain:

1. Why consistent hashing beats modulo-based sharding for data distribution.
2. How virtual nodes improve load balancing across the cluster.
3. Strategies for handling node failures and additions.
4. How hot spots arise and how to mitigate them (replication, key salting).
5. The relationship between consistent hashing and replication for fault tolerance.

09The one loose end: “consistent hashing” is used loosely

Consistent hashing solved a deceptively simple problem: distribute data across servers while minimizing redistribution when the server count changes. The implementation gets intricate, but the core is elegant — arrange everything in a circle and walk clockwise.

11Quick revision