Bloom filters are ubiquitous in high-throughput systems. Redis uses them for cache prefetching. Cassandra and HBase use them to avoid expensive disk lookups. Chrome used them for safe browsing checks. Network routers use them for packet deduplication. These systems process millions of operations per second, and any lock contention is unacceptable.

The good news: Bloom filters have properties that make them surprisingly easy to parallelize. Bits only ever transition from 0 to 1, never back. Setting a bit that's already set is harmless. These properties unlock elegant lock-free implementations.

This chapter explores three approaches to concurrent Bloom filters, from simple locking to lock-free designs that scale linearly with core count.

Problem Statement

What We're Building

A thread-safe Bloom filter that allows multiple threads to add elements and check membership concurrently. A Bloom filter is a probabilistic data structure that can definitively say "not present" but only probabilistically say "might be present." False positives are possible; false negatives are not.

Required Operations

Thread-Safety Requirements

Data Structure Fundamentals

Before adding concurrency, let's understand how Bloom filters work and why their structure enables efficient parallelization.

Core Concepts

A Bloom filter consists of two components:

To add an element:

To check membership:

False Positive Analysis

After inserting n elements into a Bloom filter with m bits and k hash functions, the probability that a specific bit is still 0 is:

The false positive probability (all k bits are 1 by chance) is:

Optimal Hash Function Count

Given m bits and n expected elements, the optimal number of hash functions is:

With optimal k, the false positive rate is approximately:

Practical rule of thumb: 10 bits per element gives roughly 1% false positive rate.

How Bloom Filter Works

The diagram shows adding "apple" to a Bloom filter. Three hash functions produce positions 2, 5, and 9, and those bits are set to 1.

Single-Threaded Implementation

Concurrency Challenges

Making a Bloom filter thread-safe is easier than most data structures, but there are still important considerations.

Challenge 1: Setting Multiple Bits Atomically

An add() operation sets k bits. Do these k bit-sets need to be atomic as a group?

Key insight: This is actually fine for Bloom filters. The query returned "not present" during a concurrent insert. This is a valid linearization where the query happened before the insert completed. Since we never return false negatives for completed inserts, correctness is preserved.

Challenge 2: Read Visibility

When Thread 1 sets a bit, when does Thread 2 see it? Without proper memory ordering, Thread 2 might read a stale cached value.

Solution: Use atomic operations with appropriate memory ordering, or accept eventual visibility (often acceptable for Bloom filters).

Challenge 3: The clear() Operation

clear() resets all bits to 0 while other threads might be adding or querying. This can cause serious issues:

This is a false negative: "apple" was added but won't be found because two of its bits were cleared mid-insertion.

Solution: clear() must be exclusive. Use a read-write lock where adds/queries take read lock and clear takes write lock.

Consistency Model

The probabilistic nature of Bloom filters means we can tolerate relaxed consistency. A query might miss a concurrent insert (query linearized before insert), but this doesn't violate the no-false-negatives guarantee for completed inserts.

Approach 1: Synchronized Wrapper

The simplest approach wraps the entire Bloom filter with a read-write lock.

Implementation

Analysis

Problem with Java's BitSet: BitSet.set() and BitSet.get() are not thread-safe. Multiple threads calling set() concurrently can corrupt internal state. This forces us to use write lock even for reads if we want to avoid races.

Performance Characteristics

When to Use:

Approach 2: Segmented Locking

Divide the bit array into segments, each with its own lock. Adds and queries only lock the segments they touch.

Strategy: Segment-Based Locking

Handling Cross-Segment Operations

When an add operation needs to set bits in multiple segments, we must acquire all needed locks. To prevent deadlock, we always acquire locks in segment order (lowest to highest).

Implementation

Analysis

When to Use:

Approach 3: Lock-Free with AtomicLongArray

This approach eliminates locks entirely for add() and mightContain() operations using atomic bit manipulation.

Key Insight: Idempotent Bit Setting

The crucial observation that enables lock-free Bloom filters:

Setting a bit to 1 when it's already 1 is harmless.

In other data structures, concurrent modifications cause lost updates:

But in a Bloom filter:

The bit is set regardless of who "wins." There are no lost updates because 1 OR 1 = 1.

No ABA Problem

The ABA problem occurs when a value changes from A → B → A, and a CAS operation incorrectly succeeds because it only sees the final A. Bloom filters are immune because bits only ever transition 0 → 1, never back to 0 (except during clear(), which is exclusive).

Implementation Using AtomicLongArray

We store bits in an array of long values, where each long holds 64 bits. This allows efficient atomic operations on groups of bits.

Implementation

CAS Loop Visualization

Memory Ordering Considerations

For Bloom filters, we can use relaxed memory ordering for most operations:

The key insight: eventual visibility is acceptable. If a reader doesn't immediately see a just-set bit, the query returns "not present" for an in-progress insert. This is a valid linearization.

Analysis

When to Use:

Solution Comparison

Decision Flowchart

Recommendation

For most high-performance use cases, the lock-free implementation is the best choice:

Use synchronized or segmented approaches only when:

Complete Implementation

This section provides a production-ready lock-free Bloom filter with all features.

Demo

Expected Output: