キャッシュスタンピードを防ぐ

目標

キャッシュスタンピードを実際に起こして、原本の呼び出しの急増を目で確認し、ロックとジッターとstale-while-revalidateをそれぞれ付けて、防御の効果を数字で比較します。

なぜ重要なのか

スタンピードは、キャッシュがうまく働いているときにだけ起きる事故です。人気のキーほど危険だという逆説のためです。毎秒数千回読まれていたキーが期限切れになるその一瞬に、数千のリクエストが同時にミスを経験し、すべてが原本に殺到します。1つで十分だったはずの取得が数千になり、原本が押しつぶされるとさらに多くのミスが出て、連鎖的に崩れます。このラボで特に見落としやすいのが、ステップ5です。ロックにTTLだけをかけて所有権トークンを置かないと、TTLで期限切れになったあとに別のリクエストが取ったロックを、遅れて目を覚ました元の所有者が解放してしまいます。すると2つのリクエストが同時にクリティカルセクションに入ります。分散ロックを自分で作るときに最もよく抜け落ちる部分で、そのため1つのステップを丸ごと割り当てました。

ステップ

/opt/app/slowdb.py(8151)を起動し、/root/sp/naive.pyで人気のキーを消した直後に、同時に50件をリクエストします。/root/sp/naive.outにconcurrency=50 origin_calls=<n>を書き、nは20以上である必要があります。
/root/sp/lock.pyは、ミスのときにSET lock:<키> <토큰> NX EX 5でロックを取ったリクエストだけが原本に行きます(プレースホルダーはキーとトークンです)。同じ条件で/root/sp/lock.outにconcurrency=50 origin_calls=<n>を書き、nは3以下である必要があります。
ロックを取れなかったリクエストは、最大2秒のあいだ短くスリープしながら、キャッシュを見直します。50件すべてが値を受け取る必要があります。/root/sp/lock.outにserved=50も一緒に書きます。
ロックキーにTTLがかかっている必要があります。/root/sp/lockttl.txtにlock_ttl=<초>を書き(プレースホルダーは秒数です)、1以上30以下である必要があります。
ロックの解放は、所有権トークンが一致するときだけ行います。/root/sp/owner.outにwrong_token_release=0 right_token_release=1を書きます。ソースにトークンの比較がある必要があります。
/root/sp/jitter.pyで、キー100個をbase 300秒、幅60秒のジッターで埋めます。/root/sp/jitter.txtにmin_ttl=<n> max_ttl=<n> distinct=<n>を書き、distinctは20以上、maxとminの差は30以上である必要があります。
/root/sp/swr.pyは、値と一緒に論理的な期限切れ時刻を保存し、期限切れ後も古い値を即座に返しながら、バックグラウンドで1回だけ更新します。/root/sp/swr.outにserved_from_stale=<n> origin_calls=<n>を書き、origin_callsは3以下である必要があります。
/root/sp/compare.mdにMarkdownの表を書きます。行の見出しは무방비、싱글플라이트、stale-while-revalidateの3つで(韓国語の2語は、順に「無防備」と「シングルフライト」を意味します)、원본호출列(韓国語で「原本呼び出し」を意味する語です)がある必要があります。

参考

アトミックなロック: SET lock:key <uuid> NX EX 5。戻りがOKなら取得です。
安全な解放は、値を比較してから削除する必要があり、この2つもアトミックであって初めて完全です(Luaスクリプト)。
同時リクエスト: for i in $(seq 50); do curl -s ... & done; wait
よくある間違い1は、ロックの待機者をそのまま失敗させることです。ユーザーの半分がエラーを見ます。
よくある間違い2は、ロックの解放を無条件にDELで行うことです。他人のロックを解放してしまうことがあります。

スタンピードを再現する

/opt/app/slowdb.py(8151)を起動し、/root/sp/naive.pyで人気のキーを消した直後に、同時に50件をリクエストしてください。/root/sp/naive.outにconcurrency=50 origin_calls=<n>を書き、nは20以上である必要があります。

人気のキーを消した直後に、同時リクエストを浴びせれば済みます。原本の取得数が、同時リクエスト数だけ増えます。

シングルフライトのロックをかける

/root/sp/lock.pyは、ミスのときにSET lock:<키> <토큰> NX EX 5でロックを取ったリクエストだけが原本に行くようにしてください(プレースホルダーはキーとトークンです)。同じ条件で/root/sp/lock.outにconcurrency=50 origin_calls=<n>を書き、nは3以下である必要があります。

ミスのとき、最初のリクエストだけが原本に行くようにします。ロックの取得はアトミックである必要があります。

ロックの待機者が値を受け取れるようにする

ロックを取れなかったリクエストは、最大2秒のあいだ短くスリープしながら、キャッシュを見直してください。50件すべてが値を受け取る必要があります。/root/sp/lock.outにserved=50も一緒に書きます。

ロックを取れなかったリクエストが、そのまま失敗してはいけません。短くスリープしながら、キャッシュを見直すようにしてください。

ロックのTTLでデッドロックを防ぐ

ロックキーにTTLがかかっている必要があります。/root/sp/lockttl.txtにlock_ttl=<초>を書き(プレースホルダーは秒数です)、1以上30以下にしてください。

ロックの所有者が死ぬと、誰も入れません。ロック自体に寿命を与えてください。

所有権トークンで他人のロックを守る

ロックの解放は、所有権トークンが一致するときだけ行ってください。/root/sp/owner.outにwrong_token_release=0 right_token_release=1を書きます。ソースにトークンの比較がある必要があります。

TTLで期限切れになったあとに別のリクエストが取ったロックを、遅れて目を覚ました元の所有者が解放してはいけません。

TTLのジッターで同時の期限切れを散らす

/root/sp/jitter.pyで、キー100個をbase 300秒、幅60秒のジッターで埋めてください。/root/sp/jitter.txtにmin_ttl=<n> max_ttl=<n> distinct=<n>を書き、distinctは20以上、maxとminの差は30以上である必要があります。

同じ瞬間に埋めたキーの期限切れの時刻を散らします。100個のキーのTTLの分布を確認してみてください。

stale-while-revalidateを実装する

/root/sp/swr.pyは、値と一緒に論理的な期限切れ時刻を保存し、期限切れ後も古い値を即座に返しながら、バックグラウンドで1回だけ更新してください。/root/sp/swr.outにserved_from_stale=<n> origin_calls=<n>を書き、origin_callsは3以下である必要があります。

期限切れになっても古い値をすぐ渡し、裏で1回だけ更新します。値と期限切れ時刻を別々に保存すればよいです。

3つの方式の原本呼び出し数を比較する

/root/sp/compare.mdにMarkdownの表を書いてください。行の見出しは무방비、싱글플라이트、stale-while-revalidateの3つで(韓国語の2語は、順に「無防備」と「シングルフライト」を意味します)、원본호출列(韓国語で「原本呼び出し」を意味する語です)が必要です。

無防備、ロック、stale-while-revalidateを、同じ負荷で比較します。表の形式と行の見出しが採点基準です。