System Design Placement
Consistent Hashing
Imagine ChatGPT's edge caches or Instagram's feed cache fleet needs one more machine during a traffic spike. Users keep scrolling. If the fleet used (owner = hash of the key, divided by the server count, remainder taken), almost every cached key would suddenly point at a new owner. Every request would miss its cache and fall through to the origin databases at the same moment: a miss storm.
is the quieter alternative. Keys and servers are placed on one shared , so adding or removing a node moves only a slice of keys and leaves the rest warm where they already live. This page explains why modulo fails, how the ring fixes it, how much data actually moves, and what the ring still cannot do for you.
Scale-out journey
Hash the key
A user, object, or room id hashes to one point on the ring.
Walk clockwise from that point to the next live server token.
Serve or store
That node answers; replicas are the next distinct nodes further clockwise.
Add a node
Only the arc just before the new token remaps; the rest stays warm.
Try it: add and remove nodes on the hash ring
Keys and servers share one circle. Each key belongs to the first server token at or after its hash, wrapping around. Membership changes remap only the keys crossing affected arcs.
- Nodes
- 3
- Sample keys
- 8
- Remapped (last change)
- 0
- Stable keys
- 8
Ring (tokens and sample keys)
Violet dots are sample keys; colored nodes are server tokens.
Key ownership
clockwise- user:1001B
- user:1002C
- user:1003B
- user:1004C
- cache:alphaC
- cache:betaB
- session:9C
- session:42C
Add or remove a node token on the ring. Only keys whose clockwise owner changes need migration, unlike modulo hashing where N change reshuffles almost everything.
Compare to modulo. Adding one node among N often moves about 1/N keys here. Modulo remaps roughly N/(N+1) of keys when the bucket count increments by one.
What actually happens
Start with the hero scenario: a cache fleet that must decide, for every key, which machine holds it. Placement is a map from key to owner, and the simplest map is : hash the key to a number, divide by the server count N, and use the remainder as the owner index. It spreads keys evenly and it is trivially fast. It works until N changes.
The moment you add a server, hash(key) % N becomes hash(key) % (N+1). The remainder is recomputed for every key, so most keys now point at a different machine than before. The data is still sitting on the old machines, but nobody looks there any more. In a cache that means a wave of misses; in a storage cluster it means reshuffling most replicas at once.
A avoids that by putting keys and servers into the same ordered hash space, pictured as a circle. Each server sits at a token (its own hash value), and a key belongs to the first server token clockwise from the key's position. Inserting a server steals only the wedge between its token and the previous token; every other key keeps its owner. That is why caches, key-value (KV) store replicas, CDN edges (content delivery network servers placed close to users), and chat-room routers prefer it whenever membership churns.
Once ownership is stable, the remaining craft is load shape. (many tokens per machine) smooth uneven arcs, turn migrations into explicit units, and a viral still needs application help, because hashing spreads different keys but cannot split one key's traffic. Each of these gets its own section below.
Why modulo hashing breaks on scale-out
The section above claimed that "most keys move"; here is the arithmetic behind it. Under uniform hashing, growing from 3 buckets to 4 remaps roughly three quarters of keys in expectation, and the fraction gets worse as N grows: with tens or hundreds of buckets, almost every key changes owner when N increments by one. High churn, a worse invalidation percentage at large N, and a miss storm on the backends all arrive together.
Toy remap table (same keys, % 3 vs % 4)
Four keys, their hash values, and the owner index under three servers and then four. Even in this tiny sample, half the keys moved.
| Key | Hash | % 3 | % 4 | Status |
|---|---|---|---|---|
| user:1001 | 7843 | 1 | 3 | Moved |
| user:1002 | 2917 | 2 | 1 | Moved |
| user:1003 | 5520 | 0 | 0 | Stable |
| user:1004 | 9134 | 2 | 2 | Stable |
How to choose a placement scheme
Knowing why modulo fails, three questions decide which placement scheme a system should use.
1. Does membership change? A cluster whose size is fixed forever can live with . Autoscaling caches and storage nodes should start with , because they add and remove machines as a matter of routine.
2. Do you need deterministic migration units? Prefer when operators want to move named ranges by hand. Prefer a continuous when you want new servers to steal arcs automatically.
3. Is the skew about keys or requests? Ring math spreads keys. One celebrity key still concentrates every request on one owner, so it needs the application-level tactics covered under hot keys below, optionally with (a cap on how full any one bucket may get).
Simple rule of thumb
Use consistent hashing whenever nodes join and leave. Add virtual tokens until load variance matches your SLOs (service level objectives, the latency and error targets you promise), then stop, because ring metadata is not free. Quantify movement with the fractions in Numbers to know below, and treat hot keys as a separate problem.
The hash ring
Think of the ring as a sorted list with wraparound. Hash the key, find the first node token at or after that position, and wrap to the first token if necessary. The node owns the interval after the previous token through its own token. Adding a token splits only that interval. The mapping algorithm decides the intended owner; a separate migration process must actually copy or rebuild the affected data.
The choice above assumes you can picture how a ring assigns owners, so here is the mechanism in detail. Hash keys and servers into the same ordered space. Ownership walks clockwise to the next server token, and inserting a server steals an arc from its predecessor only.
Ring sizes vary by implementation: SHA-1 style explanations use a huge 0 to 2^160 - 1 space (SHA-1 produces a 160-bit hash), while production systems often use 32-bit tokens, 64-bit tokens, or . The invariant is the same: local topology changes touch local key ranges.
Interactive ring walkthrough
Use Play or Step like the sorting demos: walk each key to its clockwise owner on three servers, then add D and see how few keys remap compared with modulo when N changes.
Bright band = wedge for the highlighted step. Dashed arc = clockwise walk to the owning token.
The visualizer shows the idea in motion; the fixed example below lets you check the arithmetic by hand, then extends it to removing a server and placing replicas.
Illustrative positions
Adding a server
Insert Node E near 450. Keys previously landing between B and E move off C onto E; everything outside that wedge stays put. In general, when a new node N4 lands between existing nodes N3 and N0, the affected range is (N3, N4]: those keys move from the old clockwise owner to N4, and keys outside that arc stay where they are. How large that slice is in expectation is covered in Numbers to know below.
Removing a server
If node N1 is removed, walk anticlockwise to the previous live node, then move that arc to the next live clockwise owner. The affected range is (prev(N1), N1]; everything else remains stable. In both directions the lesson is the same: do not scan the entire keyspace, find the small ring segment whose owner changed and migrate only that segment.
Replica placement
Virtual tokens are not independent failure domains. If the next three tokens all belong to one physical host, storing three copies there still loses all copies when that host fails. Walk to distinct physical owners and, where required, distinct racks or zones. Membership changes must preserve enough healthy copies while data moves, and readers need a defined policy when their routing map is temporarily stale.
The primary owner is usually the first token clockwise. Replicas should walk further clockwise to distinct physical nodes and distinct failure domains (racks or zones that tend to fail together). On a ring where Node B is the first token clockwise from position 420 (a different token layout from the sketch above), the chain looks like this:
- Distinct machines: two virtual nodes on the same host are not two durable copies.
- Distinct racks or zones: replica walkers skip owners in the same failure domain when durability needs it.
- Repair after failure: successor replicas serve reads while repair streams missing ranges to replacement capacity.
Numbers to know: how much actually moves
The expected moved fraction of about 1 / (N + 1) when adding a node assumes balanced placement and equal node capacity. It describes primary ownership; replicated copies, skewed object sizes, and repair traffic can change actual bytes transferred. A few very large objects can dominate copy time even when few keys move. Estimate bytes and request load in addition to key count.
Every section so far has said "only a slice moves". This card is the one place on the page with the fractions and worked sizes; later sections point back here instead of repeating them. The useful number is how much data moves when membership changes: consistent hashing keeps movement proportional to the changed capacity, not the full cluster.
Add one node
Adding one node to N existing nodes moves about 1 / (N + 1) of keys; 9 → 10 nodes moves about 10%.
Remove one node
Removing one node from N nodes moves about 1 / N of keys, reassigned to surviving owners or replica sets.
Modulo growth
N → N + 1 remaps roughly N / (N + 1) of keys under modulo; 9 → 10 nodes moves about 90%.
Virtual and weighted tokens
More tokens reduce load variance but not the expected total moved, and they add routing metadata and membership chatter. Bigger nodes get proportionally more tokens so ownership follows capacity.
Worked examples
10 TB cache. A 20-node cache holding 10 TB adds one node. The expected moved fraction is about 1/21, so roughly 476 GB moves. At a safe migration throttle of 250 MB/s, raw copy time is about 32 minutes before checksum validation (verifying copied bytes match), retries, and cache warm-up.
Million-user sizing. If 1M user profiles average 20 KB of cached state, the total cached payload is about 20 GB. Adding a 10th cache node moves about 2 GB plus metadata and warm-up reads; modulo hashing could churn about 18 GB and spike backend load.
Cost estimate formulas
move_time = bytes_to_move / safe_migration_bandwidth. Moving 2 TB at a throttled 200 MB/s takes about 2.8 hours before verification, retries, and read repair.
The fixed-slot version: slot_bytes = total_bytes / slot_count and move_time = slots_moved x slot_bytes / safe_bandwidth. Uneven slot ownership is normal during migrations; track target ownership and drain old slots gradually.
Shaping load: virtual nodes and fixed slots
The fractions above assume tokens are spread evenly around the ring, and with only a few machines they are not. Two tools fix the shape of the load: virtual nodes smooth it statistically, and fixed slots make every migration an explicit, named unit.
Few physical machines produce uneven arcs on the ring, so map each host to many virtual tokens and the statistical load evens out, trading metadata for smoother skew. Typical vnode counts land in the low hundreds per physical node in older ring-based designs. Load variance often improves roughly like 1/√(vnode count), until membership metadata, gossip (the peer-to-peer messages nodes exchange to learn who is alive), and repair overhead dominate.
Virtual node sketch
- Amaps to many tokens on the ring (for example A0 … A149), not just one.
- B, Cfollow the same pattern, so each physical machine occupies lots of small arcs.
- More ring points mean narrower wedges move when one host joins or leaves.
The same trick handles mixed hardware: weighted tokens give a large-RAM node more vnodes and a small node fewer, so ownership matches capacity. The cost is heavier routing tables on every client and router that needs the map.
Instead of a continuous ring, allocate a fixed number of hash slots and migrate whole slots between masters: predictable rebalancing for in-memory clusters. Some clustered key-value stores map keys to a fixed slot count via hash(key) % slot_count, and operators move slot ranges during scale events.
Three masters: equal thirds (illustrative)
Adding Node D
Migrate contiguous slot bands from the incumbents until each master owns roughly ¼ of the space.
The slot count is a compromise: small enough for compact cluster heartbeat bitmaps (the per-node map of who owns what), large enough to subdivide across many nodes.
Useful variants, and the hot key no ring can fix
Virtual nodes smooth ownership across many distinct keys; they do not divide requests for one key among independent owners. Bounded-load placement can limit assigned units, but a single viral object still needs caching replicas, request coalescing, or application-level splitting. Distinguish too many keys on one node from too many requests to one key before choosing a remedy.
The token ring is not the only way to get "only a slice moves". Jump hashing avoids storing a ring but only supports ordered bucket append and remove; rendezvous picks the highest-scoring node without tokens; bounded load caps how greedy clockwise walks become under skew. All three share one limit with the plain ring, covered at the end of this card.
Jump consistent hash
A stateless mapping function with no sorted ring in memory. Uniform when buckets only grow or shrink at the end; arbitrary removals need another scheme.
int jump_hash(uint64 key, int n) {
int64 b = -1, j = 0;
while (j < n) {
b = j;
key = key * 2862933555ULL + 1;
j = (b + 1) * (1LL << 31)
/ ((key >> 33) + 1);
}
return (int)b;
}Bounded-load variants cap the amount of assigned work or keys on a host and place overflow on another eligible owner. This can reduce imbalance across many keys, at the cost of more placement coordination and possible extra movement. It does not automatically split one extremely popular key’s requests; that case still needs application-level replication or decomposition.
Score each (key, node) pair and send traffic to the highest-weight node (HRW stands for highest random weight). Removing a node only affects its winners. Lookup is O(nodes), meaning every node is scored per request unless augmented, so it suits modest membership lists.
Application-level
Hashing spreads different keys, not all requests. One viral key still lands every request on the same owner, so the fixes live above the ring, alongside the bounded-load routing described in the variant card.
- Shard writes: spread a viral key across suffixes such as
post:id:{0..99}, then aggregate on read. - Request coalescing: collapse duplicate misses so one backend read fills many waiting clients instead of stampeding storage.
- Explicit override: route reads for known viral keys to a replica pool or precomputed snapshot instead of the ring.
Where you meet it
With the mechanism and its variants covered, it helps to notice how often the same remap intuition appears under different names and constraints. Managed wide-column tables (databases that store rows as sparse column families across many partitions) derive partition placement from hashed keys; splits migrate token ranges while replication follows successor lists on the ring abstraction. Wide-column token ranges are the same idea made visible: a wide 64-bit token space, replication that walks the ring for RF copies (RF is the replication factor, the number of copies kept), and repairs that reconcile divergence across peers.
Outside databases, CDN edges hash URLs to edge subsets so fleet growth reshuffles a bounded slice of cached objects instead of the entire catalog. Stateful realtime routers pin room or channel ids to processes so related streams stay together, and membership churn migrates only the affected cohorts. Network load balancers use consistent lookup tables so backend changes disrupt only a limited fraction of flows while per-packet lookup stays fast.
Rebalancing in production: playbook, failures, drills
Consistent hashing minimises how much moves; production correctness comes from controlled migration and versioned membership. The winning explanation is not "we use a ring" but "we move only the affected ranges, throttle migration, and protect hot keys separately." This card is that explanation as a playbook, plus what still goes wrong and how to rehearse it.
The rebalancing playbook
Publish membership changes with a version and define how stale clients are redirected or refreshed. For a cache, an affected key may be refilled from origin under a controlled miss budget. For authoritative storage, copy the range, catch up concurrent writes, validate it, and transfer ownership using the database’s migration protocol. Rate-limit movement so repair traffic does not starve the user requests that motivated adding capacity.
- Detect. Membership changes arrive through health checks, gossip, the control plane, or orchestration events.
- Publish. Ship a new versioned ring or slot map, keeping the old map available for in-flight clients.
- Move. Stream only the token ranges whose owner changed, throttled below customer headroom, with checksums.
- Drain. Old owners keep serving or forwarding during handoff; dual-read or dual-write catches lag but costs extra requests.
- Verify and flip. Check counts, checksums, and sampled reads, then flip authoritative ownership in the routing map.
- Keep a rollback window before deleting source copies, so a bad flip can still be undone.
Degraded modes: what still breaks
Consistent hashing reduces remap, but membership bugs and overloaded owners still take systems down. Name the safe behaviour for each case before it happens.
Node loss. Serve from the remaining replicas, throttle repair, and avoid instantly reclaiming the dead node's full capacity as new write headroom.
Stale ring map. Clients holding an old version may send to drained owners. Keep dual-serve or redirect during handoff, and reject writes that fail fencing checks (proof that the writer still owns the range).
Hot key or viral object. Ring placement cannot spread one key; fall back to local cache, replica reads, or the hot-key tactics in the previous card.
Migration overload. Cap stream bandwidth so rebalance does not starve live traffic, and prefer longer migrations over availability loss.
Common follow-ups
- Why virtual nodes? They smooth uneven ring gaps and allow weighted capacity per machine.
- What if one key is viral? Hashing spreads keys, not requests; use the hot-key tactics above.
- How do replicas work? Walk clockwise to the next distinct physical nodes, or use slot-map replica assignments.
- How do you avoid cache stampedes? Warm moved ranges gradually, cap migration bandwidth, and coalesce misses under soft TTLs (refresh before expiry).
Drills to run
- Add and remove one node under load, measuring moved bytes, p99 latency (slowest 1%), and error rate.
- Publish a stale ring version to a canary (small test) client fleet; confirm redirects or dual-read prevent silent loss.
- When explaining, quantify the expected move fraction (Numbers to know), then cover hot keys and versioned membership separately.
Minimal ring sketch (Python)
To make the mechanism concrete in code: production rings use better hashes and replication walkers, but this sketch shows how bisect (a binary search over the sorted tokens) picks an owner, and how virtual nodes and weights simply become extra tokens per node.
from bisect import bisect_left
import hashlib
def _h(s: str) -> int:
return int(hashlib.md5(s.encode(), usedforsecurity=False).hexdigest(), 16) % (2**32)
class ConsistentHashRing:
def __init__(self, nodes=None, vnodes=150):
self.vnodes = vnodes
self.ring = {} # token -> physical node
self._sorted = []
self.nodes = set()
for n in nodes or []:
self.add_node(n)
def _rebuild(self):
self._sorted = sorted(self.ring.keys())
def add_node(self, node, weight=1):
self.nodes.add(node)
for i in range(self.vnodes * weight):
self.ring[_h(f"{node}:vn:{i}")] = node
self._rebuild()
def remove_node(self, node):
self.nodes.discard(node)
self.ring = {p: n for p, n in self.ring.items() if n != node}
self._rebuild()
def get_node(self, key):
if not self.ring:
return None
pos = _h(key)
i = bisect_left(self._sorted, pos)
if i == len(self._sorted):
i = 0 # wrap clockwise around ring
return self.ring[self._sorted[i]]Wrap-up
You have seen why modulo fails, how the ring bounds movement, the numbers behind it, and the operational work around it. The takeaway below compresses that, and the sources are where the ideas were first written down.
Key takeaway
Prefer consistent placement whenever nodes join and leave regularly. Add virtual tokens until load variance matches your SLOs (latency and error targets), then stop: metadata isn't free. Combine ring routing with replication factor ≥ 3 for durability, bounded-load or explicit hot-key paths for skew, and slot-based schemes when your orchestrator wants deterministic migrations. Re-evaluate modulo hashing only for perfectly static cluster sizes.
Primary sources
- Karger et al.: Consistent Hashing (1997): the seminal paper that introduced the technique and its movement guarantees.
- Amazon Dynamo: consistent hashing: virtual nodes and preference lists (the ordered replica list per key) in a production store.
- Redis Cluster Spec: Hash slots: fixed-slot consistent placement in practice, the scheme sketched in the slots section above.
Practice and further reading
Use these exercises to connect the lesson to a design decision. State your assumptions, trace what happens to one request, and explain the rule that must remain true even during a failure. That rule is the design's correctness invariant.
Focus for this lesson: Place keys with a versioned ring or rendezvous scheme, virtual-node weighting, bounded load, replication, and controlled membership movement.
Explain the decision
Why use virtual nodes on a consistent-hash ring?
Read the reasoning
They smooth distribution, represent heterogeneous capacity with weights, and spread each physical node across failure/rebalance ranges.
Apply it to a production scenario
A node joins but old and new clients use different ring versions. What protects correctness?
Read one approach
Publish immutable versioned maps, reject or redirect stale writes, support dual lookup during transition, and cut over only after movement is verified.
Work through the numbers
Adding one node to a balanced 20-node ring moves roughly what fraction of keys?
Read the worked calculation
About 1/21 ≈ 4.8% ideally, though virtual-node distribution and replication change actual movement.
Reason through a failure
What must a membership change preserve?
Read the recovery reasoning
Each partition keeps the required replica count and an authoritative owner; concurrent maps cannot silently accept divergent writes.