Summary

This PR unlocks concurrent read scaling by adding a production-ready Bloom filter to mutable and frozen in-memory segments.

Negative lookups can now bypass the B+tree entirely instead of entering its synchronized read path. This matters across the whole LSM read pipeline: lookups commonly probe several segments before finding a key, and most of those probes are misses.

The result is dramatically better parallel read and query scaling while preserving strong single-thread performance.

What Changed

• Added a fixed-size concurrent Bloom filter for in-memory segments.
• Applied it to both mutable and fully frozen segments.
• Covered inserts, updates, deletes, and WAL reconstruction.
• Added configurable memory usage through MutableSegmentBloomFilterBitsPerItem.
  • Default: 8
  • Valid range: 0–64
  • 0 disables the filter
• Introduced IKeyHasher<TKey> for comparer-compatible hashing.
• Added automatic hashers for supported primitive types, strings, and Memory<byte>.
• Added content-based hashing for Memory<byte> keys.
• Added factory methods for configuring the hasher and Bloom-filter size.
• Added validation for missing hashers and common comparer/hasher mismatches.
• Recorded the active hasher type and Bloom-filter setting in JSON metadata.
• Preserved compatibility with metadata written before these fields existed.

Concurrency Design

The filter uses three probes contained within one 64-bit word:

• Writers publish all bits with one Interlocked.Or.
• Readers inspect the word with one Volatile.Read.
• Publication happens before the corresponding B+Tree mutation.
• Concurrent readers never observe partially published entries.
• False positives fall through to the B+Tree as expected.
• Compatible hashers cannot produce false negatives.

The allocation is rounded to a power of two, keeping lookup indexing inexpensive. With the default one-million-item mutable segment and eight bits per item, the filter occupies approximately 1 MiB.

Performance

On the current 1M-profile Windows reference workload:

The complete P16 workload finished its measured phases in 10.6 seconds, compared with 56.8 seconds at P1.

These numbers demonstrate the branch’s parallel scaling rather than a controlled before/after comparison.

Compatibility

Known key types receive an appropriate hasher automatically.

Custom key types must provide an IKeyHasher<TKey>. Keys considered equal by the configured comparer must always produce the same hash code. Custom hashers must also be deterministic and safe for concurrent use.

The Bloom filter can be disabled when required:

factory.SetMutableSegmentBloomFilterBitsPerItem(0);

Verification

• Concurrent insertion coverage
• Custom comparer and compatible hasher coverage
• Memory<byte> content-equivalence coverage
• Disabled-filter coverage
• WAL reconstruction paths
• Metadata persistence and legacy metadata compatibility
• Option validation coverage
• Successful .NET 9 and .NET 10 Release builds