Redis キャッシュのペネトレーション、ブレイクダウン、アバランチ
ペネトレーション（穿透）、ブレイクダウン（撃穿）、アバランチ（雪崩）は、Redis をキャッシュとして使うなら避けて通れない三種類の問題です。名前は似ていますが、原因も対策もそれぞれ異なります。この記事で一つずつ明確にしていきます。
キャッシュペネトレーション
キャッシュペネトレーションとは、ユーザーがリクエストしたデータがキャッシュに存在せず（つまりヒットせず）、同時にデータベースにも存在しないため、ユーザーがそのデータをリクエストするたびにデータベースへ問い合わせに行き、空を返すことになる現象を指します。
悪意のある攻撃者がシステムに存在しないデータをリクエストし続けると、短時間に大量のリクエストがデータベースに落ち、データベースの負荷が過大になり、最悪の場合データベースシステムを打ち倒してしまいます。
解決策
1）ブルームフィルター
ブルームフィルターは、実際には非常に長いバイナリベクトルと一連のランダムなマッピング関数であり、ある要素が集合に含まれるかどうかの検索に使えます。長所は空間効率とクエリ時間が一般的なアルゴリズムよりはるかに優れていること、短所は一定の誤判定率があり、削除が難しいことです。
ある要素が集合の中にあるかどうかを判定したい場合、一般的な考え方はすべての要素を保存しておき、比較によって確認するというものです。連結リストや木といったデータ構造はこの考え方です。しかし集合の要素が増えるにつれて、必要なストレージはどんどん大きくなり、検索速度もどんどん遅くなります（O(n) または O(log n)）。一方、ハッシュテーブルは Hash 関数によって要素をビット配列（Bit array）の一点にマッピングできます。こうすれば、その点が 1 かどうかを見るだけで、集合にその要素があるかどうかがわかります——これがブルームフィルターの基本的な考え方です。
2）空オブジェクトを返す
キャッシュがミスし、データベースを照会しても空だった場合、返される空オブジェクトをキャッシュに書き込んでおきます。こうすると次に同じ key がリクエストされたとき、キャッシュから直接空オブジェクトを返すため、リクエストはデータベースまで落ちません。空オブジェクトを溜め込みすぎないように、通常は空オブジェクトに有効期限を設定します。
この方法には二つの問題があります。
- 大量の key でペネトレーションが起きた場合、空オブジェクトのキャッシュがメモリを占有します。
- key が期限切れになるまでの間、キャッシュとデータベースのデータが一致しない状況が発生し得ます。
キャッシュブレイクダウン
あるホットな key が期限切れになった瞬間、大量のリクエストが同時にその key のデータにアクセスすることがあります。キャッシュがちょうど失効しているため、これらのリクエストは同時に永続化データベースへ問い合わせに行き、データをキャッシュに書き戻そうとします。その結果、データベースの負荷が瞬間的に過大になります。これがブレイクダウンです。
ここで ブレイクダウン と ペネトレーション の違いを理解しておきましょう。
ブレイクダウンは、ある一つの key が非常にホットで、大量のアクセスがその key に集中しているとき、key が失効した瞬間にすべてのリクエストがデータベースに殺到し、穴を一つ撃ち抜いてしまう、というものです。一方ペネトレーションは、アクセスされるデータが存在しないケースが中心で、大量のリクエストがどれも存在しないデータにアクセスしている状況です。
解決策
1）ミューテックスロックを使う
最初にアクセスしたスレッドだけにデータベース照会とキャッシュへの書き戻しを行わせ、他のスレッドは書き戻しの完了を待ってからキャッシュを読み直すようにします。
2）ホットデータを無期限に設定する
アクセスが極めて多いホットデータには有効期限を設定せず、代わりにビジネス側で非同期にキャッシュ内容を更新します。
キャッシュアバランチ
キャッシュアバランチとは、キャッシュ内の大量のホットな key が同時に有効期限を迎え、かつ照会されるデータ量が膨大なため、リクエストが直接データベースに落ち、データベースの負荷が過大になり、ダウンにまで至ることを指します。キャッシュブレイクダウンとの違いは、ブレイクダウンが同一データへの並行アクセスを指すのに対し、アバランチは異なるデータが軒並み期限切れになり、多くのデータが見つからないためにすべてがデータベースへ問い合わせに行く、という点です。
解決策
1）有効期限を分散させる
異なる有効期限を設定して、キャッシュの失効タイミングを均等に分布させます。通常は有効期限にランダム値を加えるか、有効期限を統一的に設計します。
2）ミューテックスロックをかける
キャッシュブレイクダウンの解決策と同じ考え方で、同時刻にキャッシュを構築するスレッドを一つだけにし、他のスレッドはブロックして順番を待ちます。
3）キャッシュを無期限にする
キャッシュブレイクダウンの解決策と同じ考え方で、キャッシュを物理的には永久に失効させず、非同期スレッドでキャッシュを更新します。
4）二層キャッシュ戦略
メインとバックアップの二層キャッシュを使います。
- メインキャッシュ：有効期限は経験則に基づいて設定し、主たる読み取り先のキャッシュとします。メインキャッシュが失効したらデータベースから最新値をロードします。
- バックアップキャッシュ：有効期限を長く設定し、ロックの取得に失敗したときに読むキャッシュとします。メインキャッシュを更新する際にはバックアップキャッシュも同期して更新する必要があります。
まとめ
三つの問題の本質はいずれも、リクエストがキャッシュを迂回して直接データベースを叩くことです。ペネトレーションは存在しないデータの照会、ブレイクダウンは単一のホット key の失効、アバランチは大量の key の同時失効です。対応の考え方にも共通点があります。キャッシュ層で無効なリクエストを食い止めるか（ブルームフィルター、空オブジェクト）、オリジンへ戻る並行数を制御するか（ミューテックスロック）、失効タイミングを制御可能にするか（期限の分散、無期限化、二層キャッシュ）です。実際に使うときは、データのホット度合いと整合性要求に応じて組み合わせて選べば十分です。
COMMENTS