Big Data AcademyQuery · move · process · govern

Chapter 11 · Probabilistic Data Structures and Approximate Analytics

HyperLogLog for Approximate Cardinality: PFADD, PFCOUNT, PFMERGE, and Error Tradeoffs

Estimate distinct AtlasMart cardinality with HLL while preserving exact ground truth, merge semantics, and explicit error boundaries.

Intermediate165–195 minutesHyperLogLog error tradeoff labRedis Open Source 8.10.1Free/local-firstLast reviewed: September 6, 2026

Learning outcomes

AtlasMart wants a daily count of distinct visitors across millions of page-view events. Keeping every visitor ID in a Set answers exactly, but cardinality and memory can grow with traffic. HyperLogLog (HLL) deliberately discards element identity and keeps only compact state that estimates cardinality.

01

Define cardinality, exact ground truth, approximation error, standard error, and merge semantics before using PF commands.

02

Use PFADD/PFCOUNT and interpret return values without pretending they reveal exact novelty.

03

Compare HLL memory behavior with an exact Set on the same bounded AtlasMart fixture.

04

Merge daily HLLs with PFMERGE while preserving a separately measured exact baseline.

05

Decide when approximately 0.81% standard error is operationally acceptable and when exact state is required.

Exact lab baseline

All Chapter 11 mandatory labs reuse the disposable Chapter 01 environment: Redis Open Source 8.10.1 from Docker Official Image redis:8.10.1, container atlasmart-redis-ch01, standalone topology, host publication 127.0.0.1:6379, TLS disabled only because traffic stays on loopback, default ACL user disabled, named users atlasmart-app and academy-admin, logical database 0, AOF with appendfsync everysec plus RDB snapshots, persistent /data, and no explicit maxmemory limit or eviction policy. Redis 8 integrates Bloom filters, Cuckoo filters, Count-Min Sketch, Top-K, and t-digest into Redis Open Source; HyperLogLog remains a long-standing core Redis data type. Fixtures stay under atlasmart:ch11:*. Mandatory work is local and uses deterministic synthetic AtlasMart data; no paid service, production endpoint, or real credential is required.

Redis 8 integration and ACL/version discipline

Redis 8 integrated five probabilistic structures that historically lived in RedisBloom/Redis Stack: Bloom filter, Cuckoo filter, Count-Min Sketch, Top-K, and t-digest. Redis 8 also added ACL categories @bloom, @cuckoo, @cms, @topk, and @tdigest, while these commands also participate in broader @read/@write/@fast/@slow categories. That can widen an old ACL rule after an upgrade, so verify effective permissions rather than assuming module-era ACL behavior. Redis 8.10.1 is a security release and specifically fixes a Count-Min Sketch RDB-loading memory-safety issue and a Top-K cleanup issue; do not downgrade the chapter lab to an older moving tag.

1. Cardinality is a count of distinct identities

Cardinality is the number of distinct elements in a collection. For AtlasMart analytics, repeated page views from one visitor should contribute one distinct visitor, not many events. An exact Redis Set stores members and can answer SCARD; an HLL does not retain recoverable member identities and therefore cannot answer membership or deletion questions.

Question Exact structure Probabilistic structure What is lost
How many distinct visitors? Set + SCARD HyperLogLog + PFCOUNT Individual membership identity
Was visitor u42 seen? Set + SISMEMBER Not supported by HLL Membership query
Remove visitor u42 from the estimate Set + SREM Not supported by HLL Deletion/reversal
Union unique visitors across days SUNION/SCARD PFMERGE or multi-key PFCOUNT Exact member list

2. Redis HLL error and memory are bounded differently from exact Sets

Redis documents a standard error of approximately 0.81% for HyperLogLog cardinality. A dense Redis HLL uses about 12 KiB for its register array plus overhead, while small HLLs can use a sparse encoding before switching to dense. The important design property is that HLL memory does not grow linearly with unique visitor count the way an exact Set does.

Do not turn 0.81% into an SLA without measurement

Standard error describes the estimator, not a promise that every individual PFCOUNT result lies inside ±0.81%. Validate error distributions on data shapes representative of your workload.

3. Preflight the actual Redis 8 command surface

redis-cli · server version and command evidence 
docker exec -e REDISCLI_AUTH=AtlasMart-Admin-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user academy-admin INFO serverdocker exec -e REDISCLI_AUTH=AtlasMart-Admin-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user academy-admin COMMAND INFO PFADD PFCOUNT PFMERGE BF.RESERVE CF.RESERVE CMS.INITBYPROB TOPK.RESERVE TDIGEST.CREATEdocker exec -e REDISCLI_AUTH=AtlasMart-Admin-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user academy-admin ACL DRYRUN atlasmart-app PFADD atlasmart:ch11:hll:test u01

COMMAND INFO is stronger evidence than assuming an old “RedisBloom module” packaging model. On Redis 8.10.1 the five formerly module-centric probabilistic families are integrated into Redis Open Source. HLL commands remain core Redis commands.

4. Build exact and approximate state side by side

redis-cli · same AtlasMart visitors in Set and HLL 
docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:visitors:exact atlasmart:ch11:visitors:hlldocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app SADD atlasmart:ch11:visitors:exact u01 u02 u03 u01 u04 u05 u02 u06 u07 u08 u09 u10 u11 u12 u13 u14 u15docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFADD atlasmart:ch11:visitors:hll u01 u02 u03 u01 u04 u05 u02 u06 u07 u08 u09 u10 u11 u12 u13 u14 u15docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app SCARD atlasmart:ch11:visitors:exactdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFCOUNT atlasmart:ch11:visitors:hlldocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app MEMORY USAGE atlasmart:ch11:visitors:exactdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app MEMORY USAGE atlasmart:ch11:visitors:hll

On a tiny fixture the HLL estimate may equal the exact count. That coincidence does not make HLL exact. Record both results and the two memory measurements; repeat with larger deterministic datasets when evaluating the tradeoff.

5. PFADD return value is not “this exact element was new”

PFADD returns 1 when at least one internal HLL register changed, and 0 otherwise. Because HLL stores compressed estimator state rather than exact members, a return of 0 does not prove that the submitted visitor was previously seen, and a return of 1 is not an exact membership log.

redis-cli · observe PFADD state-change semantics 
docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFADD atlasmart:ch11:visitors:hll u16docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFADD atlasmart:ch11:visitors:hll u16docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFCOUNT atlasmart:ch11:visitors:hll

6. PFCOUNT can itself mutate cached HLL metadata

Redis documents PFCOUNT as technically able to modify the HLL because cached cardinality is stored in its representation. Treat it as a cardinality query at the application level, but understand why ACL/replication/persistence diagnostics may show details that surprise someone expecting a physically read-only object.

7. Merge daily sketches without summing daily counts

Summing per-day PFCOUNT values double-counts visitors who appear on multiple days. Merge the estimator states instead. PFMERGE writes a destination HLL representing the union; multi-key PFCOUNT can estimate a temporary union without persisting a destination.

redis-cli · daily HLL union 
docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:hll:day1 atlasmart:ch11:hll:day2 atlasmart:ch11:hll:two-daysdocker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFADD atlasmart:ch11:hll:day1 u01 u02 u03 u04docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFADD atlasmart:ch11:hll:day2 u03 u04 u05 u06docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFCOUNT atlasmart:ch11:hll:day1docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFCOUNT atlasmart:ch11:hll:day2docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFCOUNT atlasmart:ch11:hll:day1 atlasmart:ch11:hll:day2docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFMERGE atlasmart:ch11:hll:two-days atlasmart:ch11:hll:day1 atlasmart:ch11:hll:day2docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app PFCOUNT atlasmart:ch11:hll:two-days

The exact union for this fixture is six visitors. Use that only as ground truth for the test; never “correct” production HLL output to six because the fixture happened to be small.

8. Cluster locality changes multi-key HLL operations

In Redis Cluster, multi-key commands are constrained by hash slots. If you intend to merge related HLLs server-side, design co-location deliberately—for example atlasmart:{visitors}:2026-09-05 and atlasmart:{visitors}:2026-09-06 share the same hash tag. Co-location can also create hot slots, so it is a workload tradeoff, not a universal naming rule.

9. Exact local ground truth belongs beside the estimator

python · deterministic exact baseline 
from collections import Counterfrom math import ceil# Deterministic AtlasMart fixture. Redis is not involved in this exact baseline.events = [    "u01","u02","u03","u01","u04","u05","u02","u06","u01","u07",    "u08","u09","u10","u03","u11","u12","u13","u01","u14","u15",]exact_unique = len(set(events))exact_freq = Counter(events)print("exact unique:", exact_unique)print("u01 exact frequency:", exact_freq["u01"])print("top exact:", exact_freq.most_common(5))# For a quantile ground truth, pick an explicit rank convention and document it.latencies = sorted([18,21,19,23,22,24,25,20,28,31,26,27,35,29,30,42,38,33,40,55])def nearest_rank(q):    i=max(0,min(len(latencies)-1,ceil(q*len(latencies))-1))    return latencies[i]for q in (0.5,0.9,0.99):    print(q, nearest_rank(q))

10. Wrong approach: publish PFCOUNT as an exact billing number

Suppose finance charges merchants per distinct customer and the invoice says “1,000,000 exact customers” because PFCOUNT returned 1,000,000. The data structure does not provide that guarantee. Use exact source-of-record data for contractual accounting, or explicitly define the metric as an estimate with an accepted error policy.

Repair

Keep HLL for fast dashboards/capacity signals, periodically reconcile it against an exact sample or warehouse count, graph relative error, and alert if observed error exceeds the product’s acceptable envelope.

11. Persistence and replication do not make the estimate exact

AOF/RDB can persist HLL state and replicas can copy it, but durability protects the estimator state—not the identities you discarded. A backup of an HLL cannot reconstruct the original visitor list. Replication is asynchronous and is not a backup; later chapters cover those guarantees in depth.

13. Reproducible cleanup

redis-cli · remove Chapter 11 lesson-1 fixtures 
docker exec -e REDISCLI_AUTH=AtlasMart-App-Lab-Only-2026 atlasmart-redis-ch01 redis-cli --user atlasmart-app DEL atlasmart:ch11:visitors:exact atlasmart:ch11:visitors:hll atlasmart:ch11:hll:test atlasmart:ch11:hll:day1 atlasmart:ch11:hll:day2 atlasmart:ch11:hll:two-days

14. Production judgment

Use HLL when the product question is approximate distinct cardinality and fixed-ish memory is more valuable than recoverable membership. Measure observed relative error, memory, command latency, write rate, persistence traffic, replication lag, and merge topology. Keep HLL out of exact billing, security authorization, legal counts, or any workflow that needs deletion of individual observations. PFMERGE/multi-key PFCOUNT require Cluster locality planning; retries are naturally tolerant for duplicate PFADD inputs but cannot undo accidental additions.

15. Summary and next step

HyperLogLog trades identity and exactness for compact distinct-count estimation. Lesson 2 moves from “how many unique?” to “have I probably seen this item?” with Bloom filters—and introduces the first explicit false-positive budget.

Check your understanding

  1. What does PFADD returning 1 prove?
  2. Can HLL answer whether u42 was seen?
  3. What standard error does Redis document for HLL cardinality?
  4. Why is summing daily PFCOUNT values wrong for a two-day unique count?
  5. What does persistence preserve for an HLL?
Review the answers

At least one internal HLL register changed; it does not prove exact element novelty.

No. HLL does not retain membership identities.

Approximately 0.81% standard error.

The same visitor can appear on both days, so summing double-counts overlap; merge estimator states instead.

The estimator state, not the discarded original member list.

Authoritative references

Keep knowledge open

Help the academy stay free and grow.

If these tutorials save you time, a small donation supports new lessons, technical review, diagrams, examples, and long-term maintenance.

ETHEthereum / ERC-20 only
0x716c4Ab160C4B66F31a28AE2448BfF68fc3a2ef0

Send only Ethereum or ERC-20 compatible assets to this address.