Skip to content

Redis Bloom filter pattern

The Redis Bloom filter pattern is a design pattern used to mitigate the issue of Cache penetration (caching invalid data that does not exist in the backing database).^[600-developer-principle-bloomfilter.md]

Overview

A Bloom filter is a space-efficient probabilistic data structure that is used to test whether an element is a member of a set.^[600-developer-principle-bloomfilter.md] In the context of Redis, this pattern is typically implemented using Redis Bitmaps to simulate the behavior of a standard Bloom filter (such as the one found in Google's Guava library).^[600-developer-principle-bloomfilter.md]

Application

The primary function of this pattern is to serve as a "gatekeeper" for the cache layer.^[600-developer-principle-bloomfilter.md] Before a query attempts to fetch data from the database, the Bloom filter is checked.

  • If the filter indicates the item does not exist, the application can immediately return a result without querying the database, preventing unnecessary load.
  • If the filter indicates the item might exist, the application proceeds to check the cache and then the database.

While false positives are possible (indicating an item exists when it does not), false negatives are not.^[600-developer-principle-bloomfilter.md]

Implementation Notes

When implementing this pattern, especially in distributed environments, the underlying bitmap structure must be consistent.^[600-developer-principle-bloomfilter.md] Libraries like Guava provide a putAll method, which allows for the merging of separate filter instances (e.g., from different shards or batches of data) into a single filter.^[600-developer-principle-bloomfilter.md]

Sources

  • 600-developer-principle-bloomfilter.md
  • [[Cache Avalanche]]
  • [[Cache Breakdown]]
  • [[Bitmaps]]
  • [[Probabilistic Data Structures]]