When a lookup service puts a bloom filter of existing IDs in front of its cache, how must creates and deletes update the filter?

## What the guard does A **bloom filter** is a compact probabilistic set. For this use you only need its contract, not its internals: - **"Definitely absent"**: the ID was never added. This answer is always right. - **"Possibly present"**: the ID was probably added, but a small fraction of never-added IDs also get this answer (**false positives**). A lookup service that suffers **cache penetration** (floods of requests for IDs that have no row) can load every existing ID into such a filter and check it first. "Definitely absent" requests are rejected with a not-found response and never touch the cache or database. "Possibly present" requests continue down the normal cache-aside path. The guarantee rests entirely on one condition: **every ID that exists has been added**. Creates and deletes are where that condition is kept or broken. ## The two directions of error | Filter says | Truth | Outcome | Severity | |---|---|---|---| | Possibly present | Never existed | Request passes through to cache and database | Efficiency only | | Possibly present | Deleted | Request passes through; a negative entry can absorb repeats | Efficiency only | | Definitely absent | Exists but was never added | Real item rejected as not found | Correctness bug | The design rule follows from the table. Errors that let traffic *through* are acceptable and can be tuned. An error that *rejects a real item* must be made impossible. ## Creates: the direction that breaks correctness - **Order.** Add the ID to the filter **before** the item becomes readable, or in the same step. An item that is visible in the database but missing from the filter is rejected for as long as the gap lasts. - **Every copy.** If each application instance keeps its own in-process filter, a create on one instance must reach all the others. A shared filter in a central store avoids this at the cost of a network call per check. - **Startup.** A new instance must load a complete filter before using it. Until then it should skip the guard. - **Failed creates.** Adding an ID and then failing the insert is harmless: it only leaves one extra false "possibly present". - **Fail open.** If the filter is not loaded or its store is unreachable, bypass it. Failing closed would turn a filter outage into rejecting every request. ## Deletes: the direction that only costs efficiency A **standard** bloom filter supports adding but not removing. When an item is deleted, its ID keeps answering "possibly present", so requests for it go through to the cache and database like any other miss. That is still correct, and a short-lived negative entry can absorb repeated requests for the deleted ID. Over time, deleted IDs pile up in the filter. The filter carries more set members than there are live items, so more nonexistent IDs pass as false positives and the guard slowly loses its value. Two remedies: 1. **Periodic rebuild** from the database's current set of IDs. 2. A **counting** variant, which keeps small counters instead of single bits and so supports removal, at several times the memory. ## Rebuilding without losing creates A rebuild takes time, and items keep being created while it runs. A safe sequence: 1. Create an empty new filter. 2. Start adding every new ID to **both** the old and the new filter. 3. Scan the database and add every existing ID to the new filter. 4. Once the scan finishes, switch readers to the new filter and drop the old one. If you skip step 2, an item created during the scan, after the scan has passed its position, would be missing from the new filter and rejected after the switch. ## Sizing at a glance As a rule of thumb, a bloom filter needs roughly **10 bits per item for about a 1% false-positive rate**. For an illustrative 100 million IDs, that is 1 billion bits, about 125 MB, which is far less than caching 100 million entries. With a 1% rate, about 99 of every 100 requests for never-issued IDs are rejected at the guard, and the remaining 1 falls through to the normal path. Sizing it for a tighter rate, and how the filter works inside, are separate topics. For the guard, what matters is that the filter is small, rejects most misses, and never rejects a real ID as long as creates keep it complete.