Skip to content
Tutorials Center
My learning

Topics

Lesson 36 of 37 ยท Projects and Practice

Project: A Cache Library with Stampede Protection

Build a small caching library with remember(), TTL jitter, negative caching, versioned invalidation, add-based locks and hit counters, then test it against a stampede.

Most applications do not call get and set by hand. They use a small helper, remember(key, ttl, compute), that hides the cache-aside pattern. In this project you will build such a helper, with the safety features this track introduced: TTL jitter, negative caching, versioned namespaces for invalidation, lock-based single flight and counters.

The backing store is a fake Memcached implemented in Python with a virtual clock, so everything is deterministic and runs in the live editor. The helper only uses operations a real client offers (get, set, add, delete, incr), so porting it to a real client means swapping one class.

Design

flowchart TD
  A["remember(key)"] --> B{"cached?"}
  B -->|"hit"| R["return value"]
  B -->|"miss"| L{"add lock succeeds?"}
  L -->|"yes: leader"| C["compute from source"]
  C --> S["set with jittered TTL, release lock"]
  S --> R
  L -->|"no: follower"| W["use stale copy or wait and retry"]
  W --> R

One leader recomputes; followers use the previous value or wait.

Requirements:

  1. Namespaces with versions: bump("products") invalidates every key in the namespace.
  2. TTL jitter: each stored TTL is ttl plus or minus a few percent.
  3. Negative caching: if the source returns None (not found), store a marker for a short time.
  4. Single flight: only the lock owner computes; others serve the stale value kept under a longer TTL, or fail soft.
  5. Counters: hits, misses, computes, stale serves.

The fake store

Python Step 1: a fake memcached with get/set/add/incr

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.

The library

The Cache class below wraps the store. A "stale" copy is kept inside the cached envelope: each value is stored as (value, soft_expiry) with a physical TTL that is longer, so a follower can serve slightly old data while the leader refreshes (see Cache Stampede Protection).

Python Step 2: remember() with namespaces, jitter and locks

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.

Check the output: the second lookup is a hit, the second lookup of the missing key hits the negative marker (no new database call), and after bump the new value appears because the key name changed. The old entries are never read again and age out by TTL.

Step 3: test against a stampede

To check the leader election, simulate a hot key that expired and 200 requests arriving while the leader is still computing. In real life those run in parallel; here we model "the leader is busy" by taking the lock manually and having requests arrive before it finishes.

Python Step 3: 200 requests, one computation

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.

Both scenarios do exactly one computation for 200 simultaneous requests. For the cold key the other 199 have nothing to serve and must wait (in a real client, sleep a few milliseconds and retry the cache); for the expired key they are served the stale copy and never wait. This is the difference between a design that merely protects the database and one that also protects latency.

Real concurrency adds details this single-threaded model hides: the lock TTL must exceed the typical compute time, a crashed leader leaves the lock until its TTL ends, and followers should wait with a small random back-off and a limit. Test these with real clients and real load before relying on them.

Extensions

  1. Return (value, source) so callers and logs know whether data was a hit, stale or fresh.
  2. Add per-namespace counters and compute the hit ratio each, as in Hit Ratio and Metrics.
  3. Add a remember_many() that uses a multi-get and computes only the missing keys in one batch.
  4. Add a refresh-ahead mode using the probabilistic rule from the stampede lesson.
  5. Record compute durations to size the lock TTL automatically.

Check your understanding

Quick check ยท 4 questions

of 4 answered You scored / 4 ยท perfect!

  1. 1. Why does bump(namespace) invalidate every key in that namespace?

    Incrementing the version changes every key name in the family; old keys are never read again.
  2. 2. What is negative caching for?

    A brief marker prevents a missing key from causing a database query for every request.
  3. 3. What does a follower do when it cannot get the lock but a stale copy exists?

    That keeps latency low while the leader refreshes.
  4. 4. Why must the lock have a TTL?

    An expiring lock cannot block a key permanently.

Summary

  • A remember() helper hides cache-aside and carries the safety features in one place.
  • Versioned namespaces give instant bulk invalidation without deletes.
  • Jitter spreads expiry; negative caching protects against missing keys.
  • An add lock elects one leader, and stale copies keep followers fast.
  • Test the guard under a simulated burst, then under real concurrency.

Next: Practice: Caching Exercises