Concurrent Bloom Filter — Middle Level¶

Table of Contents¶

1. Introduction
2. Where Junior Left Off
3. The Concurrency Spectrum
4. Atomic Bitsets
5. A Lock-Free Bloom Filter
6. Sharded Bloom Filters
7. Read-Heavy vs Write-Heavy Tuning
8. Counting Bloom Filters: Adding Delete
9. Observability in Production
10. Sliding-Window Filters
11. Snapshot, Restore, and Hot Reload
12. Hash Choice for Concurrent Workloads
13. Memory Layout and False Sharing
14. Library Internals That Matter at Middle Level
15. Pitfalls You Will Meet
16. Production Checklist
17. Self-Assessment
18. Summary
19. Further Reading

Introduction¶

Junior taught you what a Bloom filter is, how to build one, how to size it, and how to wrap a single library instance with sync.RWMutex so multiple goroutines can share it safely. That works — but it serialises every Add through one writer lock and tops out long before you have used the cores on a modern server.

Middle is about all the things you do after "the RWMutex wrapper is my bottleneck." There are three orthogonal axes to explore:

1. Replacing the lock with atomics. A bitset can be updated word-at-a-time with atomic.OrUint64 or CAS, eliminating the writer lock entirely. Tests become wait-free.
2. Sharding the filter. Split the bitset into N independent shards, each with its own lock or atomic word. Contention drops by 1/N at the cost of slightly trickier math for set operations.
3. Counting variants. Replace bits with small counters (typically 4 bits each) so you can decrement on Delete. Counting Bloom filters trade memory for the ability to forget.

Around all three you need observability: a Bloom filter without metrics is a black box, and the only way to know it is failing is to feel the latency rise.

After reading this you will:

• Be able to write a lock-free Bloom filter using sync/atomic.
• Pick between mutex, RWMutex, atomic, and sharded designs based on workload shape.
• Build a counting Bloom filter that supports Add, Test, and Delete.
• Expose Prometheus-style metrics: capacity, fill fraction, observed FPR, rebuild count.
• Run a sliding-window dedup filter with safe rotation.
• Avoid false sharing and other middle-level performance traps.
• Use library internals (BitSet, BaseHashes) for advanced patterns.

You do not need to know yet about partitioned Bloom filters, scalable Bloom filters, Cuckoo filters, or block-Bloom cache packing — those are senior and professional topics. Stay focused: Bloom + concurrency + observability is the middle level.

Where Junior Left Off¶

The junior solution looks like this:

type SafeFilter struct {
    mu sync.RWMutex
    f  *bloom.BloomFilter
}

It serialises every Add. Under a write-heavy workload — say 100k Add/sec from 16 goroutines — the writer lock becomes a single core's worth of throughput, no matter how many cores you have. A profile shows runtime.semawakeup and sync.(*Mutex).Lock in the top five.

The three solutions, in order of complexity:

In what follows we build each, measure each, and discuss when each is right.

The Concurrency Spectrum¶

Bloom filter concurrency divides cleanly along the update granularity axis:

• One global lock. Whole filter is the unit of mutual exclusion.
• One lock per shard. Each independent slice of the filter is its own unit.
• One atomic word. Each uint64 word in the bitset is its own unit. Atomic OR makes Adds wait-free; no lock at all.
• One bit. Theoretically the finest granularity; practically expressed as bit-level CAS, but each Add still touches a whole word so this reduces to atomic-word in practice.

The right granularity depends on:

• Workload mix. Read-heavy (>99% Test) suits RWMutex or atomic well; write-heavy suits shards or atomic.
• Filter size. A large filter spreads writes naturally across many words; contention is low without effort.
• Number of cores. More cores means more pressure to reduce contention.
• Latency sensitivity. A writer lock under contention has p99 spikes; atomic CAS retries have predictable per-operation cost.

Concrete rule of thumb:

• < 4 cores, < 10k ops/sec, < 1 MB filter: sync.RWMutex is fine.
• < 16 cores, 100k ops/sec, > 10 MB filter: atomic bitset.

• 16 cores, > 1M ops/sec, > 100 MB filter: sharded atomic.

Use the rule as a starting point; measure before believing it.

Atomic Bitsets¶

Go 1.19 added typed atomic operations: atomic.Uint64.Or, atomic.Uint64.And, atomic.Uint64.Add, etc. Prior to 1.19 you used atomic.CompareAndSwapUint64 in a loop. Go 1.23 added atomic.OrUint64(addr *uint64, mask uint64) as a package-level function. All do the same thing: an atomic read-modify-write that cannot lose bits.

Writing one bit, atomically¶

import "sync/atomic"

// Set bit i in bits[i/64].
func setBit(bits []uint64, i uint64) {
    wordIdx := i / 64
    mask := uint64(1) << (i % 64)
    atomic.OrUint64(&bits[wordIdx], mask)
}

The atomic OR fetches the current word value, ORs the mask in, and stores the result — all without an intervening read or write from any other goroutine. Two goroutines setting two different bits in the same word both succeed; neither bit is lost. This is exactly the fix for the lost-bit race we saw in junior.md.

Reading one bit, atomically¶

func testBit(bits []uint64, i uint64) bool {
    wordIdx := i / 64
    mask := uint64(1) << (i % 64)
    return atomic.LoadUint64(&bits[wordIdx])&mask != 0
}

An atomic Load reads a coherent snapshot of the word. The bit is either set or not at the time of the read; you cannot see a half-updated word.

Cost model¶

• atomic.OrUint64 is implemented as a hardware LOCK OR on x86 and an LL/SC loop on ARM. Cost: ~15–30 ns under no contention; rises sharply with contention as cache lines bounce between cores.
• atomic.LoadUint64 is a regular load with appropriate fences. Cost: 1–2 ns on x86; effectively free if the cache line is hot.

The whole reason atomics work for Bloom filters is that contention is rare in well-sized filters: the bitset is mostly half-full, so most Adds touch a different word from most other Adds. Tests are pure reads and never block.

A Lock-Free Bloom Filter¶

Let us build one from scratch. About 80 lines, no external dependencies.

package atomicbloom

import (
    "sync/atomic"

    "github.com/cespare/xxhash/v2"
)

type Filter struct {
    bits []uint64
    m    uint64
    k    uint64
}

func New(m, k uint64) *Filter {
    words := (m + 63) / 64
    return &Filter{
        bits: make([]uint64, words),
        m:    m,
        k:    k,
    }
}

func (f *Filter) hashes(key []byte) (uint64, uint64) {
    x := xxhash.Sum64(key)
    h1 := x
    h2 := x>>33 | x<<31 // rotate; ensure non-zero typically
    if h2 == 0 {
        h2 = 1
    }
    return h1, h2
}

func (f *Filter) Add(key []byte) {
    h1, h2 := f.hashes(key)
    for i := uint64(0); i < f.k; i++ {
        pos := (h1 + i*h2) % f.m
        wordIdx := pos / 64
        mask := uint64(1) << (pos % 64)
        atomic.OrUint64(&f.bits[wordIdx], mask)
    }
}

func (f *Filter) Test(key []byte) bool {
    h1, h2 := f.hashes(key)
    for i := uint64(0); i < f.k; i++ {
        pos := (h1 + i*h2) % f.m
        wordIdx := pos / 64
        mask := uint64(1) << (pos % 64)
        if atomic.LoadUint64(&f.bits[wordIdx])&mask == 0 {
            return false
        }
    }
    return true
}

func (f *Filter) Cap() uint64 { return f.m }
func (f *Filter) K() uint64   { return f.k }

This filter is:

• Safe to share across any number of goroutines. All bitset mutations are atomic.
• Wait-free for Tests. A Test never blocks.
• Almost wait-free for Adds. atomic.OrUint64 is a single hardware operation; it does not loop or retry, so Adds are also wait-free in the literal sense.
• Linearisable in a useful sense. If Add A completes-before Test B (per the Go memory model), B observes the bits A set.

Things this filter cannot do (yet)¶

• Marshal. No serialisation method.
• Estimate fill. ApproximatedSize would require summing bits.OnesCount64 across words — easy to add but allocating no temporary makes it tricky to do correctly under live writes (you would get a non-snapshotted count, which is fine for monitoring but not for equality).
• Delete. Bits cannot be unset without losing other keys' bits.
• Resize. Atomic operations on the slice header are out of scope; resizing requires a swap of the whole struct under a mutex.

For most middle-level needs, these omissions are acceptable. If you need marshal, you can atomic.Load each word in a loop and serialise the snapshot; concurrent updates during marshalling produce a valid filter (no torn words) that may include or exclude in-flight Adds — which is fine for a Bloom filter's semantics.

A benchmark¶

package atomicbloom

import (
    "fmt"
    "sync"
    "testing"
)

func BenchmarkConcurrentAdd(b *testing.B) {
    f := New(8_000_000, 7)
    b.ResetTimer()
    b.RunParallel(func(pb *testing.PB) {
        i := 0
        for pb.Next() {
            f.Add([]byte(fmt.Sprintf("k%d", i)))
            i++
        }
    })
}

func BenchmarkRWMutexAdd(b *testing.B) {
    var mu sync.RWMutex
    f := New(8_000_000, 7)
    b.ResetTimer()
    b.RunParallel(func(pb *testing.PB) {
        i := 0
        for pb.Next() {
            mu.Lock()
            f.Add([]byte(fmt.Sprintf("k%d", i)))
            mu.Unlock()
            i++
        }
    })
}

On an 8-core machine the atomic filter typically clocks 6–8x the throughput of the RWMutex-wrapped version under write-heavy load. Run it on your hardware; the ratio depends on core count and contention.

Sharded Bloom Filters¶

The other classic trick is sharding: keep N independent filters and route each key to one by hash(key) % N. Each shard has its own lock (or its own atomic bitset).

package sharded

import (
    "hash/fnv"
    "sync"

    "github.com/bits-and-blooms/bloom/v3"
)

const numShards = 32

type Filter struct {
    shards [numShards]shard
}

type shard struct {
    mu sync.RWMutex
    f  *bloom.BloomFilter
    _  [40]byte // pad to push next shard onto its own cache line
}

func New(n uint, p float64) *Filter {
    perShardN := n / numShards
    if perShardN < 1 {
        perShardN = 1
    }
    f := &Filter{}
    for i := range f.shards {
        f.shards[i].f = bloom.NewWithEstimates(perShardN, p)
    }
    return f
}

func (f *Filter) shardFor(key []byte) *shard {
    h := fnv.New32a()
    h.Write(key)
    return &f.shards[h.Sum32()%numShards]
}

func (f *Filter) Add(key []byte) {
    s := f.shardFor(key)
    s.mu.Lock()
    s.f.Add(key)
    s.mu.Unlock()
}

func (f *Filter) Test(key []byte) bool {
    s := f.shardFor(key)
    s.mu.RLock()
    defer s.mu.RUnlock()
    return s.f.Test(key)
}

Why 32 shards?¶

A good default for modern servers (16–64 cores). With too few shards you still contend; with too many you waste memory on per-shard overhead and lose cache locality. 32 is a popular choice in Cassandra, Caffeine, and other reference codebases.

The padding trick¶

_ [40]byte pads each shard to fill a 64-byte cache line (plus some). Without padding, two adjacent shards land in the same cache line, and Adds to either invalidate the other's cache copy — false sharing, the cardinal sin of multi-core data structures. With padding, each shard owns its cache line exclusively.

The padding size depends on the size of mu sync.RWMutex (24 bytes on amd64) and f *bloom.BloomFilter (8 bytes pointer). 24 + 8 = 32 bytes; pad to 64 with another 32 bytes — but I used 40 above to also include alignment margin. Profile on your platform: go test -bench with and without padding will show the cost of false sharing directly.

Sharded math¶

The combined behaviour of N shards each sized for n/N items at FPR p is — for the same Test — exactly p (the key lands in exactly one shard). So sizing is straightforward: per-shard n and per-shard p are what you choose.

The combined memory is N times the per-shard memory. So per-shard sizing for n/N items keeps total memory close to the un-sharded equivalent — there is a small constant overhead from N filter headers.

Union and Intersect are hard¶

Sharded filters complicate set operations. You cannot Union two sharded filters by Unioning each shard pair — different keys might route to different shard indices in the two filters if their hash families differ. If you need Union semantics, either:

• Make the two filters share the same shard-routing hash (pin a seed), or
• Skip sharding and use a single atomic filter.

In production this rarely bites because Union is mostly used for analytics merges, where you can afford a serialised pass.

Read-Heavy vs Write-Heavy Tuning¶

Three workloads, three best choices:

99% reads, 1% writes (typical negative cache)¶

• sync.RWMutex wrapper.
• Tests run in parallel; the occasional Add takes the write lock briefly.
• The RWMutex overhead per call is ~30 ns; for 99% reads this is negligible.

50/50 mix (event deduper)¶

• Atomic bitset. Both paths are wait-free.
• If memory pressure tolerates it, double the filter size to reduce contention probability per word.

Write-dominant (crawler URL frontier)¶

• Sharded + atomic per shard. Maximum throughput.
• Consider partitioning the work (each goroutine owns a shard's worth of work) so Adds rarely cross shards.

A heuristic: if you can express "this goroutine only writes to this slice of keys," you can shard along that boundary and have zero cross-shard contention.

Workload diagnosis with pprof¶

go test -cpuprofile=cpu.out -bench=.
go tool pprof -http=:8080 cpu.out

Look for runtime.sync.(*Mutex).Lock, runtime.sync.(*RWMutex).Lock, runtime.lock2, runtime.gopark. If those add up to more than 10% of CPU, your locks are the bottleneck — move to atomic or sharded.

go test -mutexprofile=mu.out -bench=.
go tool pprof -http=:8081 mu.out

The mutex profile shows contention time, not just CPU. A 5%-CPU mutex can be a 50%-wallclock mutex if many goroutines wait on it.

Counting Bloom Filters: Adding Delete¶

The basic Bloom filter cannot delete. The counting Bloom filter (CBF) can. The trick is to replace each bit with a small counter (typically 4 bits). Adding increments the k counters; Deleting decrements them; Testing checks they are all positive.

Why 4 bits?¶

A counter overflows when more than 2^bits - 1 keys hash to that position. For optimum k and a half-full filter, the expected number of Adds hitting any one counter is k * n / m ≈ ln 2 ≈ 0.693. The chance of a counter reaching 16 (i.e. overflowing 4 bits) is astronomically small — about 10^-12 for typical parameters. Most CBF implementations use 4 bits.

Implementation¶

package counting

import (
    "sync"

    "github.com/cespare/xxhash/v2"
)

// CountingFilter stores 4-bit counters packed two-per-byte.
type CountingFilter struct {
    mu       sync.Mutex
    counters []byte // each byte holds counters i*2 and i*2+1
    m        uint64
    k        uint64
}

func New(m, k uint64) *CountingFilter {
    return &CountingFilter{
        counters: make([]byte, (m+1)/2),
        m:        m,
        k:        k,
    }
}

func (c *CountingFilter) hashes(key []byte) (uint64, uint64) {
    x := xxhash.Sum64(key)
    h2 := x>>33 | x<<31
    if h2 == 0 {
        h2 = 1
    }
    return x, h2
}

func (c *CountingFilter) get(i uint64) uint8 {
    b := c.counters[i/2]
    if i%2 == 0 {
        return b & 0x0F
    }
    return b >> 4
}

func (c *CountingFilter) set(i uint64, v uint8) {
    v &= 0x0F
    b := &c.counters[i/2]
    if i%2 == 0 {
        *b = (*b & 0xF0) | v
    } else {
        *b = (*b & 0x0F) | (v << 4)
    }
}

func (c *CountingFilter) Add(key []byte) {
    h1, h2 := c.hashes(key)
    c.mu.Lock()
    defer c.mu.Unlock()
    for i := uint64(0); i < c.k; i++ {
        pos := (h1 + i*h2) % c.m
        v := c.get(pos)
        if v < 15 { // saturating counter
            c.set(pos, v+1)
        }
    }
}

func (c *CountingFilter) Delete(key []byte) {
    h1, h2 := c.hashes(key)
    c.mu.Lock()
    defer c.mu.Unlock()
    for i := uint64(0); i < c.k; i++ {
        pos := (h1 + i*h2) % c.m
        v := c.get(pos)
        if v > 0 && v < 15 { // do not decrement saturated counters
            c.set(pos, v-1)
        }
    }
}

func (c *CountingFilter) Test(key []byte) bool {
    h1, h2 := c.hashes(key)
    c.mu.Lock()
    defer c.mu.Unlock()
    for i := uint64(0); i < c.k; i++ {
        pos := (h1 + i*h2) % c.m
        if c.get(pos) == 0 {
            return false
        }
    }
    return true
}

The saturation rule¶

A counter that reaches 15 (the max for 4 bits) is saturated. We never increment past 15 and we never decrement from 15. Why? Because a saturated counter has lost track of the true number of Adds that hit it. Decrementing it would risk under-counting — a future Delete might bring it to 0 even though one of the original keys is still "present," producing a false negative.

The cost: a tiny fraction of bits become permanently 1. Empirically this barely affects FPR for reasonable parameters.

Concurrent counting¶

Notice that the example uses a sync.Mutex. CBFs are harder to make lock-free because counters are sub-byte (4 bits) and sync/atomic operates on whole bytes or larger. Options:

1. One mutex for the whole filter. Simplest; serialises everything. Fine for low rates.
2. One mutex per shard. Sharded CBF; same trade-offs as a sharded basic filter.
3. atomic.AddInt32 on a []int32 of counters. 4 bytes per counter (8x the memory) but lock-free.
4. CAS on whole bytes (two counters at a time). Pack two 4-bit counters in a byte; CAS the byte. Tricky — saturation logic in a CAS loop is fiddly.

Most production CBFs choose option 1 or 2.

Library support¶

bits-and-blooms/bloom/v3 does not include a counting Bloom filter. For Go, see github.com/seiflotfy/cuckoofilter for the closely related Cuckoo filter (next level), or roll your own as above. The willf/bloom organisation maintains a separate willf/cbloom repository that is less actively updated.

Observability in Production¶

A Bloom filter without metrics is a fire hazard. The four numbers you must always expose:

1. bloom_capacity_bits — m. Constant after construction; one gauge per filter.
2. bloom_fill_fraction — fraction of bits set, sampled periodically. Crosses 0.5 around the design n.
3. bloom_observed_fpr — rolling 1-minute observed false-positive rate, computed from Test calls that returned true and were subsequently disconfirmed by the slow path.
4. bloom_approximated_size — ApproximatedSize(). Useful for "are we full?"

In Go with prometheus/client_golang:

package metrics

import (
    "github.com/prometheus/client_golang/prometheus"
    "github.com/prometheus/client_golang/prometheus/promauto"
)

var (
    BloomCapacity = promauto.NewGaugeVec(prometheus.GaugeOpts{
        Name: "bloom_capacity_bits",
        Help: "Bitset size m of the Bloom filter.",
    }, []string{"name"})

    BloomFill = promauto.NewGaugeVec(prometheus.GaugeOpts{
        Name: "bloom_fill_fraction",
        Help: "Fraction of bits set in the filter (0..1).",
    }, []string{"name"})

    BloomFPR = promauto.NewGaugeVec(prometheus.GaugeOpts{
        Name: "bloom_observed_fpr",
        Help: "Observed false-positive rate (rolling window).",
    }, []string{"name"})

    BloomApprox = promauto.NewGaugeVec(prometheus.GaugeOpts{
        Name: "bloom_approximated_size",
        Help: "Swamidass-Baldi item count estimate.",
    }, []string{"name"})

    BloomTests = promauto.NewCounterVec(prometheus.CounterOpts{
        Name: "bloom_tests_total",
        Help: "Test calls. label result=hit|miss.",
    }, []string{"name", "result"})
)

A periodic updater:

import "time"

func StartGauges(name string, f *bloom.BloomFilter, hits, fpHits func() int64) {
    go func() {
        t := time.NewTicker(15 * time.Second)
        defer t.Stop()
        BloomCapacity.WithLabelValues(name).Set(float64(f.Cap()))
        for range t.C {
            fill := float64(f.BitSet().Count()) / float64(f.Cap())
            BloomFill.WithLabelValues(name).Set(fill)
            BloomApprox.WithLabelValues(name).Set(float64(f.ApproximatedSize()))
            h := hits()
            fp := fpHits()
            if h > 0 {
                BloomFPR.WithLabelValues(name).Set(float64(fp) / float64(h))
            }
        }
    }()
}

Alerts¶

The three alerts that catch 95% of incidents:

• bloom_fill_fraction > 0.7 for 10 min → "filter approaching design capacity, rebuild required."
• bloom_observed_fpr > 5 * target for 5 min → "FPR drifting; investigate."
• rate(bloom_tests_total{result="hit"}[5m]) / rate(bloom_tests_total[5m]) > 0.5 → "filter is no longer eliminating most lookups; cost-benefit broken."

A team running with these three alerts will not be surprised by their Bloom filter.

Sampling observed FPR¶

You cannot afford to confirm every Test against the slow path — that defeats the filter. Sample 1% of "maybe" answers:

import "math/rand/v2"

func (s *Service) Lookup(id string) (bool, error) {
    maybe := s.f.TestString(id)
    if !maybe {
        atomic.AddInt64(&s.misses, 1)
        return false, nil
    }
    // 1% sample: always confirm regardless of cache outcome, for FPR tracking.
    if rand.IntN(100) == 0 {
        exists, _ := s.db.Exists(id)
        atomic.AddInt64(&s.confirmedSamples, 1)
        if !exists {
            atomic.AddInt64(&s.falsePositiveSamples, 1)
        }
    }
    // Real path:
    exists, err := s.db.Exists(id)
    return exists, err
}

falsePositiveSamples / confirmedSamples is your observed FPR estimate. With a 1% sample at 10k queries/sec, you get 100 samples/sec — plenty of statistical power to detect drift within minutes.

Sliding-Window Filters¶

For dedup-with-finite-memory the two-window pattern from junior generalises to N-window:

package window

import (
    "sync"
    "time"

    "github.com/bits-and-blooms/bloom/v3"
)

type WindowFilter struct {
    mu       sync.RWMutex
    windows  []*bloom.BloomFilter
    interval time.Duration
    n        uint
    p        float64
}

func New(n uint, p float64, windows int, interval time.Duration) *WindowFilter {
    wf := &WindowFilter{
        windows:  make([]*bloom.BloomFilter, windows),
        interval: interval,
        n:        n,
        p:        p,
    }
    for i := range wf.windows {
        wf.windows[i] = bloom.NewWithEstimates(n, p)
    }
    go wf.rotateLoop()
    return wf
}

func (wf *WindowFilter) rotateLoop() {
    t := time.NewTicker(wf.interval)
    defer t.Stop()
    for range t.C {
        fresh := bloom.NewWithEstimates(wf.n, wf.p)
        wf.mu.Lock()
        // Shift: drop oldest, insert fresh at index 0.
        copy(wf.windows[1:], wf.windows[:len(wf.windows)-1])
        wf.windows[0] = fresh
        wf.mu.Unlock()
    }
}

func (wf *WindowFilter) Seen(key []byte) bool {
    wf.mu.RLock()
    for _, w := range wf.windows {
        if w.Test(key) {
            wf.mu.RUnlock()
            return true
        }
    }
    wf.mu.RUnlock()
    wf.mu.Lock()
    defer wf.mu.Unlock()
    // Double-check current window after lock upgrade.
    if wf.windows[0].Test(key) {
        return true
    }
    wf.windows[0].Add(key)
    return false
}

With windows = 24 and interval = time.Hour, you remember the last 24 hours of keys with hourly granularity. Memory is 24 * sizeof(one filter).

The rotation race¶

The rotation goroutine takes the write lock briefly. During that window, callers wait. For a 24-window setup that means one ~microsecond hiccup per hour — utterly invisible.

Why not one filter that you ClearAll?¶

A ClearAll at the rotation boundary creates a discontinuity: a key Added at 12:59:59 is forgotten at 13:00:00 sharp. The sliding-window pattern smooths that edge by keeping the previous window(s) available.

Snapshot, Restore, and Hot Reload¶

A Bloom filter's serialised form is small (just m bits plus headers). Persist it to keep the negative cache warm across restarts.

Snapshot¶

func snapshot(f *bloom.BloomFilter, path string) error {
    data, err := f.MarshalBinary()
    if err != nil {
        return err
    }
    tmp := path + ".tmp"
    if err := os.WriteFile(tmp, data, 0o600); err != nil {
        return err
    }
    return os.Rename(tmp, path)
}

The .tmp + rename pattern guarantees atomicity: a crash mid-write leaves the previous snapshot intact.

Restore¶

func restore(path string) (*bloom.BloomFilter, error) {
    data, err := os.ReadFile(path)
    if err != nil {
        return nil, err
    }
    f := &bloom.BloomFilter{}
    if err := f.UnmarshalBinary(data); err != nil {
        return nil, err
    }
    return f, nil
}

If the file is corrupt, UnmarshalBinary returns an error; fall back to a freshly constructed filter and accept the cold-start cost.

Hot reload¶

Suppose another process rebuilds the filter (e.g. a nightly batch job) and you want to swap it in without restarting your service.

type HotFilter struct {
    mu sync.RWMutex
    f  *bloom.BloomFilter
}

func (hf *HotFilter) Reload(path string) error {
    fresh, err := restore(path)
    if err != nil {
        return err
    }
    hf.mu.Lock()
    hf.f = fresh
    hf.mu.Unlock()
    return nil
}

func (hf *HotFilter) Test(k []byte) bool {
    hf.mu.RLock()
    defer hf.mu.RUnlock()
    return hf.f.Test(k)
}

The swap is atomic from a reader's perspective — once the pointer changes, all new RLocks see the new filter; in-flight RLocks finish on the old one.

Versioning the file format¶

Prefix your serialised form with a one-byte version tag:

const fileVersion = 2

func snapshotV2(f *bloom.BloomFilter, path string) error {
    data, err := f.MarshalBinary()
    if err != nil {
        return err
    }
    tmp := path + ".tmp"
    out := append([]byte{fileVersion}, data...)
    if err := os.WriteFile(tmp, out, 0o600); err != nil {
        return err
    }
    return os.Rename(tmp, path)
}

func restoreV2(path string) (*bloom.BloomFilter, error) {
    raw, err := os.ReadFile(path)
    if err != nil {
        return nil, err
    }
    if len(raw) < 1 {
        return nil, errors.New("empty snapshot")
    }
    switch raw[0] {
    case fileVersion:
        f := &bloom.BloomFilter{}
        err := f.UnmarshalBinary(raw[1:])
        return f, err
    default:
        return nil, fmt.Errorf("unknown snapshot version %d", raw[0])
    }
}

Future-you adding a new format will not break old snapshots, and old code reading new snapshots fails loudly rather than silently.

Hash Choice for Concurrent Workloads¶

The library uses MurmurHash3. Three reasons to consider alternatives:

1. Speed. xxhash (cespare/xxhash/v2) is ~2x faster on long inputs.
2. Determinism across processes. Library Murmur uses a fixed seed, so two processes hash the same. hash/maphash uses a per-process random seed — not compatible across processes.
3. Adversarial inputs. If attackers can choose inputs to collide on bits, you need a keyed hash with a private seed: hash/maphash (per-process seed) or siphash (keyed, designed against hash flooding).

For concurrent use the hash itself is irrelevant to safety — hashes are pure functions and pure functions are always safe. The choice matters for cross-process compatibility and adversarial robustness.

A keyed-hash custom filter¶

For an adversarial setting, a roll-your-own based on maphash with a private seed:

package keyedbloom

import (
    "hash/maphash"
    "sync/atomic"
)

type Filter struct {
    bits []uint64
    m    uint64
    k    uint64
    seed maphash.Seed
}

func New(m, k uint64, seed maphash.Seed) *Filter {
    return &Filter{
        bits: make([]uint64, (m+63)/64),
        m:    m,
        k:    k,
        seed: seed,
    }
}

func (f *Filter) hashes(key []byte) (uint64, uint64) {
    h := maphash.Bytes(f.seed, key)
    h2 := h>>33 | h<<31
    if h2 == 0 {
        h2 = 1
    }
    return h, h2
}

func (f *Filter) Add(key []byte) {
    h1, h2 := f.hashes(key)
    for i := uint64(0); i < f.k; i++ {
        pos := (h1 + i*h2) % f.m
        atomic.OrUint64(&f.bits[pos/64], 1<<(pos%64))
    }
}

func (f *Filter) Test(key []byte) bool {
    h1, h2 := f.hashes(key)
    for i := uint64(0); i < f.k; i++ {
        pos := (h1 + i*h2) % f.m
        if atomic.LoadUint64(&f.bits[pos/64])&(1<<(pos%64)) == 0 {
            return false
        }
    }
    return true
}

Each process generates its seed at startup (maphash.MakeSeed()), keeping it secret. An attacker cannot precompute colliding keys without knowing the seed.

When to roll your own at all¶

The library covers 95% of needs. Roll your own when:

• You need atomic Adds without a mutex (the library is not internally atomic).
• You need a keyed hash for adversarial robustness.
• You need an embeddable filter without external dependencies.
• You need to teach the algorithm.

Otherwise, use the library.

Memory Layout and False Sharing¶

Two pieces of data placed in the same 64-byte cache line invalidate each other when either is written. For a Bloom filter this matters in two places:

Place 1: Two filters in one struct¶

type Service struct {
    usersFilter   *bloom.BloomFilter
    productsFilter *bloom.BloomFilter
}

Both pointers fit in 16 bytes; the struct fits in one cache line. The pointers are not the problem — the bitsets they point to are far away in memory. The pointers themselves are read-mostly. This layout is fine.

Place 2: Per-shard mutex¶

Recall:

type shard struct {
    mu sync.RWMutex
    f  *bloom.BloomFilter
    _  [40]byte
}

Without the padding, f.shards[0].mu and f.shards[1].mu share a cache line. A writer locking shard 0 invalidates the cache copy of shard 1's mutex for every other goroutine — even goroutines that are only reading shard 1's mutex must reload it. This shows up as runtime.lock2 taking ~3x its expected time.

The padding moves each shard's mutex onto its own line. The 40-byte choice was sloppy; a robust formulation:

import "golang.org/x/sys/cpu"

type shard struct {
    _  cpu.CacheLinePad
    mu sync.RWMutex
    f  *bloom.BloomFilter
    _  cpu.CacheLinePad
}

cpu.CacheLinePad is a platform-aware padding type. Two pads bracket each shard's fields, guaranteeing no neighbour can share the line.

Place 3: Atomic-bitset adjacent fields¶

If you embed your atomic bitset in a struct alongside other frequently-written fields, false sharing returns:

type Filter struct {
    count uint64  // <- written on every Add
    bits  []uint64
}

count and bits are next to each other; on each Add you increment count AND OR a bit in some bits[i]. If bits[0] happens to share a cache line with count, every Add invalidates count across cores. Pad them apart, or move count out of the hot struct.

Library Internals That Matter at Middle Level¶

A few bits-and-blooms/bloom/v3 internals you should understand.

BaseHashes¶

The library computes four 64-bit hashes per key (baseHashes), then derives the k positions as (h[0] + i*h[1] + i^2 * h[2] + i^3 * h[3]) mod m. The quadratic and cubic terms beyond simple double hashing give better independence between positions, particularly for small m where double hashing's correlation becomes visible.

BitSet.Count¶

Uses math/bits.OnesCount64 per word. Cost: O(m / 64). For a 100 MB filter, ~100k word reads — a millisecond. Fine for periodic gauges, expensive for per-call use.

MarshalBinary¶

Serialises m, k, and the bitset words in little-endian. No version byte; the format has been stable since v3.0.

Union¶

f.Union(g) requires f.Cap() == g.Cap() && f.K() == g.K(). Returns a new filter whose bitset is the bitwise OR. Adds in either input become Adds in the output.

Intersect¶

f.Intersect(g) returns the bitwise AND. The resulting filter answers "yes" only when both inputs would. Intersection of Bloom filters does not give a clean intersection of the underlying sets — there are extra false positives unless both inputs were constructed from the same hash family. Use with care.

Add and Test are not lock-protected¶

The library makes no attempt at concurrency safety. The README explicitly says so. Any concurrent use requires an external wrapper.

Pitfalls You Will Meet¶

Pitfall: forgetting atomic.LoadUint64 on the read side¶

If you use atomic.OrUint64 on writes but plain bits[i] & mask on reads, the read can return a stale value. Go's memory model guarantees nothing about non-atomic reads of words that other goroutines write atomically. Always pair: atomic write, atomic read.

Pitfall: sharding by len(key) rather than hash(key)¶

return &f.shards[len(key)%numShards] // WRONG

This distributes keys by length, not by content. All 16-byte UUIDs land in the same shard. Use a hash.

Pitfall: ApproximatedSize() under heavy live writes¶

Count() reads each word without atomics; concurrent writes can produce a slightly inaccurate count. For a gauge, that is fine. For a condition (e.g. "rebuild when n >= threshold"), use a separately maintained atomic.Int64 counter incremented on each Add.

Pitfall: forgetting to handle nil filter during reload¶

if hf.f == nil {
    return false
}
return hf.f.Test(k)

A nil filter (e.g. after a failed restore) must produce a sane answer — "false" is conventional. Better: never let hf.f be nil; assign a fresh empty filter on construction.

Pitfall: per-shard sizing for total n¶

Each shard should be sized for n / numShards, not for the full n. Sizing each shard for the full n wastes 16x memory in a 16-shard setup.

Pitfall: rebuilding under load¶

A naive "drain all Tests, rebuild" forces a pause. Always:

1. Build the new filter in the background.
2. Atomically swap the pointer.
3. Garbage-collect the old filter.

Never lock-and-rebuild in place.

Pitfall: trusting ApproximatedSize at high fill¶

At >70% fill, the estimator's variance balloons. Use fill fraction (Count() / Cap()) instead for "should I rebuild" decisions.

Pitfall: counter under-decrement in CBF¶

If your code calls Delete(key) for a key that was never Added, you decrement counters that other keys are relying on. Result: false negatives. Always pair Delete with a prior Test or maintain authoritative bookkeeping outside the filter.

Production Checklist¶

• Workload classified: read-heavy / write-heavy / mixed.
• Wrapper chosen: Mutex, RWMutex, atomic, or sharded — based on classification.
• go test -race runs on a representative concurrent test.
• Padding applied to shard structs (cpu.CacheLinePad).
• Prometheus metrics for capacity, fill, observed FPR, hits/misses.
• Alerts on fill > 0.7 and FPR > 5x target.
• Sampled-confirmation path implemented for observed-FPR measurement.
• Snapshot/restore tested with corruption injection.
• Hot reload swap is atomic from readers' perspective.
• Rebuild path documented and tested.
• Cache-aside ordering enforced (truth before filter on writes).
• Filter never written before the source of truth on registration.
• CBF (if used) handles saturation with the no-decrement rule.

A team running this checklist will not have Bloom-filter incidents above the noise floor.

Self-Assessment¶

• I can implement a lock-free Bloom filter using sync/atomic.
• I can explain why atomic.OrUint64 eliminates the lost-bit race.
• I can write a sharded Bloom filter with proper cache-line padding.
• I can implement a 4-bit counting Bloom filter with saturation handling.
• I can expose a Bloom filter as four useful Prometheus metrics.
• I can implement a sliding-window filter with atomic rotation.
• I can snapshot and restore a filter with versioned serialisation.
• I can pick between MurmurHash3, xxhash, and hash/maphash for a given use case.
• I can identify and fix false sharing in a sharded filter benchmark.
• I can recite the cache-aside ordering rule from memory.

Summary¶

The basic library plus a sync.RWMutex ships your first concurrent Bloom filter. From there, the middle-level toolkit gives you four upgrades:

• Atomic bitsets for lock-free Add/Test.
• Sharded filters for write-heavy contention reduction.
• Counting variants when you need Delete.
• Observability so you know when the filter is failing you.

Each tool is independent of the others; you mix as needed. Workload shape (read/write ratio, ops/sec, core count, latency sensitivity) drives the choice. Production hygiene — alerts, snapshots, hot reload, rebuild paths — is non-negotiable.

Senior.md takes the next architectural step: partitioned Bloom filters, scalable Bloom filters, Cuckoo filters, and integrating filters with the larger storage stack. Once you have shipped one middle-level filter into production, you are ready.

Further Reading¶

• Fan, L., Cao, P., Almeida, J., & Broder, A. (2000). Summary Cache: A Scalable Wide-Area Web Cache Sharing Protocol. The original Counting Bloom Filter paper.
• Mitzenmacher, M., & Upfal, E. Probability and Computing, sections on Bloom filters and Cuckoo hashing.
• Bonomi, F., Mitzenmacher, M., Panigrahy, R., Singh, S., & Varghese, G. (2006). An Improved Construction for Counting Bloom Filters. d-left counting filters.
• bits-and-blooms/bloom/v3 source.
• cespare/xxhash/v2 README and benchmarks.
• Go memory model: https://go.dev/ref/mem.
• sync/atomic package documentation.
• Brendan Gregg's blog on false sharing.
• Designing Data-Intensive Applications, chapter 3.

Diagrams & Visual Aids¶

A single atomic OR on a contended word¶

Two goroutines want to set bit 3 and bit 5 of word0.

Time | A                            | B                            | word0
-----|------------------------------|------------------------------|-----------
 t1  | atomic.OrUint64(&w, 1<<3)    |                              | 0x00 -> 0x08
 t2  |                              | atomic.OrUint64(&w, 1<<5)    | 0x08 -> 0x28

Final word0 = 0x28. Both bits set. No race.

Each OrUint64 is one indivisible hardware operation. The cache line bounces between cores, but neither bit is lost.

Sharded filter routing¶

key "alice" -- hash --> 0xA9F3 -- mod 32 --> shard 19
                                              |
                                              v
                                         ┌─────────┐
                                         │ shard19 │ -- own mutex, own bitset
                                         └─────────┘

key "bob"   -- hash --> 0xB6C2 -- mod 32 --> shard 2
                                              |
                                              v
                                         ┌─────────┐
                                         │ shard02 │ -- own mutex, own bitset
                                         └─────────┘

Different keys typically route to different shards; concurrent Adds rarely contend.

Counting Bloom filter cell layout¶

counters[]:  byte 0      byte 1      byte 2      byte 3
             ┌──┬──┐    ┌──┬──┐    ┌──┬──┐    ┌──┬──┐
             │c0│c1│    │c2│c3│    │c4│c5│    │c6│c7│
             └──┴──┘    └──┴──┘    └──┴──┘    └──┴──┘
              4b 4b      4b 4b      4b 4b      4b 4b

8 counters in 4 bytes. Total memory: m/2 bytes (vs m/8 for a basic filter — 4x).

Sliding-window filter rotation¶

Time  | windows[0] | windows[1] | windows[2] | windows[3] |
------|------------|------------|------------|------------|
 t=0  | fresh      | fresh      | fresh      | fresh      |
 t=1h | fresh      | hour0      | fresh      | fresh      |
 t=2h | fresh      | hour1      | hour0      | fresh      |
 t=3h | fresh      | hour2      | hour1      | hour0      |
 t=4h | fresh      | hour3      | hour2      | hour1      |  hour0 dropped

Each tick: shift down, drop oldest, install fresh at index 0. The Seen check ORs over all windows.

Mutex profile of an under-contended RWMutex¶

60%  bloom.(*BloomFilter).Add
20%  sync.(*RWMutex).Lock
10%  sync.(*RWMutex).Unlock
 5%  runtime.gopark
 5%  other

The 30% in Lock+Unlock means you are losing throughput to lock acquisition. Move to atomic or sharded.

Cache-line layout: padded shards¶

cache line 0:  [pad ][ shard0 (mu, f) ][pad ]
cache line 1:  [pad ][ shard1 (mu, f) ][pad ]
cache line 2:  [pad ][ shard2 (mu, f) ][pad ]
...

Each shard occupies its own cache line. Writes to shard 0's mutex do not invalidate shard 1.

Observed-FPR sampling flow¶

Test(k) -- mayExist? --no-->  return false
                       -yes-> 
                              99%  --> use cache decision (no DB sample)
                               1%  --> sample: confirm via DB
                                       confirmed real? -> increment hits
                                       confirmed not?  -> increment hits AND fpHits

observedFPR = fpHits / hits over the sampled subset, refreshed every 15s.

Deep Dive: Building a Production-Ready Atomic Bloom Filter¶

The 80-line atomic Bloom filter earlier in this file is correct but minimal. A production-quality one adds:

• Marshal and Unmarshal.
• An Add that returns "was already maybe present" (atomic TestAndAdd analogue).
• A safe ApproximatedSize that does not require quiescence.
• A ClearAll that is atomic.
• An optional Hasher injection so callers can swap MurmurHash3 for xxhash, maphash, or siphash.

package atomicbloom

import (
    "encoding/binary"
    "errors"
    "io"
    "math"
    "math/bits"
    "sync/atomic"

    "github.com/cespare/xxhash/v2"
)

type Hasher func(key []byte) (uint64, uint64)

func defaultHasher(key []byte) (uint64, uint64) {
    x := xxhash.Sum64(key)
    h2 := x>>33 | x<<31
    if h2 == 0 {
        h2 = 1
    }
    return x, h2
}

type Filter struct {
    bits   []uint64
    m      uint64
    k      uint64
    hasher Hasher
}

func New(m, k uint64) *Filter {
    return NewWithHasher(m, k, defaultHasher)
}

func NewWithHasher(m, k uint64, h Hasher) *Filter {
    if m == 0 || k == 0 {
        panic("m and k must be positive")
    }
    return &Filter{
        bits:   make([]uint64, (m+63)/64),
        m:      m,
        k:      k,
        hasher: h,
    }
}

func NewWithEstimates(n uint64, p float64) *Filter {
    m, k := EstimateParameters(n, p)
    return New(m, k)
}

func EstimateParameters(n uint64, p float64) (m, k uint64) {
    m = uint64(math.Ceil(-float64(n) * math.Log(p) / (math.Ln2 * math.Ln2)))
    k = uint64(math.Round(float64(m) / float64(n) * math.Ln2))
    if k < 1 {
        k = 1
    }
    return
}

func (f *Filter) positions(h1, h2 uint64) func(int) uint64 {
    return func(i int) uint64 {
        return (h1 + uint64(i)*h2) % f.m
    }
}

func (f *Filter) Add(key []byte) {
    h1, h2 := f.hasher(key)
    pos := f.positions(h1, h2)
    for i := uint64(0); i < f.k; i++ {
        p := pos(int(i))
        atomic.OrUint64(&f.bits[p/64], 1<<(p%64))
    }
}

func (f *Filter) Test(key []byte) bool {
    h1, h2 := f.hasher(key)
    pos := f.positions(h1, h2)
    for i := uint64(0); i < f.k; i++ {
        p := pos(int(i))
        if atomic.LoadUint64(&f.bits[p/64])&(1<<(p%64)) == 0 {
            return false
        }
    }
    return true
}

// TestAndAdd reports whether the key was already (probably) present and then
// unconditionally adds it. Per-bit atomic, but the *combined* test+set is not
// linearisable; callers must reason about the relaxed semantics.
func (f *Filter) TestAndAdd(key []byte) bool {
    h1, h2 := f.hasher(key)
    pos := f.positions(h1, h2)
    allSet := true
    for i := uint64(0); i < f.k; i++ {
        p := pos(int(i))
        mask := uint64(1) << (p % 64)
        old := atomic.LoadUint64(&f.bits[p/64])
        if old&mask == 0 {
            allSet = false
        }
        atomic.OrUint64(&f.bits[p/64], mask)
    }
    return allSet
}

func (f *Filter) ClearAll() {
    for i := range f.bits {
        atomic.StoreUint64(&f.bits[i], 0)
    }
}

// ApproximatedSize uses the Swamidass-Baldi estimator. Safe to call concurrently;
// returns an estimate based on the current snapshot of bits.
func (f *Filter) ApproximatedSize() uint64 {
    set := uint64(0)
    for i := range f.bits {
        set += uint64(bits.OnesCount64(atomic.LoadUint64(&f.bits[i])))
    }
    if set == 0 {
        return 0
    }
    if set == f.m {
        return math.MaxUint64
    }
    return uint64(-float64(f.m) / float64(f.k) * math.Log(1.0-float64(set)/float64(f.m)))
}

func (f *Filter) FillFraction() float64 {
    set := uint64(0)
    for i := range f.bits {
        set += uint64(bits.OnesCount64(atomic.LoadUint64(&f.bits[i])))
    }
    return float64(set) / float64(f.m)
}

// WriteTo serialises a snapshot of the filter. Safe under concurrent writes;
// the snapshot is consistent at the word level (no torn words) but may include
// or exclude in-flight Adds.
func (f *Filter) WriteTo(w io.Writer) (int64, error) {
    var header [16]byte
    binary.LittleEndian.PutUint64(header[0:8], f.m)
    binary.LittleEndian.PutUint64(header[8:16], f.k)
    n, err := w.Write(header[:])
    written := int64(n)
    if err != nil {
        return written, err
    }
    buf := make([]byte, 8)
    for i := range f.bits {
        binary.LittleEndian.PutUint64(buf, atomic.LoadUint64(&f.bits[i]))
        n, err = w.Write(buf)
        written += int64(n)
        if err != nil {
            return written, err
        }
    }
    return written, nil
}

func ReadFrom(r io.Reader) (*Filter, int64, error) {
    var header [16]byte
    n, err := io.ReadFull(r, header[:])
    read := int64(n)
    if err != nil {
        return nil, read, err
    }
    m := binary.LittleEndian.Uint64(header[0:8])
    k := binary.LittleEndian.Uint64(header[8:16])
    if m == 0 || k == 0 {
        return nil, read, errors.New("invalid filter header")
    }
    f := New(m, k)
    buf := make([]byte, 8)
    for i := range f.bits {
        n, err = io.ReadFull(r, buf)
        read += int64(n)
        if err != nil {
            return nil, read, err
        }
        f.bits[i] = binary.LittleEndian.Uint64(buf)
    }
    return f, read, nil
}