R7.03.3 · dive 3

Frequency and percentiles, estimated.

Count-Min Sketch estimates how often each item was seen — over-counting only, never under-counting. T-Digest estimates percentiles without sorting. Top-K finds the heavy hitters.

All three are module commands, for observability over a stream too large to measure exactly. Count-Min keeps a small grid; a query takes the minimum across the hash rows. Select an item below to follow its count through the grid. The same one-sided error is the wrong property for a count that gates a decision — EchoMQ's attempts fence is an exact integer.

Count-Min Sketch Top-K T-Digest The EchoMQ contrast References

Count-Min Sketch — the minimum across rows. Select an item; the readout reports its estimate and why the query takes the minimum.

§1

Count-Min Sketch — frequency, over-counting only

probabilistic-data-structures.md.txt · frequency

Count-Min Sketch estimates how many times each item has been seen. Its error is one-sided: it may over-count, never under-count. It is a small grid of counters with several hash rows; an increment bumps one counter per row, and a query takes the minimum across the rows for that item. The minimum is the tightest estimate, because collisions only ever add to a counter, so the smallest of the rows has the fewest stray additions.

CMS.INITBYDIM page_views 2000 5     # width 2000, depth 5 — a module command
CMS.INCRBY page_views "/home" 1 "/about" 1
CMS.QUERY page_views "/home"        # an estimate ≥ the true count, never below it

The trade is a fixed-size grid against exact per-key counters. For a few hot keys an exact HINCRBY is fine; for millions of distinct keys in a stream the grid bounds the memory while keeping the error one-sided and small.

Notes on ValkeyThe Count-Min Sketch commands — CMS.INITBYDIM, CMS.INCRBY, CMS.QUERY — are provided by a module (Valkey-Bloom / Redis-Stack), not the core engine; the width and depth fix the grid size and so the error bound — a wider grid means fewer collisions and a tighter estimate — valkey.io/commands.

Count-Min estimates frequency over a huge stream at a fixed footprint, over-counting only. The minimum across rows is the tightest estimate — useful for observability, not for a count the system acts on.

§2

Top-K — the heavy hitters

probabilistic-data-structures.md.txt · heavy hitters

Top-K tracks the K most frequent items in a stream without storing all of them. It may temporarily misrank but converges to the true ranking over time. The commands are module commands, TOPK.*:

TOPK.RESERVE trending 10 50 3 0.9   # top 10 — a module command
TOPK.ADD trending "topic:redis" "topic:python" "topic:redis" "topic:go"
TOPK.LIST trending                  # the current top items

It fits trending topics, popular products, or the most frequent errors — the few items that matter, found without counting every item exactly.

Top-K surfaces the heavy hitters of a stream without a full tally, converging on the true ranking — another observability estimate, bounded and cheap.

§3

T-Digest — percentiles at the tails

probabilistic-data-structures.md.txt · percentiles

An exact percentile means sorting every observation — impractical for a continuous stream of latencies. T-Digest keeps a compressed sketch that estimates percentiles accurately, especially at the tails (p99, p99.9) where an average tells you nothing:

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

It fits SLA monitoring (“p99 latency under 100ms”) and any analysis where the average hides the tail. The estimate is close, not exact — bought for a fixed footprint over an unbounded stream. Hover the quantiles below to see where each falls on a latency distribution.

A quantile, estimated vs exact. Select a quantile; the readout reports its estimate and how it compares to the exact value.

T-Digest estimates percentiles — tightest at the tails, where the average is useless — over an unbounded stream, without sorting. Close, not exact, for a fixed footprint.

§4

The EchoMQ contrast — exact counters

echo_mq/jobs.ex · the attempts fence

EchoMQ's counters are exact integers, not sketches. The attempts field of the job HASH is an exact retry fence — @enqueue writes it '0', and each delivery increments it with HINCRBY — and the dedup membership is the exact emq:{q}:de:<dedupId> key from the hub. A grep of the echo_mq library finds no CMS., TDIGEST., or TOPK. anywhere.

echo/apps/echo_mq/lib/echo_mq/jobs.ex · @enqueue — the exact attempts fencefrozen

redis.call('HSET', KEYS[1], 'state', 'pending',
  'attempts', '0', 'payload', ARGV[2])
-- each delivery: HINCRBY the row's attempts by 1 (an exact integer fence)

The reason is the same as for dedup: these counters drive decisions, not dashboards. The attempts fence decides whether a job has exhausted its retries and must move to the dead set; an over-count would dead-letter a job too early, an under-count would loop a poison job forever. A Count-Min Sketch's “over-count only, bounded error” is exactly the wrong property for a counter that gates a control-flow decision. Sketches are for observability over a huge stream where a small bounded error is fine — page-view frequency, trending topics, p99 latency — not for a counter the system acts on.

the pattern

Count-Min (frequency, over-count only), Top-K (heavy hitters), T-Digest (percentiles): bounded-error estimates over an unbounded stream, at a fixed footprint. For observability, not control flow.

EchoMQ (counter-example)

The attempts fence (HINCRBY on the job HASH) and the de: dedup are exact integers and exact keys: they gate decisions, so a bounded error is unacceptable.

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. Where the count gates a decision — EchoMQ's retry fence — keep the exact integer, as EchoMQ does.

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

The exact-counter home

The job HASH — state / attempts / payload — and the exact de: dedup are taught in full in R7.1, the system of record: the row is the record of truth, and its counters are exact because the system acts on them.

/bcs

The architecture

The exact attempts fence is part of the Branded Component System discipline — the counter lives on the entity's row, gated by its branded id. The Branded Component System is the architecture EchoMQ is built to.

§5

References

sources · related

Sources

Redis — Count-Min Sketch — the counter grid and the minimum-across-rows query.
Redis — CMS.INITBYDIM — initialise a Count-Min Sketch by width and depth; a module command.
Redis — T-Digest — percentile estimation, accurate at the tails.
Redis — Top-K — heavy-hitter tracking without storing every item.

Related in this course

R7.03 · Probabilistic data structuresthe module hub and the exact-vs-probabilistic frame
R7.03.2 · Bloom & Cuckoomembership estimation; the same one-sided-error idea
R7.03.1 · HyperLogLogcardinality estimation at 12KB
R7.01.1 · System of recordthe exact job HASH (attempts, de:) the sketches are contrasted against
/bcs · The Branded Component Systemthe architecture EchoMQ is built to