Count-Min Sketch Architecture, in depth: an implementation guide to memory layout, hashing once, concurrency, serialization and testing the error bound

The structure in one paragraph

A sketch is d rows of w counters and d hash functions, one per row. To add c occurrences of key x, compute the column h_i(x) in each row and add c to that counter. To estimate the count of x, read the same d counters and return the smallest. Every counter the key touches holds the key's true count plus whatever other keys collided into it, so each counter is an overestimate and the minimum is the least-polluted one. With w = ceil(e / eps) and d = ceil(ln(1 / delta)), the estimate exceeds the true count by more than eps * N with probability at most delta, where N is the total of all increments.

The error is additive and relative to N, not to the key's own count. A key seen ten times in a stream of ten million can be reported as ten thousand. That is the property that decides where Count-Min belongs: finding and ranking heavy keys, rate limiting, cache admission, and trending detection, not measuring rare keys.

Sizing, briefly

Pick eps from the smallest count you need to trust, and delta from how often you can afford an estimate outside that band. Then round the width up to a power of two, which makes the column computation a mask instead of a modulo and only improves the bound.

The middle row is a common production choice: 80 KiB answers frequency queries for any number of distinct keys. For a window of ten million events, the rounded width gives an error band of about e / 4096 * 10,000,000, roughly 6,600 counts. If the heavy keys you care about occur hundreds of thousands of times, that is precise. If they occur thousands of times, you need a wider sketch or a shorter window.

Memory layout

Store the counters as one contiguous array in row-major order, counters[row * w + col], not as a list of row objects. One update touches exactly d counters in d different cache lines. With d = 5 that is five cache misses in the worst case, which is the real cost of an update once the sketch outgrows L2. Keeping d small matters more than any micro-optimization of the hash.

Choose the counter width deliberately. 32-bit unsigned counters overflow at about 4.29 billion, which a long-lived sketch on a busy key can reach. Use 64-bit counters if the sketch is never reset, or 32-bit counters with saturating addition and a window rotation that resets them long before saturation. Sixteen-bit counters with saturation are worth considering for cache admission, where only relative order among small counts matters. Whatever you choose, record it in the header, because merging a 32-bit sketch into a 64-bit one is a format conversion, not a merge.

Hashing once, stably

You do not need d independent hash functions. Compute one 64-bit hash, split it into halves h1 and h2, and derive row i's column as (h1 + i * h2) mod w. This double-hashing construction, analyzed by Kirsch and Mitzenmacher for Bloom filters, gives the same asymptotic error in practice at a fraction of the cost. With a power-of-two width, force h2 to be odd; an even stride shares a factor with w and makes rows collide in lockstep.

The hash must be stable across processes, languages and releases, because a sketch that outlives one process is only useful if the next process hashes the same key to the same columns. That rules out Python's built-in hash() for strings, which is randomized per process, and language hash codes whose output is not specified. Use a named algorithm with an explicit seed, and write both into the header. Canonicalize keys before hashing too: case, Unicode normalization, trailing whitespace and integer-versus-string encodings of the same identifier all split one real key into several sketch keys.

If users can choose keys and learn from the sketch, for example in a rate limiter, an attacker who knows the hash and seed can craft many keys that collide with a victim's columns and push the victim's estimate up. Use a keyed hash with a secret seed in that setting, and rotate it with the window.

A reference implementation

The code below is deliberately plain Python so each decision is visible. It uses BLAKE2b from the standard library as the stable, seedable hash, 64-bit counters, conservative update as an option, and a header that is checked on merge and on load.

import hashlib, math, struct
from array import array

MAGIC, VERSION = b"CMS1", 1

class CountMin:
    def __init__(self, eps, delta, seed=0, conservative=False):
        w = 1 << math.ceil(math.log2(math.e / eps))
        self.w, self.d = w, math.ceil(math.log(1 / delta))
        self.mask, self.seed, self.cu = w - 1, seed, conservative
        self.n = 0
        self.c = array("Q", bytes(8 * self.w * self.d))

    def _cols(self, key: bytes):
        h = hashlib.blake2b(key, digest_size=8,
                            key=self.seed.to_bytes(8, "little")).digest()
        v = int.from_bytes(h, "little")
        h1, h2 = v & 0xFFFFFFFF, (v >> 32) | 1          # odd stride
        return [i * self.w + ((h1 + i * h2) & self.mask) for i in range(self.d)]

    def add(self, key: bytes, count=1):
        idx = self._cols(key)
        self.n += count
        if self.cu:  # raise only the counters below the new estimate
            target = min(self.c[j] for j in idx) + count
            for j in idx:
                if self.c[j] < target:
                    self.c[j] = target
        else:
            for j in idx:
                self.c[j] += count

    def estimate(self, key: bytes):
        return min(self.c[j] for j in self._cols(key))

    def header(self):
        return struct.pack("<4sHHIIQ?", MAGIC, VERSION, 64,
                           self.w, self.d, self.seed, self.cu)

    def merge(self, other):
        if other.header() != self.header():
            raise ValueError("incompatible sketches: width, depth, seed or mode differ")
        for j in range(len(self.c)):
            self.c[j] += other.c[j]
        self.n += other.n

    def to_bytes(self):
        return self.header() + struct.pack("<Q", self.n) + self.c.tobytes()

Three choices deserve comment. The header carries a format version, the counter width, the dimensions, the seed and the update mode, so a mismatch fails loudly instead of producing a sketch whose columns mean nothing. The byte order is fixed as little-endian. And conservative update is a construction-time flag, because it changes what the counters mean: a conservative-update sketch cannot support decrements, since it no longer knows how much of each counter belongs to which key. Merging two conservative-update sketches by addition still gives a valid overestimate, but the result is looser than a single sketch fed the combined stream.

Concurrency

There are three workable designs, and the first is almost always right.

• One sketch per thread, merged on read or on a timer. Updates need no synchronization, and merge is element-wise addition. Memory is multiplied by the thread count, which is cheap at 80 KiB. This is the design to reach for in stream processors, where each partition already owns its state.
• Shared sketch with atomic adds. Relaxed atomic fetch-and-add on each of the d counters is correct for the plain update, because addition commutes and every increment lands. Contention on a hot key's columns becomes the bottleneck, which is exactly the key you care about.
• Conservative update under concurrency. This is the trap. The update reads the minimum and then raises counters to it, and two racing updates can both read the same minimum and each raise to min + 1, losing an increment. That breaks the one-sided guarantee: the sketch can now underestimate. Use per-thread sketches, or a lock per sketch, if you need conservative update.

Readers need no lock for plain sketches if a slightly stale estimate is acceptable, which it almost always is: every estimate already carries an error of eps * N.

Worked example: trending search terms

A search service wants the top 50 query terms per five-minute window, across 40 frontend instances. Each instance keeps a sketch with eps = 0.001, delta = 0.01, rounded to w = 4096, d = 5, and alongside it a min-heap of the 200 keys with the highest estimates it has seen. On each query it adds the normalized term, re-estimates it, and updates the heap if the estimate beats the heap's minimum.

Every five minutes, each instance ships its serialized sketch and its heap's keys to an aggregator. The aggregator checks each header, merges the 40 sketches, takes the union of the candidate keys, re-estimates every candidate against the merged sketch, and publishes the top 50. The window saw 12 million queries, so the error band is about 8,000. The fiftieth term had 31,000 occurrences, so the list is stable; a term near the cut-off at 30,000 could be misplaced by a few places, but a term with 500 occurrences cannot appear. The heap exists because a sketch cannot enumerate its keys; the pattern is covered further in the top-k and heavy hitters guide.

Network cost is 40 times 80 KiB plus the candidate lists, about 3.3 MB per window, and it does not grow with the number of distinct terms. That is the reason to use a sketch rather than shipping exact counts.

Testing the error bound you actually get

Unit tests for a sketch should not check exact values. They should check the guarantee: no estimate below the truth, and the fraction of keys with error above eps * N no greater than delta, with some slack for sampling. Drive it with a skewed stream, because uniform streams hide collision behavior.

import random
from collections import Counter

def check_bound(eps=0.001, delta=0.01, n=1_000_000, keys=200_000, seed=7):
    rng = random.Random(seed)
    weights = [1 / (r + 1) ** 1.1 for r in range(keys)]      # Zipf-like
    stream = rng.choices(range(keys), weights=weights, k=n)
    exact, cms = Counter(stream), CountMin(eps, delta, seed=seed)
    for k in stream:
        cms.add(str(k).encode())
    band = eps * cms.n
    over = under = 0
    for k, true in exact.items():
        est = cms.estimate(str(k).encode())
        under += est < true
        over += (est - true) > band
    assert under == 0, "a Count-Min sketch must never underestimate"
    assert over / len(exact) <= 2 * delta, f"{over} keys outside the band"
    return over / len(exact)

Run it for several seeds and both update modes, and keep the observed failure rate as a metric. In practice the observed rate is far below delta, because the bound is loose. A sudden rise usually means the hash has lost independence, for instance after a change to the index derivation or a key encoding that makes many keys share a prefix.

Operating a sketch

If you would rather not own the code, RedisBloom provides a Count-Min type: CMS.INITBYDIM or CMS.INITBYPROB to create one, CMS.INCRBY to add, CMS.QUERY to estimate and CMS.MERGE to combine sketches of equal dimensions. The same header discipline applies: create all sketches that will ever be merged from one configuration.

Whoever owns it, monitor three numbers per sketch: N, the implied error band eps * N, and the fill ratio, the fraction of non-zero counters. A band that grows past the smallest count you act on means the window is too long. A fill ratio near 1 means every column carries pollution and estimates for small keys are meaningless.

Failure modes

• Unbounded windows. N only grows, so the error band grows with it. Rotate sketches per window, or keep a ring of per-interval sketches and sum the recent ones.
• Silent format drift. A service upgrade changes the hash library or the key encoding; merged results become noise without any error. The header check and a canary key with a known count catch it.
• Counter overflow. Wrapped 32-bit counters turn the largest key into the smallest. Use 64 bits or saturate.
• Reading small counts. Estimates below eps * N are indistinguishable from collision noise. Pair the sketch with a threshold, or with a Bloom filter if what you really need is membership.
• Using it for distinct counts or quantiles. Count-Min answers frequency. For cardinality use HyperLogLog; for latency percentiles use t-digest.

What to do next

1. Write down the smallest count you will act on and the window length; compute eps and the width from them.
2. Pick a stable seeded hash, document the key canonicalization, and derive row indices from one hash with an odd stride.
3. Implement or configure the sketch with a header carrying version, counter width, dimensions, seed and mode; refuse merges on mismatch.
4. Use one sketch per thread or partition and merge; avoid shared conservative update.
5. Add the bound test above to CI and track the observed error rate across releases.
6. Export N, the error band and the fill ratio as metrics, and rotate the sketch before the band crosses your action threshold.