Skip to content
Tutorials Center
My learning

Topics

Lesson 11 of 42 ยท Specialized Data Types

HyperLogLog and Probabilistic Structures

Learn Redis HyperLogLog (PFADD, PFCOUNT, PFMERGE), Bloom filters and Count-Min Sketch: approximate counting, error rates and memory use, with live JavaScript sketches.

Some questions are expensive to answer exactly. "How many different people visited this page today?" needs a set that remembers every visitor, and for a hundred million visitors that set is gigabytes of memory. Probabilistic data structures trade a small, well-understood error for a huge saving: they answer approximately, in a fixed amount of memory, no matter how much data flows through them.

Redis has one of these built in for a long time, the HyperLogLog, which counts distinct elements in at most 12 KB with a standard error of about 0.81%. In Redis 8, further probabilistic types ship with Redis itself (earlier they came from the RedisBloom module in Redis Stack): the Bloom filter and cuckoo filter (is this item probably in the set?), the Count-Min Sketch (about how often did this item occur?), Top-K (which items are the heaviest?) and t-digest (percentiles). This lesson teaches the HyperLogLog commands in detail and the Bloom filter and Count-Min Sketch ideas.

Real Redis cannot run on this page, so the redis-cli snippets are read-only. The runnable examples are JavaScript sketches written from scratch: a HyperLogLog with 16,384 registers like Redis uses, a Bloom filter and a Count-Min Sketch. They use a small 32-bit hash function instead of Redis's own, so exact estimates differ from a real server, but the behaviour, the error sizes and the guarantees are the real ones.

Trade accuracy for memory

Fixed size Memory does not grow with the data.
Small error Known, tunable, usually under 1-2%.
No listing You cannot read the items back.
1 / 2

HyperLogLog: counting distinct items

A HyperLogLog (HLL) turns every element into a hash and watches the rarest pattern it has seen. If you flip a fair coin, getting ten heads in a row is rare, and seeing it suggests you have flipped roughly a thousand times. The HLL applies that idea to the leading zeros of hashes: it splits the hash into a register number (the first 14 bits, so 16,384 registers) and a remainder, and each register remembers the longest run of leading zeros seen among its remainders. Averaging over many registers gives a stable estimate of how many distinct elements went in. Adding the same element again produces the same hash and changes nothing, which is why the structure counts distinct items.

Three commands cover it:

  • PFADD key element [element ...] adds elements. It returns 1 if the internal state changed (so the count may have gone up) and 0 otherwise.
  • PFCOUNT key [key ...] returns the estimated number of distinct elements. With several keys it returns the size of their union, without storing it.
  • PFMERGE destkey sourcekey [sourcekey ...] stores the union of several HLLs in one, ready to be counted or merged further.
Text
127.0.0.1:6379> PFADD visitors:2026-11-08 ana bo cy ana
(integer) 1
127.0.0.1:6379> PFCOUNT visitors:2026-11-08
(integer) 3
127.0.0.1:6379> PFMERGE visitors:week visitors:2026-11-07 visitors:2026-11-08
OK
127.0.0.1:6379> PFCOUNT visitors:week
(integer) 5

For small sets Redis uses a compact sparse encoding and then switches to a dense one that is at most about 12 KB. The key is physically a string with a special header, so TYPE shows string, but treat it as opaque and never write to it with string commands. The first TryIt builds the same structure in JavaScript, checks its error at four sizes, and shows that merging overlapping sets does not double count.

JS A HyperLogLog from scratch

Press Run (or Ctrl + Enter) to see the console output here.

No output.

Every row of the accuracy table stays within a couple of percent, and the union of the two days overlaps correctly: the 20,000 users present on both days are counted once.

Choosing and using HLL

Use a HyperLogLog when you only need the count (unique visitors, distinct search terms, distinct IP addresses) and an error under one percent is acceptable. Keep one HLL per page per day and merge them for weekly or monthly totals. Do not use it when you need the members back, when a billing decision depends on the exact number, or for small sets where an exact set costs almost nothing. Its commands are O(1) for PFADD and PFCOUNT on a single key, and PFCOUNT on several keys costs more because it merges them on the fly.

Bloom filters: "definitely not" or "probably yes"

A Bloom filter is a bit array of size m plus k hash functions. To add an item, hash it k times and set those k bits. To check an item, hash it the same way: if any of the bits is 0 the item was definitely never added; if all are 1 it was probably added, because other items may have set the same bits by chance. So a Bloom filter has no false negatives but can have false positives, and you choose the false-positive rate in advance. You cannot remove items (clearing a bit could erase other items), and you cannot list them.

The rate depends on the load: with n items added, the expected false-positive probability is (1 - e^(-k n / m))^k. For a target rate p, the filter needs about -n ln p / (ln 2)^2 bits (roughly 9.6 bits per item for 1%) and k = (m / n) ln 2 hash functions. In Redis 8 you ask for this directly:

Text
BF.RESERVE seen:urls 0.01 1000000
BF.ADD seen:urls https://example.com/a
BF.EXISTS seen:urls https://example.com/a

BF.RESERVE key error_rate capacity creates the filter, BF.ADD/BF.MADD add items and BF.EXISTS/BF.MEXISTS check them. Typical uses: a crawler that must not visit a URL twice, "has this user already seen this recommendation?", and a cheap gate in front of a slow database (if the filter says "definitely not", skip the lookup, which protects against cache-penetration attacks with random keys).

Count-Min Sketch: about how often?

A Count-Min Sketch (CMS) is a small grid of counters, depth rows by width columns, with one hash function per row. To count an item, hash it once per row and increment the counter in that cell. To estimate its count, read the same cells and take the minimum. Collisions can only add to a cell, never subtract, so the estimate is never below the true count and sometimes above it. The error shrinks as the width grows (more columns, fewer collisions) and the chance of a large error shrinks as the depth grows. It is perfect for "how many times was each API key used today?" when there are millions of distinct keys. In Redis 8 the commands are CMS.INITBYDIM key width depth (or CMS.INITBYPROB key error probability), CMS.INCRBY key item count and CMS.QUERY key item. TOPK.* builds on the same idea to track just the heaviest items.

The second TryIt implements a Bloom filter and a Count-Min Sketch, measures the Bloom filter's real false-positive rate against the formula, and shows that the sketch never underestimates.

JS A Bloom filter and a Count-Min Sketch

Press Run (or Ctrl + Enter) to see the console output here.

No output.

In the Bloom filter part, the false-negative count is 0 and the measured false-positive rate (about 1%) matches the formula, using roughly 1.2 KB for 1,000 items.

Look at the last line of the output: it must always be 0. That one-sided error is the guarantee that makes the sketch usable for rate limiting and "is this key hot?" checks, because it can only be too cautious, never too relaxed. The estimates of the tail keys, which are rare in truth, are the ones inflated by collisions with the heavy keys.

Comparing the options

Question Exact tool Probabilistic tool Error
How many distinct items? Set + SCARD HyperLogLog about 0.81% either way
Have I seen this item? Set + SISMEMBER Bloom or cuckoo filter false positives only
How often did this item occur? Hash with HINCRBY Count-Min Sketch overestimates only
Which items are most frequent? Sorted set + ZINCRBY Top-K approximate ranking

If the data fits comfortably in memory, prefer the exact structure: it is simpler and has no error to explain. Reach for a sketch when the number of distinct items is so large that exact tracking costs more than the question is worth.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does PFCOUNT visitors return?

    A HyperLogLog counts distinct elements approximately, in a fixed small amount of memory, and cannot return the elements themselves.
  2. 2. A Bloom filter says an item exists. What do you know?

    Bloom filters have no false negatives, but a yes can be a false positive caused by other items setting the same bits.
  3. 3. Which command gives the number of distinct visitors across two daily HyperLogLogs without creating a new key?

    PFCOUNT with several keys merges them on the fly and returns the union estimate. PFMERGE would store the result in a destination key instead.
  4. 4. How can a Count-Min Sketch estimate differ from the true count?

    Different items can share a cell, which inflates counters but never reduces them, and the minimum over the rows is the least inflated value. The result is never below the true count.
  5. 5. When should you prefer a plain set over a HyperLogLog?

    A set costs little for small collections, returns its members and is exact. A HyperLogLog is for counts where a fraction of a percent of error is acceptable.

Summary

  • Probabilistic structures give approximate answers in fixed memory; pick the one matching your question.
  • PFADD, PFCOUNT and PFMERGE implement a HyperLogLog: about 12 KB, standard error about 0.81%, duplicates ignored, union by merging.
  • A Bloom filter (BF.* in Redis 8) has no false negatives and a tunable false-positive rate; items cannot be removed or listed.
  • A Count-Min Sketch (CMS.*) estimates frequencies and never underestimates; Top-K and t-digest follow the same trade.
  • When data is small or exactness matters, use a set, hash or sorted set instead.

Next, search by location with Geospatial Indexes.