Consistent Hashing Ring

Start from brute force

The obvious way to spread keys over nodes is modulo hashing: nodes[hash32(key) % len(nodes)]. It works as far as it goes: it is deterministic, close to uniform, and O(1) per key, so O(K) time and O(1) extra space for K keys. It does not produce ring ownership (on the first example it gives ['A', 'B', 'A'], not ['C', 'A', 'C']), and its real failure is churn. A key keeps its node only if h % N == h % (N + 1); going from 3 nodes to 4 that holds for 1 key in 4, and measured on the 10,000 keys user0 to user9999 with this hash32, 7,502 changed owner. In a cache, every one of them is a miss.

The approach

Put nodes and keys on the same circle of 32-bit hash values, and let each key belong to the first node point clockwise from it. The insight is locality: a node owns only the arcs that end at its own points, so a joining node takes keys only from the arcs it lands in, and a leaving node hands its arcs to the next points clockwise. No other key moves. Virtual nodes give each node vnodes scattered points, so the arcs even out. The invariant is that ring is sorted by point, which makes “the first point at or after kh” well defined, and wrapping to ring[0] closes the circle.

The reference builds ring from (hash32(n + "#" + str(r)), n) for every node and replica and calls ring.sort(). For each key it computes kh = hash32(key), sets owner = ring[0][1] as the wrap-around default, then scans for the first point >= kh and breaks. The scan is linear; because the ring is sorted, bisect_left on the points finds the same index in O(log R).

Walk through an example

The first example builds nine points (three nodes, three replicas each), sorts them, and routes each key to the first point at or above its hash.

Complexity

Reference: sorting R = N · vnodes points is O(R log R), and each of K keys scans up to R of them: O(R log R + K · R) time, O(R + K) space. bisect cuts lookups to O(K log R). Modulo hashing: O(K) time and O(1) extra space, but going from N to N + 1 nodes remaps about N/(N + 1) of the keys.

Edge cases to test

• A key past the largest point: hash32("k207") is 4285853574, above the top point 4184374926, so the scan finds nothing and the owner = ring[0][1] default routes it to B.
• vnodes = 1 on the first example: three points only, and all three keys land on C. Across the keys user0 to user9999, C took 7,997 of 10,000. That lumpiness is why virtual nodes exist.
• A single node, assign(["k1", "k2", "k3"], ["A"], 1): every key maps to A, whether it wraps or not.
• No nodes, or vnodes = 0: the ring is empty and ring[0] raises IndexError. The statement assumes at least one point; production code should reject an empty ring explicitly.
• The same key twice, ["dup", "dup"]: both route to the same node, because routing is a pure function of the key and the ring.
• Characters outside the Basic Multilingual Plane, such as the emoji U+1F600: the Python hash32 iterates code points and the TypeScript one iterates UTF-16 code units, so the hash is 2046440521 in Python and 3276203938 in TypeScript. The two languages agree only on BMP text.

Common mistakes

• Too few virtual nodes — the ring is lumpy and some nodes run hot.
• Falling back to hash(key) % N: going from N to N + 1 nodes remaps about N/(N + 1) of the keys, 7,502 of the 10,000 keys user0 to user9999 when a fourth node joins three.
• Forgetting wrap-around: a key past the last node point belongs to the first node.
• In TypeScript, calling ring.sort() with no comparator: it compares the pairs as strings, so [1184223885, "C"] sorts before [129767782, "B"] and “clockwise” stops meaning anything. Sort with (a, b) => a[0] - b[0].

Follow-ups an interviewer asks next

Thousands of virtual nodes and millions of lookups: make routing faster.

Keep the points in their own sorted list and binary-search it: i = bisect_left(points, kh), owner ring[i % len(ring)][1]. That is O(log R) per key instead of O(R), and on the keys user0 to user9999 it returns exactly what the linear scan returns. Build the ring once and reuse it, instead of rebuilding it on every call to assign.

A node joins or leaves. Which keys move, and how do you update the ring?

Only keys in the arcs ending at that node’s points. With this hash32, the 10,000 keys user0 to user9999 and 50 vnodes, adding D moved 2,513 keys, all to D, and removing B moved exactly B’s 2,913. To update without a rebuild, insert or delete the node’s points in a sorted structure: O(vnodes · log R) in a balanced tree, O(vnodes · R) in a plain sorted array.

The nodes have different capacities.

Give each node a number of virtual nodes proportional to its weight, so a machine with twice the memory gets twice the points and, on average, twice the keys. The routing code does not change, and removing a weighted node still moves only its own keys.

Store every key on three nodes for durability.

Walk clockwise from the key’s position and collect the first three distinct physical nodes, skipping points that belong to a node already picked. This is the preference-list idea from Dynamo-style stores, and with virtual nodes the replicas of one node’s keys are spread across many different neighbors.

Where this shows up

Consistent hashing is how distributed caches and databases (Dynamo, Cassandra, Riak, Memcached clients) spread keys so a membership change moves only ~K/N keys instead of the whole keyspace — turning a node add/remove from a cache-wide stampede into a small, local reshuffle.

Reference solution

def hash32(s):                      # provided: xmur3 32-bit (matches TypeScript)
    h = (1779033703 ^ len(s)) & 0xffffffff
    for ch in s:
        h = ((h ^ ord(ch)) * 3432918353) & 0xffffffff
        h = ((h << 13) | (h >> 19)) & 0xffffffff
    h = ((h ^ (h >> 16)) * 2246822507) & 0xffffffff
    h = ((h ^ (h >> 13)) * 3266489909) & 0xffffffff
    return (h ^ (h >> 16)) & 0xffffffff


def assign(keys, nodes, vnodes):
    ring = []                        # (point on the ring, node name)
    for n in nodes:
        for r in range(vnodes):
            ring.append((hash32(n + "#" + str(r)), n))
    ring.sort()                      # order points clockwise
    out = []
    for key in keys:
        kh = hash32(key)
        owner = ring[0][1]           # default: wrap to the first point
        for point, node in ring:
            if point >= kh:
                owner = node         # first point at/after the key
                break
        out.append(owner)
    return out


print(assign(['k1', 'k2', 'k3'], ['A', 'B', 'C'], 3))  # -> ['C', 'A', 'C']

function hash32(s: string): number {   // provided: xmur3 32-bit (matches Python)
  let h = (1779033703 ^ s.length) >>> 0;
  for (let i = 0; i < s.length; i++) {
    h = Math.imul(h ^ s.charCodeAt(i), 3432918353);
    h = (h << 13) | (h >>> 19);
  }
  h = Math.imul(h ^ (h >>> 16), 2246822507);
  h = Math.imul(h ^ (h >>> 13), 3266489909);
  h ^= h >>> 16;
  return h >>> 0;
}

function assign(keys: string[], nodes: string[], vnodes: number): string[] {
  const ring: [number, string][] = [];   // [point, node]
  for (const n of nodes)
    for (let r = 0; r < vnodes; r++) ring.push([hash32(n + "#" + r), n]);
  ring.sort((a, b) => a[0] - b[0]);       // clockwise order
  return keys.map((key) => {
    const kh = hash32(key);
    for (const [point, node] of ring) if (point >= kh) return node;
    return ring[0][1];                    // wrap around to the first point
  });
}

console.log(assign(['k1', 'k2', 'k3'], ['A', 'B', 'C'], 3)); // -> ["C","A","C"]