Consistent Hashing

The ring

Take a hash function whose output is a big number, and bend its range into a circle: 0 at the top, the maximum value just before it. Hash each server name to a point on the circle. Hash each key too. A key is stored on the first server you meet walking clockwise from it.

Now add Server E between B and C. Only the keys between B and E change owner (they used to walk on to C). Every other key stays exactly where it was.

Removing a server is the mirror image: its keys move to the next server clockwise, and nothing else changes.

Virtual nodes

With only one point per server, the gaps between servers are random sizes, so one server might own 40% of the ring and another 10%. And when a server leaves, all its keys land on a single neighbour.

The fix is virtual nodes: hash each server many times (A#0, A#1, … A#99) so it appears at 100 scattered points. Each server now owns many small arcs, the shares even out, and a departing server's keys spread across all the others. A machine with twice the capacity simply gets twice as many virtual nodes.

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

class HashRing {
    private final int replicas;
    private final TreeMap<Long, String> ring = new TreeMap<>();

    HashRing(Collection<String> nodes, int replicas) {
        this.replicas = replicas;
        for (String node : nodes) {
            addNode(node);
        }
    }

    static long hash(String s) {
        try {
            byte[] d = MessageDigest.getInstance("MD5").digest(s.getBytes(StandardCharsets.UTF_8));
            return ((long) (d[0] & 0xff) << 24) | ((d[1] & 0xff) << 16) | ((d[2] & 0xff) << 8) | (d[3] & 0xff);
        } catch (Exception e) {
            throw new IllegalStateException(e);
        }
    }

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

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

    String nodeFor(String key) {
        Map.Entry<Long, String> e = ring.ceilingEntry(hash(key));
        return (e != null ? e : ring.firstEntry()).getValue(); // wrap around
    }
}

import bisect
import hashlib

class HashRing:
    def __init__(self, nodes, replicas):
        self.replicas = replicas
        self.points = []  # sorted hash positions
        self.owner = {}   # position -> node
        for node in nodes:
            self.add_node(node)

    @staticmethod
    def hash(s):
        return int(hashlib.md5(s.encode()).hexdigest()[:8], 16)

    def add_node(self, node):
        for i in range(self.replicas):
            h = self.hash(f"{node}#{i}")
            self.owner[h] = node
            bisect.insort(self.points, h)

    def remove_node(self, node):
        for i in range(self.replicas):
            h = self.hash(f"{node}#{i}")
            del self.owner[h]
            self.points.remove(h)

    def node_for(self, key):
        i = bisect.bisect_left(self.points, self.hash(key))
        return self.owner[self.points[i % len(self.points)]]  # wrap around

The tests check the three promises: adding E moves only keys to E (about a fifth of them); removing B moves only B's keys; and with 100 virtual nodes each of the four servers gets roughly a quarter.

Where it is used

• Distributed caches: clients pick a Memcached or Redis node per key, and adding a node only invalidates a small share of the cache.
• Dynamo-style databases: Amazon's Dynamo paper describes partitioning with a ring and virtual nodes; Cassandra uses the same idea, storing each key on the next few nodes clockwise as replicas.
• Load balancers and CDNs: send the same client or URL to the same backend so its local cache stays warm.

Common mistakes

• Using one point per server, which gives very uneven shares.
• Forgetting the wrap-around: keys after the last point belong to the first server.
• Using a hash function with poor spread, clustering servers together.
• Thinking consistent hashing removes all data movement: about 1/N of the keys still move, and they must be copied.

Interview questions

Try answering out loud before you open each one.

Check yourself

Related topics

• Sharding (Partitioning)Databases
• Load Balancing AlgorithmsEdge and Traffic

Further reading

• Dynamo: Amazon's Highly Available Key-value Store DeCandia et al., SOSP 2007
• Cassandra documentation: Dynamo Apache Cassandra