Consistent hashing

Consistent hashing assigns keys to servers so that when a server joins or leaves, only the keys on one slice of the hash space change owner, about 1/N of them, instead of nearly all of them. You hash servers and keys onto the same ring, give each key to the first server clockwise, and give each server many positions (virtual nodes) so the slices come out even.

Picture it first: depots on a ring road

A courier company in a city with a ring road runs four depots, and every parcel goes to exactly one of them.

Rule one: pincode mod 4. Send each parcel to depot number (pincode mod 4). When a fifth depot opens for the festive rush, the rule becomes pincode mod 5, and four parcels in every five change depot, even those nowhere near the new one.

Rule two: drive clockwise. Mark each address as a point on the ring road and drive clockwise to the first depot. A new depot takes only the parcels on the stretch just before it; a closed depot’s stretch passes to the next one. Everyone else’s route stays the same.

The catch: if the depots sit bunched on one side of the city, one gets the long empty stretch and most of the parcels. So give each depot several small counters around the ring, and the short stretches add up to a fair share.

Map it back: the depots are servers (cache nodes, database shards, backends), the parcels are keys, the ring road is the hash space, opening a depot is scaling out, a depot shutting is a failure, and the small counters are virtual nodes.

The problem with hash mod N

The obvious way to spread keys is to send a key with hash h to server h mod N. Each server gets about 1/N of the keys, a lookup is one division, and there is no state to share. For a fixed N, it is perfect.

The trouble starts when N changes. A key keeps its server only if h mod N equals h mod (N + 1). In any block of N(N + 1) consecutive hash values (0 to 19 for N = 4), the two remainders agree only for the first N values and then drift apart until the block repeats. So 1/(N + 1) of keys stay put, and the rest move:

fraction moved = 1 − 1/(N + 1) = N/(N + 1)

Hashing a million keys with MD5 agrees: 79.95% moved going from 4 to 5 servers, 90.91% from 10 to 11.

The right-hand column is the point. Filling a new server needs only 1/(N + 1) of the keys, all moving to it. Modulo hashing moves N times that, mostly between old servers that didn’t need to change. What that costs depends on what the servers hold:

• Caches. A moved key is a miss. Grow a four-node cache to five on the morning of a Big Billion Days–style sale and about 80% of cached keys are looked up on the wrong node, so most reads fall through to the database at the worst moment. Last.fm wrote ketama, a memcached client library, because hash(key) % serverlist.length “effectively wiped the entire cache” whenever they added or removed a server.
• Databases. A moved key is data copied over the network. Moving 80% of a 10 TB cluster to add one node is a migration project, not a scaling step (see database sharding).

The ring: servers and keys in one hash space

Consistent hashing, introduced by Karger and colleagues at MIT in 1997 for distributed web caches, treats the hash output as a position in a large space, say 0 to 2⁶⁴ − 1, bent into a circle so the largest value wraps to 0.

1. Place the servers. Hash each server’s name or ID, for example hash("cache-7").
2. Place the keys. Hash each key with the same function.
3. Walk clockwise. A key belongs to the first server at or after its position, wrapping past the top.

So each server owns the arc from the previous server (exclusive) to itself (inclusive), exactly as the Dynamo paper describes its partitioning.

No coordination is needed at lookup time, which is why memcached clients adopted consistent hashing without touching the servers; Karger’s paper even aimed for clients with slightly different server lists to mostly agree. Its construction picks the closest bucket point; Dynamo, Cassandra and ketama use the clockwise successor, which makes ownership a simple arc.

Adding or removing a node moves one slice

Add server E between A and B. The keys in (A, E] used to walk past that spot to B; now they stop at E. No key moves between A, B, C and D, and every moved key moves to the new server. Remove a server and its arc is absorbed by its clockwise successor; nobody else is touched. Karger called this monotonicity; the Dynamo paper calls it the principal advantage of consistent hashing, since a node’s arrival or departure “only affects its immediate neighbors”. On average a new node takes about 1/(N + 1) of the keys, the minimum from the table above.

Two things in the figure should worry you:

• Luck sets the size of the slice. In a 10-server simulation with one position each (set-up below), adding an 11th server took 11.2% of the keys against an ideal 9.1%. Removing a server with a tiny arc moved 1.4%; removing the busiest would have dumped 27.8% of all keys on one neighbour.
• One neighbour does all the work. A joining node streams everything from one donor, and a failed node’s whole load lands on one successor. If that successor was near capacity, it falls over too and passes a doubled range to its successor: a cascade.

Both problems have the same fix.

Virtual nodes: many small slices instead of one big one

With one random position per server, arc lengths vary wildly. For N random points on a circle, the expected largest gap is H(N)/N of the circle, where H(N) = 1 + 1/2 + … + 1/N. For 10 servers H(10) ≈ 2.93, so the unluckiest server should expect about 2.9× its fair share.

The fix, which Dynamo calls virtual nodes and Cassandra calls tokens or vnodes, is to give each server V positions: hash node-3#0, node-3#1, … node-3#255. Each share becomes the sum of V small arcs, and its standard deviation shrinks roughly like 1/√V of the mean: at V = 256, 1/√256 = 6.25%.

A simulation you can reproduce

The set-up: Python, with MD5 truncated to 64 bits as the hash. Ten servers, node-0 to node-9; token i of server n sits at hash(node-n#i). One million keys, key-0 to key-999999, each assigned to the next token clockwise by binary search. Each row is 50 runs with a different salt prefixed to the token names; loads are divided by the fair share of 100,000 keys.

The one-token median of 2.88× matches the H(10) ≈ 2.93 prediction, and the last column tracks 1/√V. Lamping and Veach measured the same curve for Karger’s scheme: standard errors of 0.32, 0.10 and 0.032 at 10, 100 and 1,000 points per bucket.

Bigger clusters need more tokens for the same evenness, because more servers means more chances that one is unlucky. With 100 servers (measuring exact arc lengths), the busiest sits at 1.73× the mean with 16 random tokens each and 1.16× with 256.

Virtual nodes buy three more things, all listed in the Dynamo paper:

• Failures spread out. With 256 tokens, removing one of the 10 servers sent its keys to all 9 survivors, each taking 8–13% of them, instead of to one neighbour.
• Joins pull from everyone. A new server takes a small slice from every existing server, so no single donor is swamped.
• Capacity weights. Give a server tokens in proportion to its capacity. Ketama uses about 160 points per server, scaled by its share of total memory, so a 64 GB node gets twice the points of a 32 GB one.

What virtual nodes cost

Tokens are not free. The ring holds N × V entries that every router needs. Cassandra’s documentation notes that each token adds up to 2 × (RF − 1) ring neighbours, where RF is the replication factor, so more combinations of node failures take some range offline. And repair and streaming work, done per range, multiplies with the token count.

That is why Cassandra changed course. In 2.x, tokens were random, so the default had to be 256 per node to stay balanced. From 3.x, a deterministic token allocator places them deliberately, and the current default is 16; the production guide says 8 gives roughly 10% variance. Random tokens need hundreds per node; planned tokens need far fewer.

Replication on the ring

The ring also tells you where the copies go. In Dynamo, a key’s first node clockwise is its coordinator, which also stores the key on the next N − 1 nodes clockwise. That ordered list is the key’s preference list. Two details matter:

• Distinct physical nodes. With virtual nodes, the next few tokens may belong to the same machine, so Dynamo and Cassandra skip any token whose server is already on the list.
• More than N candidates. If a replica is down, Dynamo sends reads and writes to the first N healthy nodes on a longer list; a stand-in keeps the write with a hint and hands it back when the owner recovers (sloppy quorums and hinted handoff, covered in quorums and leaderless replication).

So each node stores N arcs’ worth of keys: in the Dynamo paper’s example with N = 3, node D holds (A, B], (B, C] and (C, D].

Cassandra generalises the walk. SimpleStrategy walks tokens until it has RF distinct nodes; NetworkTopologyStrategy, which its documentation recommends for all production clusters, takes a replication factor per data centre and also tries to put each replica in a different rack.

The ring only decides which nodes hold a key. How the copies stay in sync is covered in data replication, and the consistency trade-offs in CAP and PACELC.

Lookups in code

The standard implementation is a sorted array of token positions plus each token’s owner. A lookup hashes the key and binary-searches for the first token greater than it, wrapping to index 0 at the end.

With 100 servers × 256 tokens, the array has 25,600 entries: log₂ 25,600 ≈ 15 comparisons per lookup, and at 8 bytes per position plus a 4-byte server index, 25,600 × 12 B ≈ 300 KB of ring.

import bisect
import hashlib


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


class HashRing:
    def __init__(self, tokens_per_unit: int = 128):
        self.tokens_per_unit = tokens_per_unit
        self.points: list[int] = []      # sorted token positions
        self.owner: dict[int, str] = {}  # token position -> node

    def add(self, node: str, weight: int = 1) -> None:
        for i in range(self.tokens_per_unit * weight):
            p = h(f"{node}#{i}")
            self.owner[p] = node
            bisect.insort(self.points, p)

    def remove(self, node: str) -> None:
        self.points = [p for p in self.points if self.owner[p] != node]
        self.owner = {p: n for p, n in self.owner.items() if n != node}

    def lookup(self, key: str, replicas: int = 1) -> list[str]:
        """The first `replicas` distinct nodes clockwise from the key."""
        found: list[str] = []
        start = bisect.bisect_right(self.points, h(key))
        for step in range(len(self.points)):
            node = self.owner[self.points[(start + step) % len(self.points)]]
            if node not in found:
                found.append(node)
                if len(found) == replicas:
                    break
        return found


ring = HashRing()
for name in ["cache-a", "cache-b", "cache-c"]:
    ring.add(name)
ring.add("cache-d", weight=2)                # twice the memory, twice the tokens
print(ring.lookup("user:42", replicas=3))    # three distinct nodes, in ring order

With 200,000 keys, cache-d gets about 42% of them (40% expected); remove cache-b and about 18% of keys move, all former cache-b keys. In production, build a new immutable array on each membership change and swap it in atomically, because lookups vastly outnumber changes.

Lookup speed matters in practice. Discord maps each guild (a “server” in the app) to a node with a consistent hash ring. When a session node restarts, each of its up to 500,000 sessions looks up the node for its guilds, about 5 each: 2.5 million lookups. Asking the one process that owned the ring cost about 12 µs a call, 30 s in total; copying the ring out of an in-memory table cost 7 µs, 17.5 s; a read-only shared copy cost 0.3 µs, 0.75 s, at the price of up to a second to rebuild it on the rare ring change.

The ring can live in the client (ketama-style memcached clients, Cassandra’s token-aware drivers: fastest, but every client needs the same server list), in a proxy (simpler clients, one more hop; see distributed caching), or in every node (Dynamo nodes gossip token sets and forward requests to the right coordinator).

Beyond the ring: other schemes

Rendezvous hashing (highest random weight)

Rendezvous hashing, from Thaler and Ravishankar in the 1990s, has no ring. Score every server with hash(key, server) and pick the highest. When a server leaves, each of its keys moves to whichever server scored second, which is random, so the load spreads evenly over all survivors. For replicas, take the top k scores.

You gain balance without tokens: in the same 10-server simulation the busiest server held 1.004× its fair share, and adding an 11th moved 9.08% of keys, all to the newcomer. You pay with an O(N) lookup, one hash per server: nothing for 20 cache servers, a lot for thousands of shards on a hot path.

Jump consistent hash

Lamping and Veach at Google published a function of about five lines that maps a 64-bit key and a bucket count n to a bucket in [0, n). It needs no memory, averages fewer than ln(n) + 1 loop iterations, and splits keys almost perfectly: a measured standard error of 0.000000008, against 0.03 for a ring with 1,000 points per bucket. Growing to n + 1 buckets moves exactly 1/(n + 1) of the keys, an equal slice from every bucket.

The catch: only the last bucket can be added or removed. You cannot take out bucket 7 because its server died. That fits replicated storage shards whose count only grows, the paper’s own framing, but not a cache pool where any server can vanish.

Maglev hashing

Google’s Maglev software load balancer picks a backend for every packet, and its NSDI 2016 paper ranks even load above minimal disruption. Each backend gets its own permutation of a prime-sized lookup table (65,537 entries by default), and backends take turns claiming their most-preferred empty slot until the table is full. A lookup is one array read, and backends’ entry counts differ by at most one; choosing a table above 100 × N entries keeps the difference under 1%.

You pay with a little extra churn: in a simulation with 10 backends, adding an 11th changed 9.3% of the entries where 9.1% is the minimum, which connection tracking absorbs. In the paper’s test with 1,000 backends, same-sized ring and rendezvous tables needed 29.7% and 49.5% overprovisioning to absorb their imbalance. See also L4 vs L7 load balancing.

Consistent hashing with bounded loads

Mirrokni, Thorup and Zadimoghaddam (2016) gave each server a capacity of (1 + ε) times the average load. A key walks clockwise as usual but skips full servers, so no server ever exceeds that cap, and each insertion or removal moves O(1/ε²) other keys, a bound that doesn’t grow with the cluster. Smaller ε means tighter balance but more movement. Google used it in Cloud Pub/Sub, and Vimeo’s HAProxy implementation cut its cache bandwidth by a factor of almost 8.

Fixed hash slots: the Redis Cluster contrast

Redis Cluster has no ring. Every key maps to one of 16,384 slots with HASH_SLOT = CRC16(key) mod 16384, and a table says which master owns each slot. That is modulo hashing, but the modulus never changes; scaling moves whole slots between nodes, so the “consistent” part comes from the indirection table.

You gain explicit control. An operator decides exactly which slots move, and keys sharing a hash tag such as {user1000} land in one slot, so multi-key commands work. During a move the source marks the slot MIGRATING and the target IMPORTING; requests for keys already moved get an ASK redirect, and after the switch a MOVED redirect updates the client’s slot table, so the slot stays available. You pay with a ceiling of 16,384 masters (about 1,000 suggested) and moves someone must orchestrate. The map is cheap to gossip: a heartbeat’s slot bitmap is 16,384 bits = 2 KB.

Dynamo converged on the same idea. With random tokens, a joining node “stole” ranges by having other nodes scan their stores, and in the busy shopping season bootstrapping took almost a day. Amazon moved to Q fixed, equal-sized partitions, Q/S per node for S nodes: partitions moved as whole files and membership metadata shrank a thousandfold, at the cost of coordinating membership changes.

Choosing a scheme

Bounded loads is not a row because it is a modifier: add it to a ring when request rates, not key counts, overload servers. For how these choices play out in full designs, see design a key-value store and design a distributed cache.

Going deeper: what consistent hashing doesn’t fix

Hot keys

Consistent hashing balances keys, not traffic. If one key takes 10% of all requests (the live score in an IPL final, the one phone everyone wants in a flash sale), it lives on one node and its replicas however many tokens you use. Dynamo’s authors saw this: over a day, up to 20% of nodes were more than 15% off the average request load at quiet times and about 10% at peak, when many popular keys spread the work. Even the 1997 paper split the job: consistent hashing chose which caches held a page, and a separate tree of caches per page absorbed floods of requests for it.

Clients that disagree about membership

If two app servers have different server lists, they send the same key to different places: duplicate cache entries, or a write on one node and a read from another. Publish membership from one source (a config service, versioned gossip, or the cluster itself, as with Redis’s MOVED replies). Caches have a sneakier variant: a node drops out briefly, its keys are updated on the successor, and when it returns, readers go back to its stale copies. Flush a returning cache node or keep TTLs short.

Moving data still costs

The ring decides which keys move, not how fast; Dynamo’s early bootstraps took almost a day. To rebalance without downtime:

1. Add one node at a time and stream its ranges from the donors in the background, throttled.
2. Keep the old owners serving until the copy completes, forwarding or double-writing keys that change meanwhile (Redis’s ASK redirects do this per key).
3. Switch ownership with one versioned update to the ring or slot table, and let donors delete only after the new owner confirms.

A cache has nothing to copy, but each new node costs a burst of misses on about 1/(N + 1) of the keys: add capacity before an IRCTC-style 10 am rush, not during it.

Hashing destroys order

A range query such as “orders between 10:00 and 10:05” touches every node, because adjacent keys hash to random positions. For range scans, partition by range, or hash only a prefix of the key and keep order within it; database sharding covers both.

Cheat sheet

How to say it in the interview

“If I shard with hash of key mod N, adding a fifth server to four moves 80% of the keys: a miss storm for a cache, a full reshuffle for a database. So I’d hash nodes and keys onto a 64-bit ring and give each key to the first node clockwise. A new node takes only the keys on its arc, about 1/N of them. Each node gets a couple of hundred virtual nodes, weighted by capacity, so it lands within about 10 to 15% of its fair share and a failure spreads across the cluster. Replicas go on the next three distinct physical nodes, and lookups are a binary search over a token array that clients cache. Hot keys still need a local cache or key splitting.”

How many virtual nodes? Enough that the busiest node fits your headroom. With random placement the spread falls like 1/√V: 256 tokens put the busiest of 10 servers at about 1.09× the mean, and of 100 servers at 1.16×. More tokens cost memory, repair work and availability, since each adds neighbours. With deliberate placement, as in Cassandra’s allocator, 8 to 16 per node is enough.

What happens when a node dies? Who serves its keys? In a replicated store, the other replicas on the preference list already have the data; Dynamo also writes to the next node in line with a hint and hands it back on recovery. The ring changes only when the node is declared gone for good, and virtual nodes spread its re-replication across many nodes. In an unreplicated cache, its keys map to the successors and start as misses.

Does consistent hashing solve hot keys? No. It evens out how many keys each node owns, not how many requests one key gets. Use a local cache, replicate or split the key, or coalesce requests.

Why does Redis Cluster use hash slots instead? Fixed slots make movement explicit: CRC16(key) mod 16384 picks a slot, a table maps slots to masters, and resharding moves whole slots with ASK and MOVED redirects while they stay available. Hash tags keep related keys together for multi-key commands. The modulus never changes, so the mod N problem never arises; the price is a size ceiling and orchestrated moves.

How do you rebalance without downtime? Add one node at a time, stream its ranges in the background with a throttle while the old owners keep serving, flip ownership with one versioned update, and delete from the donors only after the new owner confirms. For a cache, add capacity ahead of the peak.

Where to go next

• Database sharding: shard keys, range versus hash partitioning, resharding.
• Distributed caching: client-side hashing, proxies and Redis Cluster.
• Quorums and leaderless replication: what happens on the preference list.
• Data replication: keeping replicas in sync.
• Cassandra and DynamoDB: token rings in production.
• Redis: hash slots and resharding in practice.
• Load balancing: L4 vs L7: where Maglev-style hashing sits.
• Hot keys, cache stampede and invalidation: what consistent hashing leaves for you.
• Design a key-value store and design a distributed cache: the ring inside a full design.

References and further reading

1. Consistent Hashing and Random Trees (Karger et al., STOC 1997)cs.princeton.eduThe original idea: buckets and items hashed onto the unit interval, several points per bucket, monotonicity, and clients with different views of the cache set.
2. Dynamo: Amazon’s Highly Available Key-value Store (DeCandia et al., SOSP 2007)allthingsdistributed.comClockwise ring ownership, virtual nodes, preference lists of distinct nodes, hinted handoff, measured imbalance, and the move from random tokens to fixed equal partitions.
3. A Fast, Minimal Memory, Consistent Hash Algorithm (Lamping and Veach, 2014)arxiv.orgJump consistent hash and its sequential-bucket limit, the measured balance of ring implementations, and a description of rendezvous hashing.
4. Maglev: A Fast and Reliable Software Network Load Balancer (Eisenbud et al., NSDI 2016)usenix.orgMaglev hashing’s permutation-filled lookup table, its 65,537-entry default, and its balance compared with ring and rendezvous tables.
5. Consistent Hashing with Bounded Loads (Google Research blog, 2017)research.googleThe (1 + ε) capacity cap, the O(1/ε²) movement bound, and its use in Cloud Pub/Sub and in HAProxy at Vimeo.
6. Redis Cluster specificationredis.io16,384 hash slots via CRC16, hash tags, live slot migration with MIGRATING/IMPORTING and ASK/MOVED redirects, slot bitmaps in heartbeats.
7. Apache Cassandra documentation: Dynamo architecturecassandra.apache.orgThe token ring walk, vnodes and their availability cost, the old 256-token default, the newer token allocator, and replica placement strategies.
8. Apache Cassandra documentation: Production recommendations (tokens)cassandra.apache.orgThe current 16-token default and when 1, 4, 8 or 16 tokens per node make sense.
9. How Discord Scaled Elixir to 5,000,000 Concurrent Users (Discord engineering)discord.comA consistent hash ring lookup turning into a hot path, with measured per-lookup costs before and after.
10. ketama: consistent hashing for memcached clients (Last.fm)github.comWhy memcached clients moved off hash mod N, the continuum, about 160 points per server, and weights by memory.