When designing a system with millions of users or resources, we often use Redis caching to reduce database load. But what happens when requests keep looking for IDs that do not exist? Redis keeps returning cache misses, the database still checks every ID, and legitimate users can experience slower responses as query volume grows.
This is also a useful scenario to discuss in a system design interview: how do you avoid unnecessary queries when bots or attackers send large numbers of requests for nonexistent resource IDs? This article explores how Bloom filters in Redis screen these requests, how the workflow changes, and what the benefits and limitations look like through concrete examples.
1. Overview: Reject Nonexistent IDs Before Reading Data
A Bloom filter provides a lightweight screening step before data retrieval. When the filter is complete and synchronized, a negative result lets the application return “not found” immediately. A positive result continues to the cache and, when necessary, the database.
- Without a Bloom filter: nonexistent ID → Redis cache miss → database lookup → 404.
- With a Bloom filter: nonexistent ID → usually a negative filter result → 404, skipping the cached payload and database lookup.
- Benefit: fewer unnecessary queries, especially when bots or attackers keep requesting different nonexistent IDs.
A simple example: out of one million requests, suppose 500,000 look for nonexistent data. If the filter rejects all of them, the system avoids 500,000 cached-payload reads and 500,000 database queries. With a 1% false-positive rate on this group, the expected number avoided is 495,000 at each layer.
A Bloom filter hosted in Redis still requires a Redis membership check. These figures describe cached-payload reads and database queries skipped, rather than API requests disappearing or all Redis accesses being eliminated.
A Bloom filter returns either negative (definitely absent from the set loaded into the filter) or positive (possibly present, requiring further verification). A positive result can be a false positive. Use negative results to skip lookups only when the filter is complete and synchronized. If a new user exists in the database but has not been added to the filter, the application could incorrectly return 404.
For a closer look at the internal mechanism, read Bloom Filters Explained — System Design, which illustrates insertion, membership checks, and false positives.
2. Requests for Missing Data Still Consume Resources
Suppose you operate a service with 10 million users. A typical user lookup follows this path:
User lookup request → Redis cache → cache miss → database.
This works well for existing users. But if a client keeps sending IDs that do not exist, Redis keeps missing and the database still checks every request.
This is cache penetration : requests for nonexistent data pass through the cache and reach the database. It differs from a cache stampede, where many requests simultaneously fetch the same existing data after its cache entry expires.
An indexed SELECT may be fast. Tens of thousands of unnecessary SELECTs per second still consume connections, CPU, network bandwidth, and operating budget.
The question we want to answer before those lookups is: could this ID exist in the dataset?
3. How Attackers Exploit Cache Misses to Overload the Database
An attacker does not need access to the data to create load. They can repeatedly send requests containing nonexistent resource IDs that still match the format accepted by the API.
Without a Bloom filter: request a nonexistent ID → Redis cache miss → database query → no record → 404. Switch to another nonexistent ID, and the entire workflow repeats.
If the application does not cache “not found” results, each request can trigger a database query. Even with negative caching, constantly changing the ID makes previously cached results difficult to reuse.
The result can be a busy connection pool, higher database CPU usage, and longer waits for legitimate requests. The cache still serves valid data, but it does not stop requests for nonexistent IDs from reaching the database.
With a Bloom filter: request a nonexistent ID → check the filter in Redis → most checks return negative → return 404 immediately, without reading the cached payload or querying the database. Only positive results proceed.
This reduces database load caused by cache penetration. Application and Redis traffic remain, so rate limiting is still necessary. The configured false-positive rate also does not guarantee the same reduction for every attack pattern: repeatedly requesting an ID that produces a false positive can still bypass the filter. Negative caching and rate limits help address this case.
4. A Redis Cache Miss Does Not Mean the User Does Not Exist
Redis typically caches only part of the dataset. Keys can expire or be evicted. The database remains the source of truth.
The Bloom filter in this article therefore represents user IDs in the database , rather than just keys currently present in the cache.
- The application receives a request to look up a user by ID.
- If the filter is unavailable or cannot be trusted, use the normal cache → database workflow.
- If the filter is ready, check the ID using the Bloom filter in Redis.
- Negative: return “not found,” skipping the profile cache and database.
- Positive: read the profile cache; on a hit, return the user.
- Cache miss: query the database. If the user exists, update the cache and return the data. Otherwise, return “not found.”
Four scenarios illustrate the difference:
| Scenario | Bloom filter | Profile cache | Database | Response |
|---|---|---|---|---|
| User exists and is cached | Positive | Hit | Not queried | 200 |
| User exists, but cache entry expired | Positive | Miss | User found | 200, refresh cache |
| User does not exist | Usually negative | Not read | Not queried | 404 |
| User does not exist, but filter returns a false positive | Positive | Miss | User not found | 404 |
A false positive causes an extra lookup, but must never cause the system to return a user that does not exist.
5. Load Examples: How Many Database Queries Can You Avoid?
5.1. One Million Requests, Half for Nonexistent Data
Suppose the system receives 1,000,000 resource lookup requests :
- 500,000 requests look for existing resources.
- 500,000 requests look for nonexistent resources, using different IDs.
- The filter is complete and synchronized; there is no negative cache or other blocking layer.
- The normal workflow reads Redis cache first and queries the database on a miss.
For the 500,000 requests targeting nonexistent resources:
| Operation for nonexistent IDs | Without a Bloom filter | With a filter, all results negative | With a filter, 1% false positives |
|---|---|---|---|
| Bloom filter checks in Redis | 0 | 500,000 | 500,000 |
| Cached-payload reads in Redis | 500,000 | 0 | About 5,000 |
| Database queries after cache misses | 500,000 | 0 | About 5,000 |
| Reads avoided at each cache/database layer | 0 | 500,000 | About 495,000 |
The Bloom filter keeps nearly 500,000 requests out of the data retrieval workflow. With a 1% false-positive rate, it is expected to reject 495,000 requests: 49.5% of all incoming requests and 99% of requests for nonexistent data.
The 500,000 requests for existing resources still continue through data retrieval. Their database query count depends on the cache hit rate. For example, with a 90% cache hit rate, existing resources contribute another 50,000 database queries:
| Total database queries across one million requests | Query count |
|---|---|
| Without a Bloom filter | 500,000 + 50,000 = 550,000 |
| With a Bloom filter, 1% false positives | 5,000 + 50,000 = 55,000 |
| Queries avoided | 495,000 , a 90% reduction |
These are calculations under stated assumptions, rather than benchmark results. Since the filter lives in Redis, all one million requests still check it, and positive results also read the cached payload. The benefit is a substantial reduction in database queries and skipping cached-payload reads for negative results; it does not guarantee fewer total Redis commands.
5.2. An Example in Requests per Second
Suppose the API receives 50,000 requests per second:
- 80% target nonexistent users: 40,000 requests per second.
- 20% target existing users: 10,000 requests per second.
- Existing users have a 90% cache hit rate.
- The filter contains all user IDs and has a 1% false-positive rate.
Without a Bloom filter: 40,000 nonexistent-user requests plus 1,000 cache misses for existing users produce 41,000 database queries per second.
With a Bloom filter: 40,000 × 1% plus 1,000 produces an expected 1,400 database queries per second.
Under these assumptions, database queries drop by approximately 96.6%. This is an illustrative calculation. Repeated requests, ID distribution, cache hit rate, and filter synchronization all affect actual results.
With Redis's Bloom filter support, each request still accesses Redis for a membership check. The application must load the IDs and keep them synchronized; Redis does not automatically read the database to maintain this set.
6. Illustrated Use Cases
6.1. Profile APIs with Millions of Users
A community application has 10 million users. Alongside legitimate profile views, the API receives invalid links and ID-probing requests from bots.
Without a Bloom filter: every nonexistent ID causes a Redis cache miss followed by a database lookup that finds no user. With 10,000 requests per second targeting different nonexistent IDs, the database could receive 10,000 queries per second just to confirm their absence, assuming no other blocking layer.
With a Bloom filter: request → check the user ID set in Redis → return 404 on a negative result; otherwise read the cache and database as needed. If approximately 1% of these nonexistent-ID requests produce false positives, their expected database query count falls to about 100 per second.
Benefit: most unnecessary queries are rejected before reaching the database, reducing competition for resources with legitimate users. This is an illustrative calculation, rather than a guaranteed reduction for every workload.
For existing users, the effect differs:
| Example request | Without a filter | With a filter | Effect |
|---|---|---|---|
| Alex, ID 1001, profile cached | Cache hit → return profile | Filter positive → cache hit → return profile | Neither queries the database; the filter adds a check |
| Ben, ID 1002, cache entry expired | Cache miss → database → refresh cache | Filter positive → cache miss → database → refresh cache | A database read is still required for the existing user |
| ID 99999999 does not exist, filter negative | Cache miss → no database record → 404 | Filter negative → 404 | Avoids the database query and cached-payload read |
| Nonexistent ID producing a false positive | Cache miss → no database record → 404 | Filter positive → cache miss → no database record → 404 | No database query reduction for this request |
6.2. Resource Lookups: Posts, Products, and Files
A store has millions of products, or a publishing platform has millions of posts. An attacker repeatedly sends nonexistent IDs to the resource detail API.
Without a Bloom filter: product/post request → Redis cache miss → database ID lookup → no data → 404. When IDs constantly change, cached entries for existing resources do not reduce these queries.
With a Bloom filter: request → check the filter for the resource type → return 404 immediately on a negative result; otherwise continue to the cache and database. Each resource type has its own ID set, preventing a product filter from being used to check post IDs.
Benefit: fewer queries to check nonexistent resources, leaving database capacity for legitimate product and post retrieval. Existing resources that are not cached still require database reads. Deleted resources whose IDs remain in the filter may still pass through and require verification against the source of truth.
For files, the workflow is similar: stop on a negative result; on a positive result, look up metadata, check permissions, and retrieve the file from storage. The filter can reduce unnecessary metadata lookups, but it does not confirm that the file is still present in storage.
In a multi-tenant system, include the tenant in the membership key, such as tenant:42:product:123, to distinguish namespaces. A positive result only permits the lookup to continue; access control remains a separate requirement.
6.3. Checking Username Availability During Registration
An application lets users check username availability during registration. Users try new names, or bots submit large numbers of unused names.
Without a Bloom filter: each availability check consults an exact data store to determine whether the username exists, unless the result is already cached.
With a Bloom filter: normalize the username → check the registered-name set → skip the duplicate-check read on a negative result; on a positive result, query the database to distinguish an existing name from a false positive. Do not report that a name is taken based only on a positive result.
Benefit: fewer availability-check reads for unused names. Account creation still writes to the database; the filter does not reduce write costs or guarantee that the name remains available when the account is saved.
Two requests can still attempt to register the same name simultaneously. A database unique constraint must enforce uniqueness. A Bloom filter does not replace that constraint.
Apply consistent username normalization during insertion and lookup, including case handling, Unicode handling, and product-specific rules.
6.4. Checking Previously Crawled URLs or Processed Events
A crawler receives new URLs, or an event-processing system needs to know whether an event ID has already been handled.
Without a Bloom filter: before processing, the system reads its history store for every URL or event ID to check for duplicates.
With a Bloom filter: check the recorded-ID set → on a negative result, skip the history-check read and proceed to recording/processing; on a positive result, consult the exact store to confirm a duplicate. Recording must still handle concurrent requests correctly.
Benefit: fewer history reads when most URLs or events are new. If most have already been recorded, the filter usually returns positive and saves fewer reads. Recording and processing costs remain.
Discarding an event based solely on a positive result could lose a legitimate event because of a false positive. For payments or other workflows requiring exact handling, use idempotency keys and storage mechanisms with appropriate guarantees.
7. Considerations Before Production
7.1. Synchronizing New Users
Suppose the database has just committed user:2001, but the filter update is delayed. A request arriving during that window could incorrectly receive 404.
One way to reduce this window is to add the ID to the filter before the record becomes visible to readers. If the database write fails, the extra ID in the filter merely causes unnecessary lookups. However, updating the filter first does not resolve every issue: cached 404 responses, rollbacks, filter loss, and replica lag still need handling.
If updates are asynchronous through an outbox or CDC, provide a way to bypass the filter or directly check newly created data until synchronization completes. Monitoring lag helps detect problems, but does not itself guarantee the correctness of every negative result.
7.2. Initial Loading and Rebuilding
With 10 million users, read IDs in batches and build a new filter that does not yet serve traffic. Capture writes occurring during the scan, and switch to the new version only after loading and synchronization complete through a consistent process.
Do not enable negative-result blocking while the dataset is only partially loaded. Bypass the filter if its version, readiness, or completeness cannot be trusted.
7.3. Deleting Users
A standard Bloom filter does not support deleting an individual item by clearing its bits, because multiple IDs may share them. A deleted user can still produce a positive result, followed by a database lookup that finds no record.
Periodic rebuilding can remove old IDs. If frequent deletion is required, consider a structure that supports it and evaluate that structure's guarantees separately.
7.4. Negative Caching and Rate Limiting
Caching “not found” results with a short TTL reduces lookups for repeated IDs, including those producing false positives. Distinguish a negative cache entry from a cache miss, and invalidate it when the resource is created.
Bloom filters help with many different nonexistent IDs. Negative caching helps with repeated IDs. Rate limiting remains necessary because rejected requests still consume application resources.
7.5. Measuring Effectiveness
Track the negative-result rate, database query volume, latency, filter size, and update lag. Positive results followed by missing records in the source of truth can reflect deleted IDs or synchronization issues as well as false positives; do not automatically treat them all as pure filter false positives.
8. When Should You Use a Bloom Filter?
Consider a Bloom filter when the ID set is large, many lookups target nonexistent data, downstream lookups are costly, and the system can maintain a complete filter.
If most requests target existing users, the filter may simply add CPU work or an extra Redis round trip. Measure it against a realistic workload before deploying broadly.
In the API workflow, use the Bloom filter as a screening step: a trustworthy negative result lets you skip a lookup; a positive result still requires verification against an exact data source. The database determines whether the data exists, and the application determines whether the caller may access it.
I hope this article gives you more ideas for answering system design questions.
Top comments (0)