Consistent Hashing — Part 1: Foundations & Core Concepts

maang.io System Design Series

---

What is this?

Picture the grand circular lobby of a very busy hotel. Around the rim of that round room stand a handful of concierges, each at a fixed spot. There's one house rule every guest learns instantly: when you walk in, you head clockwise around the rim until you reach the first concierge you meet — that's the one who serves you, remembers your bookings, holds your luggage tag. Simple, and it means any guest can figure out their own concierge without asking a manager.

Now here's the magic. One concierge clocks off for a break. Do all the guests get reshuffled to new concierges? No — only the guests who would have walked up to the one who left simply keep walking clockwise to the next concierge. Everyone else is completely undisturbed. Hire a new concierge and slot them into an empty spot on the rim, and they quietly take over just the guests in the little arc right before them. The rest of the lobby doesn't even notice.

That circular lobby is consistent hashing. The rim is a ring of hash values, the concierges are your servers, the guests are your keys (cache entries, database rows, user sessions), and "walk clockwise to the first one you meet" is the entire placement rule. Its whole reason to exist is that one lovely property: adding or removing a server disturbs only a small slice of the keys, not all of them.

The one-line idea: Put both the keys and the servers onto the same circular hash space, and let each key belong to the first server it meets going clockwise. Then adding or removing a server remaps only about 1/N of the keys — one server's share — instead of nearly all of them. That single property is what makes elastic, always-on distributed systems practical.

We'll keep returning to this hotel lobby across all three parts. Let's first see the pain it was invented to cure.

---

1. Why it exists — the hash % N disaster

Say you're running a distributed cache: 4 memcached servers, and you want to spread millions of keys across them evenly. The obvious first idea is modulo hashing:

server_index = hash(key) % N        # N = number of servers

Hash the key to a big number, take it modulo 4, and you get a server 0–3. It's beautifully simple, it spreads keys evenly, and it's O(1) to compute. For a fixed fleet, it's genuinely fine.

The disaster shows up the moment N changes — and in a real system, N changes all the time: a server crashes, you scale out for Black Friday, a box gets cycled for a kernel patch. Watch what happens when you go from 4 servers to 5:

Changing the divisor scrambles the arithmetic for nearly every key. When you add one server to a fleet of N, modulo hashing remaps roughly N/(N+1) of all keys — for a big fleet, that's basically all of them.

Why is this catastrophic? Think about what those keys are:

• A cache: every remapped key is now a cache miss. Add one node and almost your entire cache goes cold at once — a thundering herd of misses slams your database exactly when you were trying to relieve load. Teams have taken down their primary database by adding a cache server.
• A sharded datastore: every remapped key is a row that must physically move to a new machine. Resharding that copies ~100% of your data every time you scale is a non-starter.

This is the pain. You want to change the size of the fleet cheaply — move only the keys that genuinely need to move. That's exactly, and only, what consistent hashing gives you.

💡 The one-sentence contrast that interviewers want to hear: modulo hashing binds every key's location to the total count N, so changing N moves everything; consistent hashing binds a key only to its neighbor on the ring, so changing the fleet moves only the neighbors.

---

2. The mental model — the ring

Here's the whole idea, built up in four moves. Keep the hotel lobby in mind.

Move 1 — Draw a ring (the hash space). Take the output range of a hash function — say a 32-bit hash, the integers 0 to 2³²−1 (about 4.29 billion) — and bend that line into a circle so that the largest value wraps back around to 0. Every possible hash value is now a point on the rim. This ring is fixed and enormous; it never changes size.

Move 2 — Place the servers on the ring. Hash each server's identity (its name, IP, or ID) to get a point, and stand the server at that point on the rim. Four servers → four concierges scattered around the circle.

Move 3 — Place the keys on the ring. Hash each key the same way to get its point on the rim.

Move 4 — Assign by walking clockwise. A key is owned by the first server you reach going clockwise from the key's point. (That server is called the key's successor.) If you walk clockwise past the top of the ring, you wrap around to 0 and keep going — the circle has no end.

That's it. Every server owns the arc of the ring that sits counter-clockwise before it, up to the previous server. The vocabulary you'll reuse everywhere:

Term	Plain meaning
Ring / hash space	The circle of all hash values (0 … 2³²−1), wrapping at the top.
Node / token	A server placed at a point on the ring. Its point is its token.
Key	The thing being placed (a cache entry, a row, a session).
Successor	The first node clockwise from a key — the key's owner.
Arc / range	The stretch of the ring a node owns (from the previous node up to itself).

Now replay the two operations that made modulo hashing explode:

• Remove a node (a concierge leaves): only the keys in that node's arc need a new owner, and they all flow to the next node clockwise. Every other arc is untouched. That's ~`1/N` of the keys moving, not all of them.
• Add a node (hire a concierge, slot them in): the newcomer lands on some point and steals just the slice of arc between itself and the previous node from whatever node used to own it. Again ~`1/N` of the keys move; the rest never budge.

That contrast — reshuffle everything vs disturb one neighbor — is the entire payoff.

---

3. How you actually use it

You rarely implement the ring by hand; it lives inside a library or a datastore. But the shape is worth seeing once, because it's genuinely tiny. The core is a sorted collection of node points plus a lookup:

import bisect, hashlib

def h(s: str) -> int:                      # 32-bit hash of a string
    return int(hashlib.md5(s.encode()).hexdigest(), 16) % (2**32)

class HashRing:
    def __init__(self, nodes):
        self.ring = sorted(h(n) for n in nodes)     # node points, sorted
        self.by_point = {h(n): n for n in nodes}

    def get_node(self, key: str) -> str:
        point = h(key)
        i = bisect.bisect(self.ring, point)         # first node clockwise
        if i == len(self.ring):                      # wrapped past the top
            i = 0
        return self.by_point[self.ring[i]]

Read the lookup slowly, because it's the whole algorithm: hash the key to a point, then binary-search the sorted list of node points for the first one that's ≥ the key — that's "walk clockwise to the first node." Wrap to index 0 if you fell off the top. Lookup is O(log N) in the number of nodes (a binary search), and the ring itself is a handful of integers in memory. That's all it takes to make a fleet elastic.

In practice you reach for it through something that already speaks "ring":

# memcached client (Ketama), configured to hash consistently
# instead of the naive modulo — so losing one server evicts
# only that server's slice, not the whole cache.
distribution = "consistent"      # Ketama ring, ~160 points/server
hash         = "md5"
servers      = ["cache-1:11211", "cache-2:11211", "cache-3:11211"]

You'll meet the same ring, unnamed, inside Amazon DynamoDB and Apache Cassandra (the ring that decides which node owns a partition — see the Apache Cassandra topic), inside load balancers that pin a user to a backend, and inside CDNs choosing an edge cache. Wherever a system must spread data across an elastic fleet and survive members joining and leaving, there's a consistent-hash ring somewhere underneath.

---

4. When to reach for it — and when not

Reach for consistent hashing when all three of these are true:

1. You're spreading keys across a set of nodes (cache, shard, backend pool).
2. That set changes membership over time — scaling, failures, rolling restarts.
3. You care that a change moves as little data as possible (warm caches, cheap rebalancing).

If the fleet is genuinely fixed forever, plain hash % N is simpler and perfectly fine — don't add a ring for elasticity you'll never use. And consistent hashing is not the only tool for the "minimal movement" job; know its cousins:

Approach	How it decides ownership	Reach for it when…
hash % N	hash(key) mod N	The fleet never changes. Dead simple, O(1).
Range partitioning	Sorted key ranges per node (A–F, G–M, …)	You need ordered scans across keys — but watch for hot ranges. See the Partitioning (Sharding) topic.
Consistent hashing	First node clockwise on a ring	Elastic fleet, want minimal reshuffling, O(log N) lookup. The default for distributed caches and Dynamo-style stores.
Rendezvous (HRW) hashing	Pick the node with the highest hash(key, node)	Small/medium fleets; no ring to maintain, but O(N) per lookup.
Jump consistent hash	A clever O(log N) formula, no memory	Node count only grows/shrinks at the end; you can't remove an arbitrary node.

We'll compare these head-to-head in Part 3 — interviewers love asking "why the ring and not rendezvous hashing?" For now, hold the shape: consistent hashing is the general-purpose answer when membership churns and you want the churn to stay cheap.

⚠️ One honest caveat you should carry into Part 2: the plain ring spreads keys well on average, but with only a few nodes the arcs can come out wildly uneven — one concierge stuck with 40% of the lobby, another idling with 8%. Real systems fix this with virtual nodes, which is the first thing we unpack next. Plain consistent hashing is the idea; virtual nodes are what make it usable.

---

5. Key takeaways

1. The problem: hash % N ties every key to the fleet size N, so adding or removing one server remaps nearly all keys — a cache-miss storm or a full data reshuffle. That's the pain consistent hashing exists to remove.
2. The model: put keys and nodes on the same circular hash space (the ring); a key belongs to the first node clockwise (its successor). Each node owns the arc before it.
3. The payoff: adding or removing a node moves only that node's arc — about 1/N of the keys. Everyone else stays put, so caches stay warm and rebalancing is cheap.
4. The implementation is tiny: a sorted list of node points plus a binary search — O(log N) lookup, a few integers of state. You usually get it via a library (Ketama) or a datastore (Cassandra, DynamoDB).
5. Reach for it when an elastic fleet must minimize data movement on membership change; know its cousins (modulo, range, rendezvous, jump). And note the caveat we fix next: the plain ring can be unbalanced — virtual nodes are the cure.

Next, Part 2 opens the machinery: the sorted-map data structure behind the ring, virtual nodes and the math of why they balance load, how replication walks the ring, the bounded-load variant that tames hot nodes, and a worked example with real numbers.