jonnify·redis /redis-patterns/data-modeling/probabilistic-data-structures

R7.03 · Data Modeling & Memory — module hub · a contrast

Probabilistic data structures.

Count unique items with HyperLogLog (12KB fixed), test set membership with Bloom filters, or estimate frequencies with Count-Min Sketch — trading small accuracy loss for massive memory savings.

This module is taught as a contrast. When a dataset grows to billions of items, exact counting and exact membership become prohibitively expensive, so a probabilistic structure gives up exactness for a fixed, tiny footprint with a known error rate. EchoMQ made the opposite choice for deduplication: the emq:{q}:de:<dedupId> key stores every id exactly — O(n) memory, zero false positives — because a false “already seen” would silently drop a job. A grep of the whole echo_mq library finds no probabilistic structure at all. The three dives take the family apart and state the trade both ways.

The family, by memory and engine. Select a structure to read what it estimates, its error type, its memory shape, and whether it is core Valkey or a module command.
structure core (green) · module (blue) HyperLogLogcore · PF* Bloommodule · BF.* Cuckoomodule · CF.* Count-Minmodule · CMS.* T-Digestmodule · TDIGEST.* Top-Kmodule · TOPK.* each: a small known error bought for a fixed, tiny footprint
readout · Select a structure. Each answers one question approximately — cardinality, membership, frequency, or percentile — to trade a known error for a fixed, tiny footprint. Only HyperLogLog is core Valkey.
§1

The contrast that frames the module

echo_mq/metrics.ex · echo_mq/jobs.ex

Probabilistic structures earn their place only by what they give up: exactness. So the clearest way into them is the choice not to use one. EchoMQ deduplicates jobs, and it does so exactly. Every producer-chosen idempotency key is parked at a real string key holding the actual branded job id, and EchoMQ.Metrics.get_deduplication_job_id/3 reads it back:

# echo/apps/echo_mq/lib/echo_mq/metrics.ex — the branded job id parked at emq:{q}:de:<dedupId>
def get_deduplication_job_id(conn, queue, dedup_id) when is_binary(dedup_id) do
  key = Keyspace.queue_key(queue, "de:" <> dedup_id)
  case Connector.command(conn, ["GET", key]) do
    {:ok, nil} -> :absent
    {:ok, id} when is_binary(id) -> {:ok, id}
    other -> other
  end
end

The admission script adds a second exact check — EXISTS KEYS[1] on the job key refuses a duplicate by id:

-- echo/apps/echo_mq/lib/echo_mq/jobs.ex — @enqueue, the exact dup-refusal by job key
if redis.call('EXISTS', KEYS[1]) == 1 then
  return 0
end
Two roads from the same question. Select a membership answer; the readout names what it costs and what its error does. EchoMQ took the exact road for dedup; probabilistic is the other road.
exact (EchoMQ) probabilistic emq:{q}:de:<dedupId> stores every id O(n) memory zero false positives never drops a job a Bloom / Cuckoo filter fixed, tiny footprint tunable FP rate zero false negatives a false “present” is possible same question — different price
readout · Select a road. EchoMQ took the exact one for dedup — emq:{q}:de:<dedupId>, O(n) memory, zero false positives — because a false “already seen” would drop a real job.

A grep of the whole echo_mq library finds zero probabilistic structures — no PFADD, no BF./CF./CMS.. That is deliberate: a probabilistic dedup would occasionally report “already seen” for a job it never saw, and the queue would drop real work silently. Probabilistic structures are the road for the other direction — a huge cardinality where a bounded error is acceptable.

§2

HyperLogLog: counting unique items

probabilistic-data-structures.md.txt · cardinality

HyperLogLog (HLL) estimates the cardinality — the count of unique items — of a set. A plain Set storing one billion unique user ids needs roughly 12GB of RAM. An HLL needs exactly 12KB regardless of how many elements you add, with about 0.81% standard error.

HLL hashes each element and observes the maximum number of leading zeros in the resulting bits. The probability of seeing N leading zeros is 1/2N, so the longest run estimates how many distinct elements were added; multiple registers and a harmonic mean reduce the variance. The commands are core Valkey — no module required:

PFADD visitors:2024-01-30 "user:123" "user:456" "user:789"   # add elements (creates the key)
PFCOUNT visitors:2024-01-30                                  # the estimated cardinality
PFMERGE visitors:week visitors:2024-01-28 visitors:2024-01-29  # union of HLLs, no double-count

Use it for unique visitors, distinct search queries, or distinct IP addresses — any place an approximate count of a huge set is acceptable. For one million actual uniques the estimate typically lands between 991,900 and 1,008,100. The HyperLogLog dive carves this slice, with the exact-Set-vs-HLL memory cliff.

Notes on ValkeyPFADD returns 1 when the registers changed and 0 otherwise; an HLL is stored in a string and starts in a compact sparse encoding, converting to the fixed-size dense encoding as the cardinality grows — which is why a small HLL is under 12KB and a large one settles at 12KB — valkey.io/commands/pfadd.

HyperLogLog turns a 12GB exact count into a 12KB estimate with a 0.81% error — the probabilistic trade in its clearest form. It answers how many, not which, which is exactly why it cannot stand in for EchoMQ's exact dedup.

§3

Bloom & Cuckoo: membership testing

probabilistic-data-structures.md.txt · membership

A Bloom filter answers “is this item in the set?” with possible false positives but zero false negatives. A “no” is definite; a “yes” is “probably”. Items are hashed by several functions, each setting a bit in a shared array; a lookup checks the same bits — any zero proves absence. Bloom commands are module commands (Valkey-Bloom / Redis-Stack), not core:

BF.RESERVE usernames 0.01 1000000   # 1% false-positive rate, capacity 1M — a module command
BF.ADD usernames "john_doe"
BF.EXISTS usernames "john_doe"

The signature use is the cache-penetration problem: a flood of requests for non-existent keys each misses the cache and hits the database. A Bloom filter holding the real keys rejects the absent ones immediately — if the filter says “absent”, skip the cache and the database. The zero-false-negative guarantee is what makes this safe: a real key is never wrongly rejected, and a false positive only costs one needless lookup.

A Cuckoo filter is a Bloom filter that supports deletion, storing fingerprints via cuckoo hashing. Use Cuckoo when items must leave the filter — tracking active sessions that expire, for instance:

featureBloomCuckoo
deletionnot supportedsupported
space (low FP rates)goodbetter
insertfasterslightly slower
lookupslightly slowerfaster

Both contrast with EchoMQ's exact de: membership. A Bloom filter's one-sided error is in the wrong direction for idempotency: it never wrongly says “absent”, but it can wrongly say “present” — and a false “already seen” drops a job. So EchoMQ stores every id exactly. The Bloom & Cuckoo dive carves both, with the false-positive dial.

A Bloom filter is safe where a false positive is cheap (a wasted cache lookup) and the no-false-negative guarantee protects real keys. Where a false positive is catastrophic — dropping a job — use the exact key EchoMQ uses.

§4

Estimation: frequency, percentiles, heavy hitters

probabilistic-data-structures.md.txt · T-Digest · CMS · Top-K

T-Digest estimates percentiles without sorting every observation — accurate at the tails (p99, p99.9) where an average misleads. Count-Min Sketch estimates how many times each item has been seen, with possible over-counting but never under-counting. Top-K tracks the K most frequent items without storing all of them. All three are module commands:

TDIGEST.CREATE latencies                       # percentiles — a module command
TDIGEST.ADD latencies 45.2 89.1 12.5 156.7
TDIGEST.QUANTILE latencies 0.5 0.95 0.99       # estimated p50, p95, p99

CMS.INITBYDIM page_views 2000 5                # frequency — a module command
CMS.INCRBY page_views "/home" 1 "/about" 1
CMS.QUERY page_views "/home"                   # an estimate ≥ the true count

TOPK.RESERVE trending 10 50 3 0.9              # heavy hitters — a module command
TOPK.ADD trending "topic:redis" "topic:go"
TOPK.LIST trending

They fit observability over a huge stream — SLA p99, page-view frequency, trending topics — where a small bounded error is fine. They are the wrong tool for a counter the system acts on: EchoMQ's attempts retry fence is an exact HINCRBY integer, because an over-count would dead-letter a job too early. The Count-Min & T-Digest dive carves all three.

Count-Min, T-Digest, and Top-K answer “how often” and “what percentile” cheaply, with a bounded error, over streams too large to count exactly. Use them for observability — not for a count that gates a decision, where EchoMQ keeps the exact integer.

§5

Choosing the right structure

probabilistic-data-structures.md.txt · the decision

Each structure answers one question approximately to save memory. The discipline is the same in every case: name the error you can tolerate, then pick the structure whose error is that.

needstructureengineerror type
count unique itemsHyperLogLogcore · PF*cardinality ±0.81%
check set membershipBloom / Cuckoomodule · BF.*/CF.*false positives possible
calculate percentilesT-Digestmodule · TDIGEST.*percentile estimates
count item frequencyCount-Min Sketchmodule · CMS.*over-counting possible
the pattern

A probabilistic structure trades a small, known error for a fixed, tiny memory footprint — answering cardinality, membership, frequency, or percentile approximately, at a fraction of the exact cost.

its EchoMQ application (counter-example)

EchoMQ's emq:{q}:de:<dedupId> membership is exact — O(n) memory, zero false positives. For producer idempotency a false positive would drop a job, so the exact key is the right call, and the echo_mq library carries no probabilistic structure at all.

Notes on ValkeyPFCOUNT returns the estimated cardinality of one or more HyperLogLogs in core Valkey; the module structures — BF.*, CF.*, CMS.*, TDIGEST.*, TOPK.* — ship in Valkey-Bloom / Redis-Stack, not the core engine — valkey.io/commands/pfcount.

Name the error you can tolerate and pick the structure whose error matches it — and notice when the tolerable error is zero, as it is for idempotency, where EchoMQ keeps the exact de: key. A codemojex note, forward-tense: unique-player counts per round or day are the natural HyperLogLog fit for the workshop's “uniques” view, but codemojex ships no HLL surface today, so it is shown standalone in the dive, not as a claim about the live code.

/redis-patterns/data-modeling/primary-database/system-of-record

The exact-dedup home

The emq:{q}:de:<dedupId> key and the @enqueue EXISTS refusal are taught in full in R7.1, the system of record: the job HASH is the record of truth, and its dedup is exact by the same logic. This module is its mirror image — the road not taken.

/bcs

The architecture

EchoMQ's exact-dedup choice follows from the Branded Component System discipline — the branded id is the identity a dedup key is built from. The Branded Component System is the architecture EchoMQ and codemojex are built to, where this and the other modeling decisions are grounded.

R7.3 grounds the probabilistic family against EchoMQ's exact dedup. The three dives take cardinality, membership, and estimation in turn. Return to the Data Modeling & Memory chapter to continue.

§6

The three dives

hyperloglog → bloom-and-cuckoo → count-min-and-t-digest

Each dive takes one slice of the family, in order: cardinality at a fixed 12KB, membership with no false negatives, and the estimation trio — frequency, percentiles, heavy hitters. Each closes against EchoMQ's exact choice.

R7.03.1built

HyperLogLog

Cardinality at a fixed 12KB, ~0.81% error; PFADD/PFCOUNT/PFMERGE in core Valkey; the exact-Set-vs-HLL memory cliff and the EchoMQ exact-dedup contrast.
R7.03.2built

Bloom & Cuckoo

Membership with no false negatives; Bloom (BF.*, the cache-penetration use) vs Cuckoo (CF.*, supports delete) — module commands; the false-positive dial against exact de:.
R7.03.3built

Count-Min & T-Digest

Frequency (CMS.*), percentiles (TDIGEST.*), heavy hitters (TOPK.*) — module commands for observability, contrasted with EchoMQ's exact attempts fence.

The three dives ground in the same contrast: a bounded-error estimate where it is acceptable, and the exact key where it is not. Begin with HyperLogLog.

§7

References

sources · related

Sources

Related in this course