無効化の順序が作る古い値

一言でいうと

キャッシュがDBと異なる値を返している時間は、「無効化したかどうか」よりも、読み取りと書き込みの操作がどの順序で割り込んだかで決まります。同じ戦略でも、順序が1つ違うだけで、数msだけ間違うこともあれば、TTLがなければ、次の書き込みが来るまで間違い続けます。

なぜ必要なのか

cache-asideでは、読み取りは「キャッシュを確認 → なければDBを読む → キャッシュに入れる」の3歩で、書き込みは「DBコミット + キャッシュ処理」の2歩です。歩と歩の間ごとに、別のリクエストの歩が割り込めます。もっとも多く引用される記録が、FacebookのScaling Memcache at Facebook(NSDI 2013)です。彼らは、書き込みの経路でキャッシュを更新せずに削除しますが、その理由を「削除は冪等だから」と記しています。

それでも問題は残ります。論文は、stale setを「Webサーバーがキャッシュに入れた値が、入れるべき最新の値ではない場合」と定義し、並行する更新が並べ替えられるときに生じると説明しています。解決策はleaseです。キャッシュミスのとき、memcachedがそのキーに結び付けられた64ビットのトークンを渡し、クライアントが値を入れるときにトークンを一緒に送り、その間にdeleteが来ると、トークンが無効になって、入れることが拒否されます。

パターンそのもの(cache-aside、無効化、スタンピード、TTLジッター、stale-while-revalidate)は、「Redisとキャッシュ」コースが扱います。このモジュールは、その下の層、割り込みの順序を決定的に再現して、古い値の読み取りを数える場所です。

どう動くのか

代表的な割り込みが3つあります(Rは読み取り、Wは書き込み)。

名前	順序	残るもの
遅れて到着した読み取りのset	Rがミス → RがDBからv0を読む … Wがコミット(v1) → Wが削除 … Rがv0をset	削除より遅く入ってきたv0
削除が先、コミットが後	Wが削除 … Rがミス → v0を読む → v0をset … Wがコミット(v1)	コミット前に再び埋められたv0
2つの書き込みの逆順のset	W1がコミット(v1) … W2がコミット(v2) → v2をset … W1がv1をset	遅れて到着したv1

最初の行は、「書き込み後の削除」でも防げません。遅延二重削除(削除 → コミット → しばらく後にもう一度削除)は、遅れたsetが2回目の削除より先に到着するときにだけ防げます。待つ時間が読み取りの遅延より短ければ、意味がありません。ところが、読み取り経路の最悪の遅延(GCの停止、リトライ、遅いネットワーク)は、普段の指標の中央値には表れないので、この戦略は、たいてい問題なく動いていて、まれに崩れます。2つ目の行が、「削除してから書き込む」が安全でない理由です。削除とコミットの間の窓に、読み取りが古い値を再び埋めます。

バージョン比較(CAS): キャッシュに値と一緒にDBのバージョンを入れ、「今キャッシュにあるバージョンより厳密に大きいときだけ上書きする」をキャッシュの中でアトミックに確認すれば、遅れて到着した古いバージョンが、新しいバージョンを上書きできません。Redisのトランザクションのドキュメントは、WATCHでcheck-and-setを提供すると記しています。監視したキーがEXECの前に変わると、トランザクション全体が中止され、nullが返ります。8.4からは、文字列キーに対して、SETのIFEQのような比較オプションもあります。memcacheのleaseも同じ発想で、論文はload-link/store-conditionalになぞらえています。比較の方向を逆に書くと、防ごうとしたことがそのまま起きます。

TTLは上限だが、コミットが基準ではない: TTLは、キャッシュに入れた瞬間から数えます。古い値が遅れて入ってくると、その値は、入ってきた時刻からTTLの間、生き続けます。そのため、古さの上限は、TTLではなく「遅れたsetの遅延 + TTL」です。TTLがなければ、割り込んだ古い値は、次の書き込みが来るまで残ります。Amazon Builders' Libraryのキャッシュの記事も、TTLは、クライアントがどれだけ古いデータを許容できるかと、データがどれだけ静的かで選ぶと記しています。

何を測るのか: このモジュールは、古さをコミット時刻を基準に定義します。読み取りが終わった時刻 − その読み取りが返したバージョンを置き換えたコミットの時刻。書き込みを開始した時刻から測ると、コミット前の時間が混ざりますが、その間はDBも古い値だったので、キャッシュが嘘をついたわけではありません。

現場での姿

同じ論文は、leaseの2つ目の用途としてthundering herdの緩和を挙げ、この問題に弱いキーで、DB問い合わせのピークが毎秒17Kから1.3Kに減ったと報告しています。スタンピードの話は、「Redisとキャッシュ」コースにつながります。キャッシュの無効化をイベントとして流す設計(アウトボックス)は「マイクロサービスアーキテクチャ」コースが、メッセージが2回届いたり順序が入れ替わったりする場面は「注文が二度届き、一度は消えた」コースが扱います。ラボの5つのシナリオは、上の表の順序を1つずつ再現するように、時刻と遅延を手で選んだもので、採点ツールが使う隠しシナリオは、同じルールでランダムに混ぜたものです。どちらであっても、ここで投げる問いは同じです。この順序で、キャッシュはどれくらいの間、間違っていたのか。そして、自分で直るのか。

次のラボですること

決定的なシミュレーターに、書き込みと読み取りの戦略をジェネレーターとして差し込みます。5つのシナリオで、6つの戦略の古い読み取りの数と最大の古さを測り、永遠に直らない組み合わせを見分けたあと、数字で戦略を1つ選びます。