Design a Distributed Cache

Design a Distributed Cache

Step 1 of 11

nodes4

One working set, too large for a single box, spread over machines arranged as a ring.

The Idea

Spread one hot working set over twenty machines and keep the map steady when a machine dies. Assume reads dominate, the data fits nowhere near one box, and a miss is expensive rather than fatal.

Real-World Example

Lockers arranged in a circle with an attendant beside each one. Every bag goes to the attendant standing clockwise of where it lands, so one attendant leaving shifts only the bags in their own stretch.

The Tradeoff

Hashing keys onto a ring moves a single node's share when a node joins or leaves, instead of remapping everything, and leaves load lumpy until each machine is scattered across the ring as many virtual points. Eviction is the other half of the design: a TTL bounds staleness, and least-recently-used decides who leaves when memory runs out.

Your turn

Put the steps in the right order.

1. 1Store the value on that node and evict the least recently used entry if it is full↑↓
2. 2Hash the key onto the ring and walk clockwise to the owning node↑↓
3. 3Read from the origin store on a miss↑↓
4. 4Ask that node for the key↑↓

Check order

Mini quiz

1 / 3

Consistent hashing is chosen over key modulo node-count because:

• AIt is cheaper to compute
• BAdding one node under modulo remaps almost every key
• CIt avoids hash collisions
• DIt removes the need for a TTL