The shape
Every system counts something, and somewhere it is paying for the exact answer in memory, in coordination, or in both. The move is to notice that nobody needs the exact value, decide what error is acceptable, and buy a large saving with it.
The saving is not marginal. Counting distinct items exactly means keeping every item you have seen, so the memory grows with every new one. The alternative is a sketch: a small, fixed-size summary that answers "how many distinct" without storing the items at all. A 12 KB sketch is accurate to within about 1 percent, whether you saw 1,000 things or 1 billion. The exact version grows forever. The sketch never grows at all, and that gap is what makes some designs possible in the first place.
Some examples:
- "How many distinct users viewed this?" Exact means a set of every user id. Approximate means a HyperLogLog sketch of a few kilobytes.
- "Has this client exceeded 100 requests per minute?" Exact means a timestamp per request. Approximate means a sliding window estimate from two counters, or a token bucket that never stores a request at all.
- "How many likes does this post have?" Exact means a locked row read at write consistency. Approximate means a cached aggregate that is a few seconds behind.
The common structure: a question whose answer drives a decision, where the decision does not change across a band of values. If the band is wide, you are paying for precision nobody uses.
The moves
Three different techniques get grouped under this name, and they trade away different things. Confusing them is the most common mistake here.
How many distinct? This one is called probabilistic cardinality. A HyperLogLog sketch answers with a standard error of about 0.81 percent from 12 KB, no matter the true count. Two properties matter as much as the size. First, sketches merge. A sketch is an array of registers, and merging two of them means taking the larger value in each matching position. That gives you exactly the sketch you would have got by counting both streams together from the start. So each shard counts on its own with no coordination, and you combine them at read time. Second, the error is a proved bound rather than something that happened to hold in testing. The 0.81 percent comes out of the mathematics of the sketch, so you can put it in a design review the way you would put a latency budget in one.
Bloom filters are the same family aimed at a different question, membership rather than count, and their error runs one way only. A Bloom filter can say something is present when it is not. It can never say something is absent when it is really there. So it is safe for "skip the expensive lookup if this is definitely not here", and never safe for "this is definitely present".
How many in total? This one is called bounded staleness. Keep a counter in memory on each node and flush the total to a shared data store, such as a database or Redis, periodically. The count is eventually exact; at any instant it is behind by at most one flush interval times the write rate. You gave up freshness, not accuracy, and the maximum error is a number you chose when you set the interval.
How many recently? This one is called windowed estimation. Keep one counter per fixed window and estimate the sliding window by weighting the previous window by how much of it the current window overlaps. Two integers per key instead of a timestamp list. The error is not probabilistic; it comes entirely from assuming the previous window's traffic was evenly spread, so a burst at the wrong moment produces an overcount or an undercount.
Counting distinct viewers of one popular item:
exact, a set of 8-byte user ids
10M distinct = 80 MB
100M distinct = 800 MB
per item, and it grows forever
HyperLogLog sketch
10M distinct = 12 KB
100M distinct = 12 KB
standard error = 0.81%
⇒ at 10M distinct, 6,600x less memory
⇒ at 100M distinct, 66,000x less memory
⇒ the sketch does not grow. That is the point.
Now the question that decides whether it is allowed:
the number is rendered as "10.2M views". The display
rounds to three significant figures anyway, so it has
already thrown away about 0.5% either way. The sketch's
0.81% error is the same size as that rounding.
Nobody can see the error. It was never in the output.That is the general test. Follow the number all the way to where a human or a decision consumes it, and check how much precision survives the trip. Very often the exactness was being destroyed downstream anyway, by rounding, by a chart axis, or by a threshold with a wide band around it.
How to tell you have this problem
Memory grows with distinct things rather than with active things. If a per-item structure gets bigger the longer the item exists, and it is holding identifiers only to avoid double counting, that is the cardinality case. Draw a chart of that structure's size over time; a line that never flattens is the signal.
A counter is a coordination point. If incrementing requires a lock, a round trip to a single owner, or a transaction, and the increment rate is high, that is the staleness case. Look for a row whose write rate is orders of magnitude above the rest of its table.
You are storing timestamps to answer a question about a window. A list of request times per key, trimmed on every read, is the windowed case. The tell is that memory per key scales with the request rate rather than being fixed.
Before reaching for any technique, ask one question: who or what actually consumes this number? A billing system needs it exact, because it charges money against it. A dashboard does not, because nobody glancing at a chart can tell it is off by 1 percent. If the answer is "we show it on a page", or "we compare it to a threshold somebody picked by feel", then nothing downstream needs the exactness. You can trade it for memory.
What it costs
The error has a direction, and you must know which. A rate limiter that undercounts lets abuse through; one that overcounts rejects real users. These are not symmetric and the product usually has a strong preference. Saying "roughly 100 requests a minute" is not a specification. "At most 5 percent over, never under" is.
Approximate numbers leak into places that need exact ones. The count you showed on a page gets copied into a report, then into an invoice. There is no type system stopping this. The defence is naming: call the field estimated_views, not views, so the next person has to think.
Sketches are opaque when they are wrong. An exact set can be inspected and diffed. A HyperLogLog register array cannot be reasoned about by looking at it. So when a count seems wrong, you cannot tell whether it is expected error, a bug in the merge, or the count genuinely changing. Keep an exact count for a handful of keys as a control, and track those keys both ways. If the two stay inside the sketch's known error bound, it is working as designed. If they drift further apart, you have a bug rather than noise.
Bounded staleness has an unbounded tail during incidents. The bound "one flush interval" holds while flushes succeed. When the data store is unavailable and flushes start queueing, the error grows without limit, and this happens exactly when people are looking at dashboards to understand an incident.
Merging has its own rules. Sketches only union correctly if they use identical parameters and hash functions. A parameter change is a migration, and mixing versions silently produces wrong answers rather than errors.
Where it shows up in the course
| article | the form it takes there |
|---|---|
| Bloom Filters and Probabilistic Structures | the membership half of the family, and why a Bloom filter cannot answer a question about how many |
| Distributed Rate Limiter | the sliding window counter, estimating a rolling window from two fixed ones, and the burst pattern that defeats the even-spread assumption |
| URL Shortener | HyperLogLog for unique visitors, where exact distinct counts over a petabyte cost far more than the answer is worth |
Getting it wrong
Reaching for a sketch before stating the tolerance. The technique is chosen by the error budget. Picking the technique first means the budget becomes whatever the technique happens to give, which is backwards.
Assuming the error is uniform. HyperLogLog's 0.81 percent is a standard error across many counts, not a guarantee about your one count. Any single estimate can be further out than that. Small counts use a different estimator entirely, linear counting rather than the HyperLogLog formula, because the HyperLogLog formula is known to be biased in that range.
Using an approximate count where money or law is involved. Billing, quota that customers pay for, and anything auditable need the exact path. It is fine to show the estimate and bill from the ledger; it is not fine to bill from the estimate.
Forgetting that the sliding window estimate assumes even traffic. It is exact only if the previous window was evenly spread. Traffic that arrives in bursts at window boundaries is precisely the traffic a rate limiter is meant to catch.
Letting staleness be undefined. "Eventually consistent" is not a bound. The bound is the flush interval. Put it in the design and on a dashboard, because during an incident it is the number that tells you whether what you are looking at can be trusted.