Redis - HyperLogLog

Redis HyperLogLog

Imagine you need to count the number of unique visitors to a massively popular website. Storing every unique IP address in a Redis Set would consume a huge amount of memory. This is the exact problem HyperLogLog solves.

HyperLogLog is a probabilistic data structure used to estimate the number of unique items in a set (its ‘cardinality’) with incredible memory efficiency. It provides a very good approximation using only about 12 kilobytes of memory per key, regardless of whether you’re counting a thousand items or a billion. The trade-off is a small, fixed standard error of just 0.81%.

When to Use HyperLogLog vs. Sets

• Use a Set when: You need 100% accuracy and the number of unique items is manageable (e.g., thousands or a few million). Memory usage grows linearly with the number of items.
• Use HyperLogLog when: You are counting a massive number of unique items (e.g., hundreds of millions or billions) and a close approximation with a tiny error margin is acceptable. Memory usage is constant and very small.

Example: Counting Unique Search Queries

Let’s add several search queries to a HyperLogLog structure. Notice that adding the same query multiple times doesn’t significantly change the final count.

# User 1 searches for 'redis tutorial'
> PFADD search:queries "redis tutorial"
(integer) 1  # The internal state changed

# User 2 searches for 'what is hyperloglog'
> PFADD search:queries "what is hyperloglog"
(integer) 1

# User 3 searches for 'redis tutorial' again
> PFADD search:queries "redis tutorial"
(integer) 0  # The internal state did not change, as this element was likely observed before

# User 4 searches for 'php redis client'
> PFADD search:queries "php redis client"
(integer) 1

# Now, let's get the estimated count of unique searches
> PFCOUNT search:queries
(integer) 3

Redis HyperLogLog Commands

The API for HyperLogLog is very simple, consisting of just three commands.

Command	Description
PFADD key element [element …]	Adds one or more elements to the HyperLogLog. It doesn’t actually store the elements, but uses their hash to update its internal bitmap.
PFCOUNT key [key …]	Returns the approximated cardinality of one or more HyperLogLogs. If multiple keys are provided, it returns the estimated cardinality of their union.
PFMERGE destkey sourcekey [sourcekey …]	Merges multiple HyperLogLog structures into a single one. This is useful for calculating combined unique counts, for example, combining daily unique user counts into a weekly or monthly total.

Practical Application: Merging Daily Counts

You can track unique visitors daily and then easily calculate the weekly unique visitors without having to store all unique IDs for the entire week.

# Add visitors for Monday
> PFADD visitors:2023-10-23 user1 user2 user3

# Add visitors for Tuesday
> PFADD visitors:2023-10-24 user2 user4 user5

# How many unique visitors were there across both days?
> PFMERGE visitors:week-43 visitors:2023-10-23 visitors:2023-10-24
OK

> PFCOUNT visitors:week-43
(integer) 5  # The count of unique users: user1, user2, user3, user4, user5