HyperLogLog

How many distinct people visited a website yesterday? It sounds trivial: keep a list of the IDs you have seen, and ignore repeats. With a billion visitors that list weighs gigabytes — and you need one for every page, every hour, every region.

The obvious exact method costs memory proportional to the number of distinct items. When the stream is bigger than your machine, "just remember everything" stops being an option.

HyperLogLog, published by Philippe Flajolet, Éric Fusy, Olivier Gandouet and Frédéric Meunier in 2007, answers the question with a stunning trade: it gives you the count to within a few percent using only kilobytes, no matter how astronomically large the true number is — and it never stores a single item.

Below is a tiny HyperLogLog sketch with just a few buckets. Press Add items to stream values through it — some new, some repeats. The sketch never stores what it sees; it only remembers, per bucket, the longest run of leading zeros in the hashes it has met.

<p class="hint">{{hint}}</p>
<div class="stats">
  <div class="stat"><span class="lbl">{{lbl_true_distinct}}</span><span id="truth" class="val">0</span></div>
  <div class="stat"><span class="lbl">{{lbl_hll_estimate}}</span><span id="est" class="val est">0</span></div>
  <div class="stat"><span class="lbl">{{lbl_error}}</span><span id="err" class="val">0%</span></div>
  <div class="stat"><span class="lbl">{{lbl_memory}}</span><span id="mem" class="val">80 bits</span></div>
</div>
<div id="buckets" class="buckets"></div>
<div class="btns">
  <button id="add" type="button">{{btn_add}}</button>
  <button id="reset" type="button" class="ghost">{{btn_reset}}</button>
</div>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.stats { display: grid; grid-template-columns: repeat(4, 1fr); gap: .5rem; margin: .4rem 0 .8rem; }
.stat { background: #f1f4f8; border: 1px solid #dde4ec; border-radius: 8px; padding: .5rem .6rem; text-align: center; }
.lbl { display: block; font-size: .7rem; text-transform: uppercase; letter-spacing: .04em; color: #5a7088; }
.val { display: block; font: 700 1.15rem ui-monospace, monospace; color: #1d3557; margin-top: .15rem; }
.val.est { color: #0a7d33; }
.buckets { display: grid; grid-template-columns: repeat(16, 1fr); gap: 3px; margin: .2rem 0 .9rem; align-items: end; height: 90px; }
.bucket { background: #c9ccd1; border-radius: 3px 3px 0 0; display: flex; align-items: flex-start;
          justify-content: center; font: 700 11px ui-monospace, monospace; color: #1d3557;
          min-height: 6px; transition: height .25s; }
.btns { display: flex; gap: .5rem; flex-wrap: wrap; }
button { font: 600 14px system-ui, sans-serif; padding: .45rem .9rem; border: 1px solid #1d3557;
         background: #1d3557; color: #fff; border-radius: 8px; cursor: pointer; }
button.ghost { background: #fff; color: #1d3557; }

// Code not found

Watch the estimate climb toward the true distinct count while memory stays flat. The intuition is a coin-flipping game: if the most extreme streak you have ever seen is k heads in a row, you have probably flipped about 2ᵏ times. A long run of leading zeros in a random hash is exactly that streak — so the rarest hash you have seen tells you roughly how many distinct items produced it.

Why does so little memory suffice? It comes down to what you actually need to know.

• Exact counting is expensive. To never make a mistake you must remember which items you have already seen — provably linear memory in the number of distinct elements. There is no way around it if zero error is required.
• The leading-zeros trick. Hash each item to a random bit string. The maximum number of leading zeros seen, ρ, behaves like the longest streak in a coin game: about 2^ρ distinct items are needed to produce a streak of length ρ. A single bucket gives a noisy estimate.
• Averaging with buckets. HyperLogLog splits the hash to route items into m buckets and combines them with a harmonic mean, taming the variance. Each bucket only stores a small integer — $O(\log \log n)$ bits — hence the name.
• The accuracy law. The relative error is about 1.04/√m. With m = 2048 buckets that is roughly 2.3% error in around 1.5 KB, for any cardinality up to billions.

So HyperLogLog does not beat the lower bound for exact counting — it sidesteps it by accepting a small, controllable error. This is the streaming-algorithm bargain, the same spirit as Bloom filters: trade a little certainty for an enormous memory win.

"How many distinct X?" is one of the most asked questions in data systems, and HyperLogLog answers it cheaply almost everywhere:

• Web analytics: unique visitors per page, per day, per region — millions of counters that would never fit if each stored a full ID set.
• Databases and warehouses: Redis (PFCOUNT), Presto, Apache Druid, Google BigQuery and Amazon Redshift all ship approximate COUNT(DISTINCT) built on HyperLogLog.
• Networking and security: counting distinct source IPs or ports in a traffic stream to spot scans and floods.
• Mergeable counts: two sketches can be combined by taking the per-bucket maximum, so you can count distinct users across a whole cluster by merging tiny summaries.

Understand HyperLogLog and you understand the broader family of probabilistic sketches — the same trade behind Bloom filters and other tools that summarize unbounded data in bounded space.

HyperLogLog turns a humble observation — that a long run of leading zeros is rare, and rarity measures how many tries you took — into a tool that counts the uncountable. It never stores an item, and its memory barely grows as the count explodes from thousands to billions.

The lesson reaches past one algorithm. When perfect answers cost too much, the smartest move is often to ask for an almost perfect one. Accept a few percent of error and the impossible becomes a kilobyte. The next time a dashboard tells you "1.2 million unique visitors," remember: nobody counted them. A few hundred tiny counters watched the coin flips and made a very good guess.