RedisのBloom filterでキャッシュ貫通を防ぐ

1. 概要

キャッシュ貫通は、クライアントが継続的に存在しないキーをリクエストするときに発生します。キャッシュにはデータがないため、すべてのリクエストがデータベースに落ちてしまいます。この記事では、Bloom filterがこのシナリオに対して安価で効果的な盾である理由を説明します。また、Spring Boot 3.xアプリケーションでRedisson経由でこれを実装する方法も学びます。

読み終わったら、フィルタのパラメータを選択する方法、初期データをロードする方法、読み書きフローに統合する方法、その動作を検証するテストを書く方法がわかるようになります。

2. キャッシュ貫通とは？

よくあるcache-asideパターンを使用するProductServiceがあるとしましょう：

public Optional<Product> findById(long id) {
    RBucket<Product> bucket = redisson.getBucket("product:" + id, JsonJacksonCodec.INSTANCE);
    Product cached = bucket.get();
    if (cached != null) {
        return Optional.of(cached);
    }
    Optional<Product> fromDb = productRepository.findById(id); // DB クエリ
    fromDb.ifPresent(p -> bucket.set(p, Duration.ofMinutes(30)));
    return fromDb;
}

このフローは実在するデータで問題ありません。では、誰かがid = -1、id = 999999999、またはランダムなidを持つ数千のリクエストを送信したときに何が起こるかを見てみましょう：

• Redisはキーがないためnullを返します。
• コードはDBに落ちますが、DBでも見つかりません。
• キャッシュには何も書き込まれないため、次のリクエストは正確に同じプロセスを繰り返します。

結果として、キャッシュは役に立たなくなり、DBが全負荷を担います。これはクライアント側のバグ、クローラー、または意図的な攻撃の可能性があります。

一般的な最初の対策は、短いTTLで空の値（nullオブジェクト）をキャッシュすることです。このアプローチは不良キーのセットが小さい場合に効果的です。攻撃者がランダムなidを使用する場合、失敗します。各idは1回だけ出現し、数百万の無意味な空のキーを保存する必要があります。これがBloom filterが活躍する場面です。

3. Bloom filterはどのように動作するのか

Bloom filterは確率的データ構造で、2つの要素で構成されています：

• mビットの配列で、最初はすべて0です。
• k個のハッシュ関数。各関数は要素を配列内の位置にマップします。

2つの主な操作は次のとおりです：

• add(x): xのk個のハッシュを計算し、対応するビットを1に設定します。
• contains(x): xのk個のハッシュを計算します。いずれかのビットが0の場合、xは確実に追加されていません。すべてが1の場合、xは追加されている可能性があります。

最も重要な特性は、偽陰性がなく、偽陽性のみが存在することです。フィルタが「ない」と答えるとき、あなたは絶対に信じることができ、キャッシュやDBに触れずに即座に404を返すことができます。フィルタが「ある可能性があります」と答えるとき、あなたは通常のフローに進みます。この小さい誤検率は完全に許容できます。

フィルタサイズは予想要素数nと望ましい偽陽性率pから計算されます：

m = -n * ln(p) / (ln 2)^2
k = (m / n) * ln 2

n = 1_000_000製品とp = 0.01（1%）の例：

m ≈ 9_585_059 bit ≈ 1.14 MB
k ≈ 7 ハッシュ関数

わずか1 MB のRedis RAMで100万のidを保護するのに十分です。この数は、これらのid自体をSetに保存する場合よりもはるかに小さいです。

4. Redissonのセットアップ

RedissonはRBloomFilterを提供します。これはRedisの純粋なビットマップで実装されています。したがって、追加のモジュールを必要としないRedisのすべてのバージョンで動作します。

<dependency>
    <groupId>org.redisson</groupId>
    <artifactId>redisson-spring-boot-starter</artifactId>
    <version>3.45.1</version>
</dependency>

このスターターは、spring.data.redis.*プロパティから接続設定を自動的に読み込みます：

spring.data.redis.host=localhost
spring.data.redis.port=6379

この後、任意のbeanにRedissonClientをinjectできます。

5. Bloom filterの初期化

アプリケーション全体で共有するBeanとしてフィルタを作成しましょう：

@Configuration
public class BloomFilterConfig {

    public static final String PRODUCT_FILTER = "bf:product:ids";

    @Bean
    public RBloomFilter<Long> productIdFilter(RedissonClient redisson) {
        RBloomFilter<Long> filter = redisson.getBloomFilter(PRODUCT_FILTER);
        boolean created = filter.tryInit(1_000_000L, 0.01);
        if (!created) {
            // フィルタは既にRedisに存在し、古い設定を保持しています
            log.info("Bloom filter {} は既に存在します、size={} bit、k={}",
                    PRODUCT_FILTER, filter.getSize(), filter.getHashIterations());
        }
        return filter;
    }

    private static final Logger log = LoggerFactory.getLogger(BloomFilterConfig.class);
}

上のコードは以下を行います：

• getBloomFilter(...)はプロキシオブジェクトを作成するだけで、まだRedisに何も書き込みません。
• tryInit(1_000_000L, 0.01)はセクション3の公式に従ってmとkを計算し、設定をRedis上の補助ハッシュに保存します。フィルタが既に初期化されている場合、メソッドはfalseを返します。例えば、アプリケーションの別のインスタンスが既に実行されている場合です。
• getSize()とgetHashIterations()は、フィルタが実際に使用しているビット数とハッシュ関数の数を示します。

上記のパラメータでは、ログは次のように出力されます：

Bloom filter bf:product:ids は既に存在します、size=9585058 bit、k=7

注意： フィルタが既に存在する場合、tryInitは設定を変更しません。コード内でexpectedInsertionsを変更しても古いフィルタを削除しない場合、新しい設定は警告なく無視されます。

6. 初期データのロード

空のフィルタは、実在するidを含むすべてのidに対して「ない」と答えます。したがって、チェックを有効にする前に、すべての既存のidをロードする必要があります。

@Component
public class ProductFilterWarmUp implements ApplicationRunner {

    private final ProductRepository productRepository;
    private final RBloomFilter<Long> productIdFilter;

    public ProductFilterWarmUp(ProductRepository productRepository,
                               RBloomFilter<Long> productIdFilter) {
        this.productRepository = productRepository;
        this.productIdFilter = productIdFilter;
    }

    @Override
    public void run(ApplicationArguments args) {
        if (productIdFilter.count() > 0) {
            return; // 別のインスタンスによって既にロードされています
        }
        List<Long> ids = productRepository.findAllIds();
        ids.forEach(productIdFilter::add);
        log.info("Bloom filterに{}個のidをロードしました", ids.size());
    }

    private static final Logger log = LoggerFactory.getLogger(ProductFilterWarmUp.class);
}

ここで、ProductRepository.findAllIds()は単にidカラムを取得しています。例えば、JPAを使う場合は@Query("select p.id from Product p")です。count()は有効なビット数に基づいて要素数を推定するため、フィルタに既にデータがあるかどうかを確認するのに十分です。

数百万レコードの場合、List全体をロードするのではなくページング（またはfetch sizeを持つStream）でロードすべきです。addの各呼び出しはRedisへのラウンドトリップであるため、ウォームアップをアプリケーション起動を遅くするのではなく別のジョブで実行することを検討してください。

7. ProductServiceへの統合

次に、読み込みフローでフィルタをキャッシュの前に配置しましょう：

@Service
public class ProductService {

    private final RedissonClient redisson;
    private final RBloomFilter<Long> productIdFilter;
    private final ProductRepository productRepository;

    public ProductService(RedissonClient redisson,
                          RBloomFilter<Long> productIdFilter,
                          ProductRepository productRepository) {
        this.redisson = redisson;
        this.productIdFilter = productIdFilter;
        this.productRepository = productRepository;
    }

    public Optional<Product> findById(long id) {
        if (!productIdFilter.contains(id)) {
            return Optional.empty(); // 確実に存在しない
        }
        RBucket<Product> bucket = redisson.getBucket("product:" + id, JsonJacksonCodec.INSTANCE);
        Product cached = bucket.get();
        if (cached != null) {
            return Optional.of(cached);
        }
        Optional<Product> fromDb = productRepository.findById(id);
        fromDb.ifPresent(p -> bucket.set(p, Duration.ofMinutes(30)));
        return fromDb;
    }

    @Transactional
    public Product create(Product product) {
        Product saved = productRepository.save(product);
        productIdFilter.add(saved.id());
        return saved;
    }
}

ここでのProductは単純なレコードrecord Product(Long id, String name, BigDecimal price)です。各ステップを見てみましょう：

• contains(id)がfalseを返すということは、idが確実にシステムに存在しないということです。リクエストはRedisの1つのコマンドの代価で即座にブロックされ、DB クエリは消費されません。
• フィルタがtrueを返す場合、リクエストは通常のcache-asideフローを続けます。偽陽性のため、存在しないidの約1%がまだ通過します。この小さな量はDBが簡単に処理できます。
• createでは、新しいidがフィルタに追加されます。このステップを忘れると、新しく作成された製品はユーザーから「消えます」。

書き込みの順序についてのクイックノート：addがtransaction内で実行されても、commitが失敗した場合、フィルタは存在しないidを含みます。その結果はもう1つの偽陽性の追加であり、完全に無害です。逆の場合は心配になります。DBに既に製品がある場合でもフィルタが「ない」と返す時間がある場合は、偽陰性を自分で作成しています。したがって、フィルタに追加することをDB書き込み前または同時に優先してください。

8. フィルタの動作をテストする

Redisの実際のテストのため、Testcontainersを追加します：

<dependency>
    <groupId>org.testcontainers</groupId>
    <artifactId>junit-jupiter</artifactId>
    <version>1.20.4</version>
    <scope>test</scope>
</dependency>

以下のテストは2つのコアプロパティを検証します：偽陰性がないこと、および偽陽性率が設定された値に近いこと。

@Testcontainers
class ProductBloomFilterTest {

    @Container
    static GenericContainer<?> redis =
            new GenericContainer<>("redis:7.4-alpine").withExposedPorts(6379);

    static RedissonClient client;
    static RBloomFilter<Long> filter;

    @BeforeAll
    static void setUp() {
        Config config = new Config();
        config.useSingleServer()
              .setAddress("redis://" + redis.getHost() + ":" + redis.getMappedPort(6379));
        client = Redisson.create(config);

        filter = client.getBloomFilter("test:product:ids");
        filter.tryInit(5_000L, 0.01);
        LongStream.rangeClosed(1, 5_000).forEach(filter::add);
    }

    @AfterAll
    static void tearDown() {
        client.shutdown();
    }

    @Test
    void givenAddedIds_whenContains_thenAlwaysTrue() {
        boolean allPresent = LongStream.rangeClosed(1, 5_000).allMatch(filter::contains);

        assertThat(allPresent).isTrue();
    }

    @Test
    void givenUnknownIds_whenContains_thenFalsePositiveRateIsLow() {
        long falsePositives = LongStream.rangeClosed(5_001, 10_000)
                .filter(filter::contains)
                .count();

        double rate = falsePositives / 5_000.0;
        assertThat(rate).isLessThan(0.02);
    }
}

最初のテストは、追加されたすべてのidが認識されることを確認します。2番目のテストは、追加されたことのないidで、フィルタがまだ「ある可能性があります」と報告する数を数えます。p = 0.01では、測定された比率は通常1％前後で変動します。2％のしきい値はテストが不安定にならないようにします。

[INFO] Tests run: 2, Failures: 0, Errors: 0, Skipped: 0

9. 代替案：Redisのネイティブ Bloom コマンド

Redis StackまたはRedis 8以上を使用している場合（確率的データ型が統合されています）、BF.*コマンドを直接使用できます：

redis-cli BF.RESERVE bf:product:ids 0.01 1000000
redis-cli BF.MADD bf:product:ids 1 2 3
redis-cli BF.EXISTS bf:product:ids 2
redis-cli BF.EXISTS bf:product:ids 42

OK
1) (integer) 1
2) (integer) 1
3) (integer) 1
(integer) 1
(integer) 0

ネイティブバージョンにはいくつかの利点があります。BF.EXISTSの各コマンドは、サーバー側で一度だけハッシュを計算します。BF.MADDは1つのコマンドで複数の要素を追加できます。さらに、フィルタは容量を超えた場合に自動的にスケーリングできます。逆に、RedissonのRBloomFilterは、追加のモジュールをサポートしていないマネージドサービスなどの「プレーンな」Redisで動作します。インフラに応じて選択してください。

10. よくあるエラーと使用してはいけない場合

注意： 古典的なBloom filterはdelete操作をサポートしていません。ビットをオフにすると、同じビットを共有する別の要素が「失われ」、偽陰性が作成される可能性があります。

覚えておく必要があるいくつかのポイント：

• データ削除：製品が削除される場合、そのidはフィルタに残ります。これは安全で、単に偽陽性になるだけです。ただし、削除率が高い場合、フィルタは時間とともに「汚れ」ます。解決策は、定期的にフィルタを新しいキーに再構築する（例：bf:product:ids:v2）ことです。RENAMEを使用して切り替えます。別のオプションは、削除をサポートするCuckoo filter（CF.*）を使用することです。
• 予想容量を超える：予想100万要素であるが、実際には500万要素がある場合、偽陽性率は急増します。count()をgetExpectedInsertions()と比較して監視し、しきい値に達する前に再構築します。
• データのロード忘れまたは不完全：空またはデータが不足しているフィルタは、有効なリクエストもブロックします。ウォームアップが完了するまでチェックを有効にするだけのフィーチャーフラグを使用できます。
• 複数のデータ書き込みパス：バッチジョブ、CSV インポート、または別のサービスを介してデータが作成される場合、それらのすべてのパスがフィルタを更新する必要があります。より安全な方法は、CDCまたはイベントを介して更新することです。
• 使用しない場合：小さなキーセット（数千要素、Redis Setで十分）、事前にリストできないキー（例：自由形式の検索結果）、またはシステムがDBとフィルタ間の同期遅延を許容しない場合。

Bloom filterを短いTTLの空値キャッシュと組み合わせることは、合理的な多層防御です。Bloom filterはほとんどの不良idをブロックし、空キャッシュは繰り返し呼ばれる少数の偽陽性を処理します。

11. 結論

キャッシュ貫通は、リクエストが存在しないキーを狙うときにキャッシュを使えなくします。Bloom filterはこの問題を非常に低いコストで解決します：100万idで約1 MB、チェックあたり1つのRedisコマンド、および偽陰性がないことを保証します。

この記事では、フィルタサイズを計算し、RedissonRBloomFilterを使用して初期化する方法を見ました。初期データをロードし、ProductServiceでキャッシュの前にフィルタを配置し、Testcontainersでテストを書いて動作を検証しました。最後に、フィルタを定期的に再構築し、すべてのデータ書き込みパスを同期させることを計画してください。