Skip to content
Tutorials Center
My learning

Topics

Lesson 59 of 65 ยท Projects

Project: A Sharded Cache with Consistent Hashing

Build a distributed cache in Python: an LRU node, a consistent hash ring with virtual nodes, TTL expiry, node failure and rebalancing, and measure hit rates and key movement.

Caching is the most common way to make a system fast, and sharding is how a cache grows beyond one machine. In this project you will build both: an LRU cache node with expiry, a consistent hash ring that spreads keys over several nodes, and a client that survives a node being added or removed. You will measure how many keys move when the cluster changes, which is the whole reason consistent hashing exists.

The pieces

flowchart LR
    APP["Application"] --> CL["Cache client"]
    CL --> RING["Hash ring"]
    RING --> N1["Node A (LRU)"]
    RING --> N2["Node B (LRU)"]
    RING --> N3["Node C (LRU)"]
    CL -. "miss" .-> DB[("Database")]

On a miss the client reads the database and fills the cache (the cache-aside pattern).

Step 1: an LRU node with TTL

An LRU (least recently used) cache evicts the entry unused for the longest time when it is full. An OrderedDict gives O(1) access, move-to-end and eviction. A TTL (time to live) makes entries expire so stale data does not live forever.

Python LRU cache with expiry

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Step 2: the hash ring

With hash(key) % number_of_nodes, adding a fourth node changes the answer for about three quarters of the keys; your cache effectively empties and the database is flooded. A hash ring avoids this: nodes and keys are both hashed onto a circle, and each key belongs to the next node clockwise. Adding a node takes over only the arc just before it. Virtual nodes (many ring points per node) even out the distribution.

Python Modulo hashing versus a ring

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Modulo hashing moved about 80 percent of keys, the ring only about 15 percent (the ideal is 20 percent, so the exact number depends on where the points land): just the keys that now belong to the new node.

Step 3: the cluster client

The client uses the ring to find the node, reads through to the "database" on a miss, and fills the node. We then add traffic, a node failure and a recovery, and watch the hit rate.

Python Cache-aside client, node failure and recovery

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

After a failure you should see the hit rate dip and then recover, because only the keys that belonged to the failed node had to be reloaded. With modulo hashing the dip would affect nearly everything.

Step 4: things to explore

  1. Hot keys: a single very popular key overloads its node. Add a small local cache in the client, or replicate hot keys to two nodes.
  2. Stampede protection: when a popular key expires, thousands of readers miss at once. Add a per-key lock so only one reader reloads it (single flight).
  3. Replication: write each key to the next two nodes on the ring so one failure loses nothing.
  4. Write policies: compare write-through (update cache and database together) with cache-aside and with write-back (update cache, flush later).
  5. Eviction: replace LRU with LFU (least frequently used) and compare hit rates on the skewed workload.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does 'hash(key) % N' behave badly when N changes?

    Changing the modulus remaps most keys, causing a flood of misses.
  2. 2. What do virtual nodes improve?

    Many ring points per node smooth out uneven arc sizes.
  3. 3. What is the cache-aside pattern?

    The application owns the logic of loading and filling the cache.
  4. 4. What is a cache stampede?

    Single flight or request coalescing prevents the simultaneous reloads.

Summary

  • An LRU node with TTL is the building block of a cache cluster.
  • Consistent hashing moves only about 1/N of the keys when a node joins or leaves; modulo hashing moves most.
  • Virtual nodes balance load; cache-aside fills nodes on misses.
  • Failures cost a temporary hit-rate dip rather than a total cache loss.
  • Hot keys, stampedes and replication are the next problems to solve.

Next: Project: A Message Queue with Retries