Counting the exact number of unique visitors to a website, unique IP addresses hitting an API, or unique items in a billion-row log sounds like it should require storing every distinct value you’ve seen. For small sets that’s fine — a hash set does the job. At billions of items, storing every distinct value becomes its own infrastructure problem: a precise count of a billion unique 64-bit values needs gigabytes just to hold the set. HyperLogLog solves this by giving up exactness for a tiny, fixed memory footprint: Redis’s implementation estimates cardinality up to very large counts using no more than 12 kilobytes, with a documented error rate of about 0.81%.
At a Glance
| Attribute | Detail |
|---|---|
| What it is | A probabilistic algorithm that estimates the number of distinct elements (cardinality) in a multiset |
| What it guarantees | No exact count — a statistical estimate with a bounded, tunable standard error |
| Theoretical accuracy | Relative error of about 1.04/√m, where m is the number of registers (Flajolet et al., 2007) |
| Redis implementation | Up to 12 KB per HyperLogLog key, standard error of 0.81%, supports up to 2^64 counted elements |
| Typical use cases | Unique visitor counts, unique query counts, distinct IP/user counts at very high volume |
| Origin | Flajolet, Fusy, Gandouet, Meunier, “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm,” AofA 2007 / DMTCS Proceedings |
Short Verdict
HyperLogLog is the right tool when you need an approximate distinct count at a scale where an exact one is impractical, and the wrong tool the moment you need an exact answer or the ability to list the actual members. It can’t tell you who visited your site, only roughly how many distinct visitors there were. In exchange for giving that up, it holds its memory footprint essentially flat regardless of whether you’re counting thousands or billions of items — Redis’s own documentation states its implementation uses at most 12 KB per key, with a standard error of 0.81%, independent of how many elements have actually been added.
The Problem: Counting Distinct Items at Scale
The naive way to count unique items is to put every item into a set and read off its size. This is exact, but the set’s memory grows linearly with the number of distinct items — counting a billion unique 64-bit values this way means storing something close to a billion 64-bit values, which is gigabytes of memory for a single count. If you need to track unique visitors across millions of separate time windows, pages, or customers simultaneously, that cost multiplies by every window you’re tracking.
The HyperLogLog algorithm, introduced by Philippe Flajolet, Éric Fusy, Olivier Gandouet, and Frédéric Meunier in a 2007 paper presented at the Conference on Analysis of Algorithms (AofA), is the end point of a line of research — starting with earlier algorithms like LogLog — aimed at estimating cardinality using a fixed, small amount of memory regardless of the true cardinality. Their paper reports that with m = 2048 registers, 32-bit hashing, and 5-bit registers, HyperLogLog can estimate cardinalities “largely beyond 10^9” with roughly 2% accuracy while using only about 1.5 KB of memory — several orders of magnitude less than storing the actual set.
How It Works: Hashing, Leading Zeros, and Harmonic Means
The core trick behind HyperLogLog (and its LogLog predecessor) rests on a simple observation about random bit strings. If you hash every item to a uniformly random bit string, the probability that a given hash starts with exactly k leading zero bits is 1/2^(k+1). So if you’ve hashed n distinct items, the maximum number of leading zeros you’ve observed across all of them gives you a rough signal about how large n probably is — more items means a better chance that at least one hash got a long run of leading zeros purely by chance.
A single such observation is a very noisy estimator, so the algorithm splits incoming items across many independent “buckets” (registers) using a few bits of each hash to choose the bucket, and tracks the maximum leading-zero count seen in each bucket separately. HyperLogLog’s specific contribution over earlier LogLog variants is to combine the per-bucket estimates using a harmonic mean rather than LogLog’s geometric mean, which the original paper shows pushes accuracy very close to the theoretical limit for this class of algorithm: a standard error of about 1.04/√m, where m is the number of registers (buckets) used. More registers means a tighter estimate, at the cost of more memory — the classic precision-for-space trade that defines every probabilistic structure covered on this site.
A Minimal Implementation in Python
This is a simplified version of the core idea — enough to show the mechanism (hashing, bucket assignment, leading-zero tracking, and harmonic-mean estimation), not a production-grade implementation, which needs bias correction for small and very large cardinalities that the original paper derives separately.
import hashlib
import math
class HyperLogLog:
def __init__(self, b=10):
self.b = b # number of bits used to pick a bucket
self.m = 1 << b # number of buckets (registers)
self.registers = [0] * self.m
# bias-correction constant for the harmonic-mean estimator
self.alpha = 0.7213 / (1 + 1.079 / self.m)
def _hash(self, item):
digest = hashlib.sha256(item.encode("utf-8")).digest()
return int.from_bytes(digest[:8], "big")
def add(self, item):
h = self._hash(item)
bucket = h & (self.m - 1) # low b bits select the bucket
remaining = h >> self.b
leading_zeros = 1
while remaining & 1 == 0 and leading_zeros < 64 - self.b:
remaining >>= 1
leading_zeros += 1
self.registers[bucket] = max(self.registers[bucket], leading_zeros)
def count(self):
harmonic_sum = sum(2.0 ** -r for r in self.registers)
raw_estimate = self.alpha * self.m * self.m / harmonic_sum
return round(raw_estimate)
hll = HyperLogLog(b=10)
for i in range(100_000):
hll.add(f"user:{i}")
print(hll.count()) # approximately 100,000, within a few percent
The key properties to notice: memory is fixed at m registers regardless of how many items are added, adding an item is O(1), and merging two HyperLogLogs that share the same number of registers is just a register-wise maximum — no need to touch the original data at all.
Real-World Uses: Redis
Redis ships HyperLogLog as a first-class data type accessed through three commands documented on redis.io: PFADD adds elements and runs in constant time and space, PFCOUNT returns the approximate cardinality of one or more keys, and PFMERGE combines several HyperLogLogs into one destination key — exactly the register-wise-maximum merge the math above implies, which runs in O(n) in the number of HLLs being merged, not the number of items ever added to them. Redis’s documentation states the structure uses “12k bytes in the worst case, or a lot less if your HyperLogLog has seen very few elements,” with a standard error of 0.81%, and supports counting up to 2^64 distinct elements. Because an HLL is stored as an ordinary Redis string internally, it can be read and written with GET/SET like any other string value, which makes it trivial to back up or transfer between instances.
The constant-size merge property is what makes HyperLogLog genuinely useful for analytics pipelines beyond a single counter: you can maintain a separate HLL per hour, merge 24 of them into a daily estimate, and merge 30 daily HLLs into a monthly one, all without re-reading a single original event — a property that plain exact-counting sets simply don’t offer at this cost.
HyperLogLog sits in the same family of space-efficient probabilistic structures as the Bloom filter covered elsewhere on this site — both trade a bounded, known error rate for memory that’s orders of magnitude smaller than an exact structure would need, though they answer different questions: a Bloom filter answers “have I seen this exact item before?” while HyperLogLog answers “how many distinct items have I seen in total?”
Trade-offs
- No exact count, ever: even with a tiny error rate, HyperLogLog can never return the precisely correct cardinality, and that error is probabilistic, not a worst-case bound.
- No membership queries or enumeration: you can ask “how many distinct items?” but never “was this specific item one of them?” or get the list back.
- Accuracy is tunable, not free: more registers (higher m) means a tighter error bound but proportionally more memory — Redis fixes this trade-off internally, but a custom implementation has to choose it explicitly.
- Mergeable without the original data: once items are summarized into registers, several HLLs merge into one in time proportional to the number of structures, not the number of items ever counted — a major operational advantage for distributed counting.
Bottom Line
HyperLogLog is the standard answer to “how many distinct things happened” when the honest alternative is either an expensive exact count or no count at all. Flajolet and colleagues proved it gets within a hair of the theoretical best accuracy achievable for any algorithm using this little memory, and Redis’s production implementation turns that math into a practical 12-KB data type with sub-1% error that any application can use with three commands. If you need to know exactly who or what was counted, or need a guaranteed-exact number for billing or compliance, this is the wrong tool. If you need “roughly how many unique X” at a volume where storing every X is itself the problem, it’s close to the best tool available.
FAQ
How accurate is Redis’s HyperLogLog in practice?
Redis’s own documentation states a standard error of 0.81%, described elsewhere on the same page as “less than 1%” — meaning a true count of 1,000,000 would typically be estimated within roughly 8,100 of the real value, though individual results vary statistically.
Can I get the list of items HyperLogLog counted?
No. The structure only ever produces a cardinality estimate; it discards the specific items entirely during insertion and cannot enumerate, reconstruct, or test membership of what it counted.
Why “HyperLogLog” specifically, and not just “LogLog”?
The 2007 paper by Flajolet, Fusy, Gandouet, and Meunier builds on the earlier LogLog algorithm but replaces its geometric-mean estimator with a harmonic mean, which the authors show achieves accuracy close to the theoretical optimum for this class of algorithm while using less memory than LogLog needed for the same accuracy.
Can two HyperLogLogs be merged without re-processing the original data?
Yes — this is one of its most useful properties. Redis’s PFMERGE command combines multiple HLL keys into one by taking the maximum value in each corresponding register, which produces a mathematically correct estimate for the union of the original sets without touching the original items.
Sources
- Flajolet, Fusy, Gandouet, Meunier, “HyperLogLog: the analysis of a near-optimal cardinality estimation algorithm,” AofA 2007 / DMTCS Proceedings
- Redis Documentation — HyperLogLog
- Related reading on this site: Bloom Filters Explained
- Related reading on this site: Skip Lists Explained
Discover more from Software Online Review
Subscribe to get the latest posts sent to your email.
