三つの書き込み戦略とスタンピード

一言でいうと

読み取り戦略と書き込み戦略は、別々の軸です。そして、人気のあるキーほど、期限切れの瞬間が危険になるという逆説が、スタンピードの核心です。

なぜ必要なのか

キャッシュパターンの話をするとき、人々が混ぜて使う3つの名前があります。cache-aside、write-through、write-behindです。これらは対立する選択肢ではなく、別々の問いに対する答えです。最初のものは、読み取りを誰が埋めるのかに対する答えで、あとの2つは、書き込みをどう伝播するのかに対する答えです。

cache-asideは、アプリケーションがキャッシュを直接管理します。読むときはキャッシュを見て、なければ原本から読んでキャッシュに入れます。書くときは原本を更新して、キャッシュを削除します。更新ではなく削除だという点が重要です。2つの書き込みがすれ違うとキャッシュに古い値が残ることがありますが、削除にはそのリスクがありません。

write-throughは、書き込みがキャッシュと原本を同時に更新します。キャッシュが常に最新なので、読み取りがいつも速いです。その代わり書き込みが遅くなり、しばらく読まれないデータまでキャッシュに埋めて、領域を無駄にします。

write-behindは、キャッシュにだけ書き、原本への反映をあとでバッチで行います。書き込みが非常に速く、複数の書き込みをまとめられますが、反映の前にキャッシュが落ちるとデータが消えます。消失に耐えられるか、別の耐久性の仕組みがあるときだけ使います。

どう動くのか

3つの戦略を1つの表にまとめると、こうなります。

戦略	書き込み速度	読み取りの鮮度	消失リスク	代表的な状況
cache-aside	普通	ミス後に最新	低い	汎用、読み取り中心
write-through	遅い	常に最新	低い	鮮度が重要
write-behind	非常に速い	常に最新(キャッシュ基準)	高い	書き込みの急増、消失を許容

そして、キャッシュで最も悪名高い落とし穴が、スタンピードです。毎秒数千回読まれていた人気のキーが期限切れになるその一瞬に、数千のリクエストが同時にミスを経験し、すべてが原本に殺到して同じ値を再計算します。1つで十分だったはずの取得が数千に膨れ上がり、原本が押しつぶされます。最悪の場合、原本が落ち、さらに多くのミスが出て、連鎖的に崩れます。

逆説はこうです。人気のある項目ほど危険なのです。よく読まれる値ほど、期限切れの瞬間の同時ミスが大きいからです。

対策は4つです。1つ目はロック、またはシングルフライトです。ミスのとき最初のリクエストだけが原本を取得し、残りは待ちます。2つ目はTTLのジッターです。期限切れの時点を散らします。3つ目はstale-while-revalidateです。期限切れになっても古い値をすぐ返し、バックグラウンドで1回だけ更新します。4つ目は確率的な早期期限切れです。期限切れが近づくほど、高い確率で先に更新します。

実務では組み合わせます。ジッターで期限切れを散らし、stale-while-revalidateで待ちをなくし、ロックで更新を1つにまとめます。

現場での姿

ロックを使うときに、必ず一緒に気をつけるべきことが2つあります。ロックにTTLをかけて、所有者が死んでも解放されるようにすること、そして所有権トークンを置いて、他人のロックを誤って解放しないようにすることです。後者を忘れると、AのロックがTTLで期限切れになったあとにBがロックを取ったのに、遅れて目を覚ましたAがBのロックを解放してしまうことが起きます。

無効化をどう設計するか

キャッシュで最も難しい問題は埋めることではなく、いつ捨てるかを決めることです。方法は3つで、それぞれ負担する複雑さが違います。

時間で捨てる(TTL)。 最も単純で、ほとんどの場合に十分です。「どれだけ古い値まで見せてよいか」を決めれば、それがそのままTTLです。ただしこの問いは技術ではなく業務の判断なので、開発者が1人で決めて済ませると、あとで「なぜいま変えたものが見えないのですか」になります。

変わったときに消す。 原本を直すコードが、関連するキャッシュキーも一緒に消します。鮮度はよくなりますが、そのキーをすべて知っている必要があることが問題です。商品が1つ変わると、商品詳細、一覧、検索結果、おすすめ一覧がすべて古くなりますが、コードのあちこちに散らばったこの関係を漏らさずに維持するのは難しいです。

バージョンで丸ごと無効化する。 キーにバージョン番号を入れ、何かが変わったらその番号を上げます。古いキーは誰も探さなくなり、TTLで自然に消えます。個々のキーを追跡しなくてよいのではるかに堅牢ですが、一度にあまりに多くのものが無効になるので、その直後にミスが集中します。前に見たスタンピードが、まさにこのときに起きます。

実務では、たいていTTLを土台に敷き、本当に即座に反映されるべきものだけを選んで、削除を加えます。 すべてに削除を付けようとすると維持できず、すべてをTTLだけにすると重要な変更が遅れて見えます。どのデータがどちらなのかは、業務の担当者と一緒に決めることで、その判断を表にして残しておけば、あとからキャッシュ関連の事故の半分がなくなります。

最後に、キャッシュがなくてもサービスが動く必要があります。 キャッシュを丸ごと空にしたときに、原本がその負荷に耐えられないなら、それはキャッシュではなく、原本の一部になったということです。この状態ではキャッシュの障害がそのままサービスの障害になるので、少なくとも原本がどこまで耐えられるかは知っておく必要があります。

次のラボですること

遅い原本を相手にcache-asideを実装してヒット率を測り、バージョンキーで全体の無効化をやってみます。そのあと別のラボで、スタンピードを実際に起こし、4つの防御を1つずつ付けて、原本の呼び出し回数を数字で比較します。