# How to Count 100 Billion Things in 12 Kilobytes

> Source: <https://dev.to/lovestaco/hyperloglog-how-to-count-100-billion-things-in-12-kilobytes-5aae>
> Published: 2026-09-16 12:23:43+00:00

*Hello, I'm Maneshwar, and I'm building LiveReview — a blast-radius aware AI code review built for your business-critical systems. [Star us](https://github.com/HexmosTech/LiveReview/) to help devs discover the project, give it a try, and share your feedback to help improve the product.*

An interviewer asks you a question that sounds almost insultingly easy.

How many unique visitors did the site have today?

You say: easy, I'll hash every request ID into a set. `HashSet<String>`, one entry per unique visitor, done before the coffee's cold.

Then they say: it's a hundred billion requests.

Your hash set just quietly asked the OS for about a terabyte of RAM, and the OS just as quietly said no.

You could shard it. Spin up forty machines, split the ID space, merge partial sets at query time.

That works. It is also an entire distributed system you now have to run, just to answer "how many different people showed up."

There's a much smaller way to answer this, and it doesn't even need to remember the visitors.

A hash set is exact because it remembers everything.

Every single unique ID gets a slot, forever, because that's the only way to know for certain you haven't seen it before.

That's also exactly why it doesn't scale. Memory grows linearly with the number of uniques, no matter how you slice it, shard it, or compress the keys.

If your product only ever has a few hundred thousand daily uniques, this is a complete non-problem. Use the hash set, go home.

But once you're talking billions, "remember everything" stops being an engineering decision and starts being a bet against your cloud bill.

The way out isn't a bigger hash set. It's giving up on "exact" entirely, on purpose, in exchange for something that fits in your CPU's L2 cache.

Here's the actual insight, stripped of the mechanism around it.

Hash every ID into a long, effectively random bit string.

Now look at how many zeros it has at the start, before the first `1` bit shows up.

Since each bit is a coin flip, the odds are simple: 50% of hashes start with at least one zero, 25% start with at least two, 12.5% with at least three, and so on. Each extra leading zero you demand halves how many hashes will have it.

Flip that around and it becomes a counting trick.

If you've hashed a handful of IDs and none of them start with three zeros, that's unremarkable, you'd expect that from 8 items. But if you've seen a hash that starts with six zeros, that's a 1-in-64 event. Seeing it *once* is weak evidence you've hashed something on the order of 64 items, because you'd need to try roughly that many random hashes before one that rare shows up.

So: hash every incoming ID, and keep a running max of the longest leading-zero streak you have ever seen. That single number, "longest streak seen so far," gives you a rough estimate of `2^streak` unique items.

This idea goes back to Flajolet and Martin's original 1985 probabilistic counting paper, and the modern form is called [HyperLogLog](https://en.wikipedia.org/wiki/HyperLogLog), from [Flajolet, Fusy, Gandouet and Meunier's 2007 paper](http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf).

Here's the single-counter version, in about ten lines, so you can see exactly how weak it is on its own:

``` python
import random

def leading_zeros(x, bits=32):
    if x == 0:
        return bits
    return bits - x.bit_length()

def single_counter_estimate(n_items):
    max_streak = 0
    for _ in range(n_items):
        h = random.getrandbits(32)
        max_streak = max(max_streak, leading_zeros(h))
    return 2 ** max_streak

# run it a few times on the same n and watch the estimate swing wildly
for _ in range(5):
    print(single_counter_estimate(10_000))
```

Run that a handful of times against the same `n_items` and the estimates will swing by 2x, 4x, sometimes more in either direction. One lucky hash with an extra-long streak, or one unlucky run without one, and the whole estimate moves.

A single coin flip streak is just too noisy to trust. HyperLogLog doesn't use one counter, it uses thousands, and averages them in a very specific way.

Instead of one counter, take the first few bits of each hash and use them to pick one of `m` buckets, say `m = 16384`. The remaining bits of the hash get the leading-zero treatment from before, and the result updates that bucket's own running max.

You now have thousands of tiny, independent "longest streak I've seen" estimators, each looking at a different slice of the ID space. Average them, and the noise from any one unlucky or lucky streak gets smoothed out by the other 16,383 buckets.

There's one more wrinkle worth knowing. HyperLogLog uses the *harmonic mean* across buckets, not the arithmetic mean. A plain average gets wrecked by a single bucket that got a freakishly long streak, since `2^streak` grows exponentially, one outlier bucket can dominate a normal average completely. The harmonic mean punishes large outliers far more than small ones, which is exactly the failure mode you need to guard against here.

``` php
flowchart TD
    A[ID arrives] --> B[Hash it to a uniform bitstring]
    B --> C[First p bits pick a bucket]
    C --> D[Count leading zeros in the rest]
    D --> E{Longer streak than<br/>this bucket has seen?}
    E -->|Yes| F[Store it as the bucket's max]
    E -->|No| G[Discard, bucket keeps its max]
    F --> H[m buckets, each holding one max streak]
    G --> H
    H --> I[Harmonic mean across all buckets]
    I --> J[Bias-correct for small and huge counts]
    J --> K[Cardinality estimate, ~2% error]

    classDef decision fill:#f4d35e,stroke:#b8991f,color:#1a1a1a
    classDef start fill:#e9ecef,stroke:#6c757d,color:#1a1a1a
    classDef step fill:#6ea8ff,stroke:#2f5fbf,color:#1a1a1a
    classDef store fill:#5ee6c8,stroke:#1f9c86,color:#1a1a1a
    classDef result fill:#9d8cff,stroke:#5b4bcc,color:#1a1a1a

    class A start
    class E decision
    class B,C,D step
    class F,G,H store
    class I,J,K result
```

With `m` buckets, the standard error works out to roughly `1.04 / sqrt(m)`. Plug in 16,384 buckets and you land at just over 0.8% expected error, which is where Redis's implementation sits.

That error bound doesn't depend on whether you counted a million items or a hundred billion. It only depends on `m`, the number of buckets, which is a number you pick up front.

That's the whole trade. You fix your error tolerance once, at design time, by choosing `m`, and the memory cost stays flat forever after. A few small corrections handle the edges: [linear counting](https://en.wikipedia.org/wiki/HyperLogLog#Practical_considerations) kicks in when very few buckets have been touched yet, so a tiny actual count doesn't get wildly overestimated, and a large-range correction avoids hash collisions skewing things once you approach 2^32 distinct items.

The best part of HyperLogLog isn't the estimate, it's that two of them merge for free.

Since each bucket is just "the max streak seen," merging two HyperLogLogs means taking the elementwise max of their buckets. No replay, no recomputation, no access to the original IDs at all. That's why it works so well for things like "daily uniques" that you also want to roll up into "weekly uniques."

Redis has had this built in for years, as three commands:

```
# add IDs as they arrive, one PFADD per event
PFADD visitors:2026-09-16 user_881 user_204 user_991

# get the estimated cardinality, ~12KB per key no matter how big it gets
PFCOUNT visitors:2026-09-16

# merge daily counters into a weekly one, no replaying the day's events
PFMERGE visitors:week-38 visitors:2026-09-12 visitors:2026-09-13 visitors:2026-09-14 visitors:2026-09-15 visitors:2026-09-16
```

[Redis's PFADD docs](https://redis.io/docs/latest/commands/pfadd/) put the standard error at 0.81%, using [Google's HyperLogLog++ paper](https://research.google/pubs/hyperloglog-in-practice-algorithmic-engineering-of-a-state-of-the-art-cardinality-estimation-algorithm/) for the small-and-large range corrections on top of the original algorithm.

It's not just Redis either. [BigQuery's `APPROX_COUNT_DISTINCT`](https://cloud.google.com/bigquery/docs/reference/standard-sql/approximate_aggregate_functions), Presto and Trino's `approx_distinct`, and Spark's `approx_count_distinct` are all the same idea wearing a SQL function's clothes. Every "unique visitors" widget on every analytics dashboard you've ever glanced at is very possibly running this exact algorithm under the hood, right now, while you read this sentence.

None of this means throw away exact counting. It means know which question you're answering.

If the number needs to be exact, billing a customer per API call, deduplicating a payment, deciding whether a user already redeemed a coupon, HyperLogLog is the wrong tool. It cannot tell you whether one specific ID has been seen, only roughly how many distinct ones have.

If your cardinality is small anyway, a few thousand, a few hundred thousand, a plain hash set fits in memory with room to spare and gives you an exact answer for free. Reach for HyperLogLog when the count itself is the product, "how many uniques," "how many distinct IPs," "how many distinct search terms," and the scale is big enough that remembering every item stops being realistic.

That's the whole pitch. You trade a guarantee you never actually needed for a memory bill you can actually afford, with error bounds you get to choose in advance.

Next time somebody says "a hundred billion" in an interview, you now have a much better answer than "shard it."

Your team's attention is limited, and the deluge of AI-generated code is making it harder to keep production secure and reliable without slowing you down.

I'm building **LiveReview**, a blast-radius aware AI code review built for your business-critical systems.

Instead of presenting every diff with equal emphasis, **LiveReview scores each change by blast radius — how far its impact reaches through your call graph — so you can focus attention where it actually matters.**

Spend code review effort where business risk is highest — not spread evenly across every diff.

⭐ Star it on GitHub:

LiveReview is an AI code reviewer that scores every hunk of a diff by **blast radius**: how far a change reaches through your call graph, how much persistent state it touches, and how well-tested it is. A 3-line change to a shared auth check can outrank a 300-line UI tweak. Your team's attention goes to the highest-risk code first, not spread evenly across every diff.

*LiveReview's Blast Radius & Review Priority scoring, live in the diff viewer.*

| The exact math, not a black box | Visualize blast radius at a glance | Every factor that feeds the score | 
|---|---|---|

**Here's the goal:**

**Click below to try LiveReview with your codebase:**