---
title: "HyperLogLog"
description: "A cat video gets 50 million views. How many different people watched it? A tiny sketch can help us estimate the answer."
canonical_url: "https://otabek.io/blogs/hyperloglog"
md_url: "https://otabek.io/blogs/hyperloglog.md"
language: "en"
last_updated: "2026-03-26"
tags: ["Algorithms", "Data Structures"]
---

# HyperLogLog

Imagine we're building a video platform like **YouTube**. Someone uploads a cat video. It takes off: **50 million views**. The creator asks, **“But how many different people watched it?”**

![Otabek and his white cat Mimi sharing a laptop, with Mimi looking very serious about the keyboard](/images/blogs/hyperloglog/cover-otabek-mimi.png)

You might replay that cat video 20 times. That's 20 playbacks, but still ONE viewer. The cat didn't magically gain 19 new fans 😄

```text
Playbacks:         otabek, chris, otabek
Different viewers: otabek, chris
Answer:            2
```

For playbacks, we can just add one to a counter each time we count a view. **Unique viewers** is trickier: the same viewer ID should only count once. SQL can do this with `COUNT(DISTINCT user_id)`. But what happens when millions of people keep watching, and the creator wants a fresh count every few seconds?

In the [Bloom filter post](https://otabek.io/blogs/bloom-filter), we looked at checking whether an element might exist. Today, we're going to estimate **how many different elements exist**, using surprisingly little memory. Let's see how ✨

## What About a Set?

A **Set** is like a guest list where each name can appear only once. We could keep one for the IDs that arrive:

```js
const visitors = new Set()

visitors.add('otabek')
visitors.add('chris')
visitors.add('otabek')

console.log(visitors.size) // 2
```

Duplicates disappear automatically. We can read the count without repeatedly querying all the visits. Nice!

But the Set has to remember every unique ID. With **100 million** users and 8 bytes per ID, that's **800 MB** for the IDs alone. The Set itself needs more space too. This is an example using 8-byte IDs; JavaScript strings have a different memory cost.

Now imagine separate counts for each day, each video, and each country. The memory bill starts looking less friendly.

![Set versus HLL meme: a panicked cat buried in ID cards beside a relaxed cat with a tiny statistical sketch](/images/blogs/hyperloglog/meme.png)

**Creator:** “Just a rough count, please.”

**Set:** “Got it. I'm bringing all 100 million IDs.”

**HLL:** “I brought a note.”

Both SQL and Sets can still be the right choice. But if the creator only needs to know roughly how many people they reached, do we really need to keep every ID?

## HyperLogLog

**HyperLogLog**, or **HLL**, is a **probabilistic data structure**. It keeps a few small counters and uses them to estimate how many different IDs it has seen.

You'll see two names in the documentation: **sketch** for the small summary we store, and **cardinality** for the number of different IDs. We're still trying to answer the same question: how many people watched the cat?

> **Probabilistic** means we accept some uncertainty to save memory, just like with Bloom filters. HLL gives us **an estimate**, which can differ from the true count.

If you've checked **Active Users** in **Google Analytics 4**, you've already met this idea. Google uses **HyperLogLog++** for metrics including Active Users and Sessions. That neat number on the screen is an approximation too. [Google Analytics engineering explanation](https://developers.google.com/analytics/blog/2022/hll)

Redis's version can do this with about **12 KB** of counter storage. We'll return to accuracy after seeing how it works. [Redis documentation](https://redis.io/docs/latest/develop/data-types/probabilistic/hyperloglogs/)

How can something that small say anything useful about millions of users?

Let's follow one ID:

**ID → a fixed label of zeros and ones → a little counter → an estimate.**

Once we've updated the counter, we don't need to keep that ID.

## What Can Zeros Tell Us?

Think of a **hash function** as a label printer. Give it `otabek` and it prints a label made of zeros and ones. Give it `otabek` tomorrow and it prints the SAME label. A suitable hash function spreads different inputs across random-looking bit patterns.

Now think about tossing a fair coin. One head is ordinary. Ten heads in a row is much rarer. The beginning of a good hash behaves similarly: one zero is common, ten zeros in a row is rare.

These zeros at the start are called **leading zeros**. For example, `0001...` has three.

For uniformly distributed bits, the probability that a hash starts with:

| Prefix | Probability |
| --- | --- |
| `0...` | 1 in 2 |
| `00...` | 1 in 4 |
| `000...` | 1 in 8 |
| `0000000000...` | 1 in 1,024 |

Each extra zero halves the probability. So, as we see more distinct hashes, we have more opportunities to encounter a long run of zeros.

Imagine someone shows you a hash starting with 20 zeros. You'd suspect they looked at quite a few hashes to find it. But they could also have been lucky on their first attempt! **A rare pattern is evidence, not an exact count.**

One lucky hash shouldn't decide how many viewers we think our cat reached. So we split the work across many little boxes, each keeping its own record. Those boxes are where the registers come in. [Redis creator's explanation](https://antirez.com/news/75)

## One Hash, Two Jobs

Imagine **16 little boxes**, each with a high-score display starting at zero. In HLL, a group of hashes is a **bucket**, and the number we keep for that group is a **register**. The high-score display is the register.

Each label does two jobs:

1. Its first 4 bits choose one of the 16 boxes.
2. In the remaining bits, count the zeros before the first `1`, then add 1. That's the score, called the **rank**.

Why add 1? Zero is reserved for “this box hasn't seen anything yet.” Even a label with no leading zeros should leave a mark.

Here is a made-up, shortened hash to make the steps visible:

```text
1010 | 000100101011
^^^^   ^^^
 10    3 leading zeros → rank 4
```

`1010` is 10 in binary, so this label goes to box 10. Its score is 4. We only replace the old score if the new one is larger:

```text
register[10] = max(register[10], 4)
```

That's all a register remembers: **one high score**, not the labels that produced it. [Original HyperLogLog paper](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)

Let's write the register update in JavaScript. We'll use short, made-up hashes so it's easy to follow. There's more to a working HLL, but this is the part we're trying to understand:

```js
const registers = new Uint8Array(16)

function observeHash(bits) {
  const bucket = parseInt(bits.slice(0, 4), 2)
  const remaining = bits.slice(4)
  const firstOne = remaining.indexOf('1')
  const rank = firstOne === -1 ? remaining.length + 1 : firstOne + 1

  registers[bucket] = Math.max(registers[bucket], rank)
}

observeHash('1010' + '000100101011') // rank 4 → register 10 becomes 4
observeHash('1010' + '010101101001') // rank 2 → still 4
observeHash('1010' + '000010101101') // rank 5 → becomes 5
observeHash('1010' + '000010101101') // same hash again → still 5

console.log(registers[10]) // 5
```

Notice the last line: adding the same user again changes nothing. The hash, bucket, and rank are all identical. We didn't need to keep a list of previous IDs to get that behavior!

But a NEW user can also leave the register unchanged, just like the second input. So we can't use this structure to answer “has this particular user visited?”

## Turning Registers Into a Count

Each box now has a high score. Large scores across many boxes suggest we've seen many different IDs. One unusually large score in one box is much weaker evidence.

HLL combines these clues using a special kind of average, designed to reduce the influence of extreme values. It doesn't simply add the scores. Implementations also make corrections, especially when there are only a few IDs. [Original HyperLogLog paper](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)

That's the main idea: **keep a few clues about the crowd, then estimate its size**. You can follow the rest of the post without the formula; I've put it in the [optional math section](#optional-math).

## How Much Accuracy Are We Giving Up?

Redis uses **16,384 registers**, giving about **0.81% standard error**. Think of that as the scale of the usual estimation error, **not a promise that every answer is within 0.81%**. [Redis creator's explanation](https://antirez.com/news/75)

For a true count of one million, 0.81% corresponds to roughly 8,100 users. If the creator wants to know whether a few thousand people watched or a million, that might be fine. If we're charging per unique viewer and need an exact count, we can't just shrug off the difference.

More registers improve accuracy, but need more memory. Roughly **four times as many registers** halves the standard error.

Each Redis register needs only 6 bits, so all 16,384 fit in **12 KiB**. Headers and the Redis key need a little extra space. With few IDs, Redis can use a smaller representation; once the full register array is allocated, adding IDs doesn't make it grow. [Redis implementation](https://github.com/redis/redis/blob/unstable/src/hyperloglog.c)

But if we keep **one sketch per video per day**, those sketches add up too. We still need to decide how many days of data to keep.

**Facebook** described making this tradeoff in **Presto**: `APPROX_DISTINCT` uses HLL to make large distinct-count queries more efficient, including analysis of A/B tests. Same idea, a much bigger workload than our cat video. The exact memory and accuracy depend on the implementation; Redis's 12 KiB isn't a universal HLL size. [Meta engineering post](https://engineering.fb.com/2018/12/13/data-infrastructure/hyperloglog/)

## Let's Try Redis

On a local Redis instance, using fresh example keys:

```text
PFADD hll-demo:day:1 otabek chris otabek
PFCOUNT hll-demo:day:1

PFADD hll-demo:day:2 chris jane
PFCOUNT hll-demo:day:2
```

`PFADD` feeds IDs into the sketch. Its return value tells you whether the internal representation changed, **not how many new users arrived**. [PFADD documentation](https://redis.io/docs/latest/commands/pfadd/)

`PFCOUNT` returns the estimated distinct count. The exact sets in this example contain two users each; with such small inputs, an estimate can happen to match the exact answer. It remains an estimate. [PFCOUNT documentation](https://redis.io/docs/latest/commands/pfcount/)

## What About Multiple Days or Servers?

Suppose day one has **otabek** and **chris**, while day two has **chris** and **jane**. Adding the daily counts gives 4. But there are only **3 different users** across both days. Chris didn't clone himself at midnight.

We need to combine the sketches:

```text
PFMERGE hll-demo:both-days hll-demo:day:1 hll-demo:day:2
PFCOUNT hll-demo:both-days
```

`PFMERGE` creates a sketch of the union, so shared users aren't treated as separate users just because they appeared on different days. [PFMERGE documentation](https://redis.io/docs/latest/commands/pfmerge/)

Now we can answer our creator's weekly question: keep one sketch per video per day, add the same viewer ID whenever that person watches, and merge the seven daily sketches. Someone who watched on all seven days still contributes the same ID. That's how we could build our example platform's audience estimate.

The same idea works when servers collect visits independently. For compatible sketches with the same precision and hashing rules, merging takes the maximum at each register:

```text
Server A: [2, 5, 1, 3]
Server B: [4, 2, 1, 6]
Merged:   [4, 5, 1, 6]
```

We're combining the observations, not adding the estimates. Also, every server must agree on the identifier: `user:42` and `42` are different inputs. HLL estimates distinct IDs; it doesn't figure out whether two IDs belong to the same person.

## When Shouldn't We Use It?

What if the creator now asks for a list of everyone who watched? We can't get that from HLL. Before replacing a Set, check what else we'll need from it:

| What you need | Why HLL doesn't fit |
| --- | --- |
| An exact count for billing or reconciliation | The estimate can be too high or too low. The standard error is not a hard limit. |
| A list of viewers, or “did otabek watch this?” | The sketch doesn't retain the IDs or provide membership queries. |
| How many times each person watched | Repeated IDs leave the sketch unchanged. HLL doesn't track frequency. |
| Removing one user's contribution | A normal HLL can't undo an individual insertion. |
| A small dataset that already fits comfortably in a Set | Exact counting may be simpler and entirely fast enough. |

That deletion limit matters for rolling windows too. Keep daily sketches and merge the days you need; don't subtract yesterday's estimate from a weekly estimate. [BigQuery sketch documentation](https://docs.cloud.google.com/bigquery/docs/sketches)

Also, HLL doesn't decide whether a viewer is real. Feed it a thousand different bot IDs and those are a thousand distinct inputs. Input validation and bot filtering still belong elsewhere in the system.

## Conclusion

If you need an exact count or the actual user list, SQL and Sets still have a job. If you need an approximate count across a huge stream of visits, **HyperLogLog** can save a lot of memory.

Just like with Bloom filters, the useful part is understanding what you're giving up. HLL keeps enough information to estimate the count, but it can't give you the IDs back or check membership.

Before reaching for it, ask what your system actually needs. Sometimes the exact answer is essential. Sometimes remembering 100 million IDs just to tell a creator “about 100 million people watched” is unnecessary work.

If this helped you understand the idea, share it with someone who's counting users. Or send them the cat. Whatever gets them here 😄

<a id="optional-math"></a>

## Optional: The Math Behind the Trick

Curious how we turn those high scores into a count? Here's the formula:

The original raw estimate uses a **harmonic mean** of **2ᴹ** values:

$$
E = \alpha_m \frac{m^2}{\sum_{j=0}^{m-1} 2^{-M[j]}}
$$

**m** is the number of registers, **M[j]** is the value in register j, and **αₘ** is a correction factor. The usual relative standard error is approximately:

$$
\text{Standard error} \approx \frac{1.04}{\sqrt{m}}
$$

Putting **m = 16,384** into that expression gives **0.8125%**. [Original HyperLogLog paper](https://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf)

This is the core formula, not a complete production implementation. **HyperLogLog++** adds improvements to accuracy and memory use. Use an established library rather than treating this one equation as the entire algorithm. [Google Research](https://research.google/pubs/hyperloglog-in-practice-algorithmic-engineering-of-a-state-of-the-art-cardinality-estimation-algorithm/)

### Bonus: Try the Exact SQL Count

Here is the tiny example from the introduction, ready to run:

```sql-run
CREATE TABLE visits (
  id INTEGER PRIMARY KEY,
  user_id TEXT NOT NULL,
  visit_day TEXT NOT NULL
);

INSERT INTO visits VALUES
  (1, 'otabek', '2026-03-26'),
  (2, 'chris', '2026-03-26'),
  (3, 'otabek', '2026-03-26'),
  (4, 'jane', '2026-03-27');

SELECT COUNT(DISTINCT user_id)
FROM visits
WHERE visit_day = '2026-03-26';
-- 2 unique users
```


## Sitemap

See the full [Markdown sitemap](/sitemap.md) for all pages.