@zakkster/lite-filter

A zero-GC approximate-membership filter FAMILY under one LiteFilter<K> surface, COMPLETE at 7 members: Bloom (the add-only reference), CountingBloom (deletable, ~4x space), BlockedBloom (one cache miss per query, at a higher measured FPR), Cuckoo (deletable, fingerprint-based, fail-closed at capacity), Quotient (deletable, mergeable + resizable, fail-closed at the load ceiling), XorFilter (the STATIC member, ~9.85 bits/item, built once + immutable), and BinaryFuse (the SMALLEST member, ~9.0 bits/item, static + built once) -- one-line swappable, tree-shakeable to a single filter, with a shipped bench that measures ACTUAL vs THEORETICAL false-positive rate on your own keys instead of trusting a formula.

The membership filter the ecosystem was missing

You want to answer "have I seen this key?" -- dedup, set membership, cache admission, "is this id probably in the set?" -- and a JS Set is the obvious tool. But a Set stores every key by value or reference, allocates per entry, resizes by copying, and costs tens of bytes per key plus GC pressure. A probabilistic filter answers the SAME membership question in a handful of bits per entry, at fixed preallocated memory with no per-op allocation, a small bounded tunable false-positive rate, and zero false negatives.

And choosing the right probabilistic structure is a real, hard-to-navigate decision with no universal winner -- Bloom is the baseline but cannot delete and is not the smallest; Cuckoo and Counting Bloom delete but cost more; XOR and Binary Fuse are near the space lower bound but are static. lite-filter puts that whole family behind ONE identical interface (a one-line constructor swap) plus the bench that tells you which one to pick: measured FPR vs theoretical, bits/item, add/query ns, on YOUR keys.

npm install @zakkster/lite-filter

import { Bloom } from '@zakkster/lite-filter';

const seen = new Bloom(100000, { fpp: 0.01 });   // sized for 100k items at a 1% target

seen.add('user:42');
seen.add('user:99');

seen.mightContain('user:42');   // true  -- always (added keys never read false)
seen.mightContain('user:7');    // false -- (or, ~1% of the time, a false positive)
seen.has('user:99');            // true  -- has() is the alias of mightContain
seen.size;                      // 2     -- adds recorded
seen.fpp();                     // the fill-derived FPR estimate (a formula, not a measurement)

One LiteFilter<K> surface, add/mightContain/has/size/capacity/fpp/clear, zero allocation on every hot path after construction. Integer keys opt into a strict-zero-alloc backing. All 7 members -- Bloom, CountingBloom, BlockedBloom, Cuckoo, Quotient, XorFilter, and BinaryFuse -- are shipped named exports (XorFilter and BinaryFuse are static -- built via <Member>.from(keys), sharing the query surface); sideEffects: false drops whichever you do not import.

Then measure, do not guess:

npm run bench     # measured vs theoretical FPR (% over), bits/item, add/query ns, per workload

Table of contents

• Why this exists
• What you get
• The Bloom filter, in brief
• The members
  • CountingBloom -- the deletable member
  • BlockedBloom -- the cache-local member
  • Cuckoo -- the fingerprint member
  • Quotient -- the mergeable + resizable member
  • XorFilter -- the space-optimal static member
  • BinaryFuse -- the smallest static member
• API reference
  • Construction
  • The surface
  • Integer keys -- strict zero-alloc
  • Stats -- opt-in runtime counters
  • Snapshot -- dump / restore
  • The bench tool
  • Constants
• Composability
• Zero-GC design notes
• Design decisions worth knowing
• Testing
• What this is not
• Ecosystem
• License

Why this exists

Every membership question in JS defaults to Set, and Set is exact -- which is exactly the problem when you do not need exactness. A dedup over a stream of a billion ids, a "have I crawled this URL", a cache admission gate keeping one-hit wonders out -- none of these need to store the keys, only to answer "probably yes / definitely no". Storing the keys is the cost you are trying to avoid.

A Bloom filter answers that in ~1.44 * log2(1/fpp) bits per item -- about 9.6 bits (1.2 bytes) per item at a 1% false-positive rate, versus tens of bytes per key for a Set, and with no per-op allocation and no GC churn. The tradeoff is a bounded, tunable rate of false POSITIVES; there are never false negatives.

The reason this is a FAMILY and not one filter: the right structure depends on your axes (target fpp, space, delete support, static-vs-incremental, query speed, mergeability), and there is no universal winner. lite-filter grows one member per release under one surface, and ships the bench so you measure the tradeoff on your own keys rather than copying a number from a paper.

What you get

• One uniform surface. add / mightContain / has / size / count / capacity / fpp / clear, identical across every present and future member.
• Zero-GC hot path. One preallocated Uint32Array, sized once, reused forever. add and mightContain allocate nothing on the keys:'int' and string paths.
• Fail-closed everywhere. Impossible sizing, a bad int key, a remove on an add-only member, or a corrupt snapshot all throw a [lite-filter]-tagged Error.
• The honesty bench. Measured vs theoretical FPR as % over theoretical, checked against a real Set oracle, over four seeded workloads.
• Snapshot round-trip. dump() / restore() -- the typed array IS the serial form; structurally-cloneable and JSON-safe; fail-closed on any mismatch.
• Types + tree-shaking. Filter.d.ts types LiteFilter<K>; sideEffects: false.

The Bloom filter, in brief

A Bloom filter is one bit array of m bits plus k hash functions. To add a key, compute k positions and set those k bits. To query, compute the same k positions and return true only if ALL k bits are set.

• If a key was added, its k bits are set, so mightContain returns true -- always. There are no false negatives.
• If a key was never added, its k bits might still all happen to be set by OTHER keys -- a false positive, whose probability is bounded by the configured fpp and rises as the filter fills.

lite-filter derives m and k from your (capacity, fpp):

m = ceil(-n * ln(fpp) / ln(2)^2)      bits
k = round((m / n) * ln(2))            hash positions (clamped >= 1)

All k positions come from just TWO base hashes via enhanced double hashing (pos_i = (h1 + i*h2) mod m), so a probe needs zero scratch storage. Bloom cannot delete -- clearing a key's bits would corrupt every other key sharing one of them -- so remove() throws (use CountingBloom when you need deletes).

The members

| Member | Deletes? | Space | Status | Import | | --- | --- | --- | --- | --- | | Bloom | no (remove throws) | 1x (~1.44 log2(1/fpp) bits/item) | SHIPPED (v0.1.0) | import { Bloom } from '@zakkster/lite-filter' | | CountingBloom | yes (remove -> boolean) | ~4x Bloom (4-bit counters) | SHIPPED (v0.2.0) | import { CountingBloom } from '@zakkster/lite-filter' | | BlockedBloom | no (remove throws) | 1x Bloom (one 512-bit cache line per key) | SHIPPED (v0.3.0) | import { BlockedBloom } from '@zakkster/lite-filter' | | Cuckoo | yes (remove -> boolean) | ~2x Bloom at fpp 0.01 (byte-aligned fingerprints) | SHIPPED (v0.4.0) | import { Cuckoo } from '@zakkster/lite-filter' | | Quotient | yes (remove -> boolean; also merge + resize) | ~23 bits/item at fpp 0.01 (byte-aligned slot words + guard) | SHIPPED (v0.5.0) | import { Quotient } from '@zakkster/lite-filter' | | XorFilter | no (STATIC: add/remove/clear throw) | ~9.85 bits/item at fpp 0.01 (~1.23x the space bound) | SHIPPED (v0.6.0) | import { XorFilter } from '@zakkster/lite-filter' | | BinaryFuse | no (STATIC: add/remove/clear throw) | ~9.04 bits/item at fpp 0.01, n=1e6 (~1.13x the space bound) | SHIPPED (v1.0.0) | import { BinaryFuse } from '@zakkster/lite-filter' |

The five MUTABLE members implement the same LiteFilter<K> surface, so a member is a one-line constructor swap; the only surface differences are remove (member-specific) and Quotient's extra merge / resize cold paths. XorFilter and BinaryFuse are the two STATIC members: they share the query surface (mightContain / has / size / fpp / dump) but are built via <Member>.from(keys) and throw on add / remove / clear (a static filter has no mutation surface -- rebuild to change membership). BinaryFuse is the SMALLEST member -- a construction swap over XorFilter (overlapping fuse segments) that packs to ~1.13x (vs ~1.23x) and builds faster; prefer it over XorFilter for new static sets.

CountingBloom replaces Bloom's single bit per position with a 4-bit SATURATING counter (two packed per byte, one Uint8Array). add increments the k counters, remove decrements them, and mightContain is true iff every probed counter is nonzero. This buys a real remove(key): boolean at ~4x a plain Bloom's space. Its false-positive rate tracks the SAME formula as Bloom (the bench confirms the measured % over theoretical matches Bloom's across all four workloads).

import { CountingBloom } from '@zakkster/lite-filter';

const f = new CountingBloom(100000, { fpp: 0.01, keys: 'int' });
f.add(42);
f.remove(42);            // true  -- a real delete; returns false if the key is absent
f.mightContain(42);      // false -- gone

remove runs two passes with no scratch storage: pass 1 verifies every probed counter is nonzero (else it returns false and mutates NOTHING), pass 2 decrements each counter in 1..14. Two caveats are inherent to a Counting Bloom and stated, not hidden:

• Only remove keys you actually added. If a never-added key is a false positive (all k counters nonzero via other keys), remove will decrement REAL keys and can cause a later false negative (decisions/0009).
• A saturated counter (15) is clamped forever -- never incremented past 15, never decremented (decisions/0008) -- so a key routed only through saturated counters can stick present after removal. At a 1% fpp this is negligibly rare. The multiplicity readout is deferred (decisions/0010) because saturation makes it an over-estimate.

BlockedBloom partitions the bit array into fixed 512-bit BLOCKS -- 16 x 32-bit words = 64 bytes, one cache line (decisions/0012). Every key is routed to ONE block (from its first base hash), and all k bits live inside that block. So a mightContain touches ONE cache line regardless of k -- the throughput win. It is add-only like Bloom: remove() throws.

import { BlockedBloom } from '@zakkster/lite-filter';

const f = new BlockedBloom(100000, { fpp: 0.01, keys: 'int' });
f.add(42);
f.mightContain(42);      // true -- one cache line touched, regardless of k

The caveat is inherent and MEASURED, never hidden (decisions/0013): confining a key to one block loses the cross-block independence the textbook formula assumes, so the MEASURED false-positive rate runs OVER a plain Bloom's for the SAME bits/item. fpp() reports the plain closed-form as a labeled FLOOR, not a prediction. npm run bench prints Bloom vs BlockedBloom side by side so the trade is the first thing you see: on this repo's uniform int workload, BlockedBloom query ns is LOWER than Bloom's while its measured FPR is HIGHER (e.g. ~0.014 vs ~0.010 at the same ~9.6 bits/item). To hit a target measured FPR, raise the configured fpp slightly -- never trust the floor as the delivered rate.

Cuckoo (Fan, Andersen, Kaminsky & Mitzenmacher, CoNEXT 2014) stores a small NONZERO fingerprint per key in one of TWO candidate buckets of b = 4 slots (decisions/0014). The second bucket is i2 = (i1 XOR hash(fp)) & (nb-1) -- an INVOLUTION, so an evicted fingerprint recovers its alternate bucket from the fingerprint alone. add scans both buckets and, on a full pair, KICKS a random victim to its alternate bucket up to 500 times (a single scalar victim register, zero allocation). It DELETES via a real remove(key): boolean.

import { Cuckoo } from '@zakkster/lite-filter';

const f = new Cuckoo(100000, { fpp: 0.01, keys: 'int' });
f.add(42);
f.remove(42);            // true  -- a real delete; false if the key is absent
f.mightContain(42);      // false -- gone

Two honest edges, both surfaced, never hidden:

• Fail-closed at capacity (decisions/0014). When 500 kicks are exhausted the table is full and add THROWS a [lite-filter] Error -- it never silently drops a fingerprint (which would be a false negative). Headroom is observable via saturation (size / maxLoad, where maxLoad === nb*b), an UPPER BOUND -- an add below it may still throw once the 500-kick budget is exhausted (decisions/0026). Size up when it throws.
• Only remove keys you inserted (decisions/0015). Deleting a NEVER-INSERTED key whose fingerprint collides with a real key clears that other key's slot -> a later false negative for it. This is sharper than a Counting Bloom delete (which decrements a shared counter); a Cuckoo delete removes a concrete fingerprint instance.

The measure-vs-configured hook. The fingerprint width is f = ceil(log2(8/fpp)) byte-aligned UP to an 8- or 16-bit slot. At fpp = 0.01, f rounds up to a 16-bit slot, so the delivered FPR is the width-quantized 2b/2^f = 8/1024 ~ 0.0078 -- BELOW the configured 0.01, at ~2x a plain Bloom's bytes/item (~21 vs ~9.6 at ~76% load). fpp() reports that width-quantized rate once non-empty (not a fill-varying estimate); npm run bench prints Bloom vs Cuckoo side by side so the byte-align quantization is visible. Below fpp = 8/65536 (~0.000122) the width would exceed 16 bits and construction throws.

Quotient (Bender et al., VLDB 2012) is ONE open-addressed LINEAR slot array (decisions/0016). A key's 32-bit hash splits into a QUOTIENT (the home slot index, high bits) and a REMAINDER (stored, low r bits); same-home keys form a RUN, adjacent runs a CLUSTER under linear probing, encoded by 3 METADATA bits per slot -- is_occupied, is_continuation, is_shifted -- packed in the low 3 bits of each byte-aligned word (remainder in the high bits: word = (remainder << 3) | metadata). A slot is EMPTY iff all three metadata bits are 0 (remainder 0 is a legal remainder). It DELETES via a real remove(key): boolean, and -- uniquely in the family so far -- MERGES and RESIZES.

import { Quotient } from '@zakkster/lite-filter';

const f = new Quotient(100000, { fpp: 0.01, keys: 'int' });
f.add(42);
f.remove(42);            // true  -- a real delete; false if the key is absent
f.resize(400000);        // grow (or shrink); membership + size preserved, no keys needed
f.merge(other);          // union with an identically-configured Quotient (exact additive size)

remove repairs the metadata by REBUILDING the affected cluster through the verified insert path (collect the surviving (home, remainder) pairs, clear, re-insert), so the shift-back repair is correct by construction -- not a bespoke bit fixup. The cluster scratch is preallocated, so remove is zero-allocation.

merge and resize are COLD paths (they may allocate; the hot paths stay zero-alloc). Both reconstruct each element's identity as (quotient << r) | remainder -- WITHOUT the original keys -- because the fingerprint bit budget p = q0 + r is FIXED for the filter's lifetime. Both grow and shrink preserve membership (0 false negatives) and exact size. The honest limit: the discarded high hash bits cannot be recovered, so a quotient never carries more than q0 bits of entropy -- resizing LARGER adds empty headroom (lower load) but not new quotient entropy. merge rejects fail-closed unless the other filter's seed, r, p, and keys mode all match.

Two honest edges, both surfaced, never hidden:

• Fail-closed at the load ceiling (decisions/0016). add THROWS a [lite-filter] Error when occupancy would exceed floor(0.90 * nslots) OR the linear cluster shift would run off the end -- both checked BEFORE any write, so a thrown add is a BYTE-IDENTICAL no-op (no already-added key is dropped). A Quotient stores MULTIPLICITY (it does not dedup, like Cuckoo), so a duplicate-heavy stream fills toward the ceiling and fails closed, never a silent drop. Headroom is observable via saturation (size / maxLoad, where maxLoad === floor(0.90 * nslots) and tracks resize()), an UPPER BOUND -- an add below it may still throw on a cluster-shift run-off (decisions/0026).
• Only remove keys you inserted (decisions/0017). Deleting a NEVER-INSERTED key whose (quotient, remainder) collides with a real key clears that other key's slot -> a later false negative for it (a constructed non-vacuous example is in decisions/0017).

The measure-vs-configured hook. The remainder width is r = ceil(log2(1/fpp)), and the slot word is r + 3 bits byte-aligned to a Uint8Array (r <= 5) or Uint16Array (r 6..13). At fpp = 0.01, r = 7, so the delivered FPR is the remainder-quantized load * 2^-r -- BELOW the configured 0.01 (measured ~0.0060 at ~0.55 load), at ~23 bits/item (16-bit slot words + guard). fpp() reports that quantized rate once non-empty; npm run bench prints Bloom vs Quotient side by side. Below fpp = 1/2^13 (~0.000122) the slot word would exceed 16 bits and construction throws; a q + r budget past the 32-bit base hash also throws.

XorFilter (Graf & Lemire, ACM JEA 2020) is the family's FIRST STATIC member: it is built ONCE from a KNOWN key set and frozen. It approaches the ~1.23x information-theoretic space lower bound by peeling a 3-uniform hypergraph -- each key touches 3 fingerprint slots (one per equal segment), and the slots are assigned so a key's three slots XOR to its fingerprint.

import { XorFilter } from '@zakkster/lite-filter';

const keys = [];
for (let i = 0; i < 1_000_000; i++) keys.push(i);
const f = XorFilter.from(keys, { fpp: 0.01, keys: 'int' }); // build once (or .build)
f.mightContain(42);        // true  -- 0 false negatives, guaranteed by the complete peel
f.mightContain(9_999_999); // usually false; a true is a false positive (~2^-8)
f.size;                    // 1000000 (the deduped key count)
f.add(1);                  // throws [lite-filter] -- a static filter has no mutation

It is IMMUTABLE (decisions/0019). There is no public constructor (new XorFilter() throws), and add / remove / clear all throw a [lite-filter]-tagged Error. Rebuild with XorFilter.from(newKeys) to change membership. It shares the query surface (mightContain / has / size / count / capacity / fpp / stats / dump).

Keys are a SET (decisions/0018). from() DEDUPES its input (contrast Cuckoo / Quotient, which store multiplicity), so size === capacity === |Set(keys)|.

The measure-vs-configured hook. The fingerprint is byte-aligned: fw = 8 when fpp >= 2^-8 (~0.0039), else 16; fpp < 2^-16 throws (the 16-bit floor, inclusive at 2^-16). The delivered FPR is the width-quantized 2^-fw -- BELOW the configured 0.01 at fw = 8 (MEASURED ~0.0039 over 1e6 disjoint probes), at ~9.84 bits/item for n=1e6 (LEANER than Cuckoo ~21 / Quotient ~23, competitive with Bloom ~9.6 at a lower FPR). fpp() reports the quantized rate; npm run bench prints Bloom vs XOR side by side.

Fail-closed build (decisions/0018). On a peel failure the build RESEEDS deterministically (seed ^ (attempt * 0x9e3779b1)) up to 100 times, then throws [lite-filter] -- NEVER a partial build. A partial build would fail OPEN (silent false negatives on real keys), so the build asserts the peel stack reached n BEFORE any fingerprint is assigned. Exhaustion is expected only for a DEGENERATE set (many keys that String()-encode identically). Build is a cold path (the peeling scaffold allocates); the query is strictly zero-alloc.

BinaryFuse (Graf & Lemire, "Binary Fuse Filters: Fast and Smaller Than Xor Filters", ACM JEA 2022) is the 7th and FINAL member -- a construction-algorithm SWAP over XorFilter, not a new surface. It reuses the same peel + reverse-assign, the same immutable surface, and the same snapshot integrity, but replaces XOR's 3 equal DISJOINT segments with 3 OVERLAPPING fuse segments selected by a multiply-shift, packing to ~1.13x (vs ~1.23x) and building faster.

import { BinaryFuse } from '@zakkster/lite-filter';

const keys = [];
for (let i = 0; i < 1_000_000; i++) keys.push(i);
const f = BinaryFuse.from(keys, { fpp: 0.01, keys: 'int' }); // build once (or .build)
f.mightContain(42);        // true  -- 0 false negatives, guaranteed by the complete peel
f.mightContain(9_999_999); // usually false; a true is a false positive (~2^-8)
f.size;                    // 1000000 (the deduped key count)
f.add(1);                  // throws [lite-filter] -- a static filter has no mutation

How it differs from XOR. A key's first slot is mulhiU32(h, scl) in [0, scl) (scl = segCount * segLen, a Lemire multiply-shift); the next two are one and two segments further, each perturbed within-segment. Because segLen is a power of two, the three slots always land in three DISTINCT consecutive segments -- the peeling XOR trick is never self-corrupted. Sizing is pinned to the paper / the FastFilter reference (arity 3): segLen = clamp(2^floor(log(n)/log(3.33) + 2.25), 4, 262144), segCount = max(1, ceil(round(n * sizeFactor) / segLen) - 2) with sizeFactor = max(1.125, 0.875 + 0.25*log(1e6)/log(n)) (decisions/0022).

It is IMMUTABLE and keys are a SET, exactly like XorFilter: no public constructor (new BinaryFuse() throws), add / remove / clear all throw, and from() DEDUPES so size === capacity === |Set(keys)|.

The measure-vs-configured hook. Same byte-aligned width door (fw = 8 when fpp >= 2^-8, else 16; fpp < 2^-16 throws) and same width-quantized 2^-fw FPR. MEASURED at n=1e6, fpp=0.01: slots/item 1.1305 (1.13 at 2dp), 9.04 bits/item (LEANER than XOR's ~9.85), measured FPR ~0.0039. npm run bench prints XOR vs BinaryFuse side by side.

Fail-closed build + restore. Same deterministic reseed (x100 then throw) and the same sp !== n peel-completeness fail-OPEN guard. restore() RE-DERIVES the whole segment geometry from the count (_bfDims(count)), rejecting an internally-inconsistent-but-legal sl/sc/fp.length triple, before the chk integrity check catches a keys-mode/seed flip.

API reference

Construction

new Bloom(capacity: number, options?: {
  fpp?: number;      // target false-positive probability in (0, 1). Default 0.01.
  seed?: number;     // hash seed (32-bit-coercible). Default is a fixed constant.
  keys?: 'int';      // opt into the strict-zero-alloc 32-bit-integer backing.
  stats?: boolean;   // mint the per-instance stats holder. OFF by default.
})

The five MUTABLE members share this new Member(capacity, options) shape. The two static members XorFilter and BinaryFuse are built from a key set instead, taking the same options (minus capacity, which they derive from the deduped set):

XorFilter.from(iterable: Iterable<K>, options?: {
  fpp?: number;      // target FPP; fw = 8 (fpp >= 2^-8) or 16; fpp < 2^-16 throws.
  seed?: number;     // hash seed. Default is a fixed constant.
  keys?: 'int';      // opt into the strict-zero-alloc 32-bit-integer backing.
  stats?: boolean;   // mint the per-instance stats holder. OFF by default.
})            // -> XorFilter;  .build is an alias.  new XorFilter() throws.

BinaryFuse.from(iterable: Iterable<K>, options?: { /* identical options */ })
              // -> BinaryFuse; .build is an alias. new BinaryFuse() throws.

Fail-closed doors (all throw a [lite-filter]-tagged Error): capacity non-integer or < 1; fpp not in the open interval (0, 1) (so <= 0 and >= 1 both throw); a bit count that would overflow a safe typed-array length; an unknown keys or stats value (with a did-you-mean hint). For XorFilter / BinaryFuse also: an empty key set, fpp < 2^-16, and 100 exhausted peel attempts (a degenerate key set).

The surface

| Method | Returns | Notes | | --- | --- | --- | | add(key) | void / never | Record a key. Zero-alloc on int + string keys. XorFilter / BinaryFuse: static, throws [lite-filter]. | | mightContain(key) | boolean | The query. NO false negatives; false positives bounded by fpp. | | has(key) | boolean | The sole alias of mightContain, same semantics. | | remove(key) | never / boolean | Bloom + BlockedBloom + XorFilter + BinaryFuse: throw [lite-filter]. CountingBloom + Cuckoo + Quotient: a real delete, returns boolean (member-specific). | | resize(n) / merge(other) | Quotient | Quotient only: cold-path rebuild (grow/shrink) and union with an identical filter; preserve membership. | | size / count | number | Adds recorded (a plain counter, not a distinct-key count). XorFilter / BinaryFuse: the deduped key count. | | capacity | number | The item count the filter was sized for (XorFilter / BinaryFuse: == size). | | keysMode | 'int' \| 'arbitrary' | The key mode the filter was constructed in (decisions/0025). O(1), 0-alloc -- detect a keys:'int' filter without catching an error or a full dump(). | | seed | number | The 32-bit unsigned hash seed (decisions/0025). Dynamic members: the validated ctor seed. XorFilter / BinaryFuse: the WINNING build seed (the build reseeds until the peel succeeds). | | maxLoad | number | The item ceiling as an UPPER BOUND (decisions/0026): an add past it CERTAINLY throws; below it MAY still throw on Cuckoo / Quotient. Infinity (Bloom class), nb*b (Cuckoo), floor(0.90*nslots) (Quotient, tracks resize()), size (static, always built). Not a promise of remaining room. | | saturation | number | size / maxLoad in [0, 1] (decisions/0026): 0 when maxLoad is Infinity or 0, 1 on a built static filter, never NaN. | | fpp() | number | Configured target while empty, else the fill-derived estimate (Cuckoo / Quotient / XorFilter / BinaryFuse: the width-quantized rate). | | clear() | void / never | Reset to empty (zeroes the store in place). XorFilter / BinaryFuse: static, throws [lite-filter]. | | stats() / resetStats() | -- | Require { stats: true }; fail closed otherwise. | | dump() | snapshot | Serialize. Cold; may allocate. | | Member.from(iterable, opts?) | XorFilter / BinaryFuse | Static members only (static factory; .build alias). Build from a key set; throws on a degenerate set. | | Member.restore(snap, opts?) | member | Static. Rebuild; fail closed on any mismatch. |

Integer keys -- strict zero-alloc

const f = new Bloom(1_000_000, { fpp: 0.001, keys: 'int' });
f.add(42);                 // mixed directly -- no string encoding, no allocation
f.mightContain(42);        // true
f.add(2 ** 31);            // throws [lite-filter]: keys:'int' requires a 32-bit signed integer ...

// Folding a composite signature? Use `| 0`, NEVER `>>> 0`:
f.add(((sid << 20) | (op << 12) | code) | 0);   // signed int32 -- accepted, 0-alloc

keys: 'int' restricts keys to 32-bit signed integers (-2147483648 .. 2147483647) and takes an integer-mix hash path that never encodes a string -- the mode the perf gate proves is 0 B/op. String keys on the default backing are also alloc-free (they hash over their code units); only a non-string, non-int key pays a String() encode.

The signed-fold trap (decisions/0024). The domain is SIGNED int32, so a composite signature MUST be folded with | 0, not >>> 0. A >>> 0 fold yields values in [2^31, 2^32) for half its domain, and add()/mightContain() THROW fail-closed on exactly those keys (never a silent alias of two distinct numbers). The int-key error text names the fix. ((sid << 20) | (op << 12) | code) | 0 stays in range and allocates nothing.

Stats -- opt-in runtime counters

const f = new Bloom(1000, { stats: true });
f.add('a'); f.mightContain('a'); f.mightContain('z');
f.stats();       // { adds: 1, queries: 2, hits: 1, misses: 1 }  (BY REFERENCE)
f.resetStats();  // zeroes the same holder in place

OFF by default: with no { stats: true }, _stats === null and the hot path writes nothing. stats() / resetStats() on a non-stats instance throw (null is not zero).

Snapshot -- dump / restore

const snap = f.dump();                 // plain, structuredClone- and JSON-safe
const json = JSON.stringify(snap);     // persist to disk / IPC / a worker
const g = Bloom.restore(JSON.parse(json));   // bit-identical membership

The Uint32Array store IS the serial form. restore() re-derives (m, k) from the recorded (cap, fpp) and REJECTS -- never truncates -- on any tag, member, capacity, fpp, seed, bit-count, or count mismatch. Each member's restore() is member-specific (CountingBloom.restore, Cuckoo.restore, Quotient.restore, XorFilter.restore, BinaryFuse.restore, ...) and rejects a foreign snapshot via the mem tag. XorFilter.restore re-derives the fingerprint width from fpp, the segment length bl from count, checks fp.length === 3*bl, and validates every word in 0..(1<<fw)-1 before building. BinaryFuse.restore RE-DERIVES the whole segment geometry (sl/sc) from count -- rejecting an internally-inconsistent-but-legal sl/sc/fp.length triple -- then checks fp.length === (sc+2)*sl and every word before building.

Snapshot format v3 -- integrity checksum + the string-derivation break (decisions/0021, 0023). The format tag is "litefilter/3" and every dump() carries a 32-bit integrity checksum chk over the tag, member, keys-mode, seed, every sizing/width field, count, and every store word. restore() recomputes it (after the tag check and the structural checks, before any write) and REJECTS a mismatch fail-closed. This closes a real fail-OPEN: the keys-mode and seed CANNOT be re-derived from the stored bytes, so a flipped keys ("int" <-> null) or seed used to silently reconstruct under the wrong hash path (1990/2000 false negatives on a 2000-key XOR dump in the QA repro). chk is an INTEGRITY check against accidental corruption, NOT a MAC: a determined forger who recomputes chk is out of scope, the same as any checksum.

The tag advanced "litefilter/2" -> "litefilter/3" in 1.1.0 (decisions/0023): the XorFilter / BinaryFuse STRING-key second hash g changed from fmix32(h ^ seed2) to an INDEPENDENT hashStr(s, seed2) (removing a single-hash birthday ceiling that wrongly rejected large distinct-string sets), so a "litefilter/2" XOR/BF snapshot would read every string key FALSE. One tag is ONE algorithm for the WHOLE family, so every member is re-tagged -- including Bloom and int-mode filters whose bytes are unchanged. A "litefilter/2" (or earlier) snapshot is REJECTED with a migration message -- re-dump() from a live filter to migrate.

The bench tool

import { runBench } from '@zakkster/lite-filter/benchmark/Bench.mjs';
const rows = runBench({ cap: 100000, fpp: 0.01 });
// each row: { name, bitsPerItem, k, measuredFpr, theoretical, overPct, addNs, queryNs, falseNeg }

Constants

| Export | Meaning | | --- | --- | | VERSION | the package version string ("1.2.0") | | Bloom | the reference member (also the default export) | | CountingBloom | the deletable member (4-bit saturating counters; a real remove) | | BlockedBloom | the cache-local member (one 512-bit block per key; one cache miss per query, at a higher measured FPR) | | Cuckoo | the fingerprint member (b=4 buckets; deletable, fail-closed at capacity; FPR width-quantized to 2b/2^f) | | Quotient | the mergeable + resizable member (linear quotient filter; deletable, fail-closed at the 0.90 load ceiling; FPR remainder-quantized to load * 2^-r) | | XorFilter | the space-optimal static member (3-uniform hypergraph peeling; built once via from/build, immutable, ~1.23x the space bound; FPR width-quantized to 2^-fw) | | BinaryFuse | the smallest static member (overlapping fuse segments via multiply-shift; built once via from/build, immutable, ~1.13x the space bound / ~9.0 bits/item; FPR width-quantized to 2^-fw) |

Composability

Approximate membership is machinery that lives INSIDE bigger systems. A cache admission gate that keeps one-hit-wonders out of an LRU is a canonical pairing:

import { Bloom } from '@zakkster/lite-filter';
import { LiteLru } from '@zakkster/lite-lru';

const cache = new LiteLru(10000);
const seen = new Bloom(1_000_000, { fpp: 0.01 });

function admit(key, load) {
  // Only cache a key we have seen at least once before -- one-hit wonders never
  // pollute the cache, and the filter costs ~1.2 bytes/key instead of a second Set.
  if (seen.mightContain(key)) {
    let v = cache.get(key);
    if (v === undefined) { v = load(key); cache.put(key, v); }
    return v;
  }
  seen.add(key);           // first sighting: record it, but skip the cache this time
  return load(key);
}

Pairs equally with @zakkster/lite-binary-reader -- build a filter over record ids parsed straight out of a foreign binary buffer, with no intermediate Set.

Zero-GC design notes

| Operation | Allocation (keys:'int') | Allocation (string) | Allocation (arbitrary) | | --- | --- | --- | --- | | add | 0 B | 0 B | 1 String() (amortized) | | mightContain / has | 0 B | 0 B | 1 String() (amortized) | | clear | 0 B (same ArrayBuffer) | 0 B | 0 B | | fpp / size / stats | 0 B | 0 B | 0 B | | dump | O(words) -- cold, allowed | -- | -- |

• One preallocated Uint32Array of ceil(m/32) words, sized once from (n, fpp), never grown, never reallocated. clear() zeroes it in place -- the ArrayBuffer identity is preserved (proven by the torture gate).
• Enhanced double hashing (Kirsch & Mitzenmacher, 2006): all k probe positions come from two base hashes, pos_i = (h1 + i*h2) mod m, so a probe needs no k-length array -- zero scratch storage, two real hashes per op.
• Math.imul throughout the murmur3 fmix32 mixer -- exact 32-bit multiplies, never a boxed heap double.
• Opt-in stats guard (_stats === null) is the ONLY extra hot-path branch, and it is free when stats are off.

Gated numbers (this repo, npm run test:perf + npm run torture): add + mightContain on keys:'int' = 0 B/op, maxMajor 0; 1e6 adds then requery = 0 false negatives; n=1e5, fpp=0.01, 1e6 disjoint probes = measured FPR <= 0.0125 (<= 25% over the formula). CountingBloom add / mightContain / remove on keys:'int' are also 0 scavenges at N and 8N (nibble read/modify/write, no scratch array), and 1e5 mixed add/remove ops = 0 false negatives for present keys. BlockedBloom add / mightContain on keys:'int' are 0 scavenges at N and 8N too (one block, odd-stride within-block walk, no scratch), with a measured FPR within its honest ceiling (<= 0.0175) that is PROVEN to run OVER the plain-Bloom theory (decisions/0013). Cuckoo add / mightContain / remove on keys:'int' are also 0 scavenges at N and 8N (two-bucket b=4 scan, a single scalar victim register on kicks, no scratch array), with a width-quantized measured FPR <= 0.0090 (~0.0061, under the configured 0.01 -- decisions/0014) and a PROVEN fail-closed overload throw. Quotient add / mightContain / remove on keys:'int' are also 0 scavenges at N and 8N (linear-probe split + shift, preallocated cluster scratch on remove), with a remainder-quantized measured FPR <= 0.0090 (~0.0060, under the configured 0.01 -- decisions/0016), resize + merge round-trips at 0 false negatives with preserved/additive size, and a PROVEN fail-closed load-ceiling throw that is a byte-identical no-op. XorFilter mightContain on keys:'int' is 0 scavenges at N=200000 and 8N=1600000 (3 hashes, 3 modulo reductions, an XOR-compare, no scratch); a filter built from 1e6 distinct keys reads back with exactly 0 false negatives (which can hold ONLY if the peel was complete -- the fail-open regression gate), with a width-quantized measured FPR <= 0.0050 (~0.0039, under the configured 0.01 -- decisions/0020) that is strictly > 0 (non-vacuous) at ~9.84 bits/item, plus a PROVEN fail-closed 100-attempt exhaustion throw on a degenerate set. ns/op figures are machine-local -- run npm run bench.

Design decisions worth knowing

• The hash is load-bearing, and validated by the bench, not reputation (decisions/0001). murmur3 fmix32 + a direct integer mix + an alloc-free string hash; hash quality is what keeps measured FPR near theory, so it is a gated number.
• (n, fpp) is the sizing surface (decisions/0002); explicit (bits, k) is not offered in v0.1.0. Every impossible request fails closed at the door.
• Bloom is add-only, loudly (decisions/0003). remove() throws rather than silently corrupting other keys. count is an add-call counter, not distinct keys.
• fpp() is an estimate, labeled as one (decisions/0004). Measure your own keys.
• The snapshot rejects, never truncates (decisions/0005). A corrupt or foreign snapshot is an error, not a silently-wrong filter.
• The static-build API is Member.from(iterable) (decisions/0006, resolved in v0.6.0 with XorFilter): a static factory, not add-then-freeze -- so a static member is honest about its nature and the mutable members' add stays un-gated.
• CountingBloom counters are 4-bit nibbles, two per byte (decisions/0007) -- ~4x Bloom's space for a real remove, chosen over 8-bit for space at a 1% fpp.
• Counters saturate at 15, never wrap (decisions/0008). A wrap would turn a present key into a false negative; clamping keeps reads correct, at the cost that a saturated counter never decrements.
• remove is two-pass and fail-closed (decisions/0009): verify-then-decrement, no mutation on a partial match. Removing a never-added key can corrupt other keys -- only remove keys you added.
• The multiplicity readout is deferred (decisions/0010): saturation + collisions make "how many times added?" an over-estimate, so it is not shipped un-characterized.
• CountingBloom's snapshot is the same envelope with per-byte validation (decisions/0011): mem:"CountingBloom", w:4, cnts bytes each validated 0..255 (so every nibble is 0..15) before any instance is built.
• BlockedBloom pins a 512-bit block, not configurable (decisions/0012): one 64-byte cache line per key, store nb*16 words, block from the first hash + within-block bits via an odd stride; snapshot records bb:512 + nb.
• BlockedBloom's FPR penalty is exposed, not compensated (decisions/0013): m is NOT upsized to hide it. fpp() reports the plain-Bloom form as a FLOOR the measured rate runs OVER, and the bench prints Bloom vs BlockedBloom side by side. No "same fpp for free" claim.
• Cuckoo pins b=4 / 500 kicks and byte-aligns the fingerprint (decisions/0014): f = ceil(log2(8/fpp)) rounded up to an 8- or 16-bit slot, power-of-two buckets, an involution alt-bucket XOR, and a fail-closed add THROW at capacity (never a silent drop). fpp() reports the width-quantized 2b/2^f -- typically UNDER the configured target -- surfaced, not hidden.
• Cuckoo delete has a sharp caveat (decisions/0015): removing a NEVER-INSERTED key whose fingerprint collides with a real key clears that other key's slot -> a false negative for it. Only remove keys you inserted.
• Quotient is a LINEAR quotient filter with a fixed bit budget (decisions/0016): r = ceil(log2(1/fpp)) remainder bits + 3 metadata bits per byte-aligned slot word, 2^q >= ceil(capacity/0.90) slots plus GUARD spillover, quotient high / remainder low. add is fail-closed at the 0.90 load ceiling (or off the linear end) and is a byte- identical no-op on throw; remove rebuilds the affected cluster through the insert path (metadata repair correct by construction); merge/resize re-split each stored (quotient, remainder) under the fixed budget p = q0 + r WITHOUT the keys. fpp() reports the remainder-quantized load * 2^-r -- typically UNDER target.
• Quotient delete has the same never-added caveat (decisions/0017): removing a NEVER-INSERTED key whose (quotient, remainder) collides with a real key clears that other key's slot -> a false negative for it. Only remove keys you inserted.
• XorFilter is a static build with a fail-open guard (decisions/0018): 3-segment hypergraph peeling, bl = ceil(1.23*n/3)+32, reverse-order assignment, deterministic reseed up to 100 times. The peel stack MUST reach n before any fingerprint is assigned -- a short stack is a peel failure (reseed / throw), never assigned from (a partial build would fail OPEN with silent false negatives).
• XorFilter is immutable (decisions/0019): add / remove / clear / new XorFilter() all throw [lite-filter]. clear() throws rather than producing an undefined all-zero build; rebuild via XorFilter.from(newKeys) to change membership.
• XorFilter byte-aligns the fingerprint and revalidates on restore (decisions/0020): fw = 8 (fpp >= 2^-8) or 16, fpp < 2^-16 throws; positions are hash % bl (exact, no multiply-shift precision loss); restore() re-derives fw from fpp, bl from count, and the length from bl, rejecting any corruption (never truncates).

Testing

node:test only, zero runtime deps -- 516 deterministic tests across the boundary suite. The gates (npm run verify runs all of them):

• npm test -- the boundary suite: every method, every one-sided law, every fail-closed door, plus an ASCII-source guard and an introspection suite (the keysMode / seed / maxLoad / saturation getters against MEASURED ceilings, and the signed-fold door both ways).
• npm run test:types -- tsc --noEmit proves Bloom, CountingBloom, BlockedBloom, Cuckoo, and Quotient satisfy LiteFilter<K>, that CountingBloom, Cuckoo, and Quotient remove are a real boolean (and Quotient.resize/merge return the filter), that Bloom/BlockedBloom remove is never, and that XorFilter and BinaryFuse are static (from/build/restore; add/remove/clear are never; no public constructor).
• npm run torture -- node --expose-gc: the leak tracker (retention returns to 0)
  • the GC profiler (maxMajor 0) + the Set-differential oracle (no false negatives, bounded FPR) + a CountingBloom add/remove churn oracle + a BlockedBloom oracle (0 false negatives; measured FPR within its honest ceiling AND proven OVER plain-Bloom theory) + a Cuckoo oracle (0 false negatives, delete-churn, and a PROVEN fail-closed overload throw) + a Quotient oracle (0 false negatives; delete-churn with size==present; resize + merge round-trips; a PROVEN byte-identical fail-closed ceiling throw; and validateQuotient structure after churn) + an XOR oracle (a 1e6-key static build with 0 false negatives -- the fail-open regression gate; a non-vacuous width-quantized FPR; PROVEN fail-closed exhaustion + immutability throws; 50 build-then-drop retention cycles)
  • a BinaryFuse oracle (a 1e6-key static build with 0 false negatives -- the fail-open regression gate; MEASURED slots/item in [1.08, 1.13] (2dp) and bits/item <= 9.30; a non-vacuous width-quantized FPR; PROVEN fail-closed exhaustion + immutability + inconsistent-geometry restore throws; 50 build-then-drop retention cycles)
  • a NEGATIVE int32 oracle lane (INT_MIN..-1 plus the INT_MIN / INT_MAX edges, 0 false negatives on every int-capable member)
  • the clear() ArrayBuffer-identity check for the five mutable members.
• npm run torture:controls -- the must-fail proof: a broken build MUST fail.
• npm run test:perf -- the @zakkster/lite-perf-gate zero-alloc scenarios on keys:'int' (Bloom add-churn + query-hit; CountingBloom add-churn + query-hit + remove-churn; BlockedBloom add-churn + query-hit; Cuckoo add-churn + query-hit + remove-churn; Quotient add-churn + query-hit + remove-churn; XorFilter query-hit; BinaryFuse query-hit), a NEGATIVE-int32 lane per int-capable member (all maxScavenges 0), plus ONE amortized default-backing lane (fractional / large numbers, String()-encoded) under an explicit measured BYTE budget, with an allocating mustFail for teeth.
• npm run test:demo -- the shipped demo's own boundary suite (demo/Demo.test.mjs).
• npm run bench -- the measurement tool.

What this is not

• Not cryptographic. Fingerprints are not MACs; do not use it for security.
• Not an exact set. It answers "probably yes / definitely no". Use Set when you need certainty on the positive side.
• Not a key-value store. It stores membership, never values.

Ecosystem

Part of the @zakkster/* suite of zero-GC, single-file micro-libraries. Pairs with @zakkster/lite-lru (a filter is a natural cache-admission gate) and @zakkster/lite-binary-reader (build a filter over ids parsed from a binary buffer). Same laws, same voice.

License

MIT (c) Zahary Shinikchiev [email protected]