Application of Bloom Filters in Caching Systems

Bloom filters play an important role in caching systems, primarily used to solve the "cache penetration" problem. Let's first understand the problem itself, then delve into the application solutions of Bloom filters.

1. Problem Background: Cache Penetration

In a typical caching system (such as Redis + backend database), when an application needs to query a piece of data (e.g., via a key), the standard process is as follows:

1. First, query the cache. If the data exists in the cache (a cache hit), return it directly.
2. If the data does not exist in the cache (a cache miss), query the backend database.
3. After retrieving the data from the database, write it into the cache so that subsequent requests can hit the cache, and then return the data.

"Cache penetration" refers to querying data that does not exist at all. Since this data also doesn't exist in the database, each query bypasses the cache and goes directly to the database. If there are malicious attackers or program bugs that continuously and with high concurrency request large amounts of non-existent data, it can impose massive and unnecessary pressure on the backend database, potentially even overwhelming it.

2. The Solution with Bloom Filters

A Bloom filter can serve as an efficient "pre-filter" to quickly determine whether a piece of data definitely does not exist in the system.

1. Design Scheme

• Initialization: When the system starts, pre-load all keys of existing valid data (e.g., all primary keys in the database) into a Bloom filter.
• Query Process: When a query request arrives, the process changes to:
  • Step One: Query the Bloom filter using the request's key.
  • Step Two: If the Bloom filter returns "definitely does not exist", we can be sure this key is invalid. The system immediately returns a "data does not exist" result without querying the cache or database. This step is key to defending against cache penetration.
  • Step Three: If the Bloom filter returns "may exist", continue with the standard cache query process (query the cache first, and if it's a miss, query the database).

2. Workflow Example

Assume we have a user query system where user_id is the key.

• Scenario A: Requesting a legally existing user_id=123

  1. Query the Bloom filter. Since 123 was added during initialization, the filter returns "may exist".
  2. Query the cache, get a hit, and directly return the user data.

• Scenario B: Requesting a non-existent user_id=999 (malicious attack)

  1. Query the Bloom filter. Since 999 was never added, the filter inevitably returns "definitely does not exist".
  2. The system immediately returns "user does not exist". The request is intercepted at the Bloom filter layer, generating no pressure on the cache or database.

• Scenario C: Requesting a non-existent user_id=456 (but a false positive occurs)

  1. Query the Bloom filter. Due to the small false positive rate of Bloom filters, it incorrectly returns "may exist".
  2. The system continues to query the cache, resulting in a miss.
  3. The system queries the database, and the database confirms the user does not exist.
  4. The system returns "user does not exist". Note: Typically, we would not add this non-existent key=456 to the Bloom filter, as it would increase the false positive rate. Although this request ultimately reaches the database, the number of such requests is minimal (controlled by the false positive rate), making the pressure on the database acceptable.

3. Advantages and Considerations of the Solution

Advantages:

• Extremely Space-Efficient: Bloom filters use a bit array and multiple hash functions, requiring far less memory than a hash table or set storing all keys.
• Extremely Query-Efficient: Query time is only O(k) (where k is the number of hash functions), which is constant time.

Considerations and Optimizations:

1. False Positive Rate: This is the core trade-off. We need to calculate the required bit array size and number of hash functions based on the business's acceptable false positive rate (e.g., 1%) and the estimated number of elements to be stored. A lower false positive rate requires a larger bit array.
2. Deletion Not Supported: Standard Bloom filters do not support delete operations. Because deleting a key (setting its corresponding bits from 1 to 0) might affect other keys that are also mapped to those bits. If data in the caching system needs to be deleted (e.g., user deregistration), consider using a Counting Bloom Filter, which uses counters instead of bits but occupies more space.
3. Data Synchronization Issue: When new valid data is inserted into the backend database (e.g., new user registration), the key of the new data needs to be synchronized to the Bloom filter in real-time. Otherwise, the first query for the new data would be falsely judged as "non-existent" and be intercepted. This adds complexity to the system.
4. Initialization Warm-up: The system needs to warm up a large amount of data into the Bloom filter upon startup, which can be a time-consuming operation.

Summary: Through its "definitely does not exist" property, the Bloom filter provides an efficient, low-cost protective shield for caching systems, perfectly solving the tricky problem of cache penetration. In practical applications (such as in Redis, which can be self-implemented using SETBIT and GETBIT commands or via the RedisBloom module), parameters need to be carefully tuned according to business characteristics to achieve the best balance between space, time, and false positive rate.