Consistent hashing

The problem it solves

A cache tier has 10 servers holding 50 million keys, with a 95% hit ratio. Every client picks a server with hash(key) mod 10. It is simple, fast and perfectly even. Then traffic grows and you add an 11th server.

A key stays where it was only if h mod 10 equals h mod 11. For a uniform hash, that happens for 1 key in 11. The other 91% of keys now point at a server that does not have them. The hit ratio falls from 95% to about 9% in one deploy. The database was sized for 5% of reads, and now it gets 91% of them. That’s 18 times its usual load. Losing one server does the same thing in reverse.

The general result: going from N to N + 1 servers, a key stays put only when h mod N(N+1) is below N. So a fraction 1/(N+1) stays, and N/(N+1) moves.

Change	Keys moved by mod N	Fewest that must move
4 → 5	80%	20%
10 → 11	91%	9%
64 → 65	98.5%	1.5%
100 → 101	99%	1%

The right column is the floor. The new server must take its fair share, 1/(N+1), and nothing else needs to move. Karger and others introduced consistent hashing in 1997, for web caches. (That work became Akamai.) It’s any scheme that gets close to that floor, while keeping three properties:

• Balance. Each server owns about 1/N of the keys.
• Minimal disruption. Adding or removing one server moves about 1/N of the keys, and only to or from that server.
• No lookup table on the request path. Any client that knows the member list computes a key’s owner locally, and all clients agree.

The last point is what separates it from a directory. A directory (a map from key or range to server) also gives balance and minimal movement, but every client must fetch and track the map.

How it works

Step 1: Put servers and keys on a ring

Treat the output of a 64 bit hash as a circle: 0 to 2⁶⁴ − 1, and past the top it wraps to 0. Hash each server’s name to a position on the circle. Hash each key the same way. A key belongs to the first server clockwise from it.

Now add a server. It lands at one position and takes over the arc between its counterclockwise neighbor and itself. Those keys were owned by its clockwise neighbor. Every other key keeps its owner, because nothing about their arcs changed. Removing a server is the same in reverse: its arc joins its clockwise neighbor’s. On average one change moves 1/N of the keys, which is the floor.

Server D lands between A and B: one arc changes owner

Scroll or pinch to zoom, drag to pan

• Color key
• Service

A lookup is a binary search. Keep the server positions in a sorted array. Find the first position at or after the key’s hash, and wrap to index 0 past the end. With 10,000 positions, that is about 14 comparisons, well under a microsecond. The distributed cache problem builds exactly this ring, with the code in five languages, in its stage 2.

Step 2: One point per server is lopsided

The ring above has a flaw. You can see it in the demo below, at one point per server: the arcs have random lengths. Put N random points on a circle, and the gaps between them are roughly exponentially distributed. So the standard deviation of a server’s share is about equal to its mean. The biggest gap is about ln N times the average.

Servers	Busiest server’s share, one point each	Smallest share
10	about 2.9× the average	often under 0.1×
100	about 5× the average	near zero for some

(Averages over 200 random rings.) Two problems follow. Capacity is wasted, because every server must be sized for the unluckiest arc. And failure concentrates: when a server dies, its whole arc goes to one neighbor, which suddenly carries two shares. If that neighbor tips over, its double share goes to the next one. That is a cascade, and it walks around the ring.

Step 3: Virtual nodes

Give each physical server many points instead of one: hash "s1-0", "s1-1", … "s1-159". These are virtual nodes (vnodes). Cassandra calls them tokens. A server’s share is now the sum of V small arcs, instead of one big one. And a sum of V independent gaps has a relative standard deviation of about 1/√V.

Points per server (V)	Spread of shares (std dev / mean)	Busiest of 100 servers
1	about 100%	5.0× the average
10	31%	1.96×
100	10%	1.27×
160	8%	1.21×
1,000	3%	1.08×

(Measured by simulation. The spread column matches 1/√V.) The busiest server matters more than the spread, because it sets the capacity you buy. With 100 servers at V = 160, plan for the hottest to carry about 1.2 times the mean.

Virtual nodes also fix failure concentration. A dead server’s 160 arcs each go to whatever point follows them, so its load spreads over nearly every other server. A new server takes a sliver from almost everyone instead of half of one neighbor’s load.

The costs are memory and, for databases, bookkeeping. 1,000 servers at 160 points is 160,000 entries of about 16 bytes. That’s 2.5 MB per client, and a lookup of about 17 comparisons. That is cheap. But in a storage system, each point is a range that must be streamed, repaired and tracked. That’s why Cassandra 4.0 cut its default from 256 random tokens to 16, placed by an allocation algorithm.

Try it. Start at one point per server, add a server and count the moved keys. Then switch to 64 points and watch the load bars even out. Then switch to hash mod N and add a server again.

Scheme

Hash ringhash mod N

Virtual nodes per server

141664

Add a serverReset

Make a change to see which keys move.

Keys per server. The dashed line is the average.

Biggest share of the ring vs fair share

1.00×

Spread of shares (std dev / mean)

0%

Four servers, one point each: the arcs are uneven. Add a server, then try 64 virtual nodes.

Step 4: Weights for unequal servers

Real fleets mix machine sizes. On a ring the fix is direct: give each server points in proportion to its capacity. A 96 GB cache node gets 320 points where a 48 GB node gets 160. Its share doubles and its relative spread shrinks by √2. Changing one server’s weight adds or removes only its own points, so only keys near those points move.

Ketama, the memcached client scheme from 2007, does exactly this. It gives 160 points to a server of average weight, scaled by its weight, taken 4 at a time from MD5 digests.

Step 5: Replicas by walking the ring

For replication factor 3, a key’s replicas are its preference list (Dynamo’s term). Start at the key’s position, and walk clockwise, collecting servers until you have 3. Two rules make the list useful:

• Skip points of servers already chosen. With vnodes, the next three points often include two from one machine. Two copies on one machine are one copy.
• Skip servers in a zone already chosen. A rack switch or an availability zone takes out every machine behind it. Cassandra’s NetworkTopologyStrategy walks the ring per datacenter and prefers distinct racks.

Building a preference list for one key, replication factor 3

Scroll or pinch to zoom, drag to pan

• Color key
• Service

When a server in the list is down, Dynamo-style stores keep walking. The next healthy server accepts the write, with a hint naming the real owner. It hands the write back when the owner returns. That is a sloppy quorum, covered in the key-value store problem. The ring makes it cheap, because “the next server” is already defined.

Step 6: Who holds the ring

The ring is only useful if every caller has the same one. There are three places to compute it.

Where routing runs	Extra hop	Wins when
Client library	0	You control every client and its language (ketama, Cassandra drivers)
Proxy tier (twemproxy, mcrouter, Envoy)	1, about 0.2 to 0.5 ms	Many languages or clients you cannot update
Any server forwards	1 on most requests	Clients are dumb, as with Cassandra’s coordinator fallback

The member list itself comes from a config store (etcd, ZooKeeper) or from gossip between servers. Either way, a change reaches clients at slightly different times, so for a few seconds two clients can route one key to different servers. Version the ring with an epoch and send it on every request. A server that just gave a range away refuses requests carrying an older epoch.

A client on an old ring is told to refresh

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database

TradeoffA ring with virtual nodes

We gain

Adding or removing a server moves about 1/N of keys, spread across many servers. Lookups are a local binary search, weights are just more points, and replicas fall out of a clockwise walk.

We give up

Balance is statistical, about 1/√V, so the busiest server still carries 10 to 30% more than average. Every client must hash identically and learn ring changes, and each vnode is a range a storage system must stream and repair.

Options and tradeoffs

The ring is one of five schemes

The ring is the scheme everyone draws, but it is not the only one, and it is not the best at everything. Each alternative below gives up something to win on lookup speed, memory or balance.

Rendezvous hashing (highest random weight, Thaler and Ravishankar, 1996). There is no ring. For each key, every server computes a score hash(server, key), and the highest score wins.

Remove a server, and only its keys move, because every other key’s winner is unchanged. Its keys go to their second-highest server. That’s a different server for each key, so the load spreads evenly. Sorting all scores gives a full preference order. So the top 3 are the replicas, with no skipping.

Weights use one formula, −w / ln(u), with u the score scaled to (0, 1). That makes a server win with probability w / Σw. The price is O(N) hashes per lookup.

JRendezvous.javaPyrendezvous.pyC#Rendezvous.csGorendezvous.goTSrendezvous.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;

// weight is capacity relative to the others: a node twice as big gets 2.
record Node(String name, double weight) {}

// Highest random weight hashing: every node scores the key, the highest score owns it.
// No ring and no points to store, so the only state is the node list itself.
class Rendezvous {
    private final List<Node> nodes;

    Rendezvous(List<Node> nodes) {
        this.nodes = List.copyOf(nodes);
    }

    // Sorting by score gives a full preference order. The top `count` are the replicas, and
    // they are distinct nodes by construction: no walking past duplicates as on a ring.
    List<Node> owners(String key, int count) {
        List<Node> ranked = new ArrayList<>(nodes);
        ranked.sort(Comparator.comparingDouble((Node n) -> score(n, key)).reversed());
        return ranked.subList(0, count);
    }

    // O(N) hashes per lookup. Fine for tens or hundreds of nodes, too slow per packet at
    // thousands; that is where a ring or a Maglev table wins.
    Node owner(String key) {
        Node best = null;
        double bestScore = Double.NEGATIVE_INFINITY;
        for (Node n : nodes) {
            double s = score(n, key);
            if (s > bestScore) {
                best = n;
                bestScore = s;
            }
        }
        return best;
    }

    // u is uniform in (0, 1) and fixed for this (node, key) pair. -w / ln(u) makes a node win
    // with probability w / sum(w): weights work without virtual nodes.
    static double score(Node node, String key) {
        double u = (hash64(node.name() + ":" + key) >>> 11) / Math.pow(2, 53); // top 53 bits fit a double exactly
        u += 0.5 / Math.pow(2, 53); // never 0 or 1, so ln(u) is finite and negative
        return -node.weight() / Math.log(u);
    }

    // MD5 because every client language must compute the same number for the same key.
    static long hash64(String s) {
        try {
            byte[] d = MessageDigest.getInstance("MD5").digest(s.getBytes(StandardCharsets.UTF_8));
            long h = 0;
            for (int i = 0; i < 8; i++) h = (h << 8) | (d[i] & 0xff);
            return h;
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException(e);
        }
    }
}

class Main {
    public static void main(String[] args) {
        List<Node> nodes = List.of(new Node("a", 1), new Node("b", 1), new Node("c", 1), new Node("d", 2));
        Rendezvous before = new Rendezvous(nodes);
        List<String> keys = new ArrayList<>();
        for (int i = 0; i < 100_000; i++) keys.add("user:" + i);
        Map<String, Integer> counts = new TreeMap<>();
        for (String k : keys) counts.merge(before.owner(k).name(), 1, Integer::sum);
        System.out.println(counts); // d, with weight 2, owns about 40%; the others about 20% each

        // Remove c. Only c's keys move, and they spread over a, b and d in proportion to weight.
        Rendezvous after = new Rendezvous(nodes.stream().filter(n -> !n.name().equals("c")).toList());
        long moved = keys.stream().filter(k -> !before.owner(k).equals(after.owner(k))).count();
        System.out.printf("moved %.1f%%%n", 100.0 * moved / keys.size()); // 20.0%: exactly c's keys, the minimum possible
        System.out.println(before.owners("user:42", 3).stream().map(Node::name).toList()); // [c, d, a]: three distinct replicas, in order
    }
}

Jump consistent hash (Lamping and Veach, Google, 2014). A five-line function maps a 64 bit key to a bucket in [0, n), with no memory at all. It simulates the key’s journey as buckets are added one at a time. It jumps straight to the last bucket count at which the key would have moved. The expected number of jumps is ln n, and balance is essentially perfect. Going from n to n + 1 buckets moves 1/(n+1) of keys in expectation. That’s the floor, and all of them go into the new bucket.

The catch: buckets are numbers, not names. You can grow or shrink only at the end. You can never remove bucket 3. It fits storage shards that are replica groups with stable numbers, where a failed machine is replaced inside its group.

JJump.javaPyexample.pyC#Jump.csGomain.goTSexample.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;

class Jump {
    // Jump consistent hash (Lamping and Veach, Google, 2014). Maps a 64 bit key to a bucket in
    // [0, buckets). No memory at all, near perfect balance, and growing from n to n + 1 buckets
    // moves exactly the keys that land in the new bucket, about 1/(n + 1) of them.
    static int jumpHash(long key, int buckets) {
        long b = -1, j = 0;
        while (j < buckets) {
            b = j;
            // A 64 bit linear congruential step: a cheap, deterministic stream of random numbers
            // seeded by the key, so every caller computes the same sequence. Java longs wrap.
            key = key * 2862933555777941757L + 1;
            // Jump straight to the next bucket count at which this key would move. Expected
            // number of jumps is ln(buckets), so 1,000 buckets take about 7 loop turns.
            j = (long) ((b + 1) * ((double) (1L << 31) / (double) ((key >>> 33) + 1)));
        }
        return (int) b;
    }

    // Jump hash needs a well mixed 64 bit integer, not a string. MD5's first 8 bytes,
    // the same in every client language.
    static long keyHash(String s) {
        try {
            byte[] d = MessageDigest.getInstance("MD5").digest(s.getBytes(StandardCharsets.UTF_8));
            long h = 0;
            for (int i = 0; i < 8; i++) h = (h << 8) | (d[i] & 0xff);
            return h;
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException(e);
        }
    }
}

class Main {
    public static void main(String[] args) {
        int n = 100_000, moved = 0;
        boolean allToNew = true;
        int[] counts = new int[10];
        for (int i = 0; i < n; i++) {
            long k = Jump.keyHash("user:" + i);
            int ten = Jump.jumpHash(k, 10), eleven = Jump.jumpHash(k, 11);
            counts[ten]++;
            if (ten != eleven) {
                moved++;
                allToNew &= eleven == 10;
            }
        }
        System.out.println(java.util.Arrays.toString(counts)); // about 10,000 each
        System.out.printf("moved %.1f%%%n", 100.0 * moved / n); // 9.3%, close to the ideal 1/11, all of it into bucket 10
        System.out.println(allToNew); // true
        // The catch: buckets are numbers, not names. Removing bucket 3 of 10 is not possible;
        // you can only shrink from the end. Map bucket numbers to replica groups instead.
    }
}

Maglev hashing (Google, NSDI 2016). It was built for software load balancers that must choose a backend for every packet, at line rate. The lookup table has a prime size M (65,537 by default). Each backend gets a permutation of its slots, derived from two hashes of its name: an offset and a skip. Backends take turns claiming their next preferred free slot, until the table is full.

A packet’s backend is then table[hash(5-tuple) mod M]: one array read. Every backend owns M/N slots, plus or minus one, so balance is near perfect. Disruption is close to the floor, but not at it, as the paper reports. In our simulation with 100 backends and M = 65,537, removing one changed about 1.5% of slots, instead of the minimum 1%. Connection tracking keeps existing flows on their backend. So that excess only matters for new flows.

Maglev: backends take turns filling a lookup table

Scroll or pinch to zoom, drag to pan

• Color key
• Service
• Database

Fixed slots and a map. Hash keys into a fixed number of slots, far more than servers. Keep an explicit map from slot to server. Redis Cluster uses 16,384 slots, and Couchbase 1,024 vBuckets. Riak uses a fixed ring of 64 partitions by default. Moves are whatever you choose, so a rebalance is planned work you can watch and throttle.

The price is the map. Every client or proxy must fetch it, and follow redirects when it changes. The Dynamo paper reports this beat random tokens, on balance and on bookkeeping. Its third and final strategy splits the ring into equal fixed partitions, and assigns those to nodes.

Scheme	Lookup	Memory per client	Balance	Moves on one change	Remove any server	Wins when
hash mod N	O(1)	None	Perfect	N/(N+1), almost all	Yes, at a cost	N never changes (a fixed set of partitions)
Ring with vnodes	O(log NV)	N·V points	±1/√V	About 1/N, from many	Yes	Caches and Dynamo-style stores with changing members
Rendezvous (HRW)	O(N)	The member list	Perfect in expectation	Exactly the minimum	Yes	Tens of servers, replicas as top-k, weights
Jump hash	O(ln N)	None	Near perfect	The minimum, on add	No, only the last	Numbered shards that are replica groups
Maglev	O(1), one read	Table of M entries	Within one slot	Slightly above 1/N	Yes	Per-packet load balancing
Fixed slots + map	O(1)	Slot map	As planned	As planned	Yes	Stores that migrate data and want controlled moves

TradeoffChoosing among them

We gain

Each alternative beats the ring at one thing. Rendezvous on simplicity and replica choice. Jump on memory and balance. Maglev on per-packet lookup speed. Slots on control.

We give up

Rendezvous pays O(N) per lookup. Jump cannot remove an arbitrary server. Maglev moves a little more than the minimum, and needs a table rebuild on every change. And slots need a map that every client must track.

How many virtual nodes

Points per server	Spread of shares	Cost	Used by
1	About 100%	None, but a 5× hot server and cascading failures	Nobody, deliberately
16, placed by an algorithm	A few percent	An allocator that picks tokens to fill the biggest gaps	Cassandra 4.0 and later
100 to 200, random	7 to 10%	Tiny for a cache client	Ketama (160), most cache clients
256, random	About 6%	Hundreds of ranges per node to stream and repair	Cassandra before 4.0

For a cache client, more points cost nothing that matters, so 100 to 200 is the norm. For a database, the count also sets availability. Take many random tokens and three replicas. Almost every pair of nodes shares some range. So losing any two nodes leaves some range with one copy, and quorum reads for those keys fail. With few tokens, most pairs of failures are harmless.

Tradeoff160 random points per server in a cache client

We gain

The busiest server sits about 20% above average with 100 servers, and a dead server’s load spreads over nearly all the others.

We give up

2.5 MB of ring per client at 1,000 servers and a little more CPU per lookup. In a store, the same count would mean 160 ranges per node to repair and would couple every node to every other.

Hot keys and bounded loads

Every scheme above balances keys. None balances traffic. If one video, one celebrity or one prefix gets 30% of requests, its owner gets 30% of requests, however the hash is chosen. The ring also does not react to load: a server running hot keeps all its keys.

Consistent hashing with bounded loads (Mirrokni, Thorup and Zadimoghaddam, 2016) adds a cap. Pick ε, say 0.25. No server may carry more than ⌈(1 + ε) × average⌉ of the current load (requests in flight, or connections). A request goes to its ring owner if that owner is under the cap, otherwise to the next server clockwise that is. The paper proves the expected number of reassignments per change is O(1/ε²), so a smaller ε buys tighter balance with more movement. Vimeo contributed it to HAProxy as the hash-balance-factor option to spread load across its video cache servers.

Routing one request with bounded loads

Scroll or pinch to zoom, drag to pan

• Color key
• Service

JBoundedRing.javaPybounded_ring.pyC#BoundedRing.csGobounded_ring.goTSbounded-ring.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

import java.nio.charset.StandardCharsets;
import java.security.MessageDigest;
import java.security.NoSuchAlgorithmException;
import java.util.*;

// Consistent hashing with bounded loads (Mirrokni, Thorup and Zadimoghaddam, 2016).
// A key goes to its usual ring owner unless that node already carries more than (1 + eps)
// times the average load; then it goes to the next node clockwise that has room.
class BoundedRing {
    private final double eps; // 0.25: no node carries more than 1.25 times the average
    final Map<String, Integer> load = new TreeMap<>(); // requests in flight, or keys held, per node
    private final long[] points;
    private final String[] owners;

    BoundedRing(List<String> nodes, int vnodes, double eps) {
        this.eps = eps;
        // Unsigned order, so the ring sorts the same way as in languages with unsigned 64 bit ints.
        TreeMap<Long, String> ring = new TreeMap<>(Long::compareUnsigned);
        for (String n : nodes) {
            load.put(n, 0);
            for (int i = 0; i < vnodes; i++) ring.put(hash64(n + "-" + i), n);
        }
        points = ring.keySet().stream().mapToLong(Long::longValue).toArray();
        owners = ring.values().toArray(new String[0]);
    }

    // The bound moves with the total: counting the request being placed keeps it above
    // zero when the system is empty, and the ceiling guarantees some node always has room.
    private int capacity() {
        int total = load.values().stream().mapToInt(Integer::intValue).sum() + 1;
        return (int) Math.ceil((1 + eps) * total / load.size());
    }

    String acquire(String key) {
        int cap = capacity();
        int i = firstAtOrAfter(hash64(key));
        // Walk clockwise from the key's place. Most keys stop at the first point; only keys
        // whose owner is full move on, and they move to the same next node every time, so a
        // hot key's overflow still lands on a predictable, cache-warm second choice.
        for (int step = 0; step < points.length; step++) {
            String node = owners[(i + step) % points.length];
            if (load.get(node) < cap) {
                load.merge(node, 1, Integer::sum);
                return node;
            }
        }
        throw new AssertionError("unreachable: total capacity always exceeds total load");
    }

    // When a request finishes, its slot frees up. Keys are not rebalanced back eagerly.
    void release(String node) {
        load.merge(node, -1, Integer::sum);
    }

    private int firstAtOrAfter(long h) {
        int lo = 0, hi = points.length;
        while (lo < hi) {
            int mid = (lo + hi) >>> 1;
            if (Long.compareUnsigned(points[mid], h) < 0) lo = mid + 1;
            else hi = mid;
        }
        return lo; // may be points.length: the walk's modulo wraps it to the first point
    }

    static long hash64(String s) {
        try {
            byte[] d = MessageDigest.getInstance("MD5").digest(s.getBytes(StandardCharsets.UTF_8));
            long h = 0;
            for (int i = 0; i < 8; i++) h = (h << 8) | (d[i] & 0xff);
            return h;
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException(e);
        }
    }
}

class Main {
    public static void main(String[] args) {
        BoundedRing ring = new BoundedRing(List.of("a", "b", "c", "d"), 100, 0.25);
        // 1,000 requests stay in flight, and half of them ask for one hot key.
        for (int i = 0; i < 1000; i++) ring.acquire(i % 2 == 0 ? "video:hot" : "video:" + i);
        System.out.println(ring.load); // {a=197, b=310, c=313, d=180}: none above
        // ceil(1.25 * 1000 / 4) = 313. A plain ring puts 621 on c, the hot key's owner.
    }
}

The overflow is predictable. Requests for a hot key spill to the same next server every time. So that server’s cache warms up for the hot key too. The key’s normal requests still go to its owner.

TradeoffBounded loads for a cache or request-routing tier

We gain

No server exceeds 1.25 times the average, even with one key taking half the traffic, and the spill goes to a stable second choice.

We give up

Placement now depends on current load, so the same key can land on different servers over time. That is fine for a cache, where a miss is a refill. It’s wrong for storage, where a key must be found where it was written. Every router also needs a view of every server’s load.

For storage, hot keys need different tools. Replicate the hot key to more servers, and read from any. Put a small in-process cache in front. Or split one logical key into several (key#1 to key#8), and merge on read. The distributed cache problem works through these.

Go deeperHash functions, and why the choice matters2 min

The ring is only as good as the hash. What it needs is good mixing and the same output in every language, not cryptographic strength.

Hash	Speed (64 bit output)	Notes
MD5	Slowest of these	Ketama’s choice in 2007, available everywhere, more than strong enough
MurmurHash3	Fast	Cassandra’s Murmur3Partitioner, the common modern default
xxHash64	Fastest	Several GB/s per core, good mixing
CRC16, CRC32	Fast	Fine for picking one of 16,384 slots (Redis Cluster uses CRC16), weakly mixed for ring positions

Two traps. Language built-in hashes, such as Python’s hash(), are randomized per process. So two clients disagree on every key. Java’s String.hashCode() is stable, but poorly mixed. Similar keys such as user:1 and user:2 land next to each other, and sequential keys cluster on one arc.

How it fails

Failure	What you see	Blast radius	Fix
Clients disagree on the ring	Hit ratio drops for some clients; stale values after a delete	Every key whose owner differs	One library and test vectors per language; a ring epoch on requests
One point per server, then a failure	The dead server’s neighbor doubles its load, then fails too	Walks around the ring	Virtual nodes, so a dead server’s load spreads
Membership flaps	Cold misses as keys move away, stale hits when they move back	1/N of keys per flap	Separate “down” from “removed”; flush a cache server that rejoins
One hot key	One server at 100% CPU while the rest idle	Everything else on that server	Replicate or split the key, local cache, bounded loads for caches
Replicas on one machine or zone	Data loss or unavailability when one host or rack fails	Keys whose walk hit duplicates	Skip already chosen servers and zones in the walk
A new node in a storage ring	Streaming saturates disks and network on many peers	Latency on every node it pulls from	Add one node at a time, throttle streaming
Adding a cache server without warm-up	1/N of reads miss at once	The database	Add servers one at a time, at low traffic, or warm from the old owner

Clients that disagree are the dangerous one. Two clients with different rings do not fail loudly. Client X writes user:42 to server B. Client Y reads it from server D, misses, and fills D from the database. Worse, X deletes user:42 after an update. But Y keeps reading the old copy on D, until its TTL runs out.

The causes are ordinary. A different hash in one language’s library. Servers listed by IP in one config, and by hostname in another. Or a config push that reached half the fleet. Detect it by exporting a ring checksum and epoch from every client. Alert when more than one is live for longer than a push takes.

Flapping is the subtle one. Say a missed heartbeat removes a server from the ring, and the next heartbeat adds it back. Every flap moves 1/N of keys twice. Each move is a cold miss, or a range to stream. The move back is worse in a cache. The returning server still holds its old copies. Any key written or deleted elsewhere while it was gone now serves a stale value, until its TTL expires.

Production systems keep two ideas apart. A server that is down gets its requests routed to the next replica, or answered as misses. Its ownership changes only when an operator removes it, or after a long timeout, often minutes.

Common mistake

"When a server dies, its keys move to the next server"

That is true of a ring with one point per server, and that is exactly why nobody runs one. With 160 virtual nodes, the dead server’s 160 arcs each pass to whatever point follows them. So its keys spread over nearly every other server, and each one takes about 1/N more load. The “next server” picture is what causes cascading failures, not what prevents them.

At scale

Scheme	Lookup cost, roughly	State
Ring, 160 × 1,000	17 comparisons, 100 to 200 ns	160,000 points, about 2.5 MB
Rendezvous, 100	100 hashes, 1 to 5 µs with a fast hash	The member list
Jump, 1,000	About 7 loop turns, tens of ns	None
Maglev	One array read, a few ns	65,537 entries, rebuilt in milliseconds

At 10 times the servers, say 100 to 1,000, membership changes stop being events. At 1,000 servers, some machine fails or gets replaced most days. Each change moves only 0.1% of keys, which is the point. But the change must reach every client quickly and in order. So the epoch and the config push become the critical path. Rendezvous at O(N) starts to cost real CPU per request. Split it into two levels (rendezvous over 30 groups, then over the 30 servers in a group), or move to a ring.

At 100 times, the ring itself stops being one thing. Large deployments split into cells of a few hundred servers, each with its own ring, and route to a cell first. Gossip, repair and ring changes all slow down with size, and a cell bounds the damage of a bad change. Maglev tables must stay much larger than the backend count, roughly M ≥ 100 × N, so the per-backend imbalance stays under 1%.

What to monitor:

• Keys and bytes per server, and requests per second per server, as max divided by mean. Keys measure the hash, requests measure the traffic, and the gap between them is your hot keys.
• Hit ratio during and after every membership change, and the database’s read rate beside it.
• The number of distinct ring epochs live across clients, and how long two coexist.
• Streaming throughput and duration when a storage node joins or leaves.
• The top keys by request rate, so a hot key is visible before it saturates its server.

In the interview

Interviewer asksWhy not just use hash(key) mod N?

Because changing N moves almost every key. Going from N to N + 1 servers, a key stays only when its hash gives the same remainder for both. That’s a 1 in N + 1 chance. Going from 10 to 11 servers moves 91% of keys. For a cache, that is a near-total cold start. A 95% hit ratio becomes about 9%, and the database sees 18 times its usual reads. The floor is 1/(N+1), the new server’s fair share. A hash ring with virtual nodes gets close to that floor, and so do rendezvous and jump hashing. If N truly never changes, for example a fixed set of 1,024 partitions, then mod N is fine and simpler.

Interviewer asksHow many virtual nodes would you use, and what do they cost?

A server’s share varies by about 1/√V. So 100 points gives about 10%, and 160 gives 8%. With 100 servers at 160 points, the busiest carries about 1.2 times the average. That number sets how much capacity I buy. For a cache client, 100 to 200 points cost a couple of megabytes and a binary search, so I’d use 160, like ketama. For a database, each point is a range to stream and repair. And many random tokens mean almost any two failures share a range, which hurts quorum availability. There I’d use fewer, around 16, placed by an allocation algorithm as Cassandra 4 does. Or fixed partitions, assigned by a map.

Interviewer asksA cache server dies. What happens to its keys and its traffic?

With virtual nodes, each of its arcs passes to the server holding the next point. So its keys spread over almost all the others, and each takes about 1/N extra load. All of those keys miss once and refill from the database. So the database sees a burst of 1/N of the read traffic. I would not remove the server from the ring on the first missed heartbeat. Route around it while it is down, and change ownership only after a timeout, or by an operator. Then a flap does not move keys twice. If the cache has replicas, reads go to the replica instead, and the database never sees the burst.

Interviewer asksOne key gets 30% of all requests. Does consistent hashing help?

No. It balances keys, and that key hashes to one place on any scheme. For a cache tier, I could use bounded loads. Cap each server at 1.25 times the average in-flight load, and spill the excess to the next server clockwise. That server then also caches the hot key. Storage is different, because a key must be found where it was written. There I’d replicate the hot key to more servers and read from any, add a small local cache in front, or split it into sub-keys and merge on read. The first step is finding it: a top-k of keys by request rate on each server.

Common mistake

"Consistent hashing gives an even load"

It gives an even share of the keyspace, statistically, and only with enough virtual nodes. Load is requests, not keys: a server holding 1% of keys can serve 30% of traffic if one of them is hot. It also does nothing about unequal machines unless you weight them. State which kind of balance you mean, and say what handles the other kind.

Mid-level covers

Explains why mod N moves almost every key, draws the ring, adds virtual nodes to even out load, and walks the ring clockwise for replicas.

Senior adds

Also gives the numbers: N/(N+1) moved, and a spread of 1/√V. Skips duplicate servers and zones in the replica walk. Versions the ring, so clients that disagree are caught. Keeps “down” separate from “removed”. Separates key balance from traffic balance (bounded loads, hot key replication). Knows when rendezvous, jump, Maglev or a slot map beats a ring.

Seen in

• Design a distributed cache: 64 shards on a ring, with 160 virtual nodes each (ketama). A client library routes requests, and swaps rings by epoch.
• Design a key-value store: 16 tokens per node, and a preference list of 3 distinct machines in distinct racks. Membership by gossip, and sloppy quorums with hinted handoff.
• Design a metrics and monitoring system: each series goes to 3 ingesters on a token ring, one per zone. Rule engines are sharded by rule group, on a ring.
• Design a URL shortener: the counterexample, a fixed set of 4,096 slots with an explicit map, because moves should be planned rather than computed.
• Design search autocomplete: why no hashing scheme fixes a hot key, and the edge cache that does.

Beyond these problems, you’ll find these schemes in:

• Amazon’s Dynamo and Apache Cassandra (rings with tokens).
• Memcached clients and Nginx’s hash … consistent (ketama).
• Envoy’s ring_hash and maglev load balancers.
• Google’s Maglev and Facebook’s Katran (Maglev tables for layer 4 load balancing).
• GitHub’s GLB Director (rendezvous hashing to build its forwarding table).
• CDN cache hierarchies, such as Apache Traffic Server’s consistent hash parent selection. It sends each URL to one parent cache, so the parents do not all store the same objects.

Recap

The problem. hash mod N moves N/(N+1) of keys when N changes: 91% going from 10 to 11 servers. The floor is 1/(N+1).

The ring. Servers and keys hash onto a circle. A key belongs to the first server clockwise. One change moves about 1/N of keys. Lookup is a binary search.

Virtual nodes. One point per server leaves the busiest server at 3 to 5 times the average. V points per server cut the spread to about 1/√V: 160 points, 8%, busiest of 100 at 1.2×. A dead server’s load spreads over everyone. Weights are more points.

Replicas. Walk clockwise, skipping servers and zones already chosen.

Alternatives. Rendezvous: highest score wins, O(N), replicas as top-k. Jump: no memory, near perfect balance, add or remove only at the end. Maglev: one table read per packet, near perfect balance, slightly more than minimal movement. Slots and a map: planned moves, a map to track.

Failures. Clients that disagree on the ring (fix with an epoch and test vectors). Flapping membership (separate down from removed). Hot keys (bounded loads for caches, replication or splitting for storage).

Further reading

• Partitioning and sharding, for range versus hash keys and resharding. Replication, for what happens on the preference list. Caching and load balancing, for the tiers that use these schemes.
• Dynamo: Amazon’s Highly Available Key-value Store, SOSP 2007: the ring, virtual nodes, preference lists, hinted handoff, and the three partitioning strategies it compared.
• A Fast, Minimal Memory, Consistent Hash Algorithm, Lamping and Veach, 2014: jump consistent hash, with its proof and a comparison with rings.
• Maglev: A Fast and Reliable Software Network Load Balancer, NSDI 2016. It covers the lookup table, its fill algorithm, and how disruption and balance trade off with table size.