Sizing a Bloom Filter Under a Hard 1 GiB Cap
A log pipeline must drop duplicate event IDs before aggregation. Events arrive at a steady 15,000/s for a 6-hour nightly window, IDs are random 64-bit values, and about 4% of events duplicate an ID seen earlier in the same window. The current implementation keeps every ID in an in-memory set; workers are killed by the container's 1 GiB memory limit after roughly 15 minutes, once the set reaches about 12 million entries at roughly 64 bytes per entry in the runtime's set implementation. Workers are ephemeral, have no persistent disk, and cannot be resized this quarter. One engineer proposes replacing the exact set with a Bloom filter sized for 350 million insertions at a 1% false-positive rate, backed by an exact set covering only the most recent 10 minutes (about 9 million IDs). Downstream, the pipeline reports distinct-event counts per campaign, and finance reconciles those counts against advertiser invoices to within 0.5%. A second engineer wants to shard the stream by ID across 8 workers instead.
1. Estimate the memory required by the proposed Bloom filter and by the 10-minute exact window, and say whether the combination fits.
Read the worked answer
Bloom filter. m = -n ln p / (ln 2)^2 with n = 350e6 and p = 0.01:
-ln 0.01 = 4.605,(ln 2)^2 = 0.4805, so bits per element = 9.585.m = 350e6 x 9.585 = 3.36e9 bits = 419 MB(about 400 MiB).k = (m/n) ln 2 = 9.585 x 0.693 = 6.64, so use 7 hash functions, or 2 hashes combined by double hashing to avoid 7 independent hashes per insert.
That alone fits comfortably under 1 GiB.
10-minute exact window. 15,000/s x 600 s = 9e6 IDs, at 64 B per entry = 576 MB of payload before hash-table slack; the runtime's set carries roughly 2x overhead at high load factors, so budget 1.0-1.5 GB.
Verdict: the combination does not fit. The exact window is the part that blows the budget, and it is also the part doing the safety-critical work (catching bursts of the same ID that the filter might miss). Do not delete it - shrink it to 60-120 s (1.5-3 million IDs, about 100-200 MB) and/or represent it as an open-addressed array of 64-bit hashes at a published load factor, which costs roughly 12-16 B per entry and brings 9e6 IDs down to about 144 MB. Then the total lands near 560-600 MB with headroom.
2. What does the 1% false-positive rate do to the downstream reconciliation, and is it acceptable?
Read the worked answer
Direction of the error matters. A false positive means a genuinely new ID is judged already seen and is dropped. So the distinct-count is biased low, by approximately the filter's false-positive rate at the moment each event arrives. The error is systematic and one-directional - it does not average out across campaigns or nights.
The rate is not constant. With the filter sized for exactly 350 million insertions at k=7, the false-positive probability starts near zero and rises as the bit array fills, reaching about 1% at the end of the window. Campaigns concentrated in the final hours of the window absorb almost all of the error; campaigns earlier absorb far less.
Against the 0.5% tolerance. The worst-case bias (about 1%) is twice the reconciliation tolerance, and it is not distributed evenly across campaigns, so per-campaign reconciliation can fail even if the nightly total looks acceptable. That is a contractual problem, not just a statistical one.
Options.
- Size for p = 0.1%: 14.38 bits/element x 350e6 = 5.0e9 bits = 629 MB, k = 10. Combined with a compact 60 s window this still fits under 1 GiB and pushes the bias an order of magnitude below tolerance.
- Or accept 1% and renegotiate the tolerance explicitly with finance - but say so out loud rather than discovering it in an invoice dispute.
- Do not simply enlarge n without lowering p; over-sizing for the wrong parameter wastes memory and leaves the bias unchanged.
3. The second engineer proposes sharding the stream by ID across 8 workers instead. Does that solve the memory problem?
Read the worked answer
For the exact set, no. Sharding divides the work but not the total state: 350e6 / 8 = 43.75e6 IDs per worker, at 64 B per entry = 2.8 GB per worker before hash-table overhead. Every worker is still far over its 1 GiB limit. Sharding changes where the memory lives, not how much is needed.
What sharding does buy. Per-worker Bloom filters shrink proportionally: 43.75e6 insertions at 1% needs about 52 MB per filter. Even at p = 0.1% that is about 79 MB per worker, which leaves generous headroom for a larger exact window and lower latency per worker. So sharding is a good complement to the filter, not a replacement.
Correctness caveats to state before endorsing it.
- Dedup remains correct only if an ID always maps to the same worker. With uniformly random 64-bit IDs, hashing to 8 shards is balanced; with structured IDs (campaign-prefixed, timestamp-leading) it is not, and you get a hot shard that still OOMs.
- Worker loss destroys that shard's filter and exact window, so duplicates reappear for that slice of the key space. Either accept the recount error or persist filter state - which the ephemeral, diskless constraint forbids.
- Aggregation must still be global, so the per-shard distinct counts need an exact merge keyed on campaign, which is cheap compared with the ID set.
Recommendation: Bloom filter per shard sized for p = 0.1%, 60-120 s exact window in a compact open-addressed structure, and an explicit, documented acceptance of the worker-loss recount.