One expired key, four hundred database queries
A hot key is cached for five minutes. When it expires, every in-flight request misses at once and all of them query the database. p99 latency spikes on a five minute cycle, exactly on the cycle.
Stop the stampede. The cache may not be made permanent, and the data may not be more than five minutes stale.
Example
- input
400 concurrent requests at expiryoutput1 database queryOne request recomputes; the rest either wait for it or serve the value that just expired.
Constraints
- Staleness ≤ 5 minutes.
- A crashed recomputing process must not lock the key forever.
Hints
Hint 1
A per-key lock turns 400 queries into 1 — and 399 waiters, which is its own latency problem.
Hint 2
Serving the stale value while one process refreshes is usually the better trade.
Hint 3
Whatever lock you take needs a TTL, or the first crash wedges the key permanently.
Stuck? The lesson behind this problem: 🐘 Query optimisation
java
Tab indents · Escape first to tab out
Test cases
These are the specification. Run tests checks your answer against them.
| Case | Input | Expected |
|---|---|---|
| 400 concurrent misses | concurrency=400 | expensiveQuery calls = 1 |
| warm reads do not block | concurrency=400, key warm | expensiveQuery calls = 0 |
| a failed load does not lock the key | the loader throws once | the next caller recomputes, calls = 2 |