Bloom Filters: Membership with False Positives, Capacity, Error Rate, and Scaling

Learning outcomes

AtlasMart wants to avoid expensive downstream work for product IDs that were definitely never seen before, while accepting a small number of “probably seen” responses. A Bloom filter is designed for exactly that asymmetric membership question.

1. Bloom answers “possibly present?” with asymmetric error

A Bloom filter hashes each inserted item into bits. If any required bit is absent, the item is definitely not in the filter. If all required bits are set, the item is probably present because unrelated inserts can collide onto the same bits. Correct append-only use therefore admits false positives but not false negatives.

2. Capacity and error rate are a design contract

BF.RESERVE key error_rate capacity creates a filter with an upper-bound false-positive target for its initial sub-filter. Redis documents the approximate bit cost per item as -ln(error_rate)/ln(2)^2: about 9.585 bits/item for 1%, 14.378 for 0.1%, and 19.170 for 0.01%, before object/sub-filter overhead.

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:bloom:productsdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.RESERVE atlasmart:ch11:bloom:products 0.01 1000docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.INFO atlasmart:ch11:bloom:products

Do not choose 0.000001 because it “sounds safer” without calculating memory and CPU consequences. Start from the cost of a false positive and expected cardinality.

3. BF.ADD return is itself probabilistic

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.ADD atlasmart:ch11:bloom:products product:1001docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.ADD atlasmart:ch11:bloom:products product:1002docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.ADD atlasmart:ch11:bloom:products product:1001docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.EXISTS atlasmart:ch11:bloom:products product:1001docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.EXISTS atlasmart:ch11:bloom:products product:9999

A repeated BF.ADD commonly returns 0 because the item probably already existed, but the probabilistic structure cannot turn that return into exact duplicate detection. If duplicate acceptance/rejection is contractual, maintain exact state.

4. False-positive trials need absent ground truth

To measure false positives, you must know that queried candidates were never inserted. A useful experiment has two disjoint deterministic namespaces: insert known:0000..0999, then query absent:0000..9999. Count positive results among the absent set and report false_positives / absent_trials. A single short run can land above or below the configured target by chance.

inserted={f"known:{i:04d}" for i in range(1000)}absent=[f"absent:{i:04d}" for i in range(10000)]assert not inserted.intersection(absent)# Feed inserted values to Redis BF.ADD/BF.MADD, then query absent values.# Do not fabricate a rate here: record what your server actually returns.false_positives = 0   # replace with measured positives among absent[]rate = false_positives / len(absent)print("measured false-positive rate:", rate)print("configured target:", 0.01)

5. BF.INFO proves capacity, allocated bytes, sub-filters, and item bookkeeping

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.INFO atlasmart:ch11:bloom:products CAPACITYdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.INFO atlasmart:ch11:bloom:products SIZEdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.INFO atlasmart:ch11:bloom:products FILTERSdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.INFO atlasmart:ch11:bloom:products ITEMSdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.INFO atlasmart:ch11:bloom:products EXPANSIONdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app MEMORY USAGE atlasmart:ch11:bloom:products

BF.INFO SIZE reports bytes allocated by the Bloom implementation; MEMORY USAGE is Redis key memory accounting. They answer related but not necessarily identical accounting questions.

6. Scaling is convenient, not free

By default, when the initial capacity is reached Redis can add sub-filters. The default expansion factor is 2. More sub-filters increase query work and memory overhead, which is why Redis recommends reserving a realistic initial capacity. Use NONSCALING only when a hard capacity and insert failure are acceptable.

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:bloom:scaling atlasmart:ch11:bloom:fixeddocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.RESERVE atlasmart:ch11:bloom:scaling 0.05 10 EXPANSION 2docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.RESERVE atlasmart:ch11:bloom:fixed 0.05 10 NONSCALINGdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.INFO atlasmart:ch11:bloom:scalingdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app BF.INFO atlasmart:ch11:bloom:fixed

Populate both with a controlled loop on your machine and observe when the fixed filter refuses additional inserts versus when the scaling filter adds a sub-filter.

7. Bloom does not support deletion

Bits are shared among multiple hashed elements. Clearing bits for one element could create false negatives for other elements, so the Redis Bloom API has no item-delete command. If AtlasMart must retract membership, use an exact Set or consider a Cuckoo filter with its stricter deletion preconditions.

8. Wrong approach: use Bloom as a fraud deny-list

If BF.EXISTS returns “probably present” and the application automatically blocks a customer, a false positive becomes a user-impacting security decision. Repair the design by using Bloom only as a fast prefilter and confirming positives against authoritative deny-list state before enforcement.

9. Wrong approach: guess capacity and ignore expansion

A filter reserved for 100,000 IDs but fed tens of millions may create many sub-filters. Even if it keeps functioning, query CPU and total false-positive behavior differ from the original small design. Track BF.INFO FILTERS, ITEMS, allocated bytes, observed positive rate, and insert throughput.

10. ACL upgrade boundary matters in Redis 8

Because Redis 8 integrated probabilistic commands into broader ACL categories, an application user with +@read +@write can gain access to commands that did not exist in the same categories on an older deployment. Use explicit category/command policy where least privilege matters, and re-run ACL DRYRUN during upgrades.

11. Reproducible cleanup

docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:bloom:products atlasmart:ch11:bloom:scaling atlasmart:ch11:bloom:fixed

12. Production judgment

Bloom filters fit cheap negative membership checks, cache-admission hints, duplicate-work avoidance, and “probably seen” gates where positives can be verified. Size from expected cardinality and tolerated false-positive cost; measure actual false-positive rate, filter count, memory, CPU, persistence footprint, and saturation. Do not use Bloom where deletion, exact membership, enumeration, or safety-critical authorization is required.

13. Summary and next step

Bloom filters trade exact positive membership for compact append-only state and a configurable false-positive budget. Lesson 3 introduces Cuckoo filters, which add deletion and approximate multiplicity—but deletion must be used with discipline to avoid creating false negatives.

Authoritative references

• Redis probabilistic data types — current integrated probabilistic data-structure overview
• Redis data types — current Redis data-type surface
• HyperLogLog — cardinality-estimation model and operations
• PFADD — HyperLogLog insertion semantics
• PFCOUNT — standard error, memory, and union-count semantics
• PFMERGE — persistent HLL union/merge semantics
• Bloom filter — Bloom membership model and examples
• BF.RESERVE — capacity, false-positive rate, scaling, and memory formulas
• BF.INFO — Bloom capacity/filter/memory evidence
• Cuckoo filter — Cuckoo membership/deletion tradeoffs
• CF.DEL — safe deletion requirement and corruption warning
• CF.COUNT — Cuckoo multiplicity estimate semantics
• Count-Min Sketch — frequency-estimation model
• CMS.INITBYPROB — error/probability sizing controls
• CMS.MERGE — same-dimension merge and weights
• Top-K — HeavyKeepers-based heavy-hitter model
• TOPK.LIST — ranked top-k output and WITHCOUNT
• TOPK.COUNT — deprecated count command and undercount note
• t-digest — percentile/CDF model and merge operations
• TDIGEST.CREATE — compression versus memory/accuracy tradeoff
• TDIGEST.QUANTILE — quantile estimate semantics
• TDIGEST.INFO — observations, nodes, compression, memory evidence
• Probabilistic command compatibility — current command/Redis product compatibility matrix
• Redis 8.0 release notes — integrated probabilistic features and ACL-category change
• Redis 8.10 release notes — 8.10.1 security baseline for CMS/Top-K