Approximate counting
Counting with a stated error instead of an exact figure: HyperLogLog for distinct items, a count-min sketch for item frequencies, sampling for rough totals. The design question it raises is whether the number has to be exact.
What it is
Approximate counting trades an exact figure for an estimate with an error you can state in advance, usually to save memory or write contention. The cost it avoids is real: counting distinct items exactly takes memory proportional to how many distinct items there are, because you have to remember each one to avoid counting it twice. A sketch (a compact summary of the stream) replaces that with a fixed block of counters whose size you choose from the error you can accept, so memory stays bounded however many items pass through.
Two different questions hide under the word "count", and they need different sketches. How many distinct items have I seen? is cardinality estimation, and HyperLogLog is the usual answer. How many times has this one item appeared? is frequency estimation, and a count-min sketch is the usual answer. Neither tells you which items were seen: the sketch holds state, not elements, so if you need the member list you need a set.
How HyperLogLog works. Each item is hashed into what looks like a uniformly random bit string. Among many random bit strings, the longest run of leading zeros hints at how many you've seen: if the longest run is n zeros, about 2 to the power n items have passed. One such guess has a large variance, so the algorithm uses the first few bits of the hash to pick one of m registers and lets each register keep its own maximum; the count combines the registers with a harmonic mean and a correction constant. For small counts the estimate is biased, so the original paper proposes a different method (Linear Counting) below a threshold. That paper reports counting past a billion distinct items with a standard error near 2% in about 1.5 kB, and merging two sketches is taking the larger value in each register pair, which yields the sketch of the union.
HyperLogLog in Redis. Redis has shipped it since version 2.8.9; the three commands you'll use are PFADD to add items, PFCOUNT for the estimate and PFMERGE to combine keys. The current documentation puts the memory at up to 12 KB per key, much less while a key has seen few items, with a standard error of 0.81%. A HyperLogLog is stored as a Redis string, so GET and SET serialize and restore it, and a merged key gives an estimate of the distinct items across all its sources.
Count-min sketch. A fixed-size table of counters, sized from the error you can accept rather than from the number of items. Hash collisions add to counters, so the estimate can be too high but not too low, and the error is measured relative to the total of everything added: you choose a threshold and a probability of staying within it. That makes small counts unreliable: the Redis documentation advises treating results under the error threshold as noise, often as zero. In Redis you size it by tolerance: CMS.INITBYPROB key 0.001 0.002 asks for error within 0.1% of the total with a 0.2% chance of exceeding it, and the resulting sketch is 2000 wide and 9 deep; CMS.INCRBY adds, CMS.QUERY estimates, CMS.MERGE combines.
Analytics warehouses expose the same ideas as SQL functions. BigQuery has APPROX_COUNT_DISTINCT and APPROX_TOP_COUNT among its approximate aggregate functions, alongside a separate family of HyperLogLog++ functions for working with the sketch itself.
When to use it
Reach for HyperLogLog when the question is distinct items at a scale where a set per key would be large: unique viewers per video, unique visitors per page per day, distinct IPs hitting an endpoint. Millions of keys at a bounded 12 KB each is a budget you can state; millions of sets of user IDs is not. Keep one sketch per period and per dimension (day, page, country) and merge them for rollups: the weekly figure is a merge of seven daily sketches, with no recount of the raw events.
Reach for a count-min sketch when the question is how often particular items appear and the heavy hitters are what matter: trending hashtags, the hottest keys in a cache, products that dominate a day's sales. The Redis documentation's own example is one sketch per day of product sales, which gives a reasonable figure for the top sellers while the long tail is ignored. The sketch answers "how often did X appear" for an X you supply; to discover the top items, pair it with a small list of candidates (a sorted set of the current leaders, for example) that you check and update as events arrive.
When not to
Keep the count exact when being wrong has a cost you can name: money, remaining stock in a sale, a quota that gates access, anything audited. An estimate that's 1% high on a payout is a bug, not a trade-off. Also stay exact when the distinct set is small or bounded: a set of a few hundred IDs is cheap, and a plain hash of counters for a known, bounded key space is exact and small.
Don't use a count-min sketch to read rare items. Its error is relative to the total of everything added, so an item seen a handful of times among billions of events can read far higher than the truth, and such values should be treated as noise. If rare items matter (fraud signals, first-time users), track those keys exactly in a structure of their own; untargeted sampling tends to miss them too.
A high write rate is often better met without approximation. If a single like counter is a hot key, split it into N shards, increment one at random, and sum the shards on read: the total stays exact and the write load spreads out. See Hot keys and hot partitions. Approximation earns its place when memory is the constraint, when the answer is a distinct count that sharding does not make cheap, or when you are willing to trade accuracy for less coordination between writers.
Compared
| Approach | What it answers | Memory | Error | When it is the right pick |
|---|---|---|---|---|
Exact set or hash of counters | Distinct members, or exact per-key counts | Grows with the number of distinct items | None | Small or bounded key spaces, or when you need to know which items appeared |
Sharded exact counter | One total under heavy writes | One slot per shard | None | Totals that must be exact (stock, money) where the problem is write contention, not memory |
Sampling (count 1 in k, multiply) | A rough total or breakdown | Proportional to the sample | Depends on sample size | Rough traffic breakdowns where a sketch per dimension would be overkill |
HyperLogLog | How many distinct items | Fixed: up to 12 KB per key in Redis | Standard error 0.81% in Redis | Very large distinct counts, and rollups by merging per-period sketches |
Count-min sketch | How often one item appeared | Fixed width times depth (2000 by 9 for 0.1% and 0.2%) | Overestimates; likely within a threshold set relative to the total added, with a configured chance of exceeding it | Heavy hitters and trending items, where the long tail can be ignored |
In a picture
Step 1 of 4
Hash the item
Each item (a user ID, an IP) goes through a hash function so the bits look uniformly random.