Sketch Lab

The problem

Bloom filters, Count-Min sketches, and HyperLogLog are the data structures every backend engineer has heard of and almost none can actually use. They power things people rely on daily — a database skipping a disk read, a CDN counting unique visitors, a stream processor finding the top-N heavy hitters — but the literature is papers and Greek letters, and most blog explanations flatten the one thing that matters: the error is one-sided and calculable in advance. A Bloom filter's "no" is a proof; its "yes" is a hint. Flattening that to "2% accurate" teaches the wrong thing.

The underlying pain point is trust: nobody adopts an approximate structure they can't verify. So the tool runs a real Set/Map on the same stream as ground truth and flags every single false positive as it happens — for two audiences: engineers who need to size one for real, and engineers who need to be convinced it's safe.

The approach

Hash quality is a gate, not a detail

Every error guarantee in the project assumes uniform hashing, and a bad hash voids all of them silently — the code runs, the pictures look fine, the numbers are wrong. So a hand-written MurmurHash3 got its own suite (avalanche + chi-squared) before a single structure existed, and it runs as the first job in CI, gating every other job and the deploy. If the hash is bad, no downstream result is meaningful.

Absolute and probabilistic properties are physically separated

"A Bloom filter never returns no for an inserted item" is not a statistical claim, and it lives in a test directory where no tolerance is permitted. "Measured false-positive rate falls within the predicted bound" lives elsewhere, with fixed seeds, many trials, and a tolerance derived from the estimator's variance and written down. Mixing them is how somebody eventually applies a tolerance to a property that has none. Bounds are asserted on counts via a Poisson tail rather than on rates via a normal band — in the rare-event regime a well-sized filter actually operates in, the normal approximation is worthless and produces exactly the spurious failure that teaches teams to widen tolerances until the suite means nothing.

Memory figures are real allocated bytes

The comparison against the exact structures is the project's honesty, so memory is the actual byteLength of the typed arrays — never a formula result presented as a measurement. Everything is seeded and deterministic (byte-identical state on any machine, no unseeded Math.random in the core), and long runs go to a Web Worker with buffers transferred rather than cloned.

The tests did real science

Several findings moved the numbers rather than the tolerances. A bounds test failed at ~2,500× the textbook rate at one over-provisioned configuration; investigation traced it to a structural coincidence floor in the Kirsch-Mitzenmacher hash derivation — (4n/m²)·(1+f)/(1−f) — and the missing term was added to the model, the tolerance never widened. A guard added for Bloom silently halved the Cuckoo filter's fingerprint space (measured as exactly 2.0× its bound) and was fixed by shifting past the forced bit. And the checked-in-both-directions comparison found this Cuckoo actually loses to Bloom on real bytes at every ε — so the copy says exactly what it delivers (deletion), not a space win it isn't.

Outcome

Live and public, bilingual, offline after first load. It ships four probabilistic structures implemented from the papers (Bloom 1970, Count-Min 2005, HyperLogLog 2007 including the small-range linear-counting regime most explanations skip, and a partial-key Cuckoo filter with working deletion); the memory slider — drag allocated memory down and watch predicted error from the formula track measured error from the actual stream; exact structures running alongside as ground truth, flagging every false positive with its item and colliding slots; a parameter calculator (state n and target ε, get m, k, and the resulting memory in real bytes); merge verification; and configurable uniform / Zipfian / adversarial / text streams, all shareable by URL.

Built solo in one ~12-hour build — ~11,900 lines of TypeScript with a test suite that is the third-largest area of the codebase, 328 assertions behind the hash-quality gate, on three runtime dependencies and zero hashing, sketch, or charting libraries. It's a finished portfolio instrument rather than a production library — an explicit non-goal — but production-grade in its verification: pure, deterministic, strict-typed.