bloom

bloom is a Go implementation of Bloom filters, a probabilistic data structure for testing set membership with a tunable false-positive rate and no false negatives. It exposes a BloomFilter type built on top of the bits-and-blooms/bitset package, with helpers like NewWithEstimates and EstimateParameters that compute the optimal bit-array size (m) and hash-function count (k) for a target capacity and false-positive rate, plus EstimateFalsePositiveRate for empirically validating those parameters.

The filter supports adding and testing both []byte and string keys, merging and copying filters with matching parameters, and computing an approximate cardinality via ApproximatedSize. It implements Go’s standard serialization interfaces (JSON, gob, encoding.BinaryMarshaler, and raw WriteTo/ReadFrom streams), making it straightforward to persist a filter to disk or send it over the network. The library backs Bloom-filter usage in projects including Milvus, Weaviate, Grafana Loki, SpiceDB, and ProjectDiscovery’s scanning tools.

What You Get

• A BloomFilter type with Add/Test (and string variants) for probabilistic membership queries
• NewWithEstimates and EstimateParameters to size the filter for a target capacity and false-positive rate
• Merge, Copy, and Equal for combining and comparing filters that share matching m/k
• JSON, gob, and binary (WriteTo/ReadFrom) serialization for persisting or transmitting a filter

Common Use Cases

• Deduplicating high-volume log or event streams before expensive downstream processing
• Skipping unnecessary disk or network lookups in LSM-tree storage engines and databases
• Filtering already-seen URLs or requests in web crawlers and security scanners
• Caching membership checks in distributed systems to avoid costly round-trips

Under The Hood

Architecture bloom implements its entire public surface across two files: bloom.go, which exposes the BloomFilter type (holding bit-array size m, hash-function count k, and a *bitset.BitSet from the companion bits-and-blooms/bitset package) plus constructors like New, NewWithEstimates, From, and FromWithM; and murmur.go, an unexported digest128 hashing engine reimplemented from Sébastien Paolacci’s murmur3 library specifically to avoid heap allocation during Add/Test calls. Membership checks flow through baseHashes, which derives four 64-bit values per key via sum256, and location, which applies the Kirsch-Mitzenmacher double-hashing technique to derive k independent bit positions from those four values modulo m — delegating all actual bit storage and set operations to the underlying BitSet. The design is deliberately flat and single-responsibility: there is no internal layering to trace beyond hashing feeding into bit manipulation, which keeps the abstraction easy to reason about even though it offers little room for extension beyond the one BloomFilter type.

Tech Stack The library targets Go 1.16+ with exactly two declared dependencies in go.mod: bits-and-blooms/bitset (the underlying bit-array implementation) and twmb/murmur3 (used only for cross-validating the hand-rolled hashing in tests, per the murmur.go header comment — the runtime path never imports it). There is no web framework, ORM, or database layer to speak of; this is a foundational, dependency-light data structure package. Build and QA tasks run through a Makefile (make deps, make qa), and GitHub Actions CI (test.yml) exercises the full test suite across five Go versions (1.16 through 1.20) on Ubuntu, macOS, and Windows, giving strong cross-platform assurance for a package with such a small dependency footprint.

Code Quality bloom_test.go contains roughly 30 test functions covering constructors, false-positive estimation, merge validation, and JSON/gob/binary serialization round-trips, while murmur_test.go cross-checks the custom hashing implementation against reference values. Error handling is explicit rather than swallowed — Merge returns a descriptive fmt.Errorf when filter parameters (m, k) don’t match rather than panicking or silently proceeding. Naming follows idiomatic Go conventions throughout (exported PascalCase types/methods, lowercase unexported helpers), and #nosec annotations show awareness of static-analysis tooling even though no linter config file is checked into the repo. The CI matrix running across multiple Go versions and three operating systems is a strong quality signal for a package this size.

API Design The public API is intentionally minimal — a single BloomFilter type reached through a handful of well-named constructors (New, NewWithEstimates, From, FromWithM) and a small, symmetric set of accessor methods (Add/AddString, Test/TestString, TestAndAdd, TestOrAdd, Merge, Copy, Equal). Package-level GoDoc includes runnable code snippets for every common workflow — sizing a filter, adding string and binary keys, and validating false-positive rates — so a new user can go from go get to a working filter without consulting external docs. Serialization support (JSON, gob, binary, raw WriteTo/ReadFrom) is implemented via standard Go interfaces rather than custom methods, so it composes for free with existing tooling like encoding/json and net/rpc. The tradeoff is a narrow surface: users needing counting or scalable Bloom filter variants must look elsewhere, but for the classic fixed-size filter the ergonomics are strong.