How websites count billions of unique visitors without storing everyone

We’ll cover:

The deceptively hard question
The obvious approaches (and why they hurt)
The key insight: ask a cheaper question first
HyperLogLog: Bringing Everything Together
The math and the algorithm behind HyperLogLog
Implementation (a simple Python baseline)
Where large-scale systems use it
Why it works so well — and where it falls short
Conclusion
Further Reading

1) The deceptively hard question

Imagine you've just launched your first website. A week later, you open your analytics dashboard and see:

Unique Visitors Today
---------------------
18,742

Seems simple enough.

But have you ever stopped to think about how your website actually knows those visitors were unique?

At first glance, the solution feels almost obvious. Store every visitor inside a HashSet.

Whenever a new user visits:

users.add(visitor_id)

Need the number of unique visitors?

len(users)

Problem solved.

Or is it?

Now let's stop thinking like developers building side projects and start thinking like engineers working at internet scale.

According to recent estimates, there are over 5.5 billion Internet users worldwide, with more than 5.2 billion active social media users.

Even if your application is nowhere near the size of Google or Facebook, large consumer platforms routinely receive millions of requests every second. Suppose only 30% of internet users visited your service over a long period.

That's roughly:

5.5 Billion × 30%
≈ 1.65 Billion users

Now imagine storing every single visitor inside a hash table.

Even if you stored nothing more than a 64-bit identifier (8 bytes) for each visitor—which is already an unrealistic simplification—you would need:

1.65 Billion × 8 bytes
≈ 13.2 GB

Unfortunately, real hash tables don't just store raw keys.

Every entry also carries additional overhead:

object metadata
pointers
bucket arrays
allocator bookkeeping
load-factor slack
resizing overhead

Depending on the language and implementation, the real memory consumption can easily become two to five times larger than the raw data itself.

Suddenly, something that looked like a tiny analytics feature starts consuming tens of gigabytes of RAM.

And all of that memory is being used for just one purpose:

"Count how many unique users visited."

We're not interested in retrieving those users later.

We're not searching them.

We're not updating them.

We're not attaching extra information.

We only want a single number.

1,649,384,281

That feels... wasteful.

2) The obvious approaches (and why they hurt)

Option A: store everything in a set

This gives the exact answer, but memory grows linearly with the number of users.

For a billion distinct users, that becomes too expensive very fast.

Option B: store everything in the database

You can do it, but now you pay for:

more storage
more I/O
more query cost
more coordination across nodes

It works, but it is not efficient when the only thing you need is a count.

Option C: use an approximate answer

This is where HyperLogLog becomes interesting.

Instead of remembering every item, it keeps just enough information to estimate the number of distinct values.

That trade-off is often good enough for analytics.

3) The key insight: ask a cheaper question first

Instead of asking:

“How many users have I seen?”

You ask a cheaper version:

“How large is this set likely to be?”

This tiny change in perspective is what leads to one of the most elegant ideas in computer science.

Let's perform a small thought experiment.

Suppose yesterday your dashboard displayed:

Unique visitors
---------------
22

Now imagine the real number wasn't actually 22.

It was 23.

Would anyone notice? Would the product team suddenly make different business decisions? Would marketing cancel their campaigns?

Probably not.

Even a difference of a few hundred visitors becomes almost meaningless once you're dealing with millions.

What matters is the overall trend.

Is traffic increasing? Is a campaign successful? Did today's launch attract more users than yesterday?

Analytics systems are usually interested in answering questions like these — not identifying every individual visitor.

In other words,

an approximate answer is often just as valuable as an exact one.

Once you accept that approximation is acceptable, an entirely new family of algorithms becomes available.

These algorithms intentionally trade perfect accuracy for enormous improvements in memory consumption.

They are known as probabilistic data structures.

Unlike traditional data structures, probabilistic structures don't guarantee perfect answers.

Instead, they provide answers that are:

extremely fast,
incredibly memory efficient,
and statistically accurate within a very small error margin.

Some famous members of this family include:

Bloom Filters
Count-Min Sketch
Morris Counter
HyperLogLog
Cuckoo Filters

Each solves a different problem.

Bloom Filters answer:

"Have I probably seen this item before?"

Count-Min Sketch answers:

"Approximately how many times has this item appeared?"

HyperLogLog answers:

"Approximately how many unique items have I seen?"

This last problem is known as the cardinality estimation problem.

4) HyperLogLog: Bringing Everything Together

HyperLogLog is a probabilistic data structure for estimating cardinality.

In plain English:

it hashes each item
it looks at how “rare” that hash looks
it keeps a small amount of summary information
it uses that summary to estimate how many distinct items have appeared

It does not store the full set. It stores a compact sketch.

That sketch can often fit in a few kilobytes while still giving a surprisingly accurate estimate.

The idea is simple: instead of storing every observed value, HyperLogLog hashes each item and keeps only a small summary of how rare its hash looks. Rare hashes are much more informative than common ones, so a compact sketch can still reveal a lot about how many distinct items have appeared.

5) The math and the algorithm behind HyperLogLog

What exactly is cardinality?

Cardinality is simply the number of distinct elements inside a collection.

For example,

A = {1,2,3,4}

The cardinality is 4

If duplicates exist,

A = {1,2,2,3,3,3,4}

the cardinality is still 4

because duplicates don't matter.

In mathematics this is written as

|A| = 4

HyperLogLog is specifically designed to estimate this value.

Notice the wording carefully.

It doesn't estimate the elements.

It doesn't estimate frequencies.

It estimates only the size of the unique set.

That might sound like a very specialized problem.

In reality, it appears almost everywhere.

Every day, large-scale systems need to answer questions such as:

How many unique users visited today?
How many unique IP addresses connected?
How many distinct products were viewed?
How many unique advertisements were clicked?
How many unique search queries were submitted?

All of these are cardinality estimation problems.

And storing billions of identifiers simply to answer them would be incredibly expensive.

This is exactly why databases like Redis, BigQuery, Apache Spark, Snowflake, and many modern analytics systems rely on HyperLogLog.

But HyperLogLog didn't appear overnight.

It was the result of nearly three decades of research, beginning with a surprisingly simple observation about random numbers.

To understand HyperLogLog, we first need to travel back to 1985 and look at the algorithm that inspired everything:

Flajolet-Martin: The Beginning of Probabilistic Counting

Long before HyperLogLog existed, computer scientists Philippe Flajolet and G. Nigel Martin asked a surprisingly simple question:

Can we estimate the number of unique elements without actually storing them?

At first glance, the answer seems impossible.

Suppose I continuously stream names to you:

Alice
Bob
Charlie
Alice
David
Bob
...

At any point I ask:

"How many unique names have I shown you?"

If you're not allowed to remember previous values, how could you possibly answer?

It turns out that randomness itself contains information.

The trick is learning how to read it.

A strange observation about random numbers

Imagine you repeatedly flip a fair coin.

The probability of getting Heads is 1/2,

Getting two heads in an row has probability 1/4,

Three heads in a row 1/8,

Four heads in a row 1/16,

Each additional head cuts the probability in half.

Mathematically,

                              1
P(k consecutive heads) = ------------
                              2ᵏ

Exactly the same idea appears when we hash values.

Suppose our hash function generates completely random binary numbers.

Apple
↓
011010001010...

Banana
↓
110001010111...

Orange
↓
000010101100...

Because a good hash function behaves like a random number generator, every bit has a 50% chance of being either 0 or 1

That means we can ask another interesting question.

What's the probability that a random binary number begins with one zero?

Half of them do, so, 0xxxxxxxx has probablility 1/2,

What about two leading zeros? 00xxxxxxx has 1/4,

Three? 000xxxxxx has 1/8

Four? 0000xxxxx has 1/16

Notice something familiar?

Exactly the same powers of two appear again.

Leading zeros	Probability
1	1/2
2	1/4
3	1/8
4	1/16
5	1/32
k	1/2ᵏ

This tiny probability table became the foundation of modern cardinality estimation.

Why does this matter?

Imagine hashing only four unique users.

Alice
↓
101010...

Bob
↓
011010...

Charlie
↓
111000...

David
↓
010101...

The largest number of leading zeros you observe is 1

Nothing surprising.

Now suppose you hash one thousand unique users.

Among a thousand random hashes, you'll eventually encounter something like 0000000001.... with many more leading zeros.

With one million users, seeing hashes with twenty leading zeros is no longer unusual. The larger your dataset becomes, the greater the chance of encountering an extremely rare hash.

That's the key insight.

Instead of remembering every element, we remember only the rarest hash we've ever seen.

Turning probability into an estimate

Suppose the largest number of leading zeros we've observed is R

Since seeing R leading zeros has probability:

1 / 2ᴿ

we'd expect to examine roughly

2ᴿ

different random values before seeing one.

For example,

If the rarest hash has 10 leading zeros, then

2¹⁰ = 1024

So our estimate becomes

≈ 1024 unique elements

Similarly,

Maximum leading zeros = 15

Estimate

≈ 2¹⁵

≈ 32,768

This estimate won't be exact.

Sometimes you'll be lucky and encounter an unusually rare hash earlier than expected.

Sometimes you'll be unlucky.

But on average, it works surprisingly well.

This was the central idea behind the Flajolet–Martin algorithm, published in 1985.

The Flajolet–Martin Algorithm

The algorithm itself is remarkably short.

For every incoming element:

Hash the element.
Count the number of leading zeros.
Keep the maximum value seen so far.
Estimate the cardinality using 2ᴿ where R is the maximum leading-zero count.

Pseudo-code looks like this:

max_zeroes = 0

for element in stream:
    h = hash(element)

    r = leading_zeroes(h)

    max_zeroes = max(max_zeroes, r)

estimate = 2 ** max_zeroes

Notice something remarkable.

Memory usage is now constant.

Whether you process 10 users or 10 billion users,

you're storing only a single integer.

The algorithm has effectively reduced memory complexity from O(n) to O(1)

That was revolutionary.

But there was a problem...

Although elegant, the estimate was extremely noisy. Imagine tossing a coin until you get 15 heads in a row.

Sometimes it happens surprisingly early. Sometimes it takes much longer.

Exactly the same randomness affects Flajolet–Martin.

One unusually lucky hash can double your estimate. One unlucky stream can cut it in half.

Consider these two runs.

Run A

Largest leading zeros:

Estimate:

65,536

Run B

Largest leading zeros:

Estimate:

262,144

Only two extra leading zeros increased the estimate by four times.

That's a huge amount of variance.

While the estimator was unbiased over many experiments, individual runs could be wildly inaccurate.

The obvious question became:

Can we somehow average multiple independent estimators together?

The answer was yes.

Instead of keeping just one maximum, researchers divided the stream into many independent groups and averaged their estimates.

This dramatically reduced variance and gave birth to the next evolution in probabilistic counting:

LogLog — Reducing Variance

The biggest weakness of the Flajolet–Martin algorithm wasn't memory usage—it was variance.

Imagine running the algorithm twice on two streams containing exactly the same number of unique elements.

Run 1
Maximum leading zeros = 15

Estimate = 32,768

Run 2
Maximum leading zeros = 18

Estimate = 262,144

Just three additional leading zeros caused the estimate to become eight times larger.

The estimate depended too much on one exceptionally rare hash.

Instead of relying on a single observation, researchers had a simple idea:

What if we ran many Flajolet–Martin estimators independently and combined their results?

Running multiple estimators would average out lucky and unlucky observations, dramatically reducing variance.

However, maintaining dozens or hundreds of independent hash functions would be computationally expensive.

This led to an elegant trick called stochastic averaging.

Stochastic Averaging

Instead of using many different hash functions, LogLog uses one hash function.

The hash is split into two parts.

Hash

101101001101010110...
│──────│────────────────────
 Bucket       Remaining bits

The first few bits determine which register (bucket) should receive this element.

The remaining bits are used to count leading zeros.

Suppose we use 10 bits for the bucket index.

2¹⁰ = 1024 registers

Each register now behaves like its own independent Flajolet–Martin estimator.

Register 0 → max leading zeros = 4

Register 1 → max leading zeros = 7

Register 2 → max leading zeros = 5

...

Instead of one noisy estimator, we now have thousands of small estimators.

Combining them produces a far more stable estimate.

This idea became the LogLog algorithm, proposed by Durand and Flajolet in 2003.

Compared to Flajolet–Martin, LogLog:

greatly reduced estimation variance
required only one hash computation
scaled naturally with more registers

But one issue remained.

A few unusually large register values could still skew the final estimate.

SuperLogLog — Removing Outliers

The next improvement was surprisingly straightforward.

Researchers noticed that a small number of registers occasionally received extremely large values simply due to random chance.

Those outliers disproportionately affected the estimate.

SuperLogLog addressed this by discarding the highest register values before computing the final result.

In other words, instead of trusting every register equally, it ignored the noisiest observations.

This simple statistical improvement reduced the estimation error significantly without increasing memory usage.

Although SuperLogLog was an improvement, researchers believed they could do even better.

Instead of removing outliers, they asked:

Can we combine register values in a mathematically better way?

The answer led to what is now considered the state-of-the-art algorithm for cardinality estimation.

HyperLogLog — A Better Way to Estimate the Unknown

By the time HyperLogLog was proposed in 2007, researchers had already solved two major problems.

Flajolet–Martin showed that leading zeros reveal information about cardinality.

LogLog showed that splitting observations into many buckets reduces variance.

SuperLogLog further improved the estimate by reducing the influence of outliers.

HyperLogLog asked one final question:

Can we mathematically combine all these observations in an even better way?

The answer was yes.

Instead of changing the underlying idea, HyperLogLog refined the mathematics behind the estimation.

The result was remarkable.

Using only 16 KB of memory, HyperLogLog can estimate the cardinality of billions of distinct elements with an average error of less than 1%.

That's why systems like Redis, BigQuery, ClickHouse, Apache Spark, Snowflake, and many analytics platforms rely on it today.

The Basic Idea

The core principle hasn't changed.

For every incoming element:

Hash it.
Select a register (bucket).
Count the number of leading zeros in the remaining bits.
Store only the largest value seen for that register.

That's it.

Suppose we hash the string

"alice"

and obtain the following 64-bit binary number:

001011100101011001...

HyperLogLog splits this hash into two parts.

001011100101011001...
│───────│────────────────────────────
 Index         Remaining bits

The first few bits choose the register.

The remaining bits are used to compute the rank (number of leading zeros).

Why split the hash?

This is one of the smartest ideas in HyperLogLog.

Imagine using the first 14 bits as the register index.

2¹⁴ = 16,384 registers

Each register now behaves like its own tiny Flajolet–Martin estimator.

Register 0

Largest rank = 6

Register 1

Largest rank = 3

Register 2

Largest rank = 7

...

Register 16383

Largest rank = 5

Instead of relying on one observation,

we now have 16,384 independent observations.

The estimate becomes dramatically more stable.

Computing the Rank

After selecting the register,

HyperLogLog looks only at the remaining bits.

Suppose those remaining bits are

000010110101...

The first 1 appears after 4 zeroes.

So the rank becomes 5 because we count leading zeroes + 1

This matches exactly what your implementation does.

if value == 0:
    rank = CARD_BITS
else:
    rank = leading_zeroes(value) + 1

If this rank is larger than the value already stored in the register,

the register is updated.

Otherwise,

nothing changes.

Notice something interesting.

No matter how many millions of elements arrive,

each register stores only one tiny integer.

Building the Registers

Suppose our registers initially look like

[0,0,0,0,0,0,0]

After hashing several elements,

they become

[3,5,1,7,4,2,6]

Each number answers one question:

What is the largest leading-zero count ever observed in this bucket?

Those seven numbers now summarize thousands—or even millions—of inserted elements.

This compression is exactly what makes HyperLogLog so memory efficient.

But now comes the difficult part.

How do we combine these thousands of register values into a single estimate?

Simply averaging them turns out to be surprisingly inaccurate.

HyperLogLog instead uses a different mathematical tool:

the harmonic mean.

Why the Arithmetic Mean Doesn't Work

At first glance, combining all the registers seems trivial.

Suppose our registers contain:

[4, 5, 3, 6, 4, 5, 7, 4]

Why not simply compute their average?

(4 + 5 + 3 + 6 + 4 + 5 + 7 + 4) / 8

Unfortunately, this performs surprisingly poorly.

Remember what each register actually stores.

It isn't a count.

It isn't a frequency.

It's the largest number of leading zeros ever observed in that bucket.

And those values grow exponentially.

The Harmonic Mean

Instead of the arithmetic mean,

HyperLogLog effectively computes the harmonic mean of the register estimates.

If the registers are

R₁, R₂, R₃ ... Rₘ

we first compute

Z = Σ 2⁻ᴿⁱ

In code this is simply

Z = 0

for r in registers:
    Z += 2 ** (-r)

This quantity,

often called the harmonic sum,

captures information from every register while naturally reducing the impact of unusually large observations.

The final estimate becomes

       m²
E = ----------
      Σ2⁻ᴿ

where

m = number of registers
R = value stored in each register

Already this estimator performs much better than LogLog.

But researchers discovered one final issue.

Even this estimator was slightly biased.

The Bias Correction Constant

Suppose we repeatedly generated millions of random datasets, computed the estimate, and compared it against the true cardinality.

The estimate would consistently be just a little too high. Not by much, but enough to matter.

Instead of accepting this systematic bias, Flajolet and his colleagues analyzed the estimator mathematically and also validated it experimentally over enormous numbers of random datasets. They discovered that multiplying the estimate by a small correction factor almost completely removed this bias.

That correction factor is αm (read as "alpha m").

The complete estimator becomes

        αm × m²
E = --------------
        Σ 2⁻ᴿⁱ

This is the famous HyperLogLog equation you'll find in almost every implementation.

In almost evey implementation alpha is calculated as:

alpha(α) = 0.7213 / (1 + 1.079 / m)

The constant comes from the mathematical analysis of the estimator's asymptotic behavior. This isn't an arbitrary magic number.

It's the result of carefully analyzing the probability distribution of the estimator and validating it experimentally.

Putting Everything Together

At this point, the entire HyperLogLog algorithm becomes surprisingly small.

For every element:

Hash the element
        ↓
Split hash into

Register Index
+
Remaining Bits
        ↓
Count leading zeros
        ↓
Update register if rank is larger

When someone asks for the cardinality:

For every register

↓

Compute 2⁻ᴿ

↓

Sum them together

↓

Multiply by αm × m²

↓

Return estimate

That's essentially the complete algorithm.

The implementation itself is only a few dozen lines of code.

The difficult part isn't writing the code.

The difficult part is understanding why the mathematics works.

6) Implementation (a simple Python baseline)

A Simple Python Implementation

The implementation below intentionally omits some production optimizations (such as sparse encoding, cached cardinality, and bias tables) to focus on the core algorithm.

import hashlib
import math

NUM_REGISTERS = 1 << 14  # 16,384 registers


class HyperLogLog:

    def __init__(self):
        self.registers = [0] * NUM_REGISTERS

    def _hash(self, value: str) -> int:
        # SHA-1 is used here for simplicity.
        # Production systems typically use MurmurHash, xxHash or FNV.
        digest = hashlib.sha1(value.encode()).digest()
        # retrieve only first 64 bits (8 bytes) of hash digest (big-endian)
        return int.from_bytes(digest[:8], "big")

    def add(self, value: str):
        h = self._hash(value)

        # lower 14 bits -> register
        index = h & (NUM_REGISTERS - 1)
        
        # Remaining 50 bits
        w = h >> 14

        REMAINING_BITS = 64 - 14
        
        rank = REMAINING_BITS + 1   
        if w != 0:
            rank = REMAINING_BITS - w.bit_length() + 1
        
        self.registers[index] = max(self.registers[index], rank)

    def count(self):
        m = NUM_REGISTERS

        alpha = 0.7213 / (1 + 1.079 / m)
        harmonic_sum = sum(math.ldexp(1.0, -r) for r in self.registers)
        estimate = alpha * (m * m) / harmonic_sum

        # Small-range correction (Linear Counting)
        if estimate <= 2.5 * m:
            zero_registers = self.registers.count(0)

            if zero_registers:
                estimate = m * math.log(m / zero_registers)

        return round(estimate)

Example

hll = HyperLogLog()

users = [
    "alice",
    "bob",
    "charlie",
    "alice",
    "david",
    "bob",
    "eve"
]

for user in users:
    hll.add(user)

print("Estimated Unique Users:", hll.count())

For educational purposes, this implementation is intentionally kept small.

My implementation inside RunDB is considerably closer to Redis. It uses:

native memory allocation through ctypes
dense register representation
cached cardinality
merge support
MurmurHash64A hashing
fixed-size memory layout
Redis-inspired API (ADD, COUNT, MERGE)

The underlying mathematics, however, remains exactly the same.

7) Where large-scale systems use it

HyperLogLog appears whenever a system needs to answer a simple but expensive question:

How many unique things have I seen?

It is especially useful in places where exact counts would be too costly in memory or time.

Website Analytics: Platforms use it to estimate unique visitors, sessions, and IP addresses without storing every identifier.
Digital Advertising: It helps estimate how many distinct users or devices saw or clicked an ad, even when the same person appears many times.
Databases: Many systems use approximate versions of COUNT(DISTINCT column) to keep large queries fast. Examples include Redis, BigQuery, ClickHouse, and Spark.
Distributed Systems: In large distributed setups, each server can keep its own sketch and merge them later, avoiding the cost of sending billions of IDs around the network.
Observability: It is also useful for estimating unique errors, request IDs, and affected users in monitoring pipelines.

8) Why it works so well — and where it falls short

HyperLogLog is powerful because it solves one specific problem extremely well: estimating how many distinct items have appeared, without storing every one of them.

It is especially useful when you want:

very low memory usage
fast inserts and queries
good accuracy for large-scale analytics

But it is not a replacement for a full set.

It gives an estimate, not an exact count, so it is less suitable when you need precise results for billing, auditing, or correctness-critical systems.

It also cannot answer membership questions like “Have I seen this user before?” and it does not support deletion in the classic form.

It also belongs to a broader family of probabilistic data structures, each designed for a slightly different question:

Data Structure	Solves
Bloom Filter	Whether an item is probably present
Count-Min Sketch	Approximate frequency counting
HyperLogLog	Approximate distinct counting
Cuckoo Filter	Membership queries with deletion support

Choosing the right structure depends on the question you are trying to answer.

9) Conclusion

HyperLogLog is a perfect example of how mathematics can completely change the way we think about software engineering.