Implementing the Ring: Building a Distributed Cache, Part 2

In Part 1 we decided on consistent hashing and last-write-wins replication. Now we implement the ring itself, and write a test that would catch us if we got it wrong.

The ring, for real this time

Each node gets several virtual positions on the ring, not just one — this smooths out the distribution of keys when the number of physical nodes is small:

interface RingEntry {
  position: number;
  nodeId: string;
}

function buildRing(nodeIds: string[], virtualNodesPerNode = 128): RingEntry[] {
  const ring: RingEntry[] = [];
  for (const nodeId of nodeIds) {
    for (let i = 0; i < virtualNodesPerNode; i++) {
      ring.push({ position: hashToRingPosition(`${nodeId}#${i}`), nodeId });
    }
  }
  return ring.sort((a, b) => a.position - b.position);
}

More virtual nodes means a smoother distribution but more memory per node holding the ring. 128 is a reasonable starting point; production systems often go higher.

The test that matters

The whole point of Part 1’s design was that removing a node should only move that node’s keys, not the whole keyspace. Here’s the test that proves it:

test("removing a node only remaps its own keys", () => {
  const before = buildRing(["a", "b", "c"]);
  const after = buildRing(["a", "c"]);

  const keys = Array.from({ length: 10_000 }, (_, i) => `key-${i}`);
  const remapped = keys.filter(
    (key) => nodeForKey(key, before) !== nodeForKey(key, after) && nodeForKey(key, before) !== "b",
  );

  expect(remapped).toHaveLength(0);
});

If this test passes, removing node b never disturbs a key that wasn’t already on b. That’s the entire promise of consistent hashing, verified rather than assumed.

What’s left

Replication and conflict resolution are still just described, not implemented — that’s Part 3, once there’s a ring worth replicating across.