If you’ve ever had to flag the bots in an ad-click stream, you know the first thing you reach for is a counter keyed by source. A dictionary, source to count, bump it on every click, and anything clicking a thousand times a minute lights up. It works beautifully on a sample. Then you point it at the real firehose, a million distinct sources an hour, and the counter is still holding every one of those million keys long after the humans behind them clicked once and left, and your process is sitting on a few hundred megabytes to remember a fact you’ll never use again. The bots are a handful of sources. You’re paying to remember everybody else.
The problem
To catch a high-frequency source you have to count per source, and to dedup replayed clicks you have to remember every click id you’ve seen, and both of those sets grow with your traffic, not with the fraud. The bots are twenty sources hammering the stream; the memory goes to the million ordinary sources you keep around just to confirm they’re ordinary. Exact counting answers the question, but the structure that answers it never stops growing, and on a real firehose “never stops growing” is the whole problem. What you actually want is a structure whose size you pick up front and never pay again, that’s still accurate about the thing you care about, the heavy hitters, and is allowed to be sloppy about everything else.
I built a stream to see how bad the exact version gets and how little the sloppy version costs. A million human sources each clicking a handful of times, twenty planted bots each clicking 50,000 times, twelve percent of the clicks being exact replays of an id already seen. That’s 2,430,865 clicks, 2,138,760 unique ids. I ran the same stream through the exact structures and through three probabilistic ones from Redis, Count-Min Sketch, Top-K, and a Bloom filter, and measured the memory each one actually used.
The counter that never stops growing
Memory as unique sources grow: exact vs probabilistic
That orange line is the whole reason to bother. The exact source counter alone was 126.8MB at a million sources, the exact id-set another 190.0MB, and neither has any reason to stop, every new source is a new key, every new click id is a new member. A Redis HASH instead of a Python dict trims the counter to 80.4MB, still linear, still climbing. The green line is what you get when you decide up front how much memory you’re willing to spend and refuse to spend a byte more. The interesting part is that the flat line still answers every question the climbing line did.
Counting without remembering who
A Count-Min Sketch is a small grid of counters, and every source hashes to one cell in each row. You bump those cells on every click and read a source’s count back as the smallest of its cells. Collisions make it lie, but only ever upward, and only ever by other sources landing in the same cells, so the count you read is the true count plus some collision noise. The trick is that a heavy hitter’s real count is so much bigger than the noise that you can still pick it out.
Source counting: exact dict vs Count-Min Sketch
The bots came out at 50,000 true and roughly 50,057 estimated, an overshoot of 57 on fifty thousand, noise you’d never notice. Here’s the honest part, though, and it’s not a bug. That same collision floor added a mean of 58 to the humans too, and a human’s real count was 1 to 4, so the sketch reported ordinary sources as having clicked 58, 70, 80 times. If you’d tried to use the sketch to tell two humans apart it would be useless, the floor is bigger than their entire signal. But you don’t care about two humans, you care about the twenty sources sitting five hundred times above the floor, and against 50,000 a floor of 58 vanishes. So the sketch can’t separate one quiet source from another, the floor drowns them, but the twenty hitters sit so far above it that the noise doesn’t reach them, and those twenty are the only ones you were counting for.
The list of who’s hammering you
Count-Min gives you a count if you name a source, but it won’t hand you the list of who the heavy hitters are, you’d still have to ask it about every source you ever saw, which is the memory you were trying not to keep. Top-K is the structure that keeps the leaderboard itself. It holds a small number of slots, k of them, and a decaying min-heap, and it fights to keep the busiest sources in those slots and lets the quiet ones fall out. You never enumerate anybody, you just read the board.
Top-K leaderboard: planted bot vs the busiest human that made the list
Every one of the twenty bots was in the top twenty, at their true 50,000, and the rest of the fifty-slot board was filled with humans stuck at 4, which is the whole point, the gap between a bot and the busiest non-bot is 50,000 to 4 and nothing crosses it. Sixty-seven kilobytes to carry the answer you were about to spend 126 megabytes computing. You still want the sketch alongside it, Top-K tells you who the hitters are and roughly how hard, the sketch lets you interrogate a specific source on demand, but neither of them is holding a key per source.
Catching the replays
The other half of the job is the replayed clicks, the same click id showing up again, and the exact tool for that is a set of every id you’ve seen, which was the 190MB half of that first orange line. A Bloom filter does membership without storing the members. It’s a bit array and a few hashes; adding an id flips some bits, and to test one you check whether all its bits are already set. If any bit is clear the id is definitely new; if they’re all set it’s probably a repeat, probably because some other ids might have flipped those same bits between them.
Deduping click-ids: exact set vs Bloom filter
The Bloom filter never missed a real replay, it can’t, if you’ve seen an id its bits are set, so recall was a flat 100%. What it costs you is the other direction, 0.011% of genuinely-new clicks came back marked as already-seen, twenty-two of two hundred thousand, clicks you’d wrongly drop as duplicates. That measured rate came in under the 0.1% I’d sized it for, and that’s not luck either, a Bloom filter runs below its nominal error until it fills up, and 2.14 million ids in a filter built for 2.5 million never quite got there. Size it too tight and that false-positive rate climbs; the number you pick is the number of real clicks you’re willing to throw away.
The takeaway
Exact counting answers the question and then punishes you for asking, 317 megabytes at a million sources and a straight line pointing up. The probabilistic three, Count-Min Sketch for on-demand counts, Top-K for the leaderboard, a Bloom filter for dedup, did the same job in 5.8 megabytes you allocate once and never grow, flagged all twenty bots, and caught every replay at eleven false positives in a hundred thousand. The trade you’re making is exactness for a fixed error, and you have to know where it lands, the sketch can’t tell two quiet sources apart because its collision floor is bigger than their signal, the Bloom filter will drop a tiny fraction of real clicks as fake, and both of them you have to size before you know your traffic, guess too small and the errors grow. But for catching the heavy hitters, the twenty sources that stick out five hundred times above everyone else, the sloppiness is invisible and the memory is flat, and flat is the only thing that survives a real firehose. The stream, the harness, and every structure’s numbers are in the repo. Laptop numbers on Redis 7.4.7, not a capacity statement, but the shape holds wherever you run it.
Comments