HyperLogLog Explained: Count Unique Items in 12 KB

HyperLogLog counts the distinct items in a huge stream using about 12 KB of memory, with a typical error under 1%. That is the entire pitch. A SET holding ten million user IDs costs hundreds of megabytes. A HyperLogLog counting the same ten million costs the same 12 KB it cost for ten.

If your analytics dashboard has a “unique visitors” number, a HyperLogLog is a good way to produce it. Here is how it works, why the maths is less scary than the name, and how to use it from Redis.

The problem: counting distinct things is expensive

Counting events is easy: increment a number. Counting distinct events is a different problem, because to know whether this user is new you have to remember every user you have already seen.

The exact answer needs memory proportional to the number of distinct items. For 50 million daily visitors with 16-byte IDs, that is roughly 800 MB before any overhead, per day, per page, per dimension you want to slice by. Nobody wants that bill for a number that goes on a chart rounded to the nearest thousand.

The core idea: rare patterns signal large sets

Flip a fair coin until it lands heads and write down how many tails came first. Most runs are short. A run of 10 tails in a row happens about once in a thousand tries. So if someone tells you their longest streak was 10 tails, you can guess they flipped around a thousand times.

HyperLogLog does this with hash bits instead of coins.

1. Hash every incoming item to a uniform 64-bit number.
2. Count the leading zero bits. Seeing a hash that starts with 10 zeros happens for roughly 1 in 1,024 items.
3. Remember only the largest leading-zero count you have seen.

If the maximum is 10, you have probably seen something near 2^10 items. The same item always hashes to the same value, so duplicates cannot inflate the estimate. That is where “distinct” comes from.

One maximum alone is noisy: one lucky hash ruins it. So the algorithm splits items into many buckets (called registers) using the first few hash bits, keeps a maximum per bucket, and averages across them. Redis uses 16,384 registers of 6 bits each, which is where the 12 KB comes from. More registers, less noise, more memory. Averaging with a harmonic mean keeps one outlier register from dominating.

The algorithm comes from the 2007 paper by Flajolet and colleagues, which proved the error bound.

A working sketch in Python

This is a teaching version. It skips the bias corrections that production implementations apply at small and very large counts, but it shows the whole mechanism.

import hashlib
import math

class HyperLogLog:
    def __init__(self, p=14):
        self.p = p                      # 2**14 = 16384 registers
        self.m = 1 << p
        self.registers = [0] * self.m

    def _hash(self, item: str) -> int:
        digest = hashlib.sha1(item.encode()).digest()
        return int.from_bytes(digest[:8], "big")   # 64-bit hash

    def add(self, item: str) -> None:
        h = self._hash(item)
        idx = h >> (64 - self.p)                   # first p bits pick the register
        rest = h & ((1 << (64 - self.p)) - 1)      # remaining bits
        rank = (64 - self.p) - rest.bit_length() + 1   # leading zeros + 1
        self.registers[idx] = max(self.registers[idx], rank)

    def count(self) -> int:
        alpha = 0.7213 / (1 + 1.079 / self.m)
        z = 1.0 / sum(2.0 ** -r for r in self.registers)
        estimate = alpha * self.m * self.m * z
        zeros = self.registers.count(0)
        if estimate <= 2.5 * self.m and zeros:     # small-range correction
            return round(self.m * math.log(self.m / zeros))
        return round(estimate)

hll = HyperLogLog()
for i in range(1_000_000):
    hll.add(f"user-{i}")
print(hll.count())   # close to 1,000,000, typically within about 1%

Run it a few times with different inputs. The answer wobbles around the truth, and the wobble stays about the same size whether you add a million items or a hundred million. That is the property that makes the structure useful.

Using it in Redis

Redis ships HyperLogLog as three commands with a PF prefix, named after Philippe Flajolet, who co-designed the algorithm.

# Record visitors for one page on one day
PFADD page:pricing:2026-10-13 user-1 user-2 user-3
PFADD page:pricing:2026-10-13 user-2 user-4    # user-2 is a repeat

PFCOUNT page:pricing:2026-10-13                # 4

# Unique visitors across a week, no raw IDs needed
PFCOUNT page:pricing:2026-10-07 page:pricing:2026-10-08 page:pricing:2026-10-09

# Or store the merged sketch
PFMERGE page:pricing:week-41 page:pricing:2026-10-07 page:pricing:2026-10-08

Two details. A key’s memory is at most about 12 KB, and sparse sketches start smaller and grow as items arrive. The Redis documentation on HyperLogLog gives a standard error of 0.81%. And the merge works because each register stores a maximum: the union of two sets has, per register, the larger of the two maxima.

That merge property is the real selling point for analytics. You can keep one sketch per day, per region or per shard, and answer “unique users this month” by merging 30 tiny keys. The same question on raw IDs means re-reading every set.

When not to use it

HyperLogLog is a bad fit when:

• You need exact numbers. Billing, quotas and anything with legal weight should use a real count. A 0.81% error on an invoice is a dispute.
• You need to list or look up items. There is no way to ask which users are in the sketch, or whether user-7 is. For membership checks use a Bloom filter or a set.
• You need to remove items. Registers only ever grow.
• The set is small. Under a few thousand items, a plain set is exact and costs little memory. Use the probabilistic structure only when exact counting has become the bottleneck.

Related thinking applies to rate limits and caches: when the number is allowed to be approximate, memory shrinks dramatically. The same trade shows up in rate limiting with Redis and in how consistent hashing spreads keys across shards.

What to do with this

If you already count unique things in a Redis set today, measure its memory with MEMORY USAGE key, then replay the same data into a PFADD key and compare both the memory and the count. For most analytics workloads the difference is three or four orders of magnitude in memory against an error nobody will notice on a chart.

Building analytics or data infrastructure and want it designed for cost from day one? See how CODERCOPS approaches data engineering projects.