Cache Stampede Problem とは
Cache Stampede Problem = キャッシュ失効時に大量の同時リクエストがオリジン（DB等）へ殺到し、過負荷になる問題。
TODO: Cache Stampede vs Thundering Herd
解決策(1) ❌ Distributed Lock
Not the best default.
クライアントはキャッシュミス時に、DBを叩きにいく前に、Distributed Lock のロックを取得しようとする。
- もしロックを取れれば、DBを叩き値を取得して、それをRedisに収納し、ロックを解除する。
- もしロックを取れなければ、リトライする。
問題点は、クライアントが直列に処理を待つ必要があり、timeout が発生しうること。
解決策(2) ⭕️ Background Refresh Processes
= TTLを無限（あるいは非常に長く）にし、背後のプロセスが非同期で値を上書きし続ける手法。
重い集計などでキャッシュの更新に数秒以上かかることがある場合には、効果的である。
The cost is infrastructure complexity and wasted work refreshing data that might not be requested, but for your most popular content, this insurance is worthwhile.
解決策(3) ⭕️ Probabilistic Early Refresh
それぞれのクライアントは、キャッシュの値を取得した際に、そのキーのTTLの残り時間を見る。
クライアントは、この残り時間に応じた確率で「オリジンのデータを取得してキャッシュの値を上書き」する。
この確率は残り時間が短いほど高くなる。
解決策(4) ⭕️ Single Flight Pattern
= in-memory request coalescing
= 同一マシンにおいて、最初の1クライアントだけがDBへリクエストを投げる。それ以降のクライアントはそのPromiseの結果を待つ。
これに Distributed Lock を組み合わせれば、複数マシンで同時に１リクエストが実現できるが、そこまでしなくていい。
Code Snippet
# Request coalescing pattern
class CoalescingCache:
def __init__(self):
self.inflight = {} # key -> Future
async def get(self, key):
# Check if another request is already fetching this key
if key in self.inflight:
return await self.inflight[key]
# No inflight request, we'll fetch it
future = asyncio.Future()
self.inflight[key] = future
try:
value = await fetch_from_backend(key)
future.set_result(value)
return value
finally:
del self.inflight[key]
番外編: Bulk Expiration Problem -> TTL Jitter
複数のキーのキャッシュが一斉にTTLを迎え、リクエストが一斉にDBに向かう問題。
つまりこれは、ホットキー単体ではなく、キャッシュ全体として発生する。
例えば、一時に大量のアイテムをバルクインサートしたり、毎日午前0時にキャッシュを一斉クリアするようなバッチがある場合に発生する。
Jitterを入れる際は、ベースのTTL（例: 24時間）に対して、ランダムな数分〜数時間（例:10%）のノイズを加える。