\n\tDefinitely not present (guaranteed correct)
\n\tPossibly present (may include false positives)
<\/p>\n
It never produces false negatives, which makes it well-suited for quickly rejecting items that are certainly unseen.<\/p>\n
With the introduction of Bloom filters, the request path changes slightly:<\/p>\n
\n\tGenerate candidate article IDs.
\n\tQuery the Bloom filter with (user_id, article_id) membership keys.
\n\tIf the filter returns definitely not present, treat the candidate as unseen and keep it in the ranking pipeline.
\n\tIf the filter returns possibly present, go on with exact history verification.
<\/p>\n
This design targets exactly the pain point from the previous section: the dominant negative path. Most candidates are unseen, so most checks can be resolved in-memory without remote I\/O.<\/p>\n
Why a Probabilistic Approach Fits This Workload<\/p>\n
The approach described here has several interesting properties:<\/p>\n
\n\tNegative-heavy query distribution: with ~97-98% negatives, fast negative rejection has a high impact.
\n\tStrict correctness where needed: positives can still be verified against exact storage.
\n\tPredictable memory footprint: Bloom filters compactly represent large membership sets.
\n\tTunable trade-off: as we will see later, we can control false-positive rate via m (bit array size) and k (hash count).
<\/p>\n
The next sections explain how Bloom filters work, how we implemented them in Go, and how we used the math to tune parameters for this recommendation workload.<\/p>\n
Bloom Filters in Practice<\/p>\n
In our recommendation workload, the goal of a Bloom filter is to quickly identify likely unseen candidates and avoid unnecessary expensive history lookups. Because most candidate checks are negative, the filter helps remove a large amount of avoidable storage and network work from the serving path.<\/p>\n
Core Mechanics<\/p>\n
A Bloom filter encodes membership information for a set of elements. Its core components are simple but powerful:<\/p>\n
\n\tA bit array of size m: each position stores a 0 or 1, representing whether it has been set by one or more elements.
\n\t\u00a0k hash functions: each element is mapped to k positions in the bit array. These hash functions should be independent and uniformly distribute elements across the array. Finding good hash functions is crucial for minimizing collisions and controlling the false-positive rate, making it an important engineering consideration. We\u2019ll discuss practical hash function choices in the implementation section.
<\/p>\n
Bloom filters do not store the elements themselves, only the presence information is encoded in the bits.<\/p>\n
Insertion<\/p>\n
To add an element E to the Bloom filter:<\/p>\n
\n\tApply the \\(k\\) hash functions to E:
\n\t\\(h_1(E), h_2(E), \\dots, h_k(E)\\) each produces a numeric hash.
\n\tMap the hashes into the bit array using modulo \\(m\\):
\n\t\\(index_i = h_i(E) \\mod m\\)
\n\tThis gives \\(k\\) positions in the array (it\u2019s possible for some positions to be the same due to collisions).
\n\tSet the bits at these positions to 1:
\n\t\\(\\text{bit_array}[\\text{index_i}] = 1\\)
<\/p>\n
Multiple elements may set the same bit. Bits are only ever set, never cleared. This is why standard Bloom filters cannot support deletions.<\/p>\n
Membership Queries<\/p>\n
To check if an element is present:<\/p>\n
\n\tCompute the same k hash values for the element.
\n\tCheck the corresponding bits in the array.
<\/p>\n
If any bit is 0, the element is definitely not in the set, because it would have been set to 1 during insertion.<\/p>\n
If all bits are 1, the element is possibly in the set. This is where false positives can occur: different elements may hash to the same positions, causing bits to be set even if the queried element was never added.<\/p>\n
![\"\"](\"https:\/\/www.infoq.com\/articles\/bloom-filters-practice-go-recommender\/articles\/bloom-filters-practice-go-recommender\/en\/resources\/198figure-1-1774950090560.jpg\")
<\/p>\n
Figure 1 – Bloom filter insertions and membership test<\/p>\n
In the diagram above, we insert three elements (element1, element2, element3) into the Bloom filter with 2 hash functions (h1 and h2). Each element sets two bits in the array. When we query for element4, we find that not all bits are set, so we can confidently say it is not present. (Note that in the diagram we have hash collisions: for example, element1 and element3 both set the bit at index 6, which contributes to the possibility of false positives.)<\/p>\n
Key Properties<\/p>\n
Bloom filters display several interesting properties:<\/p>\n
\n\tNo false negatives: a “not present” result is always correct.
\n\tFalse positives possible: an element may appear to exist even if it hasn\u2019t been added.
\n\tDeterministic: the same element always maps to the same bits.
\n\tEfficient in memory and speed: the bit array and simple hash computations allow fast insertions and queries.
\n\tOnly stores membership information: it cannot retrieve the original elements.
\n\tNo deletions: once bits are set, they cannot be cleared without affecting other elements. This is a fundamental limitation of standard Bloom filters, and while there are variants that support deletions (like counting Bloom filters), they come with additional complexity and memory overhead.
<\/p>\n
While the mechanics described above explain how a Bloom filter operates, this understanding alone is no guarantee \u00a0for a practical, ready-to-use filter. Without careful choices of the bit array size (\\(m\\)), the number of hash functions (\\(k\\)), and appropriate hash functions, a Bloom filter could be inefficient or produce too many false positives. In the next section, we will demonstrate how to implement a Bloom filter in Go, translating the mechanics into working code. The discussion of how to choose and tune these parameters will follow in the Practical Considerations section.<\/p>\n
Implementing a Bloom Filter in Go<\/p>\n
Go is an ideal language for implementing a Bloom filter because it provides low-level control over memory, efficient slices and arrays, and fast, predictable execution. These characteristics make it easy to reason about the bit array, hash computations, and overall performance of the filter. These are all critical for production systems that need both speed and memory efficiency.<\/p>\n
Translating the mechanics of a Bloom filter into Go is straightforward. The implementation uses a bit array and multiple hash functions, mirroring the step-by-step behavior we described in the Core Mechanics section. At this stage, we focus on the structure and basic operations; parameter tuning will be addressed in the Practical Considerations section.<\/p>\n
Defining the Bloom Filter Structure<\/p>\n
The Bloom filter structure (struct) in Go consists of a packed bit array, the number of addressable bits, and the configured hash functions. Storing hash functions in the struct avoids per-call API mistakes and keeps usage ergonomic. Using a packed representation (64 bits per word) improves memory efficiency and cache behavior compared to storing one boolean per bit:<\/p>\n
\ntype BloomFilter struct {
\n\u00a0 bits \u00a0 []uint64 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \/\/ packed bit array (64 bits per word)
\n\u00a0 m \u00a0 \u00a0 \u00a0uint \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \u00a0 \/\/ number of addressable bits
\n\u00a0 hashes []func([]byte) uint \u00a0\/\/ configured hash functions
\n}<\/p>\n
Creating a New Bloom Filter<\/p>\n
The NewBloomFilter function initializes a new Bloom filter with the specified size and hash functions:<\/p>\n
\n\/\/ NewBloomFilter creates a new Bloom filter with m bits and configured hash functions.
\nfunc NewBloomFilter(m uint, hashes []func([]byte) uint) *BloomFilter {
\n\u00a0 if m == 0 {
\n\u00a0 \u00a0 panic(“bloom filter size m must be > 0”)
\n\u00a0 }
\n\u00a0 if len(hashes) == 0 {
\n\u00a0 \u00a0 panic(“at least one hash function is required”)
\n\u00a0 }
\n
\n\u00a0 words := (m + 63) \/ 64 \/\/ ceil(m\/64)
\n\u00a0 return &BloomFilter{
\n\u00a0 \u00a0 bits: \u00a0 make([]uint64, words),
\n\u00a0 \u00a0 m: \u00a0 \u00a0 \u00a0m,
\n\u00a0 \u00a0 hashes: hashes,
\n\u00a0 }
\n}<\/p>\n
To operate on the packed bit array, we use helper methods for setting and reading individual bits:<\/p>\n
\nfunc (bf *BloomFilter) setBit(i uint) {
\n\u00a0 word := i >> 6 \u00a0 \/\/ i \/ 64
\n\u00a0 offset := i & 63 \/\/ i % 64
\n\u00a0 bf.bits[word] |= uint64(1) << offset
\n}
\nfunc (bf *BloomFilter) hasBit(i uint) bool {
\n\u00a0 word := i >> 6
\n\u00a0 offset := i & 63
\n\u00a0 return (bf.bits[word] & (uint64(1) << offset)) != 0
\n}<\/p>\n
Adding an Element<\/p>\n
The Add method takes a byte slice (the data to be added), computes configured hash values, maps them to indices in the bit array, and sets the corresponding packed bits:<\/p>\n
\nfunc (bf *BloomFilter) Add(data []byte) {
\n\u00a0 for _, hash := range bf.hashes {
\n\u00a0 \u00a0 idx := hash(data) % bf.m
\n\u00a0 \u00a0 bf.setBit(idx)
\n\u00a0 }
\n}<\/p>\n
Bits are only ever set; insertion mirrors the Bloom filter core mechanics exactly.<\/p>\n
Querying an Element<\/p>\n
The Contains method checks if an element is possibly in the Bloom filter by verifying the bits corresponding to the hash values:<\/p>\n
\nfunc (bf *BloomFilter) Contains(data []byte) bool {
\n\u00a0 for _, hash := range bf.hashes {
\n\u00a0 \u00a0 idx := hash(data) % bf.m
\n\u00a0 \u00a0 if !bf.hasBit(idx) {
\n\u00a0 \u00a0 \u00a0 return false \/\/ definitely not present
\n\u00a0 \u00a0 }
\n\u00a0 }
\n\u00a0 return true \/\/ possibly present
\n}<\/p>\n
This method returns false if any bit is not set, ensuring there are no false negatives. If all bits are set, it returns true, indicating a possible membership (with the possibility of false positives).<\/p>\n
This implementation directly mirrors the core mechanics: multiple independent hashes, bit array updates, and membership checks. Let\u2019s see a running example of how to use this Bloom filter in practice, including how to define hash functions and test the filter with some data:<\/p>\n
\npackage main
\nimport (
\n\u00a0 “Fmt”
\n\u00a0 “hash\/fnv”
\n)
\n
\n\/\/ Simple hash functions
\nfunc hash1(data []byte) uint {
\n\u00a0 h := fnv.New32a()
\n\u00a0 h.Write(data)
\n\u00a0 return uint(h.Sum32())
\n}
\n
\nfunc hash2(data []byte) uint {
\n\u00a0 h := fnv.New32()
\n\u00a0 h.Write(data)
\n\u00a0 return uint(h.Sum32())
\n}
\n
\nfunc main() {
\n\u00a0 \/\/ Define hash functions
\n\u00a0 hashes := []func([]byte) uint{hash1, hash2}
\n
\n\u00a0 \/\/ Create a Bloom filter: size 20 bits
\n\u00a0 bf := NewBloomFilter(20, hashes)
\n
\n\u00a0 \/\/ Add elements
\n\u00a0 bf.Add([]byte(“apple”))
\n\u00a0 bf.Add([]byte(“banana”))
\n\u00a0 bf.Add([]byte(“cherry”))
\n
\n\u00a0 \/\/ Query elements
\n\u00a0 tests := []string{“apple”, “banana”, “cherry”, “date”, “fig”}
\n
\n\u00a0 for _, t := range tests {
\n\u00a0 \u00a0 if bf.Contains([]byte(t)) {
\n\u00a0 \u00a0 \u00a0 fmt.Printf(“%s: possibly present\\n”, t)
\n\u00a0 \u00a0 } else {
\n\u00a0 \u00a0 \u00a0 fmt.Printf(“%s: definitely not present\\n”, t)
\n\u00a0 \u00a0 }
\n\u00a0 }
\n}<\/p>\n
In this example, we define two simple hash functions using the FNV hash algorithm. This is sufficient for demonstration, but production systems typically prefer higher-quality non-cryptographic hashes (for example Murmur3<\/a>, xxHash<\/a>, MetroHash<\/a>, or HighwayHash<\/a>) and validate distribution behavior under real keysets. After defining the two hash functions, we create a Bloom filter with a size of 20 bits and 2 hash functions. We add three fruits to the filter and then test for their presence, along with two additional fruits that were not added. The output will indicate which fruits are possibly present (with potential false positives) and which are definitely not present:<\/p>\n
The Math Behind Bloom Filters<\/p>\n Bloom filters are easy to implement, but not so easy to use effectively: you need to understand their probabilistic behavior to get the most out of them. This allows engineers to predict false-positive rates and make informed choices about memory usage and the number of hash functions required to achieve the desired false-positive rate. The math behind Bloom filters is essential for tuning their parameters (\\(m\\), \\(k\\), and the hash functions) to achieve the desired balance between memory efficiency and accuracy.<\/p>\n Below, we quickly summarize the key formulas you\u2019ll need in practice. For a deeper dive into the derivations and underlying theory, see the Appendix: The Math Behind Bloom Filters. \\(p = \\left( 1 – e^{-\\frac{kn}{m}} \\right)^k\\)<\/p>\n The optimal number of hash functions (\\(k\\)):<\/p>\n \\(k = \\frac{m}{n} \\ln 2\\)<\/p>\n The required bit array size (\\(m\\)) for a target false positive rate:<\/p>\n \\(m = -\\frac{n \\ln p}{(\\ln 2)^2}\\)<\/p>\n Results Snapshot<\/p>\n After introducing Bloom-filter gating in our recommendation path and tuning\u00a0\\(\\frac{m}{k}\\) using the formulae above, we observed three consistent outcomes in peak-window traffic:<\/p>\n
These numbers are workload-specific, but the pattern is general: when lookups are mostly negative and expensive, a well-tuned Bloom filter can remove a large portion of avoidable backend work.<\/p>\n Practical Considerations & Best Practices<\/p>\n With the mechanics implemented and the math to choose \\(k\\) and \\(m\\), we can now translate theory into engineering decisions.<\/p>\n Start with Product Constraints, Not with Bloom Filter Parameters<\/p>\n For our recommendation path, the product-level question was not “what \\(m\\) and \\(k\\) should we use?”, but rather:<\/p>\n
That gave us a concrete tuning target:<\/p>\n
This is a general rule: start from service SLOs and user-impact tolerance, then calculate Bloom filter parameters.<\/p>\n How We Chose \\(n\\), \\(m\\), and \\(k\\) in Our Case<\/p>\n In our implementation, we modeled\u00a0\\(n\\) as the expected number of viewed items represented in one filter over its lifecycle window (for example, per user over a rolling period). \\(m \\approx -\\frac{n \\ln P}{(\\ln 2)^2}, \\quad k \\approx \\frac{m}{n} \\ln 2\\)<\/p>\n Then we made three practical adjustments:<\/p>\n
In practice, this meant accepting slightly higher memory to protect false-positive behavior under growth, and avoiding an overly large k that would hurt hot-path latency.<\/p>\n In this specific recommendation use case, we also made an important serving decision: when the false-positive rate stayed within our product tolerance, we did not always route Bloom positives to exact lookup. A small false-positive rate means occasionally suppressing an unseen item, which was acceptable for feed quality, while skipping exact verification removed additional backend cost and latency. This approach worked for our use case because the occasional omission was acceptable, but in many systems, stricter guarantees are necessary.<\/p>\n This approach worked for our use case because the occasional omission was acceptable, but in many systems, stricter guarantees are necessary. In general, exact verification of Bloom positives is required when false positives are expensive or correctness-critical, but optional when product behavior can tolerate rare over-filtering.<\/p>\n Hash Function Choice: Correctness First, Then Throughput<\/p>\n In this article, hash values are derived deterministically and mapped with modulo m. The important production lesson was that hash strategy is not a cosmetic detail:<\/p>\n
\napple: possibly present
\nbanana: possibly present
\ncherry: possibly present
\ndate: definitely not present
\nfig: definitely not present<\/p>\n
\nThe false positive rate (p) is approximately:<\/p>\n
\n\tLower tail latency: p95 feed latency improved from ~140ms to ~96ms (about 31% reduction).
\n\tFewer expensive checks: exact history lookups dropped from ~120 per request to ~24 on average (about 80% reduction).
\n\tLower backend pressure: read traffic to the history store dropped by ~65-70%, while measured Bloom false-positive over-filtering stayed under ~0.5%.
<\/p>\n
\n\thow many duplicate recommendations are acceptable
\n\thow much memory can we spend in the serving tier
\n\twhat latency budget remains for per-candidate filtering.
<\/p>\n
\n\tkeep false positives low enough to avoid visible over-filtering of unseen items
\n\twhile reducing expensive exact-history lookups on the negative-heavy path.
<\/p>\n
\nWe used the standard equations:<\/p>\n
\n\tHeadroom on \\(n\\): we sized for growth, not current average, to avoid early saturation.
\n\tRounded m for implementation efficiency: we rounded to word boundaries for packed\u00a0\\(\\texttt{[]uint64}\\) storage.
\n\tClamped\u00a0\\(k\\) for CPU cost: we treated the computed value as a starting point, then chose a value that kept per-request hash work within budget (hashing may be expensive).
<\/p>\n
\n\tpoor distribution inflates collisions
\n\tcollisions inflate false positives
\n\tfalse positives raise exact-lookup pass-through
\n\tpass-through erodes the benefit of the Bloom filter.
<\/p>\n