bloom filters (and the blocked variant)

written while porting gloom to zig for stream's jss segment archive. interactive companion: the "gloom field guide" artifact (claude.ai).

the contract

answers "have I seen this?" with: no = definitely no, yes = probably. no false negatives ever; false positives at a chosen rate p. stores membership in a few bits per item — 1M DIDs at p=0.001 is ~1.8 MB vs ~30 MB for the strings. classic form (Burton H. Bloom, CACM 1970 — named for him, not the flower; born of hyphenating text against a dictionary too big for core memory): one big bit array, k hash functions, k scattered probes per key.

why "blocked"

the classic form's k scattered probes = up to k cache misses, and on modern hardware the misses dominate the arithmetic. Putze/Sanders/Singler 2007 ("Cache-, Hash- and Space-Efficient Bloom Filters"): hash first to ONE 512-bit block — exactly a cache line — then confine all k probes inside it. one memory fetch per query. cost: blocks fill unevenly (Poisson), so realized fp is worse than the classic formula → compensate with a few % more blocks.

gloom's construction (jcalabro/gloom v0.1.0)

cache-line blocked + "one-hashing" (OHBF, Lu et al. 2015):

• ONE xxh3-128 per key. hi 64 bits → block via Lemire mulhi reduction (no modulo, no capacity cliff). lo 64 folded to u32 → intra-block probe seed.
• the 512-bit block is partitioned into k prime-width bands (k=9: 41+43+47+53+59+ 67+71+73+58 = 512); probe i = offset_i + seed % prime_i. distinct primes de-correlate the probes from one seed.
• OptimalParams grows block count ~12.5% at a time until the Poisson-exact realized fp ≤ target (cap 4× base). float-sensitive — when porting, golden-test against the reference implementation.
• serialization: version|k|numBlocks|count|words|crc32c(Castagnoli), all LE.

where it earns its keep (jetstream v2)

every sealed jss segment carries gloom filters in its footer: one per segment (sized to unique DIDs) + one per 4096-event block (all identically sized so the region is indexable by multiplication), p=0.001. per-DID archive queries ask the bloom before decompressing a block: "no" skips it for certain; "maybe" costs one decompression. correctness here is all-or-nothing: one wrong bit silently drops someone's data with no error anywhere. which is why stream's zig port (src/internal/gloom.zig) is verified byte-for-byte against Go output and passes upstream's VerifySealedMetadata (row-re-derived bloom membership) on files we write.

lineage

1970 Bloom (CACM) → 2006 Kirsch/Mitzenmacher double-hashing ("hash less") → 2007 blocked (Putze/Sanders/Singler) → 2015 OHBF prime partitions (Lu et al.) → 2019 xxh3 (Collet) → 2026 gloom (Jim Calabro, for the jetstream rewrite; same Jim as uscope, the from-scratch zig debugger).