Consistent Hashing

The problem

You have a cache or database split across N servers and must decide which server holds each key. The obvious answer is:

server = hash(key) % N

It spreads keys evenly and needs no lookup table, until N changes. When a server is added or dies, the divisor changes and almost every key maps somewhere else.

For a cache this means a near-total miss storm that can knock over the database behind it. For a database it means re-copying almost the entire dataset. Consistent hashing fixes this: when the number of servers changes, only about K / N of the K keys move.

How it works

Imagine the output range of a hash function (say 0 to 2^64 - 1) bent into a circle, the ring.

1. Hash each server (for example its name or IP) to a position on the ring.
2. Hash each key to a position on the same ring.
3. Walk clockwise from the key's position; the first server you meet owns the key.

flowchart LR
  K1["key user:7 (pos 12)"] -- "next clockwise" --> B
  K2["key cart:91 (pos 47)"] -- "next clockwise" --> C
  K3["key img:3 (pos 88)"] -- "wraps past top" --> A
  A["Server A (pos 5)"] --> B["Server B (pos 30)"]
  B --> C["Server C (pos 60)"]
  C --> D["Server D (pos 80)"]
  D -- "ring wraps" --> A
  N["New server E (pos 40)"] -. "takes keys 31-40 from C only" .-> C

Adding a server E at position 40 takes over only the arc between B (30) and E (40); those keys used to belong to C. Every other key stays where it was.

Removing a server hands its arc to the next server clockwise; again, nothing else moves.

Lookups are a "find the first position ≥ h" query, so with a sorted structure (a sorted array with binary search, or a balanced tree like Java's TreeMap) each lookup costs O(log M), where M is the number of positions on the ring.

Virtual nodes

With one position per server, the ring is lumpy: random positions produce arcs of very different lengths, so one server may own three times the keys of another. And when a server leaves, all of its load lands on a single neighbour.

The fix is to give each physical server many positions, called virtual nodes or tokens: hash "A#0", "A#1", ... "A#149" and place all 150 points for server A on the ring.

Measured with the implementation below (10 servers, 50,000 keys, averaged over 20 runs), the busiest server's load relative to the average was:

Virtual nodes give three benefits:

• Even load: the relative spread shrinks roughly with 1 / sqrt(V) for V virtual nodes per server.
• Even recovery: a failed server's many small arcs are absorbed by many different servers instead of one.
• Heterogeneous hardware: a machine with twice the capacity simply gets twice as many virtual nodes.

The cost is memory and lookup time for M = N × V ring entries, and more metadata to gossip around the cluster. Cassandra historically defaulted to 256 tokens per node and lowered it to 16 in 4.0, pairing fewer tokens with a smarter token-allocation algorithm to keep balance while making repairs and streaming cheaper.

Replication

To survive failures, a key is stored on R servers rather than one. On a ring this is natural: the owner is the first server clockwise and the replicas are the next R - 1 distinct physical servers clockwise. That list is called the key's preference list in Dynamo.

• Skip positions that belong to a server already chosen; otherwise two virtual nodes of the same machine could hold "both" replicas.
• Better still, skip servers in the same rack or availability zone so one outage cannot take out every copy.
• When a server is added, it becomes a replica for the ranges just before it, and the server R positions further along stops being one, so data movement remains local.

Java Implementation

A TreeMap is a ready-made sorted ring: ceilingEntry(h) finds the first position at or after h, and firstEntry() handles the wrap-around.

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

class ConsistentHashRing {
    private final TreeMap<Long, String> ring = new TreeMap<>();   // position -> physical node
    private final int virtualNodes;

    ConsistentHashRing(int virtualNodes) { this.virtualNodes = virtualNodes; }

    void addNode(String node) {
        for (int i = 0; i < virtualNodes; i++) ring.put(hash(node + "#" + i), node);
    }

    void removeNode(String node) {
        for (int i = 0; i < virtualNodes; i++) ring.remove(hash(node + "#" + i), node);
    }

    String nodeFor(String key) {
        if (ring.isEmpty()) throw new IllegalStateException("ring is empty");
        Map.Entry<Long, String> e = ring.ceilingEntry(hash(key));     // first position >= hash
        return (e != null ? e : ring.firstEntry()).getValue();          // wrap around
    }

    List<String> replicasFor(String key, int n) {
        long h = hash(key);
        LinkedHashSet<String> owners = new LinkedHashSet<>();
        List<Collection<String>> clockwise = List.of(ring.tailMap(h, true).values(), ring.headMap(h, false).values());
        for (Collection<String> arc : clockwise)
            for (String node : arc) {
                owners.add(node);                                       // skips repeat vnodes of one machine
                if (owners.size() == n) return new ArrayList<>(owners);
            }
        return new ArrayList<>(owners);                                 // fewer than n physical nodes exist
    }

    private static long hash(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);  // first 64 bits of the digest
            return h;
        } catch (NoSuchAlgorithmException e) {
            throw new IllegalStateException(e);
        }
    }
}

public class Main {
    public static void main(String[] args) {
        ConsistentHashRing ring = new ConsistentHashRing(150);
        for (String n : List.of("A", "B", "C", "D")) ring.addNode(n);

        int keys = 100_000;
        Map<String, String> before = new HashMap<>();
        Map<String, Integer> load = new TreeMap<>();
        for (int i = 0; i < keys; i++) {
            String k = "user:" + i, owner = ring.nodeFor(k);
            before.put(k, owner);
            load.merge(owner, 1, Integer::sum);
        }
        System.out.println("Load with 4 nodes: " + load);

        ring.addNode("E");
        int moved = 0;
        for (Map.Entry<String, String> e : before.entrySet())
            if (!ring.nodeFor(e.getKey()).equals(e.getValue())) moved++;
        System.out.printf("Keys moved after adding E: %.1f%% (ideal 20%%)%n", 100.0 * moved / keys);
        System.out.println("Replicas for user:42 -> " + ring.replicasFor("user:42", 3));
    }
}

Sample output:

Load with 4 nodes: {A=26983, B=25905, C=24145, D=22967}
Keys moved after adding E: 18.5% (ideal 20%)
Replicas for user:42 -> [D, C, E]

Notes on the code:

• MD5 is used only for its even spread, not for security; production systems often use faster non-cryptographic hashes such as MurmurHash3 or xxHash.
• The signed long ordering is fine: the ring is just a circle of 2^64 positions, and the wrap from the largest to the smallest key is handled by firstEntry().
• TreeMap is not thread-safe. For a read-heavy router, build a new immutable ring on membership changes and swap it in atomically, or use ConcurrentSkipListMap.

Rebalancing in practice

The ring tells you where data should live; real systems still have to move it safely.

• Stream, then switch: a joining node copies its new ranges from current owners, and only then is it announced as the owner, so reads never hit an empty node.
• Membership agreement: every router must eventually see the same ring. Dynamo-style stores gossip ring state; others keep it in ZooKeeper or etcd and push updates to clients.
• Caches are forgiving: for a cache cluster you can skip data movement entirely and let the ~1/N of keys that moved miss once.
• Throttle movement: cap streaming bandwidth so rebalancing does not starve foreground traffic.

Alternatives and variants

Consistent hashing was introduced by Karger et al. in 1997 for distributing web caches, the work that later grew into Akamai's CDN. Today it routes requests in memcached client libraries, partitions Dynamo, Cassandra and Riak, and balances connections in load balancers.

Trade-offs

Interview Tips

• Open with the hash % N failure and the numbers: adding a fifth server to four moves ~80% of keys versus ~20%.
• Draw the ring, place three servers and a few keys, then add a server and show which arc moves.
• Introduce virtual nodes as the answer to both uneven load and uneven recovery, and mention weighting.
• Explain replication as "the next R distinct physical servers clockwise", and add rack or zone awareness.
• State the lookup cost (binary search, O(log M)) and that a TreeMap or sorted array implements it.
• Be ready to say what consistent hashing does not solve: hot keys, range scans, and membership agreement.
• If time permits, name an alternative (rendezvous or jump hash) and when you would pick it.

References

• System Design Primer: sharding (consistent hashing to reduce rebalancing)
• The Magic of Consistent Hashing (Mathias Meyer)
• Karger et al., Consistent Hashing and Random Trees (1997)
• Dynamo: Amazon's Highly Available Key-value Store (SOSP 2007)
• Lamping and Veach, A Fast, Minimal Memory, Consistent Hash Algorithm (jump hash)
• Karan Pratap Singh: System Design, consistent hashing