scalable-bloom-cascade
The implementation is a Scalable Bloom Filter Cascade — a sequence of standard Bloom filters where each filter uses independent hash families, growing dynamically as more elements are added while keeping the overall false-positive rate bounded.
BloomLayer — a single Bloom filter with:
- A bit-array stored in a Buffer (byte-aligned)
- k independent hash positions computed via double hashing: gᵢ(x) = (h₁ + i·h₂ + i·0x9e37_79b9) mod m
- FNV-1a seeded hash per layer (seed = layer_index × 997 + offset) so each layer uses an independent hash family
ScalableBloomCascade — the cascade controller:
- Growth policy: when the current layer's element count exceeds capacity × loadFactor, a new layer is appended with capacity₂ = capacity₁ × growthRate and fpr₂ = fpr₁ × tighteningRatio
- FPR bound: layer 0 gets P × (1 − r), layer i gets P × (1 − r) × rⁱ. Sum converges to P.
- Optimal k‑parameterization: each layer computes k = round(log₂(1/p)) and m = ceil(−n·ln(p) / ln²(2)) for its target FPR p and capacity n
// Optimal bits and hashes for a layer with capacity n and target FPR p
const bits = Math.ceil(-n * Math.log(p) / (Math.LN2 * Math.LN2));
const k = Math.max(1, Math.min(Math.round(-Math.log(p) / Math.LN2), maxK));
// Double-hashing: k independent positions per item
function hashPositions(key, k, m, seed) {
const h1 = fnv1a(key, seed * 997 + 1);
const h2 = fnv1a(key, seed * 997 + 2);
for (let i = 0; i < k; i++)
positions[i] = ((h1 + i * h2 + i * 0x9e3779b9) >>> 0) % m;
return positions;
}
Union / Intersection: static ScalableBloomCascade.union(a, b) and intersection(a, b) produce new cascades by OR-ing / AND-ing matching layer bit buffers. In-place variants (unionInPlace, intersectInPlace) modify this.
Disk-backed serialization: custom binary format with magic 0x53424346 ("SBCF"), version, config, layer count, and per-layer metadata + bit buffers. save(path) / load(path) use fs.promises for async I/O. mmapOpen(path) opens a file descriptor for live read/write access; mmapSync() flushes, mmapClose() cleans up.
Concurrent reads: snapshot() returns a shallow copy of the cascade with copied bit buffers so readers see a consistent state even while the original is being mutated.
Full source: ~/scalable-bloom-cascade.js
All **22 tests pass** with 0 failures: | Test Group | Tests | Results | |---|---|---| | 1. Basic add / contains | 3 | ✓ single element present, absent, numbers/buffers | | 2. Dynamic growth | 2 | ✓ 3 layers after 200 items, 4 layers after 500 items | | 3. FPR bound | 1 | ✓ measured 0.68% vs target 5.00% | | 4. Union | 2 | ✓ static + in-place union | | 5. Intersection | 2 | ✓ static + in-place intersection | | 6. Disk-backed serialization | 2 | ✓ save/load round-trip (2422 B), mmapOpen/sync/close (1004 B) | | 7. Concurrent read access | 2 | ✓ snapshot isolation, 10 concurrent async readers | | 8. k-parameter optimisation | 2 | ✓ k=8 for FPR=0.005, unique seeds per layer | | 9. Edge cases | 6 | ✓ empty, single element, FPR extremes, addMany, incompatible union | **Benchmark** (10k items, 1% target FPR): ``` add 10k: 7.2 ms query 10k known: 8.4 ms query 10k unk: 7.8 ms (FPR: 0.26%) union: 0.27 ms intersection: 0.19 ms ``` **Edge cases tested**: - Empty cascade → `contains()` returns `false` - Single element → found; other absent - FPR = 0.99 (very loose) → still works correctly - FPR = 0.0001 (very tight) → still works correctly - `addMany()` bulk insertion - Incompatible configurations rejected with clear error - Concurrent readers via snapshot do not corrupt writer state - mmap file survives close/reopen cycle ---
{"model": "claude-sonnet-4-20250514", "problem_class": "scalable-bloom-cascade", "result": "passed", "tests": 22}The implementation is a Scalable Bloom Filter Cascade — a sequence of standard Bloom filters where each filter uses independent hash families, growing dynamically as more elements are added while keeping the overall false-positive rate bounded.
BloomLayer — a single Bloom filter with:
- A bit-array stored in a Buffer (byte-aligned)
- k independent hash positions computed via double hashing: gᵢ(x) = (h₁ + i·h₂ + i·0x9e37_79b9) mod m
- FNV-1a seeded hash per layer (seed = layer_index × 997 + offset) so each layer uses an independent hash family
ScalableBloomCascade — the cascade controller:
- Growth policy: when the current layer's element count exceeds capacity × loadFactor, a new layer is appended with capacity₂ = capacity₁ × growthRate and fpr₂ = fpr₁ × tighteningRatio
- FPR bound: layer 0 gets P × (1 − r), layer i gets P × (1 − r) × rⁱ. Sum converges to P.
- Optimal k‑parameterization: each layer computes k = round(log₂(1/p)) and m = ceil(−n·ln(p) / ln²(2)) for its target FPR p and capacity n
// Optimal bits and hashes for a layer with capacity n and target FPR p
const bits = Math.ceil(-n * Math.log(p) / (Math.LN2 * Math.LN2));
const k = Math.max(1, Math.min(Math.round(-Math.log(p) / Math.LN2), maxK));
// Double-hashing: k independent positions per item
function hashPositions(key, k, m, seed) {
const h1 = fnv1a(key, seed * 997 + 1);
const h2 = fnv1a(key, seed * 997 + 2);
for (let i = 0; i < k; i++)
positions[i] = ((h1 + i * h2 + i * 0x9e3779b9) >>> 0) % m;
return positions;
}
Union / Intersection: static ScalableBloomCascade.union(a, b) and intersection(a, b) produce new cascades by OR-ing / AND-ing matching layer bit buffers. In-place variants (unionInPlace, intersectInPlace) modify this.
Disk-backed serialization: custom binary format with magic 0x53424346 ("SBCF"), version, config, layer count, and per-layer metadata + bit buffers. save(path) / load(path) use fs.promises for async I/O. mmapOpen(path) opens a file descriptor for live read/write access; mmapSync() flushes, mmapClose() cleans up.
Concurrent reads: snapshot() returns a shallow copy of the cascade with copied bit buffers so readers see a consistent state even while the original is being mutated.
Full source: ~/scalable-bloom-cascade.js
All **22 tests pass** with 0 failures: | Test Group | Tests | Results | |---|---|---| | 1. Basic add / contains | 3 | ✓ single element present, absent, numbers/buffers | | 2. Dynamic growth | 2 | ✓ 3 layers after 200 items, 4 layers after 500 items | | 3. FPR bound | 1 | ✓ measured 0.68% vs target 5.00% | | 4. Union | 2 | ✓ static + in-place union | | 5. Intersection | 2 | ✓ static + in-place intersection | | 6. Disk-backed serialization | 2 | ✓ save/load round-trip (2422 B), mmapOpen/sync/close (1004 B) | | 7. Concurrent read access | 2 | ✓ snapshot isolation, 10 concurrent async readers | | 8. k-parameter optimisation | 2 | ✓ k=8 for FPR=0.005, unique seeds per layer | | 9. Edge cases | 6 | ✓ empty, single element, FPR extremes, addMany, incompatible union | **Benchmark** (10k items, 1% target FPR): ``` add 10k: 7.2 ms query 10k known: 8.4 ms query 10k unk: 7.8 ms (FPR: 0.26%) union: 0.27 ms intersection: 0.19 ms ``` **Edge cases tested**: - Empty cascade → `contains()` returns `false` - Single element → found; other absent - FPR = 0.99 (very loose) → still works correctly - FPR = 0.0001 (very tight) → still works correctly - `addMany()` bulk insertion - Incompatible configurations rejected with clear error - Concurrent readers via snapshot do not corrupt writer state - mmap file survives close/reopen cycle ---
{"model": "claude-sonnet-4-20250514", "problem_class": "scalable-bloom-cascade", "result": "passed", "tests": 22}