Streak

A log of visitor addresses arrives one request at a time and the question is the one every analytics page asks: how many of them were distinct? The honest answer needs a set, and a set costs memory in proportion to the answer. This counts them in 768 bytes that never grow.

Each address is hashed exactly once. The top 10 bits pick a register; the run of zero bits after them is a coin-flip streak, and each register keeps only the longest streak it has ever seen. That is the whole data structure — 1024 numbers between 0 and 33, six bits each — and the top of the screen shows one hash being cut in half and filed away. Pause and step to read a single one.

The piece is built around three things that are usually asserted rather than shown:

A repeat leaves no trace. The same address hashes the same way, lands in the same register, and wins the same streak, so a duplicate is not detected and does not need to be. Run the heavy repeats log — 6000 requests, a few thousand distinct — and watch the estimate ignore the difference. Deduplication here is not a feature that was added; it is a thing the structure cannot help doing.

One register is a terrible estimator. Press one register (or click any register in the array) and a red staircase joins the chart: what that register alone would claim, from its own longest streak. It moves in factors of two, because that is the only vocabulary a single maximum has — 1024, 2048, 4096, and off the top of the chart. The smooth teal line is the harmonic mean of a thousand of those staircases. Averaging is not a refinement of the trick, it is the trick.

The error band is a purchase, not a promise. The right chart draws the running error against ±1.04/√m, the published standard error. Drop to 16 registers — 12 bytes, a 1300× saving — and the band opens to ±26% while the estimate visibly staircases along with it. Go to 4096 and the band closes to ±1.6% for 3 KB. Changing the register count keeps the same log and the same position, so the two sketches are watching identical traffic and only the accuracy you paid for has changed.

The readout underneath carries the part that never moves: an exact set of 32-bit hashes against the sketch, and what both would cost at a billion distinct visitors — 3.7 GB against the same 768 B.

Reuse

src/streak.js is a framework-free ES module:

• hash32(str) — FNV-1a with a murmur3 finalizer.
• rankOf(w, wBits) — position of the first 1 bit from the left, 1-based.
• estimateFrom(sum, zeros, m) — the estimate from the running Σ2^-M[j] and the count of untouched registers, with both of Flajolet’s corrections.
• simulate(stream, m) — one frame per request: the hash, its register, the streak it won, whether that raised anything, and the estimate afterwards. Same trace-per-tick shape as skyline, window, sift and rho.
• registersAt(frames, i, m), singleRegisterTrace(frames, j, m, i) — the array as it stood, and one register’s private opinion over time.
• makeStream / PRESETS — a request log with a duplicate rate and an optional skew, so repeats can pile onto a few crawler addresses instead of spreading evenly.
• sketchBytes(m), exactBytes(distinct), stdError(m), formatBytes.

No rendering or timers in the module; the canvas demo is reference code.

Gotchas

• The estimate is maintained incrementally — a register moving from r0 to r1 shifts the sum by 2^-r1 - 2^-r0 — so a run stays linear in the stream no matter how many registers there are. Recomputing Σ2^-M[j] per item is the obvious version and it makes m=4096 crawl.
• The murmur3 finalizer on top of FNV-1a is not decoration. FNV’s high bits avalanche poorly, and the high bits are exactly what picks the register; a biased bucket makes the whole estimator lie in a way that looks like bad luck.
• Linear counting carries the first few hundred items. Below 2.5m the raw harmonic mean is badly biased high, so the estimator switches to m·ln(m/zeros) while registers are still untouched. Remove that branch and the piece opens with a wildly wrong number and no visible reason.
• Truth is counted over the address strings, not their hashes: a 32-bit collision would be invisible to the sketch, and the chart should not quietly agree with it.
• rank is streak + 1 — a register at 0 means untouched, not “saw a zero-length streak”. The off-by-one is why oneRegisterEstimate uses 2^(rank-1).
• The register array folds several registers into one pixel column past m=256 and draws the tallest of them, so the array looks slightly fuller than it is. The touched counter next to it is exact.
• The demo bundles its own copy of streak.js (self-contained by contract); re-copy after editing src/.