---
title: "Bloom Filters: The Cheap Gate Before the Expensive Question"
description: "A Bloom filter is a small bit array plus a few hash functions that answers \"has this been seen?\" with no false negatives and a false-positive rate you choose up front."
---

# Bloom Filters: The Cheap Gate Before the Expensive Question

**Type:** [What is it?](https://yomu.fyi/visual-explainers/category/what-is-it.md)

![A diagram showing a Bloom filter as a bit array with three hash functions: an insert path sets bits to 1, a query path checks those bits, and two outcome panels show "all bits set = maybe present" versus "any bit 0 = definitely absent."](https://yomufyi.s3.us-east-1.amazonaws.com/visual-explainers/419c80bf-2eba-4a6a-ab28-795e3950dd93/image-58a4eb93-0f03-4dde-b458-dcc3d28ff4df.webp)

> A Bloom filter is a small bit array plus a few hash functions that answers "has this been seen?" with no false negatives and a false-positive rate you choose up front.

## Explanation

A Bloom filter answers membership questions with a fixed-size bit array and a small set of hash functions. Each insert hashes the item to several positions and sets those bits; each query hashes the same way and checks whether every one of those bits is already set. If any bit is zero the item was definitely never inserted, and if all bits are set the item is probably present, with the uncertainty showing up as false positives you size for in advance. The structure trades exactness and deletability for a tiny, predictable memory footprint, which makes it most useful as a cheap gate in front of an expensive lookup.

## FAQ

### Why can a Bloom filter never return a false negative?

An insert only ever sets bits to one, and nothing in the structure clears them. So if an item was inserted, all of its hash positions are still set and the query always reports possibly present. Deletion is what would break this guarantee, which is why standard Bloom filters do not support it.

### When is a Bloom filter the wrong tool?

When you need to delete entries, enumerate what is inside, or keep derived state in sync with a source of truth. Medium's Daily Digest team hit exactly this after one filter accumulated billions of read, muted, and presentation rules, and replaced it with user-scoped database queries that were roughly ten times cheaper and easier to debug.

### How do I size a Bloom filter?

You choose the bit-array size and the number of hash functions together, and those two numbers determine the false-positive rate for an expected item count. More bits per item lowers the error rate at the cost of memory, and more hash functions help only up to a point before they saturate the array. Because you cannot enumerate the filter, plan the sizing before you load data into it.

**Tags:** [Bloom Filters](https://yomu.fyi/topic/bloom-filters.md), [Caching](https://yomu.fyi/topic/caching.md), [Distributed Systems](https://yomu.fyi/topic/distributed-systems.md), [Performance](https://yomu.fyi/topic/performance.md), [Search](https://yomu.fyi/topic/search.md)

## Related reading

### [Same Query, Same Score: Consistent Ranking with StableTfl in Atlas Search](https://yomu.fyi/post/same-query-same-score-consistent-ranking-with-stabletfl-in-atlas-searc.md)
- Company: [MongoDB](https://yomu.fyi/company/mongodb.md)
- Published: Sep 25, 2026
- Type: Explainer

Paginated search in Atlas Search can show duplicate or skipped results across pages because BM25 scores drift between replicas due to changing corpus statistics. The usual workarounds like sticky routing or index snapshots require extra state and are cumbersome. The solution is StableTfl, a scoring function that uses only term frequency and document length, with term length as a proxy for rarity based on Zipf’s brevity law, eliminating corpus statistics and requiring no extra state. StableTfl is contributed to Apache Lucene and is available as a per-field similarity option in Atlas Search. Benchmarks on BEIR show StableTfl achieves 0.315 NDCG@10 compared to BM25’s 0.346, a 9% relative drop, making it suitable for paginated search, RAG pipelines, and multi-replica deployments where consistency matters more than peak relevance.


### [How Intelligent Load Shedding Prevents Cascading Failures in Tier-0 Systems](https://yomu.fyi/post/how-intelligent-load-shedding-prevents-cascading-failures-in-tier-0-sy.md)
- Company: [Salesforce](https://yomu.fyi/company/salesforce.md)
- Author: Scott Nyberg
- Published: Sep 24, 2026
- Type: Problem & solution

Salesforce’s Cloud Atlas team operates a globally distributed identity data store that must maintain five nines of availability, roughly five minutes of downtime per year. The team redesigned service protection after per-instance rate limiting proved insufficient under autoscaling and increasingly bursty, unpredictable agent-driven traffic. The new approach combines intelligent load shedding, which monitors queue time as an early indicator of system pressure before error rates spike, with coordinator-free global quota management. Servers independently measure and share customer usage to throttle noisy tenants without a centralized coordinator, preventing one customer’s surge from affecting others. This design prevents cascading failures by shedding lower-priority work before overload spreads across dependent services, ensuring graceful degradation rather than widespread outage.


### [Measuring the back/forward cache with Application Metrics](https://yomu.fyi/post/measuring-the-back-forward-cache-with-application-metrics.md)
- Company: [Sentry](https://yomu.fyi/company/sentry.md)
- Author: Abdelrahman Awad
- Published: Sep 24, 2026
- Type: Announcement

The back/forward cache (bfcache) allows instant page restores by freezing snapshots, yet its hits register no events in traditional telemetry, creating a blind spot for teams. Sentry’s bfcacheMetricsIntegration fills this gap by modeling three browser-provided signals as application metrics: a navigation counter with hit/miss outcome, a per-reason counter for misses via the notRestoredReasons API, and a distribution of fallback reload duration. The integration is opt-in and launched in JavaScript SDKs v11; detailed miss reasons are currently Chromium-only due to browser API support. Users can query these metrics to break down bfcache health by route, release, or browser, enabling discovery of regressions caused by unload listeners, cache-control headers, or third-party scripts. This turns the bfcache from an invisible performance feature into a measurable, trackable signal that teams can monitor and improve.


### [Engineering stories behind the Medium Daily Digest Algorithm: Part 2](https://yomu.fyi/post/engineering-stories-behind-the-medium-daily-digest-algorithm-part-2.md)
- Company: [Medium](https://yomu.fyi/company/medium.md)
- Author: Raphael Montaud
- Published: Aug 28, 2025
- Type: Problem & solution

Medium’s Daily Digest filtering had become costly and difficult to maintain after a single Bloom Filter instance accumulated billions of items for read, muted, and presentation rules. The system could face up to 15,000 filter questions per feed and more than 15 million per second across thousands of feeds, while Bloom Filters could not delete or enumerate entries and introduced derived-data drift. The team replaced the muted-writer filter with a user-based database query that fetched all muted writers for the current user and cross-referenced them with the story shortlist, then split read filtering between early user-based queries and later pairwise lookups. The resulting implementation removed Bloom Filters entirely, was reported as ten times cheaper in their situation, made costs independent of shortlist size, supported reading-history clearing, and was easier to control and debug.