Defending Against a Cache Stampede

Goal

Actually cause a cache stampede to see the surge in origin calls with your own eyes, then attach a lock, jitter, and stale-while-revalidate one by one and compare the defensive effect in numbers.

Why it matters

A stampede is an incident that happens only when the cache is working well. This is because of the paradox that the more popular a key is, the more dangerous it is — at the instant a key that was being read thousands of times per second expires, thousands of requests experience a miss at the same time and all rush to the original. A lookup that one would have sufficed for becomes thousands, and when the original is crushed, more misses occur and everything collapses in a chain. The part of this lab that is easiest to miss is step 5. If you put only a TTL on the lock and have no ownership token, then after it expires by TTL, the original owner, waking up late, releases the lock that another request took. Then two requests enter the critical section at the same time. This is the part most often omitted when building a distributed lock yourself, which is why a whole step is devoted to it.

Steps

Start /opt/app/slowdb.py (8151), and with /root/sp/naive.py, send 50 concurrent requests right after deleting a popular key. In /root/sp/naive.out, write concurrency=50 origin_calls=<n>, and n must be at least 20.
In /root/sp/lock.py, on a miss, only the request that obtained the lock with SET lock:<키> <토큰> NX EX 5 (key, token) goes to the original. Under the same conditions, in /root/sp/lock.out write concurrency=50 origin_calls=<n>, and n must be 3 or less.
A request that did not obtain the lock sleeps briefly for up to 2 seconds and checks the cache again. All 50 must receive the value. Also, in /root/sp/lock.out, write served=50.
The lock key must have a TTL. In /root/sp/lockttl.txt, write lock_ttl=<초> (seconds), and it must be between 1 and 30 inclusive.
Release the lock only when the ownership token matches. In /root/sp/owner.out, write wrong_token_release=0 right_token_release=1. The source must contain a token comparison.
With /root/sp/jitter.py, fill 100 keys with a base of 300 seconds and a jitter width of 60 seconds. In /root/sp/jitter.txt, write min_ttl=<n> max_ttl=<n> distinct=<n>, and distinct must be at least 20 and the difference between max and min at least 30.
/root/sp/swr.py stores a logical expiration time along with the value, and even after expiration it returns the old value immediately while refreshing only once in the background. In /root/sp/swr.out, write served_from_stale=<n> origin_calls=<n>, and origin_calls must be 3 or less.
In /root/sp/compare.md, write a markdown table. The row titles are three values, 무방비 (unprotected), 싱글플라이트 (single-flight), and stale-while-revalidate, and there must be a 원본호출 (origin calls) column.

Notes

Atomic lock: SET lock:key <uuid> NX EX 5 — if the return is OK, you have acquired it.
Safe release must be a delete after comparing the value, and these two also need to be atomic to be complete (a Lua script).
Concurrent requests: for i in $(seq 50); do curl -s ... & done; wait
Common mistake 1: simply failing the lock waiters — half of the users see errors.
Common mistake 2: always releasing the lock with DEL — you can release someone else's lock.

Reproduce the stampede

Start /opt/app/slowdb.py (8151), and with /root/sp/naive.py, send 50 concurrent requests right after deleting a popular key. In /root/sp/naive.out, write concurrency=50 origin_calls=<n>, and n must be at least 20.

Just pour concurrent requests in right after deleting a popular key. The origin query count grows by as much as the number of concurrent requests.

Put on a single-flight lock

In /root/sp/lock.py, on a miss, only the request that obtained the lock with SET lock:<키> <토큰> NX EX 5 (key, token) goes to the original. Under the same conditions, in /root/sp/lock.out write concurrency=50 origin_calls=<n>, and n must be 3 or less.

On a miss, let only the first request go to the original. Acquiring the lock must be atomic.

Let the lock waiters receive the value

A request that did not obtain the lock sleeps briefly for up to 2 seconds and checks the cache again. All 50 must receive the value. Also, in /root/sp/lock.out, write served=50.

A request that fails to obtain the lock must not simply fail. Have it sleep briefly and look at the cache again.

Prevent deadlock with a lock TTL

The lock key must have a TTL. In /root/sp/lockttl.txt, write lock_ttl=<초> (seconds), and it must be between 1 and 30 inclusive.

If the lock owner dies, nobody can get in. Give the lock itself a lifetime.

Protect others' locks with an ownership token

Release the lock only when the ownership token matches. In /root/sp/owner.out, write wrong_token_release=0 right_token_release=1. The source must contain a token comparison.

The original owner, waking up late, must not release a lock that another request took after it expired by TTL.

Spread simultaneous expirations with TTL jitter

With /root/sp/jitter.py, fill 100 keys with a base of 300 seconds and a jitter width of 60 seconds. In /root/sp/jitter.txt, write min_ttl=<n> max_ttl=<n> distinct=<n>, and distinct must be at least 20 and the difference between max and min at least 30.

Spread out the expiration times of keys filled at the same moment. Check the TTL distribution of the 100 keys.

Implement stale-while-revalidate

/root/sp/swr.py stores a logical expiration time along with the value, and even after expiration it returns the old value immediately while refreshing only once in the background. In /root/sp/swr.out, write served_from_stale=<n> origin_calls=<n>, and origin_calls must be 3 or less.

Even after expiration, give the old value immediately and refresh only once in the background. You can store the value and the expiration time separately.

Compare the origin call counts of the three approaches

In /root/sp/compare.md, write a markdown table. The row titles are three values, 무방비 (unprotected), 싱글플라이트 (single-flight), and stale-while-revalidate, and there must be a 원본호출 (origin calls) column.

Compare the unprotected version, the lock, and stale-while-revalidate under the same load. The table format and the row titles are the grading criteria.