Consistent Hashing

Consistent hashing is a key-to-node mapping scheme in which adding or removing a node changes the assignment of only about K/N of K keys across N nodes. It is used to distribute data in partitioned stores (Dynamo, Cassandra, Riak), to route requests in caches and load balancers, and to place objects in content delivery systems.

The problem with modulo hashing

The simple scheme node = hash(key) mod N assigns keys evenly, but N appears in the formula. When N changes from 4 to 5, a key keeps its node only if hash mod 4 == hash mod 5, which holds for roughly one key in five. About 80% of keys move.

In a cache, moved keys become misses, and the misses hit the database. In a data store, moved keys mean bulk data transfer. The goal is a scheme where the number of moved keys is close to the minimum, which is K/N when adding the Nth node.

The hash ring

1. Choose a hash function with a large output space, for example 32 or 64 bits. Treat the space as a circle: the largest value wraps around to zero. This circle is the hash ring.
2. Hash each node identifier (for example its address) onto the ring.
3. Hash each key onto the ring.
4. A key belongs to the first node found moving clockwise from the key's position (its successor).

flowchart LR
    subgraph Ring["Ring positions in increasing order, wrapping around"]
        direction LR
        A["Node A @ 100"] --> K1["key k1 @ 150"] --> B["Node B @ 300"] --> K2["key k2 @ 420"] --> C["Node C @ 600"] --> K3["key k3 @ 900"] --> A
    end
    K1 -.->|"owned by"| B
    K2 -.->|"owned by"| C
    K3 -.->|"owned by, wraps to"| A

Each node owns the arc between its predecessor's position and its own.

Adding a node

A new node D hashes to a position between B and C. It takes over the part of C's arc that lies before D. Only keys in that arc move, from C to D. No other assignments change.

Removing a node

If B leaves or fails, its arc is inherited by its successor C. Only the keys that belonged to B move.

Lookup

Store the node positions in a sorted structure (sorted array or balanced tree). A lookup is a binary search for the first position greater than or equal to the key's hash, wrapping to the first entry if none exists. This takes O(log N).

Problems with the basic ring

With one position per node, the arcs are random lengths. Some nodes own much more of the ring than others, and the variance is large for small N. When a node leaves, its entire arc goes to one successor, which may double that node's load.

Virtual nodes

A virtual node (vnode) is one of many ring positions assigned to a physical node. Each physical node is hashed onto the ring many times, for example using identifiers nodeA#0, nodeA#1, ..., nodeA#127.

• The load on a physical node is the sum of many small arcs, which averages toward an equal share as the vnode count grows.
• When a node leaves, its many small arcs are inherited by many different successors, so the extra load spreads over the remaining nodes.
• A node added to the cluster takes small arcs from many nodes.
• Weights. A machine with twice the capacity gets twice as many vnodes.

Costs: a larger ring metadata structure and more partitions to track, and, for replicated stores, more distinct replica relationships between nodes. Cassandra defaults have used 256 vnodes per node in older versions and fewer in newer ones; the right number is a trade-off between balance and metadata overhead.

Replication on the ring

To keep R copies of a key, store it on the owner and the next distinct nodes clockwise: the preference list. With vnodes, the walk must skip positions that belong to a physical node already in the list, otherwise several replicas could land on the same machine. Systems can also skip nodes in the same rack or availability zone.

flowchart LR
    key["key hash"] --> N1["Owner: node B"]
    N1 --> N2["Replica: node C"]
    N2 --> N3["Replica: node D"]

Dynamo-style stores combine this with quorums for reads and writes.

Related techniques

Java implementation

The ring is a TreeMap from position to node name, with positions compared as unsigned 64-bit values. The hash is FNV-1a followed by a mixing step, implemented inline because the hash must give the same value in every process and release. String.hashCode() is only 32 bits and spreads similar strings poorly, so it is not used for ring positions.

import java.nio.charset.StandardCharsets;
import java.util.ArrayList;
import java.util.HashMap;
import java.util.List;
import java.util.Map;
import java.util.NavigableMap;
import java.util.Optional;
import java.util.TreeMap;

public class Main {
    static long fnv1a(String data) {
        long h = 0xcbf29ce484222325L;
        for (byte b : data.getBytes(StandardCharsets.UTF_8)) {
            h ^= (b & 0xffL);
            h *= 0x100000001b3L; // wraps on overflow
        }
        // extra mixing so that similar strings spread across the ring
        h ^= h >>> 33;
        h *= 0xff51afd7ed558ccdL;
        h ^= h >>> 33;
        return h;
    }

    static final class Ring {
        private final int vnodes;
        private final NavigableMap<Long, String> ring = new TreeMap<>(Long::compareUnsigned);

        Ring(int vnodes) {
            this.vnodes = vnodes;
        }

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

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

        /** First vnode at or after the key's position, wrapping to the start. */
        Optional<String> owner(String key) {
            if (ring.isEmpty()) {
                return Optional.empty();
            }
            var entry = ring.ceilingEntry(fnv1a(key));
            if (entry == null) {
                entry = ring.firstEntry();
            }
            return Optional.of(entry.getValue());
        }

        /** Up to r distinct physical nodes, walking clockwise. */
        List<String> preferenceList(String key, int r) {
            long h = fnv1a(key);
            var clockwise = new ArrayList<String>(ring.tailMap(h, true).values());
            clockwise.addAll(ring.headMap(h, false).values());
            var out = new ArrayList<String>();
            for (String n : clockwise) {
                if (!out.contains(n)) {
                    out.add(n);
                    if (out.size() == r) {
                        break;
                    }
                }
            }
            return out;
        }
    }

    static List<String> assignments(Ring ring, List<String> keys) {
        return keys.stream().map(k -> ring.owner(k).orElseThrow()).toList();
    }

    public static void main(String[] args) {
        var keys = new ArrayList<String>();
        for (int i = 0; i < 10_000; i++) {
            keys.add("key-" + i);
        }

        var ring = new Ring(100);
        for (String n : List.of("node-a", "node-b", "node-c", "node-d")) {
            ring.addNode(n);
        }
        var before = assignments(ring, keys);

        Map<String, Integer> load = new HashMap<>();
        for (String n : before) {
            load.merge(n, 1, Integer::sum);
        }
        int min = load.values().stream().min(Integer::compare).orElseThrow();
        int max = load.values().stream().max(Integer::compare).orElseThrow();
        System.out.println("4 nodes: min load " + min + ", max load " + max + ", ideal 2500");

        ring.addNode("node-e");
        var after = assignments(ring, keys);
        int moved = 0;
        int movedToNew = 0;
        for (int i = 0; i < keys.size(); i++) {
            if (!before.get(i).equals(after.get(i))) {
                moved++;
                if (after.get(i).equals("node-e")) {
                    movedToNew++;
                }
            }
        }
        System.out.println("added node-e: moved " + moved + " of 10000 keys, "
                + movedToNew + " of them to node-e");

        long moduloMoved = keys.stream()
                .filter(k -> Long.remainderUnsigned(fnv1a(k), 4) != Long.remainderUnsigned(fnv1a(k), 5))
                .count();
        System.out.println("modulo 4 -> 5 would move " + moduloMoved + " keys");

        System.out.println("preference list: " + ring.preferenceList("key-42", 3));
    }
}

4 nodes: min load 2144, max load 2955, ideal 2500
added node-e: moved 2019 of 10000 keys, 2019 of them to node-e
modulo 4 -> 5 would move 7960 keys
preference list: [node-d, node-c, node-e]

Properties shown by the output:

• Every key that moved went to the new node; none moved between existing nodes.
• About one fifth of the keys moved (K/N with N = 5), whereas modulo hashing moves roughly (N-1)/N of the keys when going from N to N+1.

Limitations

• Hot keys are not solved. The ring balances key counts, not request rates. A very popular key still loads one node (see sharding and partitioning).
• Membership must be consistent. Clients and nodes need the same view of the ring. Views differing briefly cause misrouted requests, so systems propagate membership through a coordination service or gossip.
• Data movement still happens. Consistent hashing minimizes it but does not eliminate it. Newly added nodes must receive their keys, and range transfers must run in the background.
• Balance is probabilistic. More vnodes improve balance and increase metadata.

Interview questions

• Why does consistent hashing move fewer keys than modulo hashing? Assignment depends on positions on a fixed hash space, not on the node count. A node change affects only the arcs adjacent to its positions, about K/N keys.
• What do virtual nodes fix? They even out the arc sizes, so load is balanced, and they spread the load of a failed node across many survivors instead of one successor. They also allow weighting by capacity.
• How are replicas chosen on the ring? The next R-1 distinct physical nodes clockwise from the owner, skipping vnodes of nodes already chosen, and optionally skipping nodes in the same rack or zone.
• When would you choose rendezvous hashing over a ring? When the node set is small and a lookup cost of O(N) is acceptable, because it needs no ring structure and gives the same minimal-movement property.