The Redis documentation makes a pair of promises that should not be able to coexist. Ask a HyperLogLog key how many distinct items it has seen, a billion of them if you like, and it will answer using at most 12 kilobytes of memory, with a standard error of 0.81 percent. Twelve kilobytes for a billion-item question, and then that oddly confident second decimal.
Here is the thing about 0.81: it is not a benchmark result. Nobody measured it on a workload. It is 1.04 divided by the square root of 16,384, the number of registers Redis chose, and the 12 kilobytes is those 16,384 registers at six bits each. Both promises fall out of one design decision, made years before your data existed. That is the subject of this essay, because the same move that makes the trick possible is a bargain most engineers strike daily without noticing: the sketch answers its question in constant space forever, and in exchange there are questions it can never answer at all.
Counting distinct things exactly requires remembering them. To know whether the next user ID is new, you must be able to check it against every ID you have seen, so a precise distinct count of a billion 16-byte identifiers costs you gigabytes before you build a single index. For a stream, a firehose of events flowing past once, that memory bill grows without bound, and the stream does not wait while you shop for RAM.
This is the river problem. You cannot store a river. You can only decide, before the water arrives, what to measure as it passes. The entire field of streaming sketches lives inside that sentence, and the decision part matters as much as the measuring part.
HyperLogLog's answer has three moves. Excellent long-form walkthroughs exist, Alex Nadalin's freeCodeCamp essay among them, so here is the compressed version.
First, hash everything. A good hash turns each item into a fixed-size string of effectively random bits, and, crucially, the same item into the same bits every time. Duplicates therefore cost nothing: the ten-thousandth appearance of the same user ID produces the same hash and changes nothing. Deduplication was never added to the algorithm. It falls out of hashing itself.
Second, look for rare patterns. In random bits, half of all hashes start with a 1, a quarter start with 01, an eighth with 001. Seeing a hash that begins with sixteen zeros is like hearing that someone flipped sixteen heads in a row: it almost never happens unless a great many attempts occurred. So the rarest prefix you have ever observed is evidence about how many distinct items have passed. One observation is terribly noisy, one lucky hash early on and your estimate is garbage.
So, third, run thousands of observers and average them carefully. Redis uses the first 14 bits of each hash to pick one of 16,384 registers, and each register remembers only the longest run of leading zeros it has ever witnessed, a number that fits in six bits. That is the whole data structure: 16,384 six-bit maxima, 12,288 bytes. The estimates are combined with a harmonic mean, which resists exactly the lucky-outlier problem, and the 2007 paper by Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier identifies that averaging choice as the upgrade over the earlier LogLog algorithm. The paper, presented at the Analysis of Algorithms conference and published in the DMTCS proceedings, proves the accuracy claim rather than reporting it: standard error of 1.04 over the square root of the register count, cardinalities beyond a billion, about 2 percent typical error, in 1.5 kilobytes.
Notice that the paper says 1.5 kilobytes and Redis ships 12. Those are not competing claims; they are two points on one curve, and you should always state the configuration alongside the error. The formula makes the price list explicit: halving the error means quadrupling the registers. The paper's configuration and Redis's differ by eight times the memory for roughly a third of the error, which is exactly what a square root predicts. Push further and the arithmetic turns hostile; getting to 0.1 percent would take around a million registers, most of a megabyte, for one counter. Diminishing returns are not an implementation weakness. They are printed in the formula, which is why nobody ships an HLL at 0.1 percent.
One honest complication before the good part. A production HyperLogLog is two or three estimators with a seam between them. At small counts the leading-zeros machinery underestimates badly, so implementations switch to a different estimator down there, and at the switchover point the error used to spike visibly. Google's engineers, Stefan Heule, Marc Nunkesser and Alexander Hall, documented this in their 2013 paper on HyperLogLog++, and their fix for the bias in the awkward middle range was not a new theorem. It was empirical: precomputed correction tables built from simulations, interpolated with k-nearest-neighbors, k equal to 6. The bounds are provable and the proofs are real, and in the wild the seam between regimes still needed patching with lookup tables. Keep both halves of that sentence; we will need them at the end.
Now the part that the dozen existing explainers skip, which is a shame, because it is the load-bearing part.
A HyperLogLog supports exactly one set operation natively: union. And its union is a small miracle. To merge two sketches, Redis's PFMERGE takes, register by register, the maximum of the two values, and the result is not an approximation of a merged sketch. Every register ends up holding exactly the value it would have held if one counter had watched both streams from the beginning. Maximum commutes with everything the structure cares about. This is why sketches distribute so well: give every server its own 12-kilobyte counter, merge at read time, and the answer is as good as if there had been one giant counter all along.
Intersection has no such operation. There is nothing you can do register-by-register to two HLLs that yields the sketch of their overlap. The workaround everyone reaches for is inclusion-exclusion, intersection equals A plus B minus their union, but now you are subtracting three noisy estimates, and the Apache DataSketches documentation is blunt about the consequence: the errors accumulate, and when the true overlap is small relative to the sets, the relative error becomes very large. Sit with that failure mode for a second. "How many users did January and February share" is answerable, badly. And the smaller the overlap, the worse the answer, which inverts the usual value of a question: rare overlap is precisely when someone cares. The audience segments that barely intersect, the two incident logs that share three IP addresses. The sketch is weakest exactly where the question gets interesting.
Here is what makes this a decision rather than a lament: the commitment was choosable, from a menu, the whole time. Theta sketches, descendants of the K-Minimum-Values idea, natively support union, intersection and difference with well-behaved error, at a different cost profile. They ship today in Apache DataSketches, and LinkedIn's engineering team published the receipts: they wired Theta sketches into Apache Pinot specifically because they needed intersection cardinalities at scale, audience-overlap questions that HyperLogLog structurally cannot answer well. Same river, different instrument, different menu of askable questions.
So the trade is not "give up exactness, get constant space," which is how sketches are usually explained. The real trade is stranger and sharper: you commit, at design time, to the complete list of questions you will ever ask this data summary, and the summary then answers those questions forever, in kilobytes, with proven error. Ask off the menu and no amount of memory rescues you. You do not fix a wrong commitment by upgrading. You migrate to a different sketch and wait while it re-observes the river.
The commitment goes one level deeper than which questions. The Count-Min sketch, published by Graham Cormode and S. Muthukrishnan in the early 2000s, tracks approximate frequencies, how many times each item appeared, in a fixed grid of counters that never grows with the stream. Several hash functions each map an item to a counter; on a query you read all of the item's counters and take the minimum. Collisions mean other items' counts leak into yours, but leakage only ever adds. A Count-Min estimate can be too high and can never be too low.
That is a one-sided error, and it is a commitment about direction, chosen before the first packet arrives. The streaming literature's standard application is finding heavy hitters, the few items suddenly dominating a stream, which is the shape of flood and abuse detection. For that job, the two error directions have wildly different prices: an overcount sends someone to double-check a suspect that turns out innocent, while an undercount silently waves the flood through. Count-Min's design pays for its guarantee in false alarms and buys the certainty that it will never miss quietly. You could not make that purchase after the fact. The direction of allowable wrongness was baked into "take the minimum" on day one.
None of this is exotic. Redis has shipped HyperLogLog as a first-class type since 2014, announced by Salvatore Sanfilippo with the register arithmetic laid out in the post. Google's HLL++ paper does not propose anything. It describes the estimator already running inside Google's own data systems. BigQuery's APPROX_COUNT_DISTINCT is documented as HyperLogLog++ with a default precision of 15, tunable from 10 to 24 through the HLL_COUNT functions, and Google Analytics states in its developer documentation that its unique-user counts ride the same algorithm. InfluxDB carries an HLL estimator package in its source tree. Apache Druid documents cardinality sketches as a product feature. If a dashboard has ever given you a distinct-user count over a year of events fast enough to feel wrong, you have probably consumed a sketch without being told.
One discipline note, because this essay is about commitments: we verified the query functions above against their documentation, and we are deliberately not claiming which databases use HLL inside their query planners for row estimates. We did not check planner internals, so that claim is not on our menu.
And one labeled extrapolation. Compliance screening, the world where the job is counting and matching distinct entities across transaction streams, looks from outside like the perfect sketch customer, and we could find no vendor document saying so. So treat this as a prediction rather than a report, and note what the framework says: distinct counterparties across sharded streams is union work, HyperLogLog's native strength, but the question that world is actually paid to answer, which entities on this stream also appear on that list, is a small-overlap intersection, the exact query HLL handles worst. If screening systems run on sketches, the framework predicts they run on Theta-shaped ones. That prediction is falsifiable by a single well-placed engineering blog post, and we would genuinely like to be graded on it. Filed 4 August 2026, dated here so it can be resolved rather than quietly forgotten.
Step back far enough and HyperLogLog stops being a clever algorithm and becomes an unusually honest contract. Every summary you keep is a bet about the future of your own curiosity. Schemas, rollups, sampled traces, 90-day retention windows, the four metrics on the exec dashboard: each one is a decision about which questions will remain answerable after the raw data is gone, made before you know which questions will matter. The raw stream is the only artifact that answers questions you have not thought of yet, and the raw stream is the river: you cannot afford to keep it. You are already sketching. The only variable is whether your commitments are written down with their error bars, the way HLL's are, or discovered later, in an incident review, when someone asks last quarter's data a question nobody reserved the right to ask.
Which moves the useful design-time question off accuracy and onto foreclosure: did anyone write down what this summary makes unaskable? There is one test that surfaces most of it, and it takes about a minute: which pairs of things will we someday want the overlap of? Overlap is what summaries kill quietly. A summary that breaks loudly gets fixed, and HyperLogLog's intersection does not break loudly; it keeps answering, wrong by more the rarer the overlap gets.
The same question has a second edge, which is direction. If the cost of missing something and the cost of a false alarm differ, and they almost always differ, then the bias of the summary is a purchase you make once, before the first packet, and Count-Min's never-undercount guarantee is what it looks like to make it on purpose. Point the bias at the cheap mistake and record that you chose it, because a deliberate bias nobody documented is indistinguishable, a year later, from a bug.
And put the tests where the regimes meet, whatever the proofs say. That is the second half of the sentence from earlier, the one worth keeping: HyperLogLog's bounds are theorems, and production still needed simulation-built correction tables where two estimators join. Small-count to large-count, cached to computed, one estimator to the next, the seam is where proven components produce unproven behaviour.
HyperLogLog counts the river by agreeing, in advance and in writing, never to ask certain questions about the water, and it has kept that bargain in 12 kilobytes for over a decade. The dangerous summaries are not the approximate ones. They are the ones that never wrote their menu down.
hll estimator package (pkg.go.dev); Imply/Druid documentation, "Compute results with cardinality sketches."The summary you keep is a bet on your own future curiosity
HyperLogLog is honest about its bargain: the error bars are printed in the formula and the questions it cannot answer are structural rather than incidental. Most summaries are not that honest. Rollups, sampling schemes and retention windows foreclose questions too, and almost none of them write the menu down, so the foreclosure gets discovered in an incident review instead of a design review. The same hole opens under any AI system whose behaviour is reconstructed after the fact from a summary. Chain of Consciousness keeps the raw stream instead, a tamper-evident record of what an agent did, on what inputs, in what order, written while the work runs rather than summarised once it is over.
Hosted Chain of Consciousness · Verify a record
pip install chain-of-consciousness · npm install chain-of-consciousness