阅读中文版本

Build a Bloom Filter Cache Guard

A Bloom filter that sits in front of a cache to reject absent-key lookups cheaply, with counting removal, auto-scaling bit array, and a measured false-positive rate.

bloom-filter-cache/
├── src/filter.ts
├── src/scale.ts
├── src/serialize.ts
├── tests/filter.test.ts
└── package.json

for (let i=0;i<k;i++) bits[(h1+i*h2)%m]=1; return bits.every(b=>b);

if (--count[idx]===0) bits[idx]=0;

if (fillRatio > 0.75) await scaleTo(m*2);

fpr = falsePositives / queries; return fpr;

Project overview

A cache that answers every absent lookup with a miss is doing unnecessary work. Most of the keys a service is asked about are not in the cache and never will be, and each miss costs a round trip or a computation that returns nothing. A Bloom filter in front of the cache answers definitely-absent for those keys without the lookup.

The filter is a bit array and k hash functions. On add, set k bits. On query, if any of the k bits is clear, the key is definitely absent, because an added key would have set all of them. If all k bits are set, the key is probably present, but maybe not, because other keys may have set the same bits. That maybe is the false positive, and the filter is sized to keep it rare.

The counting array is what makes removal possible. A plain bit array cannot support delete, because clearing a bit that another key shares would make that key query absent. The counting array tracks how many keys set each bit, and a bit clears only when its counter reaches zero. This costs memory but buys correctness.

The auto-scale is what keeps the filter useful as the key set grows. A filter sized for a million keys saturates at two million and its false-positive rate climbs. When the fill ratio crosses a threshold, the filter allocates a larger array and re-inserts all live keys, restoring the rate. The rebuild is from the live-key log, not the old bit array, because the old array has stale bits from removed keys.

The value of this project is the measured rate, not the bit array. A filter that reports a theoretical rate based on the key count is guessing; a filter that counts its own false positives confirmed by the cache is reporting the truth, and that number is what tells an operator when to scale.

What you will build

The project delivers five capabilities, each driven by a test:

• Definitely-absent rejection
• Counting removal via secondary array
• Auto-scale on saturation
• Measured false-positive rate
• Bit-compact serialization

A bit array of m bits and k hash functions form the filter. On add, set k bits; on query, if any of the k bits is clear the key is definitely absent. A parallel counting array tracks deletions without rebuilding. When the fill ratio crosses a threshold, the filter scales to a new larger array and re-inserts all live keys.

Architecture and data model

The bit array is a Uint8Array of m bits, stored as bytes. The k indices are derived by double hashing: two base hashes h1 and h2, and the i-th index is (h1 + i * h2) mod m. This avoids k separate hash calls and still distributes indices uniformly.

The counting array parallels the bit array, one counter per bit. On add, increment the counters and set the bits. On remove, decrement the counters and clear a bit only when its counter reaches zero. A bit shared by two keys stays set after one is removed, which is correct.

The live-key log is a set of the keys currently in the filter, kept for scaling. It costs memory, so it is optional: a filter that never scales can drop the log and rely on the bit and counting arrays alone. A filter that scales needs the log, because the old bit array cannot be trusted after removals.

Scaling allocates a new bit array and counting array of twice the size, re-inserts every key from the live-key log, and swaps the arrays atomically. The swap is a pointer change, so queries during the rebuild see the old array, and the new array takes over in one step. The rebuild is stop-the-world for the swap, but the re-insertion is incremental.

The measured false-positive rate is a counter pair: total queries and false positives confirmed by the cache. A query that the filter says probably-present but the cache says absent is a false positive, and the filter increments the counter. The reported rate is the ratio, and it is logged periodically so an operator can see the drift from the theoretical rate.

Prerequisites and setup

You need the following before you begin:

• Node.js 20 LTS or later
• A cache whose absent lookups are expensive

The dependencies cover the core needs:

• node:crypto (built-in) — Double hashing for k indices

pnpm init

pnpm add -D typescript tsx vitest

Keep secrets and configuration in the environment, and validate them at boot so a misconfigured service fails loudly instead of silently dropping work.

Directory structure

bloom-filter-cache/ is organized so each concern is testable in isolation:

bloom-filter-cache/
├── src/filter.ts
├── src/scale.ts
├── src/serialize.ts
├── tests/filter.test.ts
└── package.json

Phase 1: Add and query

On add set k bits via double hashing; on query return absent if any bit is clear.

for (let i=0;i<k;i++) bits[(h1+i*h2)%m]=1; return bits.every(b=>b);

Double hashing derives k indices from two hashes, avoiding k separate hash calls.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 2: Counting removal

Track a per-bit counter so removal decrements and clears a bit only at zero.

if (--count[idx]===0) bits[idx]=0;

A plain bit array cannot support removal; the counting array is the price.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 3: Auto-scale

When the fill ratio crosses a threshold, allocate a larger array and re-insert all live keys.

if (fillRatio > 0.75) await scaleTo(m*2);

Scaling rebuilds from the live-key log, not the old bit array, to clear stale bits.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Phase 4: Measure FPR

Track queries and false positives confirmed by the cache to report a live false-positive rate.

fpr = falsePositives / queries; return fpr;

The measured rate drifts from the theoretical rate as the fill ratio changes.

The phase is driven by a test that asserts the expected behavior, so the implementation is correct before the next phase builds on it.

Testing

Add a thousand keys and query a thousand absent keys; assert the false-positive rate is near the configured target; remove half the keys and assert they query absent; fill past the threshold and assert the filter scales without losing live keys.

The tests add a thousand keys and query a thousand absent keys, then assert the measured false-positive rate is near the configured target. The theoretical rate is a function of m, k, and the key count; the measured rate should be close, and a large discrepancy means the sizing is wrong.

The removal test adds a key, removes it, and asserts it queries absent. The shared-bit test adds two keys that share a bit, removes one, and asserts the other still queries present, proving the counting array prevents a wrong clear.

The scale test fills the filter past the threshold and asserts it scales to a larger array without losing any live key. After scaling, every previously added key must still query present, and the false-positive rate should drop because the new array is larger.

The serialization test writes the filter to a buffer, reads it back, and asserts every key queries the same result before and after. The definitely-absent test queries a key that was never added and asserts absent, because that is the guarantee the cache relies on.

The counting-underflow test removes a key that was never added and asserts the counter does not go negative, because a negative counter would corrupt the bit state.

pnpm vitest run

Observability

Track the definitely-absent rejection rate, the bloom-filter resource usage, and the error count as the three primary signals for the bloom-filter-cache system. A sudden change in any of these is the signal that something has shifted, not necessarily broken but worth a look before it becomes an incident. Chart the counting removal via secondary array alongside the definitely-absent rejection so a correlation is visible at a glance, because a rising counting removal via secondary array with a stable definitely-absent rejection means the system is doing more work per unit, not that it is failing.

Log every add and query transition with the context that triggered it, because an operator who sees the symptom but not the cause will guess wrong. The log entry should carry the bloom-filter identifier, the input that caused the transition, and the outcome, so the operator can reconstruct what happened without re-running it. A log without context is a line of text; a log with context is a diagnosis.

Set alerts on the derived metrics, not the raw counters. A rate of change is more actionable than a total, because a total grows monotonically and never tells you when the growth accelerated. Alert on the definitely-absent rejection error rate crossing a threshold, the bloom-filter utilization exceeding a percentage, and the counting removal via secondary array latency exceeding the SLO. Each alert should have a runbook link, so the operator who receives it at three in the morning knows what to do, not just what is wrong.

The bloom-filter-cache system should expose its metrics in a format the existing dashboard can scrape, so the observability is additive, not a new tool. A metric that nobody reads is noise, so before adding one, confirm it has a consumer. The dashboard has three panels: throughput, error rate, and resource utilization, each with a threshold line that is the SLO, so a glance tells an operator whether the system is healthy without reading numbers.

Deployment and operations

Keep the filter in memory alongside the cache process, so a query checks the filter before the cache with no network hop. Serialize the filter to disk on a graceful shutdown and restore it on boot, so a restart does not lose the definitely-absent set and the cache is not flooded with misses.

Size the filter for the expected key count and the target false-positive rate, not the current key count. A filter that is sized exactly for today is saturated tomorrow. The sizing formula gives m and k from the key count and the rate, and the auto-scale handles the rest.

Log the measured false-positive rate and the fill ratio periodically. A rising rate with a stable key count means the filter is saturating and should scale; a rising rate with a growing key count means the sizing assumption is broken and the filter needs a larger base array.

Do not use the filter as the sole answer for presence. A false positive lets a definitely-absent key through to the cache, which returns a miss, and that is fine. The filter is a guard, not a store, and its job is to reduce cache load, not to replace it.

Security considerations

Treat every input to the bloom-filter-cache system as untrusted, because the definitely-absent rejection path is the one place an external caller controls what the system processes. Validate the input shape before any bloom-filter operation, and reject early with a clear error rather than letting a malformed input propagate into the add and query phase where it causes a confusing failure that is hard to trace back to its source.

Keep secrets and configuration in the environment, never in the repository. The node:crypto credentials, the signing keys, and the service endpoints are all environment variables, read once at boot and validated, so a misconfigured bloom-filter-cache fails loudly at startup instead of silently misbehaving at runtime. A system that starts with a bad configuration and runs anyway is a system that will produce wrong results for hours before anyone notices.

Rate-limit the definitely-absent rejection endpoint per caller, because an unbounded bloom-filter operation is a resource leak as much as a security problem. A caller that can trigger the counting removal path without limit can exhaust the system, whether intentionally or not. The rate limit is a per-caller ceiling that costs legitimate callers nothing and stops the abuse before it reaches the add and query logic.

Audit-log every state-changing operation with the caller identity, the input, and the timestamp. The audit log is not for debugging, it is for accountability: if something went wrong, the log says who did what and when. The bloom-filter-cache system writes the audit log to an append-only store that the system itself cannot modify, so a compromised system cannot rewrite its history.

Do not expose internal errors to the caller. A stack trace is a map of the system internals, and an attacker who collects them learns the bloom-filter structure. Return a generic error with a correlation id, and log the full error internally with the same id, so an operator can trace it without leaking it.

Limitations and next steps

• No iteration; you cannot list the keys in the filter, only test membership.
• Counting removal uses more memory than a plain bit array.
• Scaling is a stop-the-world rebuild; plan it for low traffic.

The filter cannot iterate its keys. You can test membership but not list the set, because the bit array does not store keys, only their hashed footprints. If you need to list keys, keep the live-key log, which is a separate structure.

Counting removal uses more memory than a plain bit array, typically four or eight bits per bit for the counter. For a large filter this is a significant overhead, and it is the price of deletion. A filter that never deletes can drop the counting array and use a plain bit array.

Scaling is a stop-the-world rebuild. The re-insertion is incremental, but the swap is atomic, and during the rebuild the old array is still queried. Plan scaling for low-traffic periods, or accept a brief period of higher false positives as the old array saturates before the new one takes over.