Engineering Atlas › System Design Fundamentals

Estimating frequencies with a Count-Min Sketch

12 min read · last reviewed 2026-10-17

Open in the interactive app: practice, quiz, mock interview →

In one minute

How it works

Structure and update

The sketch is a d by w array of integer counters, all starting at zero, plus d hash functions, one per row, each mapping an item to a column in [0, w). To record c occurrences of item x, add c to counter[i][h_i(x)] for every row i. That is d memory writes per update, independent of how many distinct items exist.

Query

To estimate x, read its counter in every row and return the smallest. Each counter holds all of x's occurrences plus colliding items, so the minimum is the tightest upper bound.

Error guarantee

Let N be the total of all updates. Choose w = ceil(e / epsilon) and d = ceil(ln(1 / delta)). Then for any item, the estimate exceeds the true count by more than epsilon * N with probability at most delta (Cormode and Muthukrishnan).

Why: in one row the expected collision mass on x's column is N / w, so by Markov's inequality it exceeds e * N / w with probability at most 1/e, and all d independent rows are that bad with probability e^-d.

For example, epsilon = 0.001 and delta = 0.001 give w = 2,719 and d = 7: 76 KB of 4-byte counters. With 100 million events, any estimate is within 100,000 of the truth with 99.9 percent probability: excellent for an item seen 5 million times, useless for one seen 50 times.

Conservative update

When adding x, compute the current estimate m and raise each of x's counters only up to m + c, so counters already inflated by collisions stop growing. This often cuts error several-fold on skewed data, but the sketch loses decrements and exact merging. The idea predates the count-min name: Estan and Varghese proposed it for counting large network flows in router memory (SIGCOMM 2002).

Merging and decrementing

Two sketches with the same dimensions and hash seeds merge by adding counters cell by cell, so per-shard or per-minute sketches roll up exactly. Without conservative update, decrements are allowed as long as no true count goes negative. Some systems need aging: Caffeine's TinyLFU halves every counter periodically so old popularity fades.

Finding heavy hitters

The sketch answers "how often is X?" but cannot list items. To track the top k, pair it with a min-heap of size k: after each update, if the item's estimate exceeds the heap minimum, insert or update it in the heap. The heap holds candidate keys; the sketch supplies their counts. Redis's Top-K structure packages this pattern, using the HeavyKeeper algorithm: counters decay exponentially when a different item collides with them, which pushes small flows out and keeps elephants accurate (Redis docs, USENIX ATC 2018).

Down the stack

Layer 1The contract

With non-negative updates, every estimate is at least the true count. With probability at least 1 - delta, it exceeds the true count by at most epsilon * N, where N is the total weight added. Two sketches with identical width, depth, and hash seeds can be merged by adding counters, and the result is exactly the sketch of the combined stream. The sketch cannot enumerate keys or report which items are frequent without a separate candidate list.

Layer 2The mechanism

Redis offers CMS.INITBYDIM (width and depth) and CMS.INITBYPROB (error and probability), CMS.INCRBY for updates (increments may be negative), CMS.QUERY for estimates, and CMS.MERGE with optional weights. These were the RedisBloom module until Redis 8 built them into the server (RedisBloom). Redis does not use the textbook sizing: CMS.INITBYPROB key 0.001 0.002 creates a 2,000 by 9 sketch, so width is 2 / error and depth is log2(1 / probability), where the paper's formulas give 2,719 by 7. Redis also tells you to treat estimates below error * total_count as noise (Redis docs). Compare dimensions, not parameters, when moving sketches between libraries.

Caffeine's TinyLFU admission policy is the best-known production use (Einziger, Friedman and Manes). Its FrequencySketch uses 4-bit counters, 16 packed into each 64-bit long, with 4 counters per item. The table is sized from the cache's maximum size, at about 8 bytes per cache entry (Caffeine wiki). After a sample of additions 10 times the cache size, every counter is halved with a shift and mask over each word, so popularity decays. Recent versions place all of an item's counters in one 64-byte block so that an update costs a single cache miss (Caffeine source). Many implementations derive the d row hashes from two base hashes as h1 + i * h2.

Layer 3The machine

A textbook sketch with d separate rows costs d independent memory accesses per update. Small sketches (76 KB, 544 KB) live in L2 or L3 cache and cost a few nanoseconds per access; larger ones pay 80 to 100 ns per row on a miss, though the CPU can overlap independent misses. Packing an item's counters into one cache line turns that into one miss.

Concurrency is the second machine cost. If many threads increment the same hot item's counters, the cache line holding them bounces between cores, at around 100 ns per transfer, and atomic increments serialise. High-throughput systems keep per-thread or per-core sketches and merge them periodically, which works because plain sketches merge by addition. Counter width is a memory trade: 4-bit counters saturate at 15, which is fine for admission decisions but useless for rate limits; rate limiters use 32-bit counters.

Why it's built this way

  1. One counter per key costs memory proportional to the number of keys, so keys share a fixed array of counters.
  2. Sharing causes collisions, so several rows with independent hashes are kept and the least-collided row, the minimum, is reported.
  3. Collisions only add, so the error is one-sided, which suits threshold decisions such as throttling or admission.
  4. Memory access dominates cost, so production versions shrink counters and co-locate an item's counters in one cache line.

Diagram

flowchart TD
    X["Item x, count c"] --> H1["Row 1: h1(x)"]
    X --> H2["Row 2: h2(x)"]
    X --> H3["Row d: hd(x)"]
    H1 --> U["Add c to each chosen counter"]
    H2 --> U
    H3 --> U
    Q["Query x"] --> R["Read d counters"]
    R --> M["Return the minimum"]
    M --> B["Estimate >= true count"]

Worked example

An API gateway wants to throttle any API key that exceeds 1,000 requests per minute. There are 30 million keys, most idle, and 400,000 requests per second across the fleet.

An exact per-key map would cost hundreds of MB per node with churn every minute. Instead each node keeps a count-min sketch per minute window.

Each node sees about 25,000 requests per second, so 1.5 million per minute. The threshold that matters is 1,000. Pick epsilon so epsilon * N is well under that: epsilon = 0.0001 gives a maximum overcount of 150 with high probability. That needs w = 27,183. With d = 5 (delta about 0.7 percent), the sketch is 136,000 counters, 544 KB at 4 bytes. Five hash computations and five increments per request cost well under a microsecond.

The error is one-sided: a key at 900 requests might read as 1,040 and be throttled early. So when an estimate crosses the threshold, start an exact counter for that key only; few keys come near the limit, so that map stays tiny.

For a global limit, nodes ship their per-minute sketches to an aggregator every few seconds and the aggregator sums them, which is valid because plain sketches merge by addition.

In the wild

Trade-offs

OptionStrengthsWeaknessesChoose when
Count-min sketchFixed memory, fast, mergeable, one-sided errorError scales with total volume, cannot list keysFrequencies of heavy items in huge key spaces
CMS with conservative updateMuch lower overestimation on skewed dataNo decrements, merge is no longer exactSingle-node counting, cache admission
Count sketch (signed)Unbiased, better for moderately frequent itemsCan underestimate, needs median of rowsYou need unbiased estimates, not upper bounds
Exact hash mapExact counts and listingMemory proportional to distinct keysKey space is small or bounded

Pitfalls in production

Leadership lens

Check yourself

  1. Why does a count-min sketch never underestimate, and when does that stop being true?

    Show answer

    Every counter for an item includes all of that item's increments plus collisions, which only add. It stops being true if negative updates push other items' contributions down, as in a stream with deletions that are not matched by earlier inserts.

  2. Doubling w and adding one row: which improves the error bound and which improves the confidence?

    Show answer

    Doubling w halves epsilon, the size of the error relative to N; adding a row reduces delta, the probability of exceeding that error, by a factor of about e.

  3. Why can't conservative-update sketches be merged by addition?

    Show answer

    Conservative update skips increments on counters that were already high, so a counter no longer equals the sum of its items' contributions, and adding two such counters does not equal the counter the combined stream would have produced.

Sources and further study

Primary

Systems docs

Books

Other curricula

Watch

Free resources

Open in the interactive app: practice, quiz, mock interview →