bits-and-blooms/bloom: a Go Bloom filter package for LSM trees, log indexes and dedup

What bits-and-blooms/bloom actually solves

The package answers one question: is this key possibly in the set, or definitely not. The README is explicit about the asymmetry. A Bloom filter always correctly reports that an element is present when it is present, but it may sometimes report that an element is in the set when it is not. That single guarantee is what makes the structure useful. You trade exactness for size, and you keep the negative answers exact.

The audience is Go engineers who own a storage or lookup path where a full key set is too large to hold or too slow to consult on every miss. The README lists the systems that embed it, and the pattern is consistent: Milvus, Weaviate's lsmkv layer, openGemini's index packages, Loki's dataobj and storage layers, SpiceDB's dispatch layer, and Split.io's Go SDK, where the README says it is used for impression deduplication. In each case the filter sits in front of something more expensive. A negative answer lets you skip a disk read, a network round trip, or a table lookup.

This is not a cache, a database, or a service you run. It is a Go module with a small surface: construct, Add, Test, and serialize. If you want a process to deploy, this is the wrong project.

NewWithEstimates and the capacity decision you cannot undo

The mechanism is standard. You choose a desired capacity and a false positive rate, and the constructor derives the number of bits m and the number of hash functions k. The README gives the canonical call for one million elements at a 1 percent rate.

    filter := bloom.NewWithEstimates(1000000, 0.01)

Keys are added and tested as []byte, so strings need an explicit conversion and numbers need encoding. The README recommends the encoding/binary library for numeric data and shows a uint32 being written into a four byte buffer with binary.BigEndian.PutUint32 before Add is called.

The constraint that matters is stated plainly: you should call NewWithEstimates conservatively, because if you specify a number of elements that is too small, the false positive bound might be exceeded. A Bloom filter is not a dynamic data structure. There is no resize, no rehash, and no growth path in the API. If your set outgrows the estimate, your only options are to accept a worse false positive rate or to build a new filter and reinsert everything.

Two hash functions are involved. The repository has a murmur.go file alongside bloom.go, and go.mod requires github.com/twmb/murmur3 v1.1.8 and github.com/bits-and-blooms/bitset v1.24.4. The bit array itself comes from the bitset dependency rather than being hand rolled in this package.

Installing the module and running a first membership test

Installation is a single go get against the v3 module path, which is what the README documents.

go get -u github.com/bits-and-blooms/bloom/v3

After that, the import path carries the v3 suffix, matching the module line in go.mod. A minimal program constructs a filter, adds a key, and tests for it. The README's own example uses the string "Love".

filter := bloom.NewWithEstimates(1000000, 0.01)
filter.Add([]byte("Love"))
if filter.Test([]byte("Love")) {
    // membership reported
}

What you should see is a true result for a key you added. What you should also expect, and what the README warns about, is that a key you never added can return true as well. That is the false positive, and it is the cost of the compression. A test returning false is the reliable signal: the key is definitely not in the set as far as this filter is concerned.

If you want to check that the parameters you chose behave as intended, the package exposes EstimateFalsePositiveRate, which the README describes as creating a temporary Bloom filter and being relatively expensive, meant for validation rather than for production paths. The documented pattern computes m and k with EstimateParameters, then feeds them back in.

m, k := bloom.EstimateParameters(n, fp)
ActualfpRate := bloom.EstimateFalsePositiveRate(m, k, n)

The README says you would expect ActualfpRate to be close to the desired rate fp in these cases. Close is the operative word, and the README itself notes that the actual rate may differ slightly from the theoretical one.

Serializing a filter and the bufio detail

Filters move between processes, so the package implements WriteTo and ReadFrom. The README's example builds a filter with New(1000, 4), writes it into a bytes.Buffer, reads it back into a fresh BloomFilter, and compares the byte counts to confirm the round trip.

f := New(1000, 4)
var buf bytes.Buffer
bytesWritten, err := f.WriteTo(&buf)
var g BloomFilter
bytesRead, err := g.ReadFrom(&buf)

Note the constructor here. New takes m and k directly, the raw bit count and hash count, while NewWithEstimates takes capacity and error rate. Both exist, and picking the wrong one is an easy mistake: passing 1000 and 4 to NewWithEstimates means something entirely different from passing them to New.

The README adds a performance tip for file and network streams: wrapping them with bufio instances gives better performance. It shows os.Create followed by bufio.NewWriter for the write side and os.Open followed by bufio.NewReader for the read side. That is a suggestion about the surrounding I/O, not a requirement of the format.

What the README does not document is a version or compatibility guarantee for the serialized bytes. There is no stated format version marker anywhere in the repository files, so if you persist filters across a dependency upgrade, that is a risk you are carrying without documentation to lean on.

Where the false positive rate is the wrong trade

The failure mode is structural, not a bug. Every false positive is a key that your downstream code will treat as present. If the filter guards a disk read, a false positive costs you one wasted read. If it guards a deduplication check, a false positive silently drops a record you have never seen. The README's description of the Split.io usage, impression deduplication, is exactly the shape where this matters: the consequence of a wrong answer is a lost event, not a slow query.

There is a second case where the package is simply the wrong tool. Bloom filters cannot delete. Nothing in the README or the API surface described there offers a removal operation, and the fixed-bit-array design is the reason. If your set shrinks, or if you need to retract a key, you need a counting variant or a different structure entirely, and you will not find one here.

The third case is exactness. If a false positive is unacceptable rather than merely expensive, no amount of tuning helps, because the rate approaches zero without reaching it. The README's framing is honest about this: the filter is a compressed representation that permits some false positives. That is the deal.

One more practical boundary: the README recommends calling NewWithEstimates conservatively, which means an overestimate costs memory you never use. There is no documented way to shrink a filter after construction either.

How this differs from a plain map or a sorted key set

The obvious alternative in Go is a map[string]struct{} or a sorted slice with binary search. Both give exact answers and both support deletion. The difference is memory per key and the cost of holding the full key material. A Bloom filter stores bits derived from hashes, not the keys themselves, which is why it can represent a large set in a fraction of the space and why it cannot enumerate its contents. If you need to list what is in the set, or iterate it, this package cannot help you.

A second alternative is a counting Bloom filter, which supports deletion at the cost of several bits per position instead of one. It is not part of this repository. If your workload involves removal, that is the family you should be looking at rather than this one.

A third comparison is worth making on the operational side. The systems the README names, Milvus, Loki, Weaviate, openGemini, use the filter as an internal component of an index or storage engine, not as a standalone service. They already own the key space and the lifecycle. If you are reaching for this package because you want a shared membership service across languages, you are looking at the wrong layer; this is a Go library that lives inside your process.

Maintenance, licence and the upgrade surface

The repository is not archived. The last push was on 2026-07-10, which is recent enough that the project is not dormant, though the release cadence tells a more uneven story: v3.7.1 landed on 2025-10-26, v3.7.0 on 2024-03-16, and v3.6.0 on 2023-10-13. Releases are infrequent, which for a data structure library is closer to a feature than a flaw. The algorithm does not change.

The dependency surface is small and worth noting because it is the main upgrade exposure. go.mod requires exactly two modules: github.com/bits-and-blooms/bitset v1.24.4 and github.com/twmb/murmur3 v1.1.8. The bit array lives in the bitset module, so a bitset upgrade is the most plausible source of behaviour change in your build. The module declares go 1.16, which is a floor rather than a ceiling.

The licence is BSD-2-Clause, a permissive licence, and the repository ships a LICENSE file at the top level. That is the kind of licence that generally imposes few obligations beyond retaining the copyright notice and the licence text in redistributions, but the exact terms are in the file and nothing here substitutes for reading it, or for your own legal review.

The Makefile is aimed at contributors rather than consumers. It defines targets including test, format, fmtcheck, vet, lint, coverage, cyclo, and a qa target that runs the full set. If you are vendoring the package, none of that affects you. If you are patching it, make qa is the documented entry point.

Editorial conclusion

Adopt bits-and-blooms/bloom if you are writing Go and need a probabilistic membership test in front of a storage layer, an index, or a dedup path, and you can state your element count before you start inserting. Do not adopt it if you need deletion, dynamic growth, or exact answers; the package gives you none of those, and the README says a Bloom filter is not a dynamic data structure. Before wiring it in, verify two things in your own code: that your capacity estimate is conservative, and that your false positive rate measured with EstimateFalsePositiveRate matches the value you passed to NewWithEstimates.

Frequently asked questions

Official sources

1. bits-and-blooms/bloom on GitHub
2. License: BSD-2-Clause
3. Project website
4. README
5. Releases