BloomFilter

A probabilistic, mergeable Bloom filter: an approximate set whose merge is bitwise OR of the underlying bit array — trivially idempotent, commutative, and associative. A Bloom filter records whether elements might have been added and never produces false negatives (every added element always reports present), with a tunable false-positive rate.

Union-only — no removes. Removal would require clearing bits that may have been set by other elements, breaking the monotone-join property that makes this a CRDT. A Counting Bloom filter supports removes but loses idempotency (a bit decremented twice is wrong), so it does not fit the Quilted contract. If you need probabilistic removes, model the filter together with a GSet of tombstones.

Hash function. Kirsch–Mitzenmacher double-hashing using canonical MurmurHash3_x86_32 (Austin Appleby, public domain): h_i(x) = (h1 + i * h2) mod m where h1 = Murmur3(x, seed=0) and h2 = Murmur3(x, seed=h1), for i ∈ [0, k). See Kirsch & Mitzenmacher (2008) "Less Hashing, Same Performance". The hash is byte-identical on all Kotlin Multiplatform targets.

Merge compatibility. Two BloomFilter instances can only be pieced if they were created with the same bitCount and hashCount. Use create with the same expectedElements and falsePositiveRate on every replica.

Delta wire format. The delta returned by add is sparse: only the (at most hashCount) Long words that were modified are included on the wire as (wordIndex, wordValue) pairs. A full state (e.g. for anti-entropy) is encoded as a dense LongArray. The custom BloomFilterSerializer selects the format automatically based on density. See nonZeroWordCount and wordCount.

Samples

// Both replicas share the same configuration: 1 000 expected elements, 1% FP rate.
var replicaA = BloomFilter.create(expectedElements = 1_000, falsePositiveRate = 0.01)
var replicaB = BloomFilter.create(expectedElements = 1_000, falsePositiveRate = 0.01)

// Each replica adds its own element independently.
replicaA = replicaA.piece(replicaA.add("alice"))
replicaB = replicaB.piece(replicaB.add("bob"))

// After merging (bitwise OR), both elements are visible to either replica.
val merged = replicaA.piece(replicaB)
check(merged.mightContain("alice"))  // no false negatives
check(merged.mightContain("bob"))    // no false negatives

// Elements never added cannot report false negatives by definition,
// but they may occasionally produce a false positive (within the rate bound).
check(!replicaA.mightContain("carol") || true)  // might be a false positive — that's expected