How Partitioning works

Before you start

• Caching

  Cache-aside is the read path everything here builds on.

  Open lesson

Why it matters

Redirect traffic no longer fits one cache node, so every short code needs a predictable owner among several nodes. Capacity changes and failures must not make clients disagree or turn the next request for nearly every code into a database miss. Adding one cache node must move only a small fraction of mappings, not flush the whole cache fleet.

Redirect traffic no longer fits one cache. You will run a ring of cache nodes. The key is the short code.

Input

ring = {10: "A", 40: "B", 75: "C"}, keys = [5, 22, 50, 62, 80, 99]

Output

[["A", "B", "C", "C", "A", "A"], ["A", "B", "D", "C", "A", "A"]]

Modulo N moves almost every sample key when node count changes. Place A, B, C, and short-code hashes on a ring instead; adding D at position 60 moves only key 50’s arc, while the mappings database still serves misses.

Put cache nodes A, B, and C at ring positions 10, 40, and 75. Hash each short code to the same 0–99 space; key 22 goes to the first node clockwise, B, while key 80 wraps to A. A binary search over sorted node positions finds that owner.

Adding D at 60 transfers only keys in its new arc, such as key 50 from C; the other sample keys stay put. Many virtual positions per physical cache smooth uneven arcs. The mappings database remains behind the ring for misses, so movement briefly costs fills rather than lost source data.