Consistent Hashing Explained: The Ring, Virtual Nodes, and Moved Keys

Why hash mod N remaps most keys

The simplest placement is server = hash(key) mod N. It spreads keys evenly and needs no stored state, until N changes. Going from 4 servers to 5, a key stays on the same server only if hash mod 4 equals hash mod 5, which happens when hash mod 20 is 0, 1, 2 or 3. That is 4 of every 20 values, so roughly 80% of keys move. The script later in this guide measured 8,035 moves out of 10,000 keys.

In a cache tier, every moved key is a miss on its new server, so adding capacity sends a burst of reads to the database at exactly the moment you are scaling. In a storage tier, every moved key is data copied across the network. NGINX's documentation states the same trade-off for its own hash method: without the consistent parameter, adding or removing a server may remap most keys, while the ketama-based consistent mode remaps only a few.

• NGINX documentation: ngx_http_upstream_module (hash, consistent)

Build the ring: one hash space for servers and keys

Hash each server onto the same space as the keys, for example 0 to 2^64 − 1, and treat that range as a circle. A key belongs to the first server found by walking clockwise from the key's hash, wrapping past the top back to zero. In code, the ring is a sorted array of server positions and the walk is a binary search, so a lookup costs O(log M) for M positions on the ring.

Now add server E. It takes over only the keys between its counter-clockwise neighbor D and itself, which previously walked on to A. No other key changes owner, and every key that moves goes to E. Removing a server hands its arc to the next server clockwise. Karger and colleagues introduced the idea in 1997 for distributed web caches, describing a hash function that changes minimally as its range of servers changes.

• Karger et al. (1997): Consistent Hashing and Random Trees

Virtual nodes fix uneven arcs

With one position per server, arc lengths are random and can differ wildly. In the measured run, five servers with one point each owned between 124 and 4,077 of the 10,000 keys, and the new server E took 1,695. The Dynamo paper names both problems with the basic scheme: random positions lead to non-uniform data and load distribution, and the algorithm ignores differences in server capacity.

Virtual nodes give each physical server many positions, often called tokens. With 100 per server, the same run produced loads between 1,814 and 2,239 against an ideal of 2,000. When a server leaves, its many small arcs spread its load across many survivors instead of dumping it all on one neighbor, and a larger machine can simply receive more virtual nodes. The cost is a bigger ring to store and rebuild; Envoy recommends setting its ring size limits explicitly.

• DeCandia et al. (2007): Dynamo, Amazon's Highly Available Key-value Store
• Envoy documentation: supported load balancers (ring hash, Maglev)

Measure key movement with a runnable script

The script hashes 10,000 keys with the first eight bytes of MD5, which is fine for placement and not meant for security. It uses hashlib rather than Python's built-in hash(), because str hashes are salted with a random value per process and would change between runs. It compares mod-N placement with rings of 1 and 100 virtual nodes per server, before and after adding E, and prints moved keys and per-server loads.

Python 3.12 printed: mod-N 4->5: 8035 moved, load: [1928, 2007, 2011, 2011, 2043]; ring vnodes=1: 1695 moved, to E: 1695, load: [124, 309, 1695, 3795, 4077]; ring vnodes=100: 1889 moved, to E: 1889, load: [1814, 1889, 1969, 2089, 2239]. Mod-N balances well but moves four keys in five. On both rings the moved count equals E's count, so no key shuffled between old servers. With 100 virtual nodes, 1,889 keys moved, close to the ideal one fifth.

import hashlib
from bisect import bisect
from collections import Counter


def h(s):
    return int.from_bytes(hashlib.md5(s.encode()).digest()[:8], "big")


def build_ring(nodes, vnodes):
    points = sorted((h(f"{node}#{i}"), node) for node in nodes for i in range(vnodes))
    return [p for p, _ in points], [node for _, node in points]


def lookup(ring, key):
    hashes, owners = ring
    return owners[bisect(hashes, h(key)) % len(hashes)]


keys = [f"user:{i}" for i in range(10_000)]
old, new = ["A", "B", "C", "D"], ["A", "B", "C", "D", "E"]
moved = sum(h(k) % 4 != h(k) % 5 for k in keys)
load = Counter(h(k) % 5 for k in keys)
print(f"mod-N 4->5: {moved} moved, load: {sorted(load.values())}")
for v in (1, 100):
    r4, r5 = build_ring(old, v), build_ring(new, v)
    moved = sum(lookup(r4, k) != lookup(r5, k) for k in keys)
    load = Counter(lookup(r5, k) for k in keys)
    print(f"ring vnodes={v}: {moved} moved, to E: {load['E']}, load: {sorted(load.values())}")

• Python language reference: object.__hash__ and hash salting

Replicate along the ring

Dynamo stores each key on its coordinator, the first node clockwise, and replicates it to the next N − 1 nodes clockwise, so each node holds the arcs of its N predecessors. The list of nodes responsible for a key is its preference list. With virtual nodes, the next N positions can belong to fewer than N physical machines, so Dynamo skips positions until the list contains distinct physical nodes. The same skipping rule is a natural place to require distinct racks or zones.

Placement only works if every router agrees on the ring. If two clients hold different membership views, they send the same key to different servers: a cache sees an extra miss, while a database may see a lost or duplicated write. Dynamo propagates membership changes with a gossip protocol and accepts an eventually consistent view. Alternatively, a central configuration service can publish one authoritative ring version. In an interview, say which you would choose and how a node learns about a change.

• DeCandia et al. (2007): Dynamo, Amazon's Highly Available Key-value Store

Know the alternatives: rendezvous, jump hash, Maglev

Rendezvous hashing, also called highest random weight, has no ring: for each key, compute a score from the key and each server, and pick the highest. A new server takes only the keys where it now wins, so movement stays minimal, but each lookup scores every server, which suits small clusters. Jump consistent hash from Lamping and Veach (2014) fits in about five lines, needs no stored state, and spreads keys evenly, but buckets must be numbered sequentially, so it suits numbered storage shards more than caches whose servers leave in any order.

Envoy also offers Maglev, which builds a fixed-size lookup table, 65,537 entries by default. Its documentation says table builds and host selection are substantially faster than ring hash, but remapping is less stable: simulations show roughly double the keys move when hosts are removed, and a larger table reduces that disruption. The interview move is to state the requirement first, whether minimal movement, balance, arbitrary removal, or lookup speed. Then pick the scheme that matches it and name what you give up.

• Lamping and Veach (2014): A Fast, Minimal Memory, Consistent Hash Algorithm
• Envoy documentation: supported load balancers (ring hash, Maglev)

Explain it in an interview, and avoid the usual mistakes

A one-minute answer: mod-N moves most keys when N changes; a ring maps servers and keys into one space; lookup walks clockwise; a membership change moves one arc; virtual nodes balance load and allow weighting; replicas live on the next distinct nodes; and every router must agree on membership. Draw the ring, add a node, and point to the arc that changes hands. Then quote one measured number, such as 8,035 versus 1,889 moved keys.

Three mistakes come up often. Claiming the ring balances load by itself: without virtual nodes, the measured spread was 124 to 4,077. Forgetting hot keys: consistent hashing spreads keys, not requests, so one viral key still lands on one server and needs replication or a cache in front of it. Using a per-process salted hash such as Python's hash() for placement. The articles below show where key movement turns into cache stampedes.

• Redis cache-aside and cache stampede
• NoSQL and Redis interview questions and answers
• 52 system design interview questions and answers
• Practice the backend interview track

Quick answers

Frequently asked questions