Consistent hashing

Key points

• hash(key) % N is fine until N changes. Go from 4 nodes to 5 and roughly 80% of keys move - every cache is cold at once.
• Consistent hashing maps nodes and keys onto the same circle. A key belongs to the first node clockwise from it.
• Add or remove a node and only its neighbour’s slice moves: about 1/N of the keys, not all of them.
• Plain rings distribute badly. Virtual nodes - 100-200 ring positions per physical node - even out the load and shrink the blast radius.
• This is how Cassandra, DynamoDB, and memcached clients place data, and how an L7 balancer keeps a user pinned to one instance.
• It balances placement, not popularity. One celebrity key still hammers one node; replicate hot keys to fix that.

Example

// A hash ring: nodes sit on a circle, each key goes to the next node clockwise.
final class HashRing {

    private final NavigableMap<Long, String> ring = new TreeMap<>();
    private final int replicas;                    // virtual nodes per physical node

    HashRing(int replicas) { this.replicas = replicas; }

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

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

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

    private long hash(String s) {                  // FNV-1a: cheap and well spread
        long h = 0xcbf29ce484222325L;
        for (byte b : s.getBytes(StandardCharsets.UTF_8)) {
            h ^= (b & 0xff);
            h *= 0x100000001b3L;
        }
        return h >>> 1;                            // keep it non-negative
    }
}

A hash ring with virtual nodes moves 1/N of your keys on a resize instead of nearly all of them.