Name: System Design Masterclass
Availability: InStock

When one cache node is no longer enough, the keys are spread over several. The obvious way to decide which node holds which key is a remainder, and it fails for a specific reason.

Two panels. Hash key modulo N: N goes from 10 to 11, every remainder changes, so almost every key moves, with keys reading keys that moved 18,177 of 20,000 and share 90.9 percent. A consistent hash ring: a new node joins, it takes an arc of the circle, and nothing else moves, with keys reading keys that moved 1,637 of 20,000 and share 8.2 percent. — ComparisonFigure 1. Adding one node to a ten node cluster moved ninety-one percent of the keys under modulo
A tenth of them should move, because the new node has to own a tenth of the key space. Modulo moved everything else as well, for no reason connected to what the cluster now looks like.

Every key that moves is a miss. A modulo cluster's hit rate goes to roughly zero at the moment a node is added and stays there until the whole working set has been refetched, which is why the ring exists.

A hand-drawn figure of a circle with eight large filled circles on it representing nodes and ten small dots just outside it representing keys, labelled big circles are nodes and small dots are keys. One position on the circle is marked with a dashed red outline. A note reads that a new node at the dashed point takes only the keys between it and the node before it. — SketchFigure 2. Both nodes and keys are hashed onto one circle, and a key belongs to the next node clockwise
Because a node owns an arc rather than a remainder, adding one only affects the keys inside the arc it takes, and every other key stays exactly where it was.

A terminal capture of the consistent hashing lab. 20,000 keys over 10 nodes and 500,000 Zipf distributed requests. A first table shows keys moved when adding a node: 90.9 percent under modulo, 11.3 percent on a ring with one virtual node and 8.2 percent with a hundred. A second table shows the busiest node by key count against virtual nodes, falling from 2.79x to 1.05x. A third table shows key imbalance against request imbalance over the same rings, where the request column goes 3.68x, 2.10, 1.93, 1.68 and 2.16. — terminal-figureFigure 3. The measurement. Three counts over the same rings and the same placements
Virtual nodes took the key imbalance from 2.79 times to 1.05, and the request imbalance from 3.68 to 2.16 without converging.

A line chart of the busiest node as a multiple of its fair share of keys against virtual nodes per physical node. It falls from 2.79 at one virtual node to 1.83 at five, 1.22 at twenty, 1.15 at a hundred and 1.05 at five hundred. — ChartFigure 4. With one point each, the busiest node held two and eight tenths times its share
Ten random points on a circle do not divide it evenly. Placing each node at many points averages the arcs out, and the imbalance falls towards one as the number of points grows.

A hundred to a few hundred virtual nodes per physical node is the usual setting and the measurement supports it. Below twenty the imbalance is large enough to matter, and above five hundred the return is small.

Where this shows up in interviews

Where this shows up in interviews

Distributed Cache

The rest of this lesson

Continue this lesson

Why Modulo Does Not Work

Ten Points Do Not Divide A Circle Evenly