Bloom filter

Deep dive

How it works

In: a key (hashed to 64 bits) · Out: "definitely absent" or "probably present" · State: an m-bit array, no per-key storage · Cost: k bit probes per insert or query (one cache line when blocked); 9.6 bits per key at 1 % false positives

insert x: h1..hk -> set bits      query y: any bit 0 -> absent
m bits:  0 1 0 0 1 1 0 1 0 0 1 0 0 1 ...
            ^     ^ ^   ^       (x's k bits)

1. Size: m = ceil(-n·ln p / (ln 2)²), k = round((m/n)·ln 2).
2. Hash once to 64 or 128 bits; derive k indexes with double hashing g_i = h1 + i·h2 (Kirsch-Mitzenmacher). No measurable FPR loss versus k independent hashes.
3. FPR after inserting n keys: p ≈ (1 - e^{-kn/m})^k.
4. Blocked (split-block) variant: the first hash bits pick one 256- or 512-bit block (in one cache line); all k bits go inside that block. One miss per query, SIMD-friendly, slightly higher FPR at equal size (order of 10-20 % more bits for the same p at around 1 %).
5. Union of two filters with equal parameters = bitwise OR. Intersection by AND is an approximation.

Code

Split-block Bloom filter as specified for Apache Parquet: 256-bit blocks of eight 32-bit words, one bit set per word (k = 8).

const SALT: [u32; 8] = [
    0x47b6137b, 0x44974d91, 0x8824ad5b, 0xa2b7289d, 0x705495c7, 0x2df1424b, 0x9efc4947, 0x5c6bfb31,
];

#[repr(C, align(32))]
#[derive(Clone, Copy, Default)]
struct Block([u32; 8]);

pub struct SplitBlockBloom { blocks: Vec<Block> }

impl SplitBlockBloom {
    /// bits_per_key ~ 10 gives order of 1 % FPR for this variant.
    pub fn new(n_keys: usize, bits_per_key: usize) -> Self {
        let nblocks = (n_keys * bits_per_key / 256).max(1);
        SplitBlockBloom { blocks: vec![Block::default(); nblocks] }
    }
    fn block(&self, h: u64) -> usize {
        // Map the high 32 bits onto [0, nblocks) without division (Lemire reduction).
        (((h >> 32) * self.blocks.len() as u64) >> 32) as usize
    }
    fn mask(x: u32) -> [u32; 8] {
        let mut m = [0u32; 8];
        for i in 0..8 { m[i] = 1 << (x.wrapping_mul(SALT[i]) >> 27); } // top 5 bits pick 1 of 32 bits
        m
    }
    /// `h` must be a good 64-bit hash of the key (Parquet uses XXH64 with seed 0).
    pub fn insert(&mut self, h: u64) {
        let b = self.block(h);
        let m = Self::mask(h as u32);
        for i in 0..8 { self.blocks[b].0[i] |= m[i]; } // compiles to one 256-bit OR with AVX2
    }
    pub fn contains(&self, h: u64) -> bool {
        let blk = &self.blocks[self.block(h)].0;
        let m = Self::mask(h as u32);
        (0..8).all(|i| blk[i] & m[i] != 0)
    }
}

/// Classic sizing for a standard (unblocked) filter.
pub fn standard_params(n: f64, p: f64) -> (usize, u32) {
    let ln2 = std::f64::consts::LN_2;
    let m = (-n * p.ln() / (ln2 * ln2)).ceil();
    (m as usize, ((m / n) * ln2).round().max(1.0) as u32)
}

Complexity and constants

• Query cost: standard filter out of cache = up to k independent misses (early exit on a 0 bit helps for negatives: expected about 2 probes when half the bits are set). Blocked filter = one miss, order of 5-20 ns in cache, order of 100 ns from DRAM.
• Insert: same probes, writes only.
• Memory for 10^9 keys at 1 %: 1.2 GB.

Efficiency

• Cost: a blocked filter query is one cache miss, order of 5-20 ns in cache and order of 100 ns from DRAM; a standard filter costs up to k misses. Memory is 9.6 bits per key at 1 % and 14.4 bits at 0.1 % (table above). A filter hit saves a disk read of tens of µs to ms. Bound: memory latency.
• Levers:
  • blocked or split-block layout — k misses become 1 (Putze et al. 2007) — filters larger than cache
  • one hash plus double hashing — one hash computation instead of k, no measurable FPR loss (Kirsch-Mitzenmacher 2006) — always
  • batch queries with prefetch — overlaps the misses of many keys (order of) — bulk probes such as joins
  • static set → xor, binary fuse or Ribbon filter — about 30 % less memory than Bloom (RocksDB, Dillinger-Walzer 2021) — set known up front
  • per-file filters sized to the file — no overfilling, loaded and evicted with the data — LSM trees
• Naive → standard → state of the art:
  • search the set or read the disk · one lookup per query, ms on disk
  • standard Bloom filter · k probes, 1.44·log2(1/p) bits per key
  • split-block Bloom with SIMD, or Ribbon / binary fuse for static sets · 1 cache line per query, 1.13× to 1.23× of the minimum bits

Implementation notes

• Hash once, derive the rest. For blocked filters use high bits for the block, low bits for in-block positions, so they are independent.
• Store filters per data block/file (LSM per SST) so they can be loaded and evicted with the data; partition large filters to keep index blocks small (RocksDB partitioned filters).
• For prefetch-friendly batch queries, compute block addresses for a batch first, prefetch, then test.
• Use a u64 multiply-shift reduction instead of % for non-power-of-two sizes.
• Serialize the hash function and seed with the filter; a filter built with a different hash is garbage.
• RocksDB's newer filters (format_version=5) are cache-local Bloom filters; Ribbon filters save about 30 % memory at somewhat higher CPU cost.

Pitfalls

• Overfilling: at 2× the design n, a 1 % filter (k = 7) becomes about 15 %. Track the count and rebuild or chain filters.
• Using k ≠ optimal because "more hashes are safer": too many k increases FPR.
• Correlated hash functions (e.g. two seeds of a weak hash) inflate FPR silently; test empirical FPR on real keys.
• Hashing different representations of the same logical key (string vs bytes, endianness) on writer and reader.
• Counting Bloom filters with 4-bit counters can overflow; saturate and never decrement a saturated counter.

Variants and alternatives

In production

• Databases and storage: LevelDB and RocksDB (per-SST filters), Cassandra and HBase (SSTable/HFile filters), Apache Parquet (split-block filter in column chunks), PostgreSQL bloom index extension.
• Networking and web: Bitcoin BIP 37 (SPV client filters), Akamai (avoid caching one-hit wonders), Chrome (formerly Safe Browsing); Broder and Mitzenmacher survey network uses such as packet routing and P2P.
• Genomics: Bloom-filter-based de Bruijn graph for genome assembly (Chikhi and Rizk 2013).

Implementations

Sources

• Burton H. Bloom, Space/Time Trade-offs in Hash Coding with Allowable Errors, Communications of the ACM 13(7), 1970. paper
• Adam Kirsch, Michael Mitzenmacher, Less Hashing, Same Performance: Building a Better Bloom Filter, ESA 2006. paper
• Felix Putze, Peter Sanders, Johannes Singler, Cache-, Hash- and Space-Efficient Bloom Filters, WEA 2007.
• Andrei Broder, Michael Mitzenmacher, Network Applications of Bloom Filters: A Survey, Internet Mathematics 1(4), 2004. paper
• Peter C. Dillinger, Stefan Walzer, Ribbon filter: practically smaller than Bloom and Xor, arXiv 2103.02515, 2021. paper
• Apache Parquet format specification, BloomFilter.md. spec
• Rayan Chikhi, Guillaume Rizk, Space-efficient and exact de Bruijn graph representation based on a Bloom filter, Algorithms for Molecular Biology 8(22), 2013. paper