Sign in Subscribe

The Bloom Filter Optimization Saga: The "Benign" Read That Wasn't

Shai Asher

• 11 min read
Share
The Bloom Filter Optimization Saga: The "Benign" Read That Wasn't

A Go Concurrency And Memory Model Deep Dive

In software engineering, some of the most insidious bugs are the ones that hide behind correct-looking code. This is a war story about a data race that slipped into a highly optimized, "thread-safe" Go Bloom filter. It’s a practical lesson in humility and a reminder that when it comes to concurrency, the Go race detector is the ultimate arbiter of truth.

Our Bloom filter (CacheOptimizedBloomFilter) was built for speed. It uses cache-line-aligned data structures, SIMD-enabled vectorized operations, and sync.Pool cuts down on allocations. For thread-safety, all bit-setting and bit-checking logic relies on the sync/atomic package.

The setBitCacheOptimized function, for example, is a model of concurrent-safe writing:

// bloomfilter.go
...
wordPtr := &cacheLine.words[op.WordIdx]
...
// Correctly uses an atomic CAS loop for thread-safe writes
for retry := 0; retry < maxRetries; retry++ {
    old := atomic.LoadUint64(wordPtr)
    new := old | mask
    if old == new || atomic.CompareAndSwapUint64(wordPtr, old, new) {
        break
    }
...

The read-side function, getBitCacheOptimized, is similarly safe, using atomic.LoadUint64 for all reads.

With this atomic-first design, the code should be perfectly race-free. But running our test suite with the -race flag told a different story.

The Smoking Gun: go test -race

The race detector immediately flagged a problem during our concurrent Add tests:

WARNING: DATA RACE
Write at 0x00c000255ec0 by goroutine 48:
  ...
  [github.com/shaia/BloomFilter.(*CacheOptimizedBloomFilter).setBitCacheOptimized](https://github.com/shaia/BloomFilter.(*CacheOptimizedBloomFilter).setBitCacheOptimized)()
      /mnt/c/Users/shaia/development/BloomFilter-thread-safety-2c/bloomfilter.go:503
  [github.com/shaia/BloomFilter.(*CacheOptimizedBloomFilter).Add](https://github.com/shaia/BloomFilter.(*CacheOptimizedBloomFilter).Add)()
      /mnt/c/Users/shaia/development/BloomFilter-thread-safety-2c/bloomfilter.go:95

Previous read at 0x00c000255ec0 by goroutine 50:
  [github.com/shaia/BloomFilter.(*CacheOptimizedBloomFilter).prefetchCacheLines](https://github.com/shaia/BloomFilter.(*CacheOptimizedBloomFilter).prefetchCacheLines)()
      /mnt/c/Users/shaia/development/BloomFilter-thread-safety-2c/bloomfilter.go:484
  [github.com/shaia/BloomFilter.(*CacheOptimizedBloomFilter).Add](https://github.com/shaia/BloomFilter.(*CacheOptimizedBloomFilter).Add)()
      /mnt/c/Users/shaia/development/BloomFilter-thread-safety-2c/bloomfilter.go:94

How the Race Detector Caught the Bug

That WARNING: DATA RACE output isn't just a suggestion; it's a definitive verdict from one of the most powerful tools in the Go ecosystem. But how does it work?

The Go race detector is a dynamic analysis tool, not a static one. This means it doesn't just read your code and guess about potential races. When you compile with the -race flag, the Go toolchain instruments your program with extra code that watches every single memory access as your test runs.

It's built on Google's ThreadSanitizer (TSan) library. Conceptually, it works by maintaining a "shadow memory" and "vector clocks" for each goroutine.

Here's a simple breakdown:

  1. Shadow Memory: For every byte of memory your program uses, the detector reserves 'shadow' memory to track which goroutines have read or written to it recently.
  2. Vector Clocks: This is a sophisticated data structure that tracks the "happens-before" relationship. Every goroutine has one, and it effectively tracks which synchronization events (like a mutex unlock or channel send) it has seen.
  3. The Check: When a goroutine (say, G48) tries to write to a memory address, the detector checks the shadow memory for that address. It sees that another goroutine (G50) recently read from it.
  4. The Verdict: The detector then compares the vector clocks of G48 and G50. It looks for a "happens-before" link between them. In our case, it found:
    • G50 (Read): Performed a non-atomic read on 0x00c000255ec0.
    • G48 (Write): Performed an atomic write on the same address.
    • Clocks: Because G50's read was non-atomic, it didn't update any synchronization state. The detector compared the clocks and found no sync event (like a mutex, channel, or matching atomic) establishing a happens-before link. The events were concurrent.
    • Result: A write concurrent with a read is a data race.

The most important thing to remember is that the race detector only finds races that actually happen during your test run. If your test isn't concurrent enough or doesn't hit the right (or wrong) timing, it might miss a race. This is why our TestRace... functions, which hammer the code from many goroutines, are so critical.

This powerful instrumentation isn't free. Programs run with -race are typically 10-20x slower and use 5-10x more memory. This is why it's a tool for testing, not production.

How to Write Tests That Catch Races

The race detector is a dynamic tool, which means it only finds races that actually happen during the test run. If your tests aren't concurrent, they won't trigger a race, and the detector will report nothing.

Your job when writing race tests is to be chaotic. You want to create a "worst-case scenario" of unlucky timing, maximizing the chance that two goroutines will access the same memory without proper synchronization.

Looking at our bloomfilter_race_test.go file, we can see a few key principles:

1. Create High Concurrency (The "Hammer") Don't just launch two goroutines. Launch 50, 100, or even 1000. The more goroutines you have competing for resources, the more likely the Go runtime's scheduler will interleave them in a way that exposes a race.

// TestRaceConcurrentAdds
numGoroutines := 100 // High number of goroutines
addsPerGoroutine := 100

var wg sync.WaitGroup
for g := 0; g < numGoroutines; g++ {
    wg.Add(1)
    go func(id int) { // Launch the goroutine
        defer wg.Done()
        for i := 0; i < addsPerGoroutine; i++ {
            bf.AddString(fmt.Sprintf("g%d_k%d", id, i))
        }
    }(g)
}
wg.Wait() // Wait for all 100 goroutines to finish

2. Test Mixed Operations (The "Chaos") A real-world application doesn't just have writes racing with writes. It has writes racing with reads, reads racing with metadata calls, and all of the above racing with operations like Clear().

Our TestRaceMixedReadWrite is a perfect example. It creates a cocktail of concurrent operations:

// TestRaceMixedReadWrite
numReaders := 50
numWriters := 50
opsPerGoroutine := 100

var wg sync.WaitGroup

// Start readers
for r := 0; r < numReaders; r++ {
    wg.Add(1)
    go func(id int) {
        defer wg.Done()
        for i := 0; i < opsPerGoroutine; i++ {
            _ = bf.ContainsString(fmt.Sprintf("initial_%d", i%500))
        }
    }(r)
}

// Start writers
for w := 0; w < numWriters; w++ {
    wg.Add(1)
    go func(id int) {
        defer wg.Done()
        for i := 0; i < opsPerGoroutine; i++ {
            bf.AddString(fmt.Sprintf("writer_%d_%d", id, i))
        }
    }(w)
}

wg.Wait()

3. Separate Race Tests with Build Tags Because race tests are heavy (due to the instrumentation) and can be slow, it's a best practice to keep them separate from your standard, fast unit tests.

You can do this by adding a build tag to the top of your _test.go file:

//go:build race

This tells the Go compiler to only include this file in the build if the race tag is provided.

  • go test ./... will run your fast unit tests (and skip this file).
  • go test -race ./... will enable the race detector and include this file, running your full concurrency suite.

By following these principles, you create the "perfect storm" that allows the race detector to do its job and find even the most subtle concurrency bugs.

Dissecting the Race

Now, let's apply that knowledge. The report is crystal clear:

  1. The Write (Goroutine 48): An atomic write is happening in setBitCacheOptimized on line 503. This is our atomic.CompareAndSwapUint64 operation.
  2. The Read (Goroutine 50): A non-atomic read is happening in prefetchCacheLines on line 484.

The race occurs within the Add function, which calls both of these functions:

// bloomfilter.go
func (bf *CacheOptimizedBloomFilter) Add(data []byte) {
	positions, cacheLineIndices := bf.getHashPositionsOptimized(data) // Line 93
	bf.prefetchCacheLines(cacheLineIndices)                            // Line 94 (The Read)
	bf.setBitCacheOptimized(positions)                                  // Line 95 (The Write)
}

One goroutine can be on line 94, executing prefetchCacheLines, while another is on line 95, executing setBitCacheOptimized.

Let's look at the "Previous read" function, prefetchCacheLines. Its sole purpose is a performance optimization: to hint to the CPU that it should load specific cache lines before they are actually needed.

// bloomfilter.go: The buggy implementation
func (bf *CacheOptimizedBloomFilter) prefetchCacheLines(cacheLineIndices []uint64) {
	// In Go, we can't directly issue prefetch instructions,
	// but we can hint to the runtime by touching memory
	for _, idx := range cacheLineIndices {
		if idx < bf.cacheLineCount {
			// This is the non-atomic read
			_ = bf.cacheLines[idx].words[0] // Line 484
		}
	}
}

The bug is subtle and stems from a misunderstanding. The developer (me, in this case) thought: "The real data-changing logic is atomic. This is just a harmless read to warm up the cache. It's not using the data, just 'touching' it. This can't cause a problem."

This assumption is wrong. But to understand why, we need to look deeper.

A Technical Deep Dive: The Go Memory Model

To understand why that "harmless" read was a critical bug, we must look beyond the sync/atomic package and at the formal specification that governs all concurrency in Go: The Go Memory Model.

The model doesn't define how memory is laid out (e.g., stack vs. heap). Instead, it defines the conditions under which a read in one goroutine is guaranteed to observe the effects of a write in another goroutine.

The Myth of Sequential Consistency

We write code like this and assume it runs in order, one line at a time:

a = 1
b = 2
c = a + b

This is called sequential consistency. The problem is that no modern hardware actually works this way. To make programs run incredibly fast, both the compiler and the CPU will break this assumption in two key ways:

  1. Instruction Reordering: The compiler and the CPU will both reorder your instructions if they can prove it doesn't change the result for a single-threaded program. The CPU might see a = 1 and b = 2 and execute them simultaneously because they don't depend on each other.
  2. CPU Caching: This is the "gremlin" that caused our Bloom filter bug. Every CPU core has its own private, high-speed cache (L1, L2). When Core 0 writes a = 1, it writes it to its own private cache. It does not write it directly to the main memory (RAM). This write can sit in Core 0's cache for a long time before it's "flushed." If Core 1 on a different CPU tries to read a, it will read the old, stale value from main memory.

The Go Memory Model is a contract. It tells you: "We know the hardware is a chaotic mess of reordering and caching. If you follow our rules (the "happens-before" rules), we guarantee we will force the hardware to behave."

The Core Concept: "Happens-Before"

The entire Go memory model is built on "happens-before."

If an event A happens-before an event B, then A's effects are guaranteed to be visible to B.

This "happens-before" relationship isn't just a rule about code order; it's a command that forces the hardware to synchronize. It inserts memory barriers that prevent reordering and force caches to flush or invalidate.

How to Establish "Happens-Before" (Synchronization)

You cannot just assume ordering. You must create it explicitly:

  1. Channels: A send on a channel happens-before the corresponding receive.
  2. Mutexes (sync.Mutex): An Unlock() happens-before the next Lock() returns.
  3. Atomic Operations (sync/atomic): An atomic.Store() happens-before a subsequent atomic.Load() on the same variable.

What is a Memory Barrier?

This is why sync/atomic and sync.Mutex are so important. They don't just protect a variable—they create memory barriers.

A memory barrier is an instruction to the CPU and compiler that enforces an ordering constraint.

  • mutex.Unlock(): This operation flushes all writes made by this goroutine to main memory.
  • mutex.Lock(): This operation invalidates the local cache, forcing the goroutine to read the "fresh" values from main memory.
  • atomic.Store(): This flushes the write.
  • atomic.Load(): This forces a fresh read.

This brings us to our bug. The non-atomic read (_ = bf.cacheLines[idx].words[0]) had no memory barrier. The CPU was free to:

  1. Reorder it: It could move this "prefetch" read to after the atomic write it was supposed to be helping!
  2. Use a Stale Cache: It would just read from its private cache, which was almost guaranteed to be out of date and would not trigger a "prefetch" of the new data.

By changing it to atomic.LoadUint64()We inserted a memory barrier, telling the compiler and CPU, "Do not reorder this operation, and actually go fetch the real value of this memory," which not only fixed the race but also correctly implemented the cache prefetch we wanted all along.out of date, we inserted a memory barrier, telling the compiler and CPU: "Do not reorder this operation, and actually go fetch the real value of this memory," which not only fixed the race but also correctly implemented the cache prefetch we wanted all along.

What is a Data Race?

The Go memory model gives a very precise definition:

A data race occurs when two goroutines access the same variable concurrently, and at least one of the accesses is a write.

Our bug is a textbook example:

  • The Access: The same memory address for bf.cacheLines[idx].words[0].
  • The Goroutines: Goroutine 48 (writing) and Goroutine 50 (reading).
  • The Concurrency: There was no "happens-before" relationship (no memory barrier) between the read and the write.
  • The Write: At least one access was a write (the atomic.CompareAndSwapUint64).

This leads us to the golden rule of sync/atomic:

If a variable is ever written to or read from using an atomic operation, all concurrent access to that variable must be atomic.

The Fix and Our Final Takeaway

Our fix was to change the non-atomic read to an atomic one, inserting the memory barrier we needed:

File: bloomfilter.go

// The fixed implementation
func (bf *CacheOptimizedBloomFilter) prefetchCacheLines(cacheLineIndices []uint64) {
	for _, idx := range cacheLineIndices {
		if idx < bf.cacheLineCount {
			// Atomically touch the cache line to bring it into cache
			// This inserts a memory barrier, fixing the race.
			_ = atomic.LoadUint64(&bf.cacheLines[idx].words[0])
		}
	}
}

This bug is a perfect example of the Law of Leaky Abstractions. In an attempt to optimize at the hardware level (CPU caching), we violated the language's memory model.

Breaking Down "The Leaky Abstraction"

That last sentence is the central thesis of this entire story. Let's break it down.

  1. "The Law of Leaky Abstractions": This is a concept from software engineer Joel Spolsky. It states that all non-trivial abstractions, to some degree, "leak" details of the underlying system they are trying to hide.
    • Abstraction: An abstraction simplifies a complex system by hiding its "under the hood" details. Go is an abstraction over machine code and CPU operations.
    • "Leaky": The "leak" happens when you're suddenly forced to understand those hidden details to fix a bug.
  2. "In an attempt to optimize at the hardware level (CPU caching)...": This is the "leak" in our story. The developer wasn't just thinking in Go. They were thinking about the physical hardware the Go code would run on—specifically, the CPU cache.
    • The Abstraction: The Go Memory Model is the language-level abstraction. It promises: "If you use our tools (channels, mutexes, sync/atomic), you don't have to worry about the messy hardware details of how different CPU cores talk to each other, how their caches are synchronized, or how they reorder instructions."
    • The "Hardware-Level" Optimization: The developer knew an atomic write is faster if the data is already in the CPU's L1/L2 cache. The prefetchCacheLines function was a clever trick to "warm up" the cache by "touching" the memory, signaling the CPU to pre-load that data.
  3. "...we violated the rules of the language's memory model.": This is the bug. In the quest for that hardware optimization, the developer broke the rules of the language-level abstraction.
    • The Language Rule (Go Memory Model): "If a variable is written to by one goroutine (even atomically), all other goroutines that read or write that same variable concurrently must also use a synchronization mechanism (i.e., be atomic)."
    • The Violation: The prefetchCacheLines function performed a non-atomic read (_ = bf.cacheLines[idx].words[0]). At the exact same time, another goroutine was performing an atomic write (atomic.CompareAndSwapUint64) on the very same piece of memory.

In short, The developer tried to "peek under the hood" of the Go language abstraction to play tricks with the CPU cache. But in doing so, they forgot to follow the abstraction's own rules. The abstraction "leaked" because to correctly implement the hardware optimization, the developer still had to follow the language's rules by making the prefetch-read atomic.

The lessons are clear:

  1. Trust the race detector. Always. go test -race is not optional.
  2. There is no "benign" data race. A race is a race.
  3. Atomic reads for atomic writes. If you write to a variable atomically, you must read from it atomically, even for "read-only" hints like prefetching.

📚 Further Reading & Resources

To truly master Go concurrency, you must read the official (and surprisingly short) specifications.

  • The Go Memory Model (Official Spec): The source of truth. Read it, then read it again.
    • https://golang.org/ref/mem
  • sync/atomic Package Documentation: The docs for the atomic package explicitly warn about mixing atomic and non-atomic access.
    • https://pkg.go.dev/sync/atomic
  • Introducing the Go Race Detector (Official Blog): Explains what the race detector looks for, which is a practical application of the memory model's rules.
    • https://go.dev/blog/race-detector

Sign up for more like this.

Enter your email
Subscribe