Module quotient_filter 

Quotient Filter for space-efficient dirty row tracking (bd-3fc1b).

A Quotient Filter is a compact approximate-membership data structure that supports insert, lookup, delete, and merge — unlike Bloom filters, which cannot delete.

How It Works

Each element is hashed to a p-bit fingerprint, split into:

• q-bit quotient (slot index): determines the canonical slot
• r-bit remainder: stored in the slot

Collisions are resolved by linear probing within a cluster. Three metadata bits per slot track the structure of runs and clusters.

Complexity

• Insert: O(1) amortized
• Lookup: O(1) amortized
• Delete: O(1) amortized
• Space: (r + 3) * 2^q bits ≈ 10% overhead above information-theoretic minimum

Use Case

For large virtualized lists (>1M rows) where only a small fraction (<1%) of rows are dirty, a Quotient Filter uses O(dirty_count) space vs O(total_rows) for a bitset.

Implementation Note

This implementation uses a simplified open-addressing scheme with (quotient, remainder) pairs stored directly, avoiding the complexity of the canonical 3-bit metadata approach while preserving the same API contract and space characteristics.

References

Bender et al. (2012): “Don’t Thrash: How to Cache Your Hash on Flash”

Structs

QuotientFilter

A Quotient Filter for approximate set membership with deletion support.

QuotientFilterConfig

Configuration for a Quotient Filter.