HyperLogLog for counting unique elements with fixed memory

  • avatar
  • 88 Views
  • 12 mins read

Counting unique visitors sounds like a small task until the numbers grow. Every distinct ID has to be remembered, every new visit needs a check against the ones already seen and memory keeps rising with each new person. HyperLogLog is an algorithm that skips the remembering. It estimates how many different items went through a stream while keeping a few kilobytes of state and in return it accepts a small error that can be measured in advance.

Why exact counting gets expensive

To count distinct items exactly, every item already seen has to be stored, because that is the only way to know a new arrival is a repeat. A 64-bit ID takes 8 bytes, so storing only the IDs takes the following memory, before counting the overhead of a hash set or a database index, while a HyperLogLog in Redis stays at 12 KB in every case:

  • 1 million distinct IDs take 8 MB.

  • 100 million distinct IDs take 800 MB.

  • 1 billion distinct IDs take 8 GB.

The cost multiplies when the question repeats. Unique visitors per day, per page, per campaign and per country each need their own set. Turning daily numbers into a weekly total means merging full sets of IDs, which is heavy work for a dashboard that refreshes all the time.

What HyperLogLog is

HyperLogLog is a probabilistic data structure that estimates cardinality, which is the number of distinct elements in a set. Internally it is an array of small counters called registers. The array has a fixed size chosen when the structure is created, so it never grows, regardless of how many elements are added. That size also sets how large the error of the estimate is.

Every element that needs to be counted goes through the same four steps when it is added:

  1. Hash the element into a fixed-length string of bits. The same element always produces the same hash.

  2. Pick the register for the element based on the number formed by the first k bits of the hash. The value k is a setting fixed when the HyperLogLog is created, and it sets the number of registers to 2k.

    For example, k = 14 gives 16384 registers numbered from 0 to 16383.

  3. In the remaining bits, find ρ, the position of the first 1. For the bits 0010, ρ is 3.

  4. Compare ρ with the value the register already holds and keep the higher one.

Since ρ is measured on each hash, it changes from element to element. A good hash function returns bits that behave like random ones, so each bit is a 0 or a 1 with equal chance, and every extra 0 before the first 1 halves the odds:

  • 1 hash out of 2 has ρ = 1

  • 1 hash out of 4 has ρ = 2

  • 1 hash out of 8 has ρ = 3

  • 1 hash out of 1024 has ρ = 10

Now read it the other way around. A register holds the highest ρ it has seen. A hash with that ρ comes once every 2ρ hashes, so the register has most likely received about 2ρ elements, since each element sends one hash. A register holding 10 points to 1024 elements and one holding 3 points to 8. Duplicates do not change this, because the same element always reaches the same register with the same ρ.

One register alone can give a wrong answer. If a single hash among only 20 elements happens to have ρ = 10, which is rare but possible, its register reports about 1024 elements instead of 20. That is why HyperLogLog uses many registers and sends each element to just one of them, so such a hash misleads only its own register.

The final count then combines the estimates of all the registers in three steps:

  1. Each register estimates how many elements it received, which is 2ρ for the highest ρ it holds. A register with ρ = 10 estimates 1024 elements and one with ρ = 8 estimates 256.

  2. The estimates of all the registers are averaged, which gives the number of elements each register received on average. A plain average has a problem, because one register that estimates far too high drags it up. HyperLogLog uses a different kind of average that pays little attention to very high estimates.

  3. The average is multiplied by the number of registers and then corrected with a constant. For example, 16384 registers with an average of 1000 elements each give about 16 million. That figure comes out too high by a proportion that the math behind the method predicts, and the correction constant, which is below 1 and depends on the number of registers, cancels that excess.

The result answers only one question, which is how many different elements have been added. It cannot list them and it cannot confirm that a given element was added.

Practical example with four registers

A miniature version makes every step visible. It uses 8-bit hashes and 4 registers. The first 2 bits choose the register (00, 01, 10 and 11 point to registers 0, 1, 2 and 3), and ρ is the position of the first 1 in the remaining 6 bits. All registers start at 0.

Item

Hash

Register

Remaining bits

ρ

Result

alice

01 001010

1

001010

3

R1 = 3

bob

10 100110

2

100110

1

R2 = 1

carol

01 010101

1

010101

2

R1 stays 3

dave

00 010000

0

010000

2

R0 = 2

alice (again)

01 001010

1

001010

3

no change

erin

11 010000

3

010000

2

R3 = 2

frank

10 001100

2

001100

3

R2 = 3

Every row follows the same path. The first 2 bits of the hash pick the register, ρ is measured on the other 6 bits, and the register changes only when ρ is larger than the value it holds.

In this run:

  1. alice, bob, dave and erin land in registers that still hold 0, so each one stores its own ρ.

  2. carol lands in register 1, which holds 3 from alice. Her ρ is 2, so nothing changes.

  3. The second alice produces the same hash as the first one, so ρ is 3 again and nothing changes.

  4. frank lands in register 2, which holds 1 from bob. His ρ is 3, so the register becomes 3.

Six distinct elements went in and the registers now hold 2, 3, 3 and 2. Each one estimates 2ρ elements, which is 4, 8, 8 and 4. Averaged the way described above, they give about 5.3 elements per register. Multiplied by the 4 registers that is about 21 and the correction constant brings it down to about 11.

The true count is 6, so the estimate is nearly double. With only 4 registers, one high ρ moves the result a lot. Real implementations use thousands of registers, which makes the error small. With 16384 registers, a test run on 100000 distinct IDs returned 100190, an error of 0.19%.

Precision, memory and error

The number of registers is 2k and the standard error is about 1.04 divided by the square root of the number of registers. Each register takes 6 bits, so the memory used is 6 bits multiplied by the number of registers. Redis, for example, uses k = 14, which gives 16384 registers and about 12 KB per key.

k

Registers

Memory at 6 bits each

Standard error

10

1024

768 bytes

3.25%

12

4096

3 KB

1.63%

14

16384

12 KB

0.81%

16

65536

48 KB

0.41%

The standard error tells how far an estimate usually is from the real count. With k = 14 the error is 0.81%, so for a real count of 1000000 an estimate is usually within about 8100 of it, between 991900 and 1008100.

Each extra bit in k doubles the registers and the memory and divides the error by about 1.4. So k is a trade-off between memory and accuracy and the right value is the smallest one whose error the question can tolerate. Redis fixes k at 14, and other systems let you choose it.

Advantages vs inconveniences

HyperLogLog uses a fixed amount of memory, set when the structure is created, that does not grow with the number of elements. Adding an element touches a single register, so the cost per element is the same on the first one and on the billionth. In exchange, the result is an estimate. An invoice, a quota or a legal report that needs the exact number cannot rely on it, while a dashboard of unique visitors can live with an error of around 1%.

A repeated element needs no special handling. It always produces the same hash, so it lands in the same register with the same ρ and changes nothing, and no check for elements already seen is needed. The other side is that the structure cannot tell which elements it has seen, so there is no way to ask if a given element was added.

Two structures can be merged into one, so daily counts become weekly or monthly totals without going back to the raw data, and a repeated element is never counted twice. The same design has limits. The elements cannot be listed or removed.

Counting unique visitors with Redis

Redis includes its own HyperLogLog implementation. Each key uses up to 12 KB of memory, the standard error is 0.81% and it can count up to 264 distinct items, which is about 18 quintillion. It is operated with three commands:

  • PFADD key element [element ...] adds elements to the structure. It returns 1 when an internal register changed and 0 otherwise.

  • PFCOUNT key returns the estimated number of distinct elements, or 0 when the key does not exist.

  • PFMERGE destkey sourcekey [sourcekey ...] stores the highest value of each register across the sources in destkey.

A common setup keeps one key per day, so each key holds the visitors of that day. The session below records two days of traffic where user u3 visits on both:

127.0.0.1:6379> PFADD visitors:hibit:2026-11-14 u1 u2 u3
(integer) 1
127.0.0.1:6379> PFADD visitors:hibit:2026-11-15 u3 u4
(integer) 1
127.0.0.1:6379> PFADD visitors:hibit:2026-11-15 u3
(integer) 0
127.0.0.1:6379> PFCOUNT visitors:hibit:2026-11-14
(integer) 3
127.0.0.1:6379> PFCOUNT visitors:hibit:2026-11-15
(integer) 2
127.0.0.1:6379> PFMERGE visitors:hibit:2026-11-14-15 visitors:hibit:2026-11-14 visitors:hibit:2026-11-15
OK
127.0.0.1:6379> PFCOUNT visitors:example.com:2026-11-14-15
(integer) 4

The third command returns 0 because u3 was already counted for that day, so no register changed. The merged key reports 4 and not 5, since u3 appears in both days and is counted once. Adding the two daily counts (3 + 2) would give 5, which counts u3 twice. A merge avoids that mistake because it combines the structures and not the numbers.

These counts are exact only because the sets are tiny. As the sets grow, results become estimates with the error described earlier.

Using HyperLogLog from PHP

In PHP the same three commands are available as the methods pfAdd, pfCount and pfMerge of the Redis class, provided by the phpredis extension. The class below wraps the daily key pattern from the previous section. It records visits, reads a daily count and merges several days into one total.

<?php

final class VisitorCounter
{
public function __construct(private Redis $redis)
{
}

private function key(string $site, string $label): string
{
return sprintf('visitors:%s:%s', $site, $label);
}

public function record(string $site, string $visitorId, string $date): void
{
$key = $this->key($site, $date);

$this->redis->pfAdd($key, [$visitorId]);
$this->redis->expire($key, 30 * 24 * 60 * 60);
}

public function count(string $site, string $label): int
{
$key = $this->key($site, $label);

return (int) $this->redis->pfCount($key);
}

/**
* Unique visitors across several days.
*
* @param string[] $dates Dates in Y-m-d format
*/
public function merge(string $site, array $dates, string $label): int
{
$targetKey = $this->key($site, $label);

$sources = array_map(fn (string $date) => $this->key($site, $date), $dates);

$this->redis->pfMerge($targetKey, $sources);
$this->redis->expire($targetKey, 30 * 24 * 60 * 60);

return (int) $this->redis->pfCount($targetKey);
}
}

The identifier passed to record should be a stable value, such as a user ID. A value that changes between visits, like a request ID, would make every visit look like a new person.

Using the class takes a few lines. The weekly figure merges seven daily keys and a visitor who appears on three of those days is counted once:

$redis = new Redis();
$redis->connect('127.0.0.1', 6379);

$counter = new VisitorCounter($redis);

// Called on every request, using a stable ID such as the user ID
$counter->record('hibit', 'u1', '2026-11-14');
$counter->record('hibit', 'u2', '2026-11-14');
$counter->record('hibit', 'u3', '2026-11-14');
$counter->record('hibit', 'u3', '2026-11-15');
$counter->record('hibit', 'u4', '2026-11-15');
$counter->record('hibit', 'u3', '2026-11-15'); // already counted, nothing changes

// Unique visitors for one day
echo $counter->count('hibit', '2026-11-14'); // 3
echo $counter->count('hibit', '2026-11-15'); // 2

// Unique visitors for several days
echo $counter->merge('hibit', ['2026-11-14', '2026-11-15'], '2026-11-14-15'); // 4

The merged key is a regular Redis key, kept for 30 days like the daily ones, so the total can be read again with count without merging the days each time. Each of these keys stays at 12 KB or less, regardless of how many terms it receives.

Conclusion

Not every question needs a perfect answer. HyperLogLog counts unique elements with a small and known error, and in return it needs only a few kilobytes of memory, no matter how much data goes through it. That trade between accuracy and cost appears in many other tools, which is why it is worth asking how exact a result really has to be before choosing how to store or count it. Often the honest reply is that close enough is fine.

 Join Our Monthly Newsletter

Get the latest news and popular articles to your inbox every month

We never send SPAM nor unsolicited emails

0 Comments

Leave a Reply

Your email address will not be published.

Replying to the message: View original

Hey visitor! Unlock access to featured articles, remove ads and much more - it's free.