Thread Safety for Concurrent Adds and Lookups

In one line

Concurrent add calls race when two threads set different bits in the same 64-bit word with plain read-modify-write. Use atomic compare-and-set on words (lock-free), an immutable filter swapped by reference, or striped/partitioned filters. Reads never need locks if writes are atomic.

0/4 · 0%

Think of it like this

Several people ticking boxes on one printed form. If two grab the same sheet, each copies it, ticks their box, and puts their copy back, one person's tick is lost. Each person needs to tick directly on the shared sheet in one motion.

Key ideas

01
The race: words[w] |= mask is read, OR, write. Thread A and B both read the same word, each sets a different bit, and the second write erases the first bit. That's a lost insert: a future false negative, the dangerous kind.
02
Lock-free fix: AtomicLongArray with a compare-and-set loop (getAndUpdate or a CAS loop). Bits are only ever set, so CAS retries are rare and never lose data. Guava's BloomFilter uses exactly this (since Guava 23).
03
Reads: mightContain concurrent with add may see some bits of an in-progress insert; the item might be reported absent until the add completes, which is acceptable because the add hadn't finished yet.
04
Immutable + swap: build a new filter off to the side (for example during a rebuild) and publish it with a volatile reference swap; readers never see a partial filter.
05
Partitioning: shard by hash into N sub-filters, each with its own lock, when heavy contention on hot words shows up (rare with large m).

Code & diagrams

AtomicBits.javajava

final class AtomicBits {
    private final AtomicLongArray words;
    AtomicBits(long numBits) { words = new AtomicLongArray((int) ((numBits + 63) >>> 6)); }

    boolean set(long pos) {                          // returns true if the bit was newly set
        int w = (int) (pos >>> 6);
        long mask = 1L << pos;
        long old, updated;
        do {
            old = words.get(w);
            if ((old & mask) != 0) return false;     // already set: nothing to do
            updated = old | mask;
        } while (!words.compareAndSet(w, old, updated));
        return true;
    }

    boolean get(long pos) { return (words.get((int) (pos >>> 6)) & (1L << pos)) != 0; }
}

Interview problem

The problem

100 threads adding and checking concurrently

100 application threads call add() and mightContain() concurrently on one filter. Design a thread-safe implementation and prove it doesn't lose inserts.

When it breaks

Shared non-thread-safe filter under concurrent writes

What you see

Rare lost bits cause rare false negatives: valid items rejected as "definitely absent", nearly impossible to reproduce in tests.

Fix & prevent

Atomic word updates (CAS) or a thread-safe library; stress-test concurrent inserts.

Explain it without notes

Why is a lost bit worse than an extra bit?

Practice

Write a stress test that shows lost inserts with a plain long array and none with the atomic version.

Trade-offs

↔
CAS adds a little overhead per write but keeps reads lock-free; immutable swaps avoid contention entirely at the cost of rebuilding.

Done when you can

I can make a Bloom filter thread-safe without global locks and test it under contention.

Command Palette