Dedup window size and the Bloom filter trap

Measure your machineNeeds Python

Problem

Deduplication needs to remember every key it has seen for as long as a duplicate can arrive: the window. Memory grows linearly with rate × window × entry size, which turns a week of window at a high rate into terabytes. A Bloom filter remembers keys in a few bits each, but it has false positives: used alone, it silently drops a share of genuinely new records as "seen before". Used in front of the exact store, it only answers "definitely new" quickly, and the exact store decides the rest.

Part A (arithmetic). Compute the memory for exact dedup at 100,000 keys per second with 32-byte entries for 1 hour and for 1 week. Part B (measurement). Insert 1,000,000 random keys into a Bloom filter sized for 1% false positives, then check 1,000,000 NEW keys. Count how many new keys are wrongly reported "seen before". Then put the Bloom filter in front of an exact set and only drop a record if both say "seen".

The question. How much memory does exact deduplication need for an hour and a week, and how many new records does a Bloom filter drop alone and in front of an exact set?

Predict

On its own, how many of a million new keys does a 1% Bloom filter wrongly drop as duplicates?

NoneHundredsAbout 10,000Far more

Run it

1Install uv once. It fetches Python and the lab's packages for you.
Terminal
```
curl -LsSf https://astral.sh/uv/install.sh | sh
```

2Get the script. It is the whole lab: read it, then download it.

dedup-window-size-and-the-bloom.py45 linesDownload

View the code

dedup-window-size-and-the-bloom.py

# /// script
# requires-python = ">=3.10"
# dependencies = ["numpy"]
# ///
# Copyright (c) 2026 Aayush Sharma · SPDX-License-Identifier: MIT
# https://thedataengineering.com/lab-code/LICENSE.txt
"""Dedup window size, and the Bloom filter trap.

(A) Memory for exact dedup at 100,000 keys per second, 32 bytes per entry,
for an hour and a week. (B) A Bloom filter sized for 1% false positives with
1,000,000 keys: how many new keys does it wrongly call duplicates? Then the
filter in front of an exact set.
"""
import argparse, json, math
import numpy as np

p = argparse.ArgumentParser(description=__doc__.splitlines()[0])
p.add_argument("--rate", type=int, default=100_000, help="Keys per second.")
p.add_argument("--entry-bytes", type=int, default=32, help="Bytes per dedup entry.")
p.add_argument("--keys", type=int, default=1_000_000, help="Keys inserted into the filter.")
p.add_argument("--fp", type=float, default=0.01, help="Target false-positive rate.")
p.add_argument("--seed", type=int, default=0, help="Random seed.")
p.add_argument("--json", help="Also write the results to this JSON file.")
args = p.parse_args()
rng = np.random.default_rng(args.seed)
mem = [{"window": w, "seconds": s, "gb": args.rate * args.entry_bytes * s / 1e9} for w, s in (("1 hour", 3600), ("1 week", 604_800))]
for m in mem: print(f"exact dedup for {m['window']}: {m['gb']:,.1f} GB")

m_bits = math.ceil(-args.keys * math.log(args.fp) / math.log(2) ** 2); k = round(m_bits / args.keys * math.log(2))
bits = np.zeros(m_bits, dtype=bool)
def pos(keys, i): return ((keys * np.uint64(0x9E3779B97F4A7C15 + 2 * i)) >> np.uint64(17)) % np.uint64(m_bits)
seen = rng.integers(0, 2**62, args.keys, dtype=np.uint64); new = rng.integers(2**62, 2**63, args.keys, dtype=np.uint64)
for i in range(k): bits[pos(seen, i).astype(np.int64)] = True
hit = np.ones(args.keys, dtype=bool)
for i in range(k): hit &= bits[pos(new, i).astype(np.int64)]
dropped = int(hit.sum())
exact = set(seen.tolist()); both = sum(1 for x in new[hit].tolist() if x in exact)
print(f"Bloom filter alone: {dropped:,} of {args.keys:,} new keys wrongly dropped as duplicates ({dropped / args.keys:.2%})")
print(f"Bloom filter, then the exact set: {both} dropped; the filter saved {args.keys - dropped:,} exact lookups")

if args.json:
    with open(args.json, "w") as f:
        json.dump({"tables": {"memory": mem, "summary": [{"dropped": dropped, "dropped_pct": dropped / args.keys * 100, "with_exact": both,
                   "saved_lookups": args.keys - dropped}]}}, f)

3Run it in the folder you saved it to, with the defaults first. Then change a knob from the table below and run it again.
Terminal
```
uv run dedup-window-size-and-the-bloom.py
uv run dedup-window-size-and-the-bloom.py --help     # every knob
```

Knobs
Knob · default	What it changes
--rate100,000	Keys per second.
--entry-bytes32	Bytes per dedup entry.
--keys1,000,000	Keys inserted into the filter.
--fp0.01	Target false-positive rate.
--seed0	Random seed.

Our run

Exact deduplication memory

Exact deduplication memory
Window	GB
1 hour	11.5
1 week	1.94K

Reference runApple M2 · 8 cores · 8 GB

Output · uv run dedup-window-size-and-the-bloom.py

exact dedup for 1 hour: 11.5 GB
exact dedup for 1 week: 1,935.4 GB
Bloom filter alone: 10,141 of 1,000,000 new keys wrongly dropped as duplicates (1.01%)
Bloom filter, then the exact set: 0 dropped; the filter saved 989,859 exact lookups

macOS 26.6.2 · Python 3.13.3 · numpy 2.5.4 · run 2026-10-20

What we found

The arithmetic gave 11.5 GB for an hour and 1.94K GB for a week. The Bloom filter alone dropped 10.1K of a million new keys (1.01%). In front of the exact set it dropped 0, and it saved 990K exact lookups, one for every key it could rule out.

Read it

A Bloom filter is a fast "no", never a trustworthy "yes". In front of an exact store it is pure gain; alone, its false-positive rate is a data-loss rate. The window is the real cost driver: it should be set by how late a duplicate can actually arrive, measured, not by a round number.