Bloom filter avec Redis : bloquer la pénétration du cache

1. Vue d’ensemble

La pénétration de cache se produit quand le client demande continuellement des clés inexistantes. Le cache n’a pas de données, donc chaque requête tombe dans la base de données. Cet article explique pourquoi Bloom filter est un bouclier bon marché et efficace pour cette situation. Vous apprendrez aussi comment l’implémenter sur Redis via Redisson dans une application Spring Boot 3.x.

Après la lecture, vous saurez comment choisir les paramètres du filter, charger les données initiales, intégrer le filter dans le flux de lecture et écrire des tests pour vérifier son comportement.

2. Qu’est-ce que la pénétration de cache ?

Supposons que vous ayez un ProductService utilisant le modèle cache-aside classique :

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); // requête DB
    fromDb.ifPresent(p -> bucket.set(p, Duration.ofMinutes(30)));
    return fromDb;
}

Ce flux est bon avec les données réelles. Maintenant, voyez ce qui se passe si quelqu’un envoie des milliers de requêtes avec id = -1, id = 999999999 ou des identifiants aléatoires :

• Redis retourne null car la clé n’existe pas.
• Le code descend à la DB, la DB ne trouve pas non plus.
• Rien n’est écrit au cache, la requête suivante répète exactement le même processus.

Il en résulte que le cache devient inutile et la DB assume toute la charge. Cela pourrait être un bug côté client, un crawler, ou une attaque intentionnelle.

Le premier remède courant est de mettre en cache la valeur vide (null object) avec un TTL court. Cette approche fonctionne bien si l’ensemble des mauvaises clés est petit. Elle échoue quand l’attaquant utilise des identifiants aléatoires : chaque id n’apparaît qu’une seule fois, et vous devez stocker des millions de clés vides sans sens. C’est là que Bloom filter brille.

3. Comment fonctionne Bloom filter

Bloom filter est une structure de données probabiliste composée de deux éléments :

• Un tableau de m bits, initialement tous à 0.
• k fonctions de hash, chacune mappant un élément à une position dans le tableau.

Ses deux opérations principales sont les suivantes :

• add(x) : calculer les k hash de x et mettre les bits correspondants à 1.
• contains(x) : calculer les k hash de x. Si au moins un bit est 0, x n’a certainement jamais été ajouté. Si tous les bits sont 1, x peut avoir été ajouté.

La propriété la plus importante est pas de faux négatifs, seulement des faux positifs. Quand le filter répond « n’existe pas », vous pouvez faire confiance absolument et renvoyer 404 directement sans toucher au cache ni à la DB. Quand le filter répond « peut exister », vous continuez le flux normal. Ce petit taux d’erreur est entièrement acceptable.

La taille du filter est calculée à partir du nombre d’éléments attendus n et du taux de faux positifs désiré p :

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

Par exemple avec n = 1_000_000 produits et p = 0.01 (1%) :

m ≈ 9_585_059 bits ≈ 1.14 MB
k ≈ 7 fonctions de hash

Seulement environ 1 MB de RAM sur Redis suffit pour protéger un million d’identifiants. Ce chiffre est beaucoup plus petit que de stocker les identifiants eux-mêmes dans un Set.

4. Configurer Redisson

Redisson fournit RBloomFilter, implémenté par un bitmap pur de Redis. Par conséquent, il fonctionne sur toutes les versions de Redis sans nécessiter de modules supplémentaires.

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

Ce starter lit automatiquement la configuration de connexion à partir des propriétés spring.data.redis.* :

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

Après cette étape, vous pouvez injecter un bean RedissonClient n’importe où dans l’application.

5. Initialiser le Bloom filter

Créons le filter comme un bean pour que l’application entière le partage :

@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) {
            // Filter existe déjà sur Redis, conserver l'ancienne configuration
            log.info("Bloom filter {} existe déjà, size={} bits, k={}",
                    PRODUCT_FILTER, filter.getSize(), filter.getHashIterations());
        }
        return filter;
    }

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

Le code ci-dessus fait ce qui suit :

• getBloomFilter(...) ne crée qu’un objet proxy sans rien écrire à Redis.
• tryInit(1_000_000L, 0.01) calcule m, k selon la formule à la section 3, puis sauvegarde la configuration dans un hash auxiliaire sur Redis. La méthode retourne false si le filter a déjà été initialisé, par exemple si une autre instance de l’application avait déjà tourné.
• getSize() et getHashIterations() vous disent combien de bits et combien de fonctions de hash le filter utilise réellement.

Avec les paramètres ci-dessus, le log affichera quelque chose comme :

Bloom filter bf:product:ids existe déjà, size=9585058 bits, k=7

Remarque : Quand le filter existe déjà, tryInit ne modifiera pas la configuration. Si vous changez expectedInsertions dans le code sans supprimer l’ancien filter, la nouvelle configuration sera silencieusement ignorée.

6. Charger les données initiales

Un filter vide répondra « n’existe pas » pour tous les identifiants, même ceux qui sont réels. Par conséquent, vous devez charger tous les identifiants existants avant d’activer la vérification.

@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; // déjà chargé par une autre instance
        }
        List<Long> ids = productRepository.findAllIds();
        ids.forEach(productIdFilter::add);
        log.info("Chargé {} identifiants dans le Bloom filter", ids.size());
    }

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

Ici, ProductRepository.findAllIds() récupère seulement la colonne id, par exemple @Query("select p.id from Product p") si vous utilisez JPA. count() retourne le nombre d’éléments estimé basé sur les bits actifs, ce qui est suffisant pour vérifier si le filter a déjà des données.

Avec des millions d’enregistrements, vous devriez lire par pages (pagination ou Stream avec fetch size) au lieu d’une List. Chaque commande add est un round-trip vers Redis, pensez donc à exécuter le warm-up via un job séparé au lieu de ralentir le démarrage de l’application.

7. Intégrer dans ProductService

Plaçons maintenant le filter avant le cache dans le flux de lecture :

@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(); // certainement n'existe pas
        }
        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 ici est un simple record record Product(Long id, String name, BigDecimal price). Examinons chaque étape :

• contains(id) retourne false signifie que l’id n’existe certainement pas dans le système. La requête est bloquée immédiatement avec un coût d’une commande Redis, zéro requête DB.
• Si le filter retourne true, la requête continue le flux cache-aside comme avant. Environ 1% des identifiants n’existant pas passent quand même à cause des faux positifs. La DB gère facilement ce petit volume.
• Dans create, le nouvel id est ajouté au filter. Si vous oubliez cette étape, le produit fraîchement créé « disparaît » pour l’utilisateur.

Concernant l’ordre d’écriture, si add s’exécute dans la transaction mais que le commit échoue, le filter contient un id inexistant. La conséquence est juste un faux positif supplémentaire, totalement inoffensif. Le cas inverse est plus préoccupant : si vous ne add qu’après le commit, il y aura un court laps de temps où le produit existe en DB mais le filter dit « n’existe pas ». C’est un faux négatif que vous créez vous-même. Par conséquent, privilégiez l’ajout au filter avant ou en même temps que l’écriture en DB.

8. Tester le comportement du filter

Pour tester sur Redis réel, ajoutez Testcontainers :

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

Le test ci-dessous vérifie deux propriétés essentielles : pas de faux négatifs, et le taux de faux positifs proche de la valeur configurée.

@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);
    }
}

Le premier test affirme que tous les ids ajoutés sont reconnus. Le deuxième test compte les ids jamais ajoutés que le filter prétend quand même exister. Avec p = 0.01, le taux mesuré fluctue généralement autour de 1%. Un seuil de 2% aide à éviter que le test soit flaky.

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

9. Alternative : les commandes Bloom natives de Redis

Si vous utilisez Redis Stack ou Redis 8+ (qui intègre déjà les types de données probabilistes), vous pouvez utiliser directement les commandes 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

La version native a quelques avantages. Chaque commande BF.EXISTS calcule le hash une seule fois côté serveur. BF.MADD permet d’ajouter plusieurs éléments en une seule commande. De plus, le filter peut se redimensionner automatiquement (scaling) s’il dépasse sa capacité. En revanche, RBloomFilter de Redisson fonctionne sur Redis « vanille », même sur les services managés qui ne supportent pas les modules. Choisissez en fonction de votre infrastructure.

10. Erreurs courantes et quand ne pas l’utiliser

Remarque : Bloom filter classique ne supporte pas la suppression. Désactiver un bit peut « perdre » un autre élément partageant ce bit, créant un faux négatif.

Quelques points à retenir :

• Suppression de données : quand un produit est supprimé, son id reste dans le filter. C’est sans danger car il devient juste un faux positif. Toutefois, si le taux de suppression est élevé, le filter devient « sale ». La solution est de reconstruire régulièrement le filter dans une nouvelle clé (par exemple bf:product:ids:v2) puis basculer avec RENAME. Une autre option est d’utiliser Cuckoo filter (CF.*), une structure qui supporte la suppression.
• Dépasser la capacité prévue : si vous avez réellement 5 millions d’éléments alors que le filter est déclaré pour 1 million, le taux de faux positifs augmentera énormément. Surveillez count() par rapport à getExpectedInsertions() et reconstruisez avant d’atteindre le seuil.
• Oublier le chargement ou chargement incomplet : un filter vide ou incomplet bloquera aussi les requêtes valides. Vous pouvez utiliser un feature flag pour n’activer la vérification qu’après le warm-up complet.
• Plusieurs chemins d’écriture : si les données sont créées via batch job, import CSV ou autre service, chaque chemin d’écriture doit mettre à jour le filter. Un moyen plus sûr est de mettre à jour via CDC ou events.
• Ne pas utiliser quand : l’ensemble des clés est petit (quelques milliers d’éléments, un Redis Set suffit), les clés ne peuvent pas être énumérées à l’avance (par exemple résultats de recherche libre), ou le système n’accepte pas le délai de synchronisation entre DB et filter.

Combiner Bloom filter avec un cache null TTL court est une défense multi-couches raisonnable. Bloom filter bloque la plupart des ids inutiles, tandis que null cache gère les rares faux positifs qui se font appeler à nouveau.

11. Conclusion

La pénétration de cache rend le cache inutile quand les requêtes ciblent des clés inexistantes. Bloom filter résout ce problème à très faible coût : environ 1 MB pour un million d’identifiants, une commande Redis par vérification, et aucun faux négatif.

Dans cet article, vous avez vu comment calculer la taille du filter et l’initialiser avec RBloomFilter de Redisson. Vous avez aussi chargé les données initiales, placé le filter avant le cache dans ProductService, et écrit des tests pour vérifier son comportement avec Testcontainers. Enfin, planifiez toujours la reconstruction périodique du filter et gardez tous les chemins d’écriture de données synchronisés avec lui.