キャッシュペネトレーションを打ち破る：Redis BloomとCuckoo Filterに切り替えた理由

データベースが死んだ日：実世界でのキャッシュの悪夢

2021年のことですが、大規模なフラッシュセール中に中規模のECサイトのバックエンドを運用していました。すべてが安定しているように見えましたが、巨大なトラフィックの波が押し寄せました。しかし、それは熱心な買い物客ではありませんでした。標的型のボット攻撃だったのです。これらのボットは割引商品には目もくれず、存在しない何百万ものランダムな商品IDを、毎秒約5万リクエストという速度でクエリし続けました。

私たちのアーキテクチャは、最適なRedisキャッシング戦略に従った標準的なパターンを採用していました。アプリはRedisを確認し、何も見つからない場合（キャッシュミス）はPostgreSQLデータベースを叩きます。ボットは存在しないIDを推測していたため、Redisは一貫して null を返していました。悪意のあるリクエストのすべてがキャッシュをバイパスして、スロークエリのようにディスクにヒットしたのです。3分以内にデータベースのCPU使用率は100%に張り付き、サイトはクラッシュしました。これが、教科書通りのキャッシュペネトレーション（Cache Penetration）の定義です。

なぜ標準的なキャッシュは負荷がかかると失敗するのか

キャッシュは高速なミラーのようなものです。何が存在するかを保存するのには長けています。残念ながら、RAMの予算を使い果たさずに、何が*存在しない*かを教えることに関しては非常に不得手です。

私はまず「ネガティブキャッシュ」を試しました。存在しないIDに対して null 値を、有効期限（TTL）5分でRedisに保存したのです。しかし、これは惨事となりました。ボットは1 hourごとに1500万個もの新しいユニークな文字列を生成したからです。Redisのメモリ使用量は、ある日の午前中だけで2GBから14GBへと爆発的に増加しました。問題を解決するどころか、ボトルネックを移動させただけでした。データベースを煩わせる前にキーが存在するかどうかを確認する、しかも低コストな方法が必要だったのです。

確率的データ構造が救世主に

膨大なAWSの請求を回避しつつこれを解決するために、私は確率的データ構造である Bloom Filter（ブルームフィルタ） と Cuckoo Filter（クックーフィルタ） に目を向けました。これらのフィルタは生データを保存しません。代わりに、コンパクトな数学的指紋（フィンガープリント）を使用して、アイテムが「確実に存在しない」か「おそらく存在する」かを教えてくれます。

ブルームフィルタ：信頼できるベテラン

ブルームフィルタは、ビット配列と複数のハッシュ関数を使用します。アイテムを追加すると、フィルタはそれを複数回ハッシュし、特定のビットを 1 に反転させます。非常に軽量で、1%の誤り率であれば、100万個のアイテムをわずか1.2MBで表現できます。

• 確実に「いいえ（No）」: IDをチェックしてハッシュビットが1つでも 0 であれば、そのアイテムは100%存在しません。即座にリクエストを遮断できます。
• おそらく「はい（Yes）」: すべてのビットが 1 の場合、そのアイテムはデータベースにある可能性があります。異なるアイテムが同じビットを共有してしまう、わずかな確率（偽陽性：False Positive）が存在します。

クックーフィルタ：モダンな代替案

最終的に、私はクックーフィルタへと移行しました。これは「クックーハッシング」という手法を使用して指紋を保存します。最大の利点は何でしょうか？クックーフィルタは削除をサポートしている点です。データベースから製品を削除した場合、フィルタからも実際に削除できます。標準のブルームフィルタでは、たった1つのエントリを削除するために全体を消去してゼロから再構築する必要があります。

ブルーム vs クックー：武器の選択

適切なツールの選択は、データのライフサイクルに完全に依存します。アーキテクチャレビューの際に、私がこれらをどのように評価しているかを紹介します：

データセットが静的（ブロックされたIPアドレスのリストなど）であれば、ブルームフィルタが最適です。SKUを頻繁に追加・削除するのであれば、クックーフィルタが明らかに勝者です。

Redisでの実践的な実装

標準のRedisはこれらを標準サポートしていませんが、Redis Stack には RedisBloom モジュールが含まれています。複雑な計算はすべてモジュールが処理してくれます. Dockerコマンド1つでテストインスタンスを起動できます：

bash
docker run -d --name redis-stack -p 6379:6379 -p 8001:8001 redis/redis-stack:latest

ブルームフィルタのデプロイ

私は通常、誤り率1%、容量100万アイテムのフィルタを確保することから始めます：

bash
# BF.RESERVE {キー} {誤り率} {容量}
BF.RESERVE product_filter 0.01 1000000

アイテムの追加とチェックはマイクロ秒単位で完了します：

bash
# IDを追加
BF.ADD product_filter "prod_99"

# IDが存在するか確認
BF.EXISTS product_filter "prod_99"  # 1を返す（見つかった）
BF.EXISTS product_filter "random_bot_id" # 0を返す（ブロックする！）

クックーフィルタのデプロイ

クックーフィルタの構文もほぼ同じですが、DEL コマンドに注目してください：

bash
CF.RESERVE user_filter 1000000
CF.ADD user_filter "user_123"
CF.DEL user_filter "user_123" # これが「スーパーパワー」です。

データ準備のプロのコツ

何百万もの既存のIDをRedisに読み込むのは退屈な作業です。レガシーなSQLダンプから巨大なCSVをエクスポートし、インポート前にクレンジングしなければならないことがよくあります。単発のタスクのためにPythonスクリプトを書くのが面倒なときは、 toolcraft.app/ja/tools/data/csv-to-json を使います。ブラウザ内ですべてを処理してくれます。データがサードパーティのサーバーに送信されることを心配せずに、Redis投入用スクリプトのためにデータを素早くフォーマットできる便利な方法です。

最善の防御策を構築する

ロジックが鍵となります。PythonやNode.jsなど、どのバックエンドであっても、フィルタを「警備員」として扱ってください。フィルタが青信号を出さない限り、リクエストを玄関に通してはいけません：

python
def get_product(product_id):
    # 1. 警備員：ブルームフィルタを確認
    if not redis.execute_command('BF.EXISTS', 'product_filter', product_id):
        return None # ここで攻撃を阻止！

    # 2. 特急レーン：標準のRedisキャッシュを確認
    product = redis.get(f"product:{product_id}")
    if product:
        return product

    # 3. 倉庫：最終手段としてデータベースに問い合わせ
    product = db.query("SELECT * FROM products WHERE id = %s", (product_id,))
    if product:
        redis.set(f"product:{product_id}", product)
    return product

これを実装した後、次のボットの波が来たときにはデータベースの負荷が92%減少しました。これは、PostgreSQLをスケールさせる際にも役立つ、安定性に大きな利益をもたらすシンプルなアーキテクチャの転換です。システムを守るということは、常により多くのRAMを投入することではありません。時には、より優れたデータ構造が必要なだけなのです。