AlgoInsight

System Design

The Word I Didn't Have: Consistent Hashing

I'd built it in production for two years before I knew what it was called. Then a Google interviewer asked me to invent it on a whiteboard in forty-five minutes.

By Admin2026-06-1811 min readconsistent-hashingdistributed-systemssystem-designcachingshardingscalability

The interviewer drew four boxes on the whiteboard, called them cache servers, and asked me how I'd spread a few billion keys across them so the load stayed even. Then he asked the real question - the one I now know was the whole point: "What happens when you add a fifth box?"

I had been doing exactly this in production for two years. At Razorpay we were running a payment system moving eight hundred crore rupees a day, and underneath it was a fleet of cache nodes that we added to and removed from constantly. I knew, in my hands, how to keep that fleet from falling over when a node joined. I had written the code. I just could not, in that room, with a stranger watching and a clock running, say the word for what I had built.

I drew something close. I waved at it. The interviewer nodded politely and moved on, and I walked out of that onsite knowing I had failed a question I had already solved at scale in the real world.

The word was consistent hashing. This post is the explanation I wish I'd had ready that day - built from nothing up to the version a senior engineer is expected to know. If you have ever felt the gap between knowing how something works and being able to explain it under pressure, this one is for you.

Start with the obvious idea (and watch it break)

Forget consistent hashing for a second. You have some keys - user sessions, cached profiles, whatever - and you have N servers to store them on. How do you decide which server holds which key?

The first idea everyone has is the right place to start, because it's almost correct:

Hash the key to a number, then take that number modulo the server count. server = hash(key) % N.

It's clean. It spreads keys evenly. Look up user:42, hash it, mod by 4, and you always land on the same server. No central directory, no lookups - pure arithmetic. For a fixed set of servers, this is genuinely fine.

The trap is the word fixed.

Servers are not fixed. They crash. You add capacity on Black Friday. A deploy cycles a node. The moment N changes - even by one - every key's hash(key) % N is recalculated against a different N, and the answer changes for almost everybody.

Don't take my word for it. This is the kind of claim you should make a machine prove to you:

import hashlib

def server_for(key, num_servers):
    h = int(hashlib.md5(key.encode()).hexdigest(), 16)
    return h % num_servers

keys = [f"user:{i}" for i in range(10000)]

before = {k: server_for(k, 4) for k in keys}   # 4 servers
after  = {k: server_for(k, 5) for k in keys}   # we added ONE server

moved = sum(1 for k in keys if before[k] != after[k])
print(f"Added 1 server (4 -> 5).")
print(f"Keys that moved: {moved} out of {len(keys)}")
print(f"That's {moved / len(keys) * 100:.0f}% of all keys remapped.")

Run it. Adding a single server moves roughly four out of every five keys.

Now think about what "a key moved" means when those servers are a cache. Every moved key is now a cache miss. Eighty percent of your traffic stampedes past the cache and hits the database all at once - the exact moment you added a server because you were already under load. This is how a capacity increase turns into an outage. I have watched it happen. It is not theoretical.

Warning: hash(key) % N is the default mental model almost every candidate reaches for, and it is correct right up until the server count changes. In an interview, proposing it is fine - not seeing why it falls apart is what loses you the round.

So the real problem isn't "how do I distribute keys." It's narrower and sharper:

How do I distribute keys so that adding or removing one server moves as few keys as possible?

That single reframing is the whole reason consistent hashing exists.

The ring

Here's the idea that fixes it, and it's beautifully simple once you see it.

Instead of hashing keys into a list of servers, hash everything onto a circle - imagine all possible hash values, 0 up to some huge number, bent around into a ring that wraps from the top back to the bottom.

Two things go on this ring:

  1. The servers. Hash each server's name ("server-A", "server-B"…) to a point on the ring. Now each server sits at a fixed position on the circle.
  2. The keys. Hash each key the same way. It lands at some point on the ring too.

To find which server owns a key, you start at the key's position and walk clockwise until you hit the first server. That server owns the key. That's the entire lookup rule.

graph LR
    K[key: user:42<br/>lands here] -. walk clockwise .-> S2
    S1[Server A<br/>position 10] --> S2[Server B<br/>position 90]
    S2 --> S3[Server C<br/>position 150]
    S3 --> S4[Server D<br/>position 220]
    S4 --> S1

This diagram shows four servers - A, B, C, and D - arranged in a circle at positions ten, ninety, one hundred fifty, and two hundred twenty. The servers are connected in a loop: A points to B, B to C, C to D, and D back to A, forming a ring. A key called user:42 lands somewhere on the ring and a dashed arrow shows it walking clockwise to the next server it reaches, which is Server B. That server becomes the owner of the key.

Now replay the disaster from before, but on the ring. You add a fifth server, Server E. It lands at some single point on the circle. Ask yourself: which keys are affected?

Only the keys that sit in the arc just before E - the ones that used to walk clockwise past that spot to reach the next server, and now stop at E instead. Every other key on the entire ring still walks to exactly the same server it always did. Nothing else moves.

That's the magic. Adding a server reshuffles one slice of the circle, not the whole thing. Mathematically, joining or leaving moves only about K/N keys (K keys across N servers) instead of nearly all of them.

Important: The one sentence to carry out of this post: with plain modulo, changing the server count remaps almost every key. With consistent hashing, it remaps only the keys in one arc of the ring. That's the difference between a graceful scale-up and a self-inflicted outage.

The catch nobody mentions first

If I stopped here, you'd have the textbook answer - and you'd get caught on the very first follow-up, the same way I did.

Look back at that ring. The servers landed at positions 10, 90, 150, and 220 - because that's where their names happened to hash to. We didn't choose those spots. The hash did, and the hash doesn't care about fairness.

So what if, by luck, three servers hash close together and one ends up alone on the far side of the circle? That lonely server now owns a giant arc - half the keys - while the other three split the rest. Your "even" distribution is anything but. One node runs hot and falls over; the others sit idle.

It gets worse on failure. When a server dies, all of its keys flow to the single next server clockwise. That neighbor suddenly inherits a double load and can tip over too - a cascading failure walking around the ring.

So the naive ring solves the remapping problem but reopens the balance problem. A strong candidate names this gap before the interviewer does.

Virtual nodes: the fix that separates the levels

Here's the move that turns "I read about consistent hashing once" into "I've actually thought about this."

Instead of placing each physical server at one point on the ring, place it at many - a hundred, two hundred - by hashing "server-A#1", "server-A#2", "server-A#3", and so on. Each of those is a virtual node, and they all point back to the same physical machine.

Now Server A isn't one fat arc sitting in one place - it's two hundred tiny slivers scattered evenly all around the circle. So is every other server. Two things fall out of this, both important:

And again - don't trust me, prove it:

import hashlib, bisect
from collections import Counter

class HashRing:
    def __init__(self, servers, vnodes=100):
        self.ring = {}
        self.sorted_hashes = []
        for s in servers:
            for v in range(vnodes):              # many points per server
                h = self._hash(f"{s}#{v}")
                self.ring[h] = s
                bisect.insort(self.sorted_hashes, h)

    def _hash(self, key):
        return int(hashlib.md5(key.encode()).hexdigest(), 16)

    def get_server(self, key):
        h = self._hash(key)
        i = bisect.bisect(self.sorted_hashes, h) % len(self.sorted_hashes)
        return self.ring[self.sorted_hashes[i]]

ring = HashRing(["A", "B", "C", "D"], vnodes=100)
load = Counter(ring.get_server(f"user:{i}") for i in range(10000))
print(dict(load))

Ten thousand keys across four servers, and the counts come out close to 2,500 each - even though we never told the ring to balance anything. The virtual nodes did it for free.

Tip: The lookup itself is a binary search over the sorted ring positions - O(log V), where V is the number of virtual nodes. That bisect call is the entire runtime cost. Cheap.

The trade-off, because there's always one: more virtual nodes means more metadata to track per server. A few hundred per node is the sweet spot real systems settle on. That's the kind of sentence - "here's the knob and here's what turning it costs" - that makes an interviewer lean in.

Where this actually lives

This isn't a whiteboard toy. Consistent hashing is load-bearing infrastructure underneath systems you used today:

When you can say "this is the partitioning scheme behind Dynamo and Cassandra" in an interview, you've stopped reciting a definition and started showing you know where the concept lives in the wild. That shift is most of what "senior" sounds like.

What I'd say now

The thing I couldn't do in that Google room wasn't invent consistent hashing. I'd already built it - virtual nodes and all - to keep a payments cache alive. What I couldn't do was compress two years of hands-on intuition into a clean forty-five-minute narrative: here's the naive approach, here's exactly how it breaks, here's the ring, here's the balance problem, here's virtual nodes, here's the trade-off.

That sequence is the answer. Not the cleverness - the ordering. Knowing it in your hands and being able to say it out loud, in order, while someone judges you, are two completely different skills. Interviews test the second one, and almost nobody practices it.

That gap - between what you've built and what you can articulate when it counts - is the entire reason six of us, plus Swati, started AlgoInsight. Between us we collected 58 FAANG rejections learning this the slow, expensive way. The point of the platform is that you don't have to.

If this clicked, Consistent Hashing is one lesson inside System Design Fundamentals - where we walk the same path for sharding, replication, caching, and the dozen other building blocks an interviewer expects you to assemble live. Same approach every time: build it from the obvious wrong answer up to the version that gets you hired.

Go deeper

More articles