Probabilistic Data Structures: Bloom Filters, HyperLogLog, Count-Min Sketch and Cuckoo Filters (2026)

Counting the unique visitors of a large site exactly needs a set that holds every visitor ID. At a billion IDs of 16 bytes each, that is 16 GB for one metric on one day, before you slice it by country, device and campaign. Yet the same answer, accurate to within a percent, fits in about 12 KB. That gap of six orders of magnitude is not a trick. It is the entire point of probabilistic data structures: they trade a small, mathematically bounded error for memory that stays flat while the data grows without limit.

Databases already depend on them. Every LSM-tree read path asks a Bloom filter before touching disk, analytics engines answer distinct-count queries from HyperLogLog sketches, and stream processors track heavy hitters in count-min sketches. Used well, they cut I/O and memory by orders of magnitude. Used carelessly, they silently return wrong numbers.

What this covers: why approximate answers are worth having, the exact Bloom filter math with a bits-per-element table, blocked, counting, cuckoo, xor and ribbon variants, HyperLogLog internals, count-min sketch error bounds, quantile sketches, mergeability across nodes, runnable Python with measured error, and the failure modes that bite in production.

Context and Background

Exact data structures have a hard lower bound. A set of n distinct keys drawn from a large universe needs on the order of n times the key size in bits, because you must be able to tell every possible set apart from every other. If you relax the contract, that bound disappears. A structure that is allowed to be wrong occasionally, in a direction you control, can be far smaller than any exact one.

The relaxation takes three shapes. A membership filter answers “have I seen this key?” and may say yes for a key it never saw (a false positive) but never says no for a key it did see. A cardinality estimator answers “how many distinct keys?” within a relative error. A frequency sketch answers “how often did this key occur?” and may over-count but never under-count. Quantile sketches answer “what is the p99 latency?” with bounded rank or relative error. Each is a one-sided or bounded-error contract, and that discipline is what makes the guarantees provable.

The lineage is long. Burton Bloom published the filter that carries his name in 1970. Flajolet and Martin introduced probabilistic counting in the 1980s, which led to LogLog and then HyperLogLog by Flajolet, Fusy, Gandouet and Meunier in 2007. Cormode and Muthukrishnan published the count-min sketch in 2005. Fan, Andersen, Kaminsky and Mitzenmacher published the cuckoo filter at CoNEXT 2014, motivated by a gap that Bloom filters could not close: deletion. Google’s engineers then published “HyperLogLog in Practice” (Heule, Nunkesser and Hall), the HLL++ paper that most production implementations follow.

Two properties matter beyond size. First, these structures are mergeable: you can build one per shard or per hour and combine them with a cheap, associative operation, which is exactly what a distributed system needs. Second, their insert cost is constant and independent of how much data came before. That combination is why they appear throughout the systems we cover on this site, from the read path in LSM-tree storage engines like RocksDB to approximate aggregation functions in columnar engines such as ClickHouse.

The cost is real and worth stating up front. You cannot enumerate the keys in these structures, you cannot get the error to zero without growing the structure, and the guarantees assume a hash function that behaves like a random one. When the data is adversarial or the hash is weak, the guarantees degrade. We return to this in the gotchas section.

Choosing a Structure by the Question You Ask

The fastest way to pick a probabilistic data structure is to name the question, then match it to the structure whose error contract fits the question. Membership questions use Bloom, cuckoo, xor or ribbon filters. Distinct-count questions use HyperLogLog. Frequency and heavy-hitter questions use count-min sketch. Percentile questions use t-digest or DDSketch.

Figure 1: Decision map for probabilistic data structures. Start from the question, then check the error direction, deletion support and mergeability before choosing.

The map above is a first filter only. Within each family, the sub-choice depends on three properties: which direction the error runs, whether you need to delete, and whether you can merge. The table below summarises the four workhorses plus the quantile sketches.

Structure	Question answered	Error contract	Deletes	Mergeable	Typical size
Bloom filter	Is key in set?	False positives only, no false negatives	No (counting variant yes)	Yes, bitwise OR for equal size	about 9.6 bits/key at 1%
Cuckoo filter	Is key in set?	False positives only	Yes	Not directly	about 12 to 13 bits/key at 0.2%
HyperLogLog	How many distinct?	Relative error 1.04 over square root of m	No	Yes, register-wise max	12 KB in Redis
Count-min sketch	How often did key occur?	Over-estimate by at most epsilon times N, with probability 1 minus delta	No (negative updates possible in limited form)	Yes, cell-wise add	w times d counters
t-digest, DDSketch	What is quantile q?	Rank error or relative value error	No	Yes	hundreds of centroids or buckets

Notice that every row is mergeable in some form except the cuckoo filter, and that is a genuine limitation: combining two cuckoo filters is not a simple bit operation because fingerprints live in positions determined by a partial-key hash and bucket occupancy. Keep that in mind when designing a distributed pipeline.

A note on the error direction, because it decides correctness of the surrounding application. A Bloom filter that says “no” is always right, so it is safe as a guard that skips expensive work: “definitely not on disk, skip the read.” A Bloom filter that says “yes” is only a hint, so the application must verify. If you reverse the guard, using the “yes” to skip verification, you have built a bug. The same logic applies to a count-min sketch: because it only over-counts, an alert threshold set on its estimate can raise false alarms but will never miss a genuinely hot key.

Bloom Filters: The Math, the Sizing Table and the Variants

A Bloom filter is an array of m bits and k hash functions. Inserting a key sets k bits; querying checks that all k bits are set. With n keys inserted, the false positive rate is approximately p = (1 – e^(-kn/m))^k, which is minimised at k = (m/n) ln 2, giving m/n = -ln(p) / (ln 2)^2 bits per element, about 1.44 log2(1/p).

Where the formula comes from

After inserting n keys with k hashes each, there have been kn bit-setting events. The probability that a particular bit is still zero is (1 – 1/m)^(kn), which is close to e^(-kn/m) for large m. A query for an absent key is a false positive only if all k probed bits are set, each independently set with probability 1 – e^(-kn/m), hence the formula. Differentiating with respect to k shows the minimum sits where exactly half the bits are set, which is why a well-tuned filter is a 50 percent dense bit array. If a filter is far denser than that, it is over-full.

Solving for m gives the sizing rule. The table below uses the optimal k and rounds to the nearest integer. The measured column comes from the Python implementation later in this post, with n = 100,000 keys and 200,000 queries for absent keys. The three measured values are real runs on synthetic data, not published benchmarks; the other rows are computed from the formula only.

Target p	Bits per element (m/n)	Optimal k	Space for 100M keys	Measured p (n = 100k)
10%	4.79	3	about 60 MB	0.0994
1%	9.59	7	about 120 MB	0.0101
0.1%	14.38	10	about 180 MB	0.0011
0.01%	19.17	13	about 240 MB	not measured
0.0001%	28.76	20	about 360 MB	not measured

Two lessons hide in this table. The first is the cost curve: every tenfold reduction in the false positive rate costs about 4.8 additional bits per key, a constant increment, so low error rates are cheap in absolute terms. Going from 1 percent to 0.001 percent costs about 10 extra bits per key, not 1,000 times more memory. The second is that hash count grows with accuracy. At p = 0.1 percent you perform 10 hash-derived probes per lookup, so CPU and cache misses, not memory, become the constraint, and this is why production filters are redesigned for cache behaviour.

Double hashing and the cost of k hashes

Computing ten independent hashes per key would be wasteful. Kirsch and Mitzenmacher showed that two hash values h1 and h2 are enough: use g_i(x) = h1(x) + i * h2(x) mod m for i from 0 to k-1, with no asymptotic loss in the false positive rate. The Python code below takes one 64-bit hash, splits it into two 32-bit halves and forces h2 to be odd. Production libraries do the same with faster non-cryptographic hashes such as xxHash or wyhash.

Blocked Bloom filters

A standard filter touches k random positions across the whole array, so a lookup of a filter bigger than the CPU cache costs up to k cache misses. A blocked Bloom filter first hashes the key to one block, typically 64 bytes, the size of a cache line, then sets and tests all k bits inside that block. One cache miss per lookup replaces k. The price is a slightly higher false positive rate for the same memory, because load across blocks is uneven: some blocks receive more keys than average and saturate earlier. The RocksDB documentation on Bloom filters describes exactly this trade: its full filter format limits each key’s probe bits to one cache line, giving a typical single cache miss per filter lookup, and its newer implementation (format_version 5, RocksDB 6.6 and later) reports a false positive rate below 0.1 percent at 16 bits per key and uses a 64-bit hash so very large filters stay accurate.

Counting Bloom filters

A plain Bloom filter cannot delete, because clearing a bit may erase evidence of other keys that share it. A counting Bloom filter replaces each bit with a small counter, usually 4 bits, incrementing on insert and decrementing on delete. It supports deletion at a cost of four times the memory, and a counter overflow (a 4-bit counter saturates at 15) can make the structure permanently wrong. Deleting a key that was never inserted is the more common and more dangerous error: it decrements counters belonging to other keys and creates false negatives, the one thing a Bloom filter must never do.

Cuckoo filters

A cuckoo filter stores a short fingerprint of each key in a hash table using cuckoo hashing. Each fingerprint can live in one of two buckets, and the alternate bucket is computable from the current bucket and the fingerprint alone: i2 = i1 XOR hash(fingerprint). This “partial-key cuckoo hashing” lets an insert evict a resident fingerprint to its alternate bucket without having the original key, which is what makes deletion and relocation possible.

The false positive rate is bounded by about 2b / 2^f, where b is the bucket size and f the fingerprint length in bits. With b = 4 and f = 12, that is 8 / 4096, about 0.2 percent. The authors report that buckets of four entries support load factors around 95 percent, so the space per item is about f / 0.95, roughly 12.6 bits here. A Bloom filter at 0.2 percent needs 12.9 bits (computed from the formula above), so the two are about equal at this rate. The cuckoo filter’s advantage grows when the target rate is low or when you need deletion. Its disadvantages are that insertion can fail when the table is nearly full (requiring a resize and rebuild), and that you must never delete a key you did not insert, or you may remove another key’s matching fingerprint.

Do not read the cuckoo filter as a strict upgrade. At a loose target such as 3 to 10 percent false positives, a Bloom filter with 3 to 5 bits per key is smaller. The cuckoo filter wins in the middle ground of low false positive rates with deletion.

Xor and ribbon filters for static sets

When the key set is built once and never changes, you can do better than a Bloom filter. Xor filters (Graf and Lemire) and ribbon filters (Dillinger and Walzer) are static: they are constructed from the full key list by solving a system of linear equations over GF(2), and the construction fails or retries if the equations are inconsistent. A lookup XORs a few table entries and compares to a fingerprint. Space approaches the information-theoretic bound of log2(1/p) bits per key plus a small overhead, versus the 1.44 factor of a Bloom filter. RocksDB ships a ribbon filter option, and its documentation states that ribbon saves about 30 percent of Bloom filter space at the cost of about 3 to 4 times as much CPU on filters, most of it in background filter construction. At a 1 percent false positive rate it uses roughly 7 bits per key against about 10 for Bloom.

That trade suits an LSM tree perfectly. SSTables are immutable, filters are built at flush or compaction time in background threads, and the memory saving applies to the most numerous, longest-lived data in the system. The same trade would be a poor choice for a filter rebuilt every few seconds on a hot path.

Where Bloom Filters Earn Their Keep: The LSM Read Path

The canonical use is the point lookup in a log-structured merge tree. A key may live in the memtable or in any of dozens of immutable SSTables across levels. Without filters, a read for an absent key checks every candidate file, paying a disk or block-cache access for each. With a per-SSTable Bloom filter held in memory, the engine asks each filter first and opens only the files that answer “maybe”.

Figure 2: A point read walks the memtable, then each SSTable’s in-memory Bloom filter. A “no” skips the file entirely, a “maybe” triggers a real block read that may turn out to be a false positive.

The arithmetic shows why this matters. Suppose a read for a missing key would otherwise probe 7 SSTables (an illustrative figure for a leveled tree with a few levels plus level-0 overlap). At 1 percent per filter, the expected number of wasted file reads is 7 x 0.01 = 0.07, so 93 percent of such reads cost zero disk I/O. At 10 percent, the expected waste is 0.7 reads, still a tenfold reduction from 7. The right target is whatever makes the false positive cost small relative to the memory spent, and our companion article on LSM-tree compaction and write amplification explains why the number of candidate files is itself a tuning variable.

Two practical points follow. First, filters help negative lookups far more than positive ones: if the key exists, you must read the block anyway, and the filter only saved you the other files. Workloads dominated by hits see smaller gains, and RocksDB documents options to skip the filter on the last level for this reason. Second, Apache Cassandra exposes the trade directly as a per-table bloom_filter_fp_chance setting; check your version’s documentation for the default, since it has differed by compaction strategy. HBase and many other LSM stores follow the same design.

Bloom filters also appear far from databases. Content delivery networks use them to avoid caching one-hit wonders, so an object is cached only the second time it is requested. Web crawlers use them to remember visited URLs. Distributed joins ship a filter of the smaller table’s keys to the large table’s nodes so non-matching rows are dropped before the shuffle, and the same idea underlies the sideways information passing in the sharded query layers discussed in our sharding guide.

Runnable Python: Bloom Filter, HyperLogLog and Count-Min Sketch

The best way to trust these bounds is to measure them. The code below is dependency-free Python 3. It uses BLAKE2b with an 8-byte digest as a convenient, well-mixed 64-bit hash; a production system would use a faster non-cryptographic hash. Every number reported later in this post came from running this exact code with a fixed seed on synthetic keys.

import hashlib, math, struct

def h64(data: bytes, seed: int = 0) -> int:
    d = hashlib.blake2b(data, digest_size=8, key=seed.to_bytes(8, "little")).digest()
    return struct.unpack("<Q", d)[0]

class Bloom:
    def __init__(self, n, p):
        self.m = math.ceil(-n * math.log(p) / (math.log(2) ** 2))
        self.k = max(1, round(self.m / n * math.log(2)))
        self.bits = bytearray((self.m + 7) // 8)

    def _idx(self, x):
        h = h64(x)
        h1, h2 = h & 0xFFFFFFFF, (h >> 32) | 1      # Kirsch-Mitzenmacher
        for i in range(self.k):
            yield (h1 + i * h2) % self.m

    def add(self, x):
        for i in self._idx(x):
            self.bits[i >> 3] |= 1 << (i & 7)

    def __contains__(self, x):
        return all(self.bits[i >> 3] >> (i & 7) & 1 for i in self._idx(x))

The HyperLogLog below uses p = 12 index bits, so m = 4,096 registers. It applies the raw harmonic-mean estimate with the standard alpha constant and falls back to linear counting when the estimate is small and empty registers exist.

class HLL:
    def __init__(self, p=12):
        self.p, self.m = p, 1 << p
        self.reg = [0] * self.m

    def add(self, x):
        h = h64(x)
        idx = h >> (64 - self.p)                    # top p bits pick a register
        w = (h << self.p) & (2**64 - 1)             # remaining bits
        rho = (64 - self.p + 1) if w == 0 else (64 - w.bit_length() + 1)
        if rho > self.reg[idx]:
            self.reg[idx] = rho

    def count(self):
        m = self.m
        alpha = 0.7213 / (1 + 1.079 / m)
        e = alpha * m * m / sum(2.0 ** -r for r in self.reg)
        zeros = self.reg.count(0)
        if e <= 2.5 * m and zeros:                  # small-range correction
            return m * math.log(m / zeros)
        return e

    def merge(self, other):                         # union of the two sets
        self.reg = [max(a, b) for a, b in zip(self.reg, other.reg)]

class CMS:
    def __init__(self, eps, delta):
        self.w = math.ceil(math.e / eps)
        self.d = math.ceil(math.log(1 / delta))
        self.t = [[0] * self.w for _ in range(self.d)]

    def add(self, x, c=1):
        for r in range(self.d):
            self.t[r][h64(x, r + 1) % self.w] += c

    def est(self, x):
        return min(self.t[r][h64(x, r + 1) % self.w] for r in range(self.d))

With 100,000 inserted keys and 200,000 absent probes, the Bloom filter results are the three measured rows in the sizing table: 0.0994, 0.0101 and 0.0011 against targets of 0.1, 0.01 and 0.001. The theory matches to within sampling noise, which is the reassurance you want before trusting any filter in a hot path. Run your own check whenever you change the hash function.

HyperLogLog: Counting Distinct Elements in Kilobytes

HyperLogLog hashes every element to a uniform 64-bit value, uses the first p bits to pick one of m = 2^p registers, and records in that register the longest run of leading zeros seen in the remaining bits. A harmonic mean over the registers estimates the distinct count with relative standard error of about 1.04 / sqrt(m). Redis uses 16,384 registers, giving 0.81 percent in at most 12 KB.

Figure 3: HyperLogLog hashes each element once, routes it to one of m registers, keeps the maximum rank per register and merges sketches by taking register-wise maxima.

The intuition behind leading zeros

If you flip a fair coin repeatedly, the longest run of heads you see grows like log2 of the number of flips. A hash value is a sequence of random bits, so the longest run of leading zeros among many hashes is a crude, high-variance estimate of log2(n). One register alone has a standard deviation of more than one whole power of two, which is useless. HyperLogLog tames the variance by splitting the stream across m registers (stochastic averaging) and averaging the per-register estimates. Averaging m roughly independent estimates cuts the error by the square root of m, which is the origin of 1.04 / sqrt(m).

The harmonic mean matters. A few registers that happen to see an extreme value would drag an arithmetic mean far upward; the harmonic mean, dominated by small values, resists those outliers. The constant alpha corrects the remaining bias; for m of 128 or more it is approximately 0.7213 / (1 + 1.079 / m).

Sizing: precision versus memory

Doubling the registers adds one index bit and reduces error by a factor of the square root of two. The table gives the theoretical standard error, and the dense size at 6 bits per register, the packing used by HLL++ and Redis.

Precision p	Registers m	Std error 1.04/sqrt(m)	Dense size at 6 bits/register
10	1,024	3.25%	768 B
12	4,096	1.63%	3 KB
14	16,384	0.81%	12 KB
16	65,536	0.41%	48 KB

The Redis HyperLogLog documentation confirms the row for p = 14: up to 12 KB per key, a standard error of 0.81 percent, a maximum cardinality of 2^64, and PFADD and single-key PFCOUNT at O(1) with PFMERGE linear in the number of sketches merged. Six bits suffice because a rank never exceeds 64 – p + 1.

Measured error from the Python implementation

Running the HLL class above with p = 12 (theoretical standard error 1.63 percent), five trials per cardinality on synthetic distinct keys, produced these signed percentage errors. They are measurements from this code, not vendor benchmarks, and five trials is a small sample, so read the root-mean-square column loosely.

True distinct count	Signed errors over 5 trials (%)	RMS error (%)
1,000	-0.80, -0.29, 0.35, 2.40, -0.29	1.16
10,000	-0.74, -0.40, 4.74, 2.90, 4.30	3.16
100,000	0.33, 0.23, -1.25, 0.56, 0.51	0.68
1,000,000	-0.68, 0.48, -2.05, -1.17, 2.05	1.45

The 10,000 row is the instructive one. It sits right at the threshold of 2.5 m = 10,240 where the algorithm switches between linear counting and the raw estimate, and the raw estimator is biased there. Heule, Nunkesser and Hall measured exactly this bias and corrected it in HLL++ with empirical bias tables for small and mid-range cardinalities. They also moved from a 32-bit to a 64-bit hash, which removes the large-range correction and lets the structure count into the billions without collisions in the hash space, and they added a sparse representation that stores only the non-empty registers while cardinality is low. My simple class implements none of those three improvements, which is why you should use a library implementation in production and the toy only to understand the mechanism.

Union is free; intersection is not

Two sketches built with the same precision and the same hash function merge by taking the register-wise maximum. The result is identical to the sketch you would have built from the union of the two streams. In the test, I added IDs 0 to 59,999 to one sketch and 40,000 to 99,999 to another, with an overlap of 20,000, then merged them: the true union is 100,000 and the estimate was 99,318, an error of 0.68 percent. Overlapping elements are counted once automatically, which is what makes daily sketches roll up cleanly into weekly and monthly ones.

Intersection is the weak spot. You can estimate it through inclusion-exclusion, |A intersect B| = |A| + |B| – |A union B|, but the error of each term is relative to its own size. If the two sets are large and the intersection is small, the result is dominated by noise and can even go negative. For cohort overlap questions with small intersections, use a different sketch family (theta sketches from the Apache DataSketches library support set operations with better error behaviour) or compute the exact answer on a sample.

Where HyperLogLog is exposed

Redis offers PFADD, PFCOUNT and PFMERGE. Analytics engines expose it as an aggregate function: ClickHouse provides uniq, uniqCombined and uniqHLL12, Trino and Presto provide approx_distinct, and Google BigQuery provides HLL_COUNT functions that store and merge sketches. Function names and default error settings do change between releases, so verify the exact accuracy parameters in your engine’s documentation before you quote an error figure to a stakeholder. The pattern that scales is to store the serialized sketch per time bucket and dimension combination, then merge at query time, rather than storing raw IDs.

Count-Min Sketch: Frequencies and Heavy Hitters

A count-min sketch is a grid of d rows and w columns of counters. Each row has its own hash function. To count an event, increment one counter per row; to estimate a key’s frequency, take the minimum across its d counters. The estimate never falls below the true count, and exceeds it by at most epsilon x N with probability at least 1 – delta, where w = ceil(e / epsilon) and d = ceil(ln(1 / delta)).

Why the minimum works

Every counter that a key hashes to contains its true count plus the counts of unrelated keys that collided into the same cell. Collisions only ever add, so every counter is an over-estimate. The minimum across independent rows is the least contaminated of them. The expected contamination in one row is N / w, and by Markov’s inequality the probability that it exceeds epsilon x N is at most 1 / e when w = e / epsilon. Requiring all d rows to fail simultaneously gives (1 / e)^d, which is at most delta when d = ln(1 / delta).

The sizing is pleasantly modest. For epsilon = 0.001 and delta = 0.01 you need w = 2,719 and d = 5, about 13,600 counters, roughly 54 KB with 4-byte counters, whether you process a million events or a trillion. What changes with volume is the absolute error bound epsilon x N: at N = 10^9 events, 0.1 percent is a million, so the sketch can only reliably separate keys whose frequencies exceed that.

Measured behaviour on skewed data

I ran the CMS class on 200,000 events drawn from a heavy-tailed distribution (Pareto, shape 0.6) with 3,487 distinct keys, using delta = 0.01. These are measurements on one synthetic stream with one seed.

Epsilon	Width x depth	Counters	Bound epsilon x N	Max over-count observed	Mean over-count	Hottest key true vs estimated
0.01	272 x 5	1,360	2,000	167	22.7	67,585 vs 67,612
0.002	1,360 x 5	6,800	400	25	1.3	67,585 vs 67,586

Two observations stand out. The guarantee holds with a large margin, because the bound is worst-case and real data is rarely adversarial. And the error is nearly irrelevant for heavy hitters but severe for rare keys: the median key in this stream occurred once, and at epsilon = 0.01 its median over-count was 19, a 1,900 percent relative error. A count-min sketch tells you reliably which keys are big. It cannot tell you whether a small key occurred 1 or 20 times. Pair it with a small min-heap of the current top-k candidates to build a streaming heavy-hitter tracker.

Conservative update and its limits

Conservative update increments only the counters that currently hold the minimum value for the key, rather than all d of them. It keeps the never-underestimate property and usually reduces over-count noticeably, at the price of breaking linearity: two conservative-update sketches can no longer be merged by plain addition with the same guarantee, and deletion is impossible. Choose it for single-node heavy-hitter detection, and plain updates when you need to merge across nodes.

For skewed streams, a count-sketch (Charikar, Chen and Farach-Colton) uses signed updates so errors cancel in expectation and give an unbiased estimate, at the cost of the one-sided guarantee. If your application needs unbiased frequency estimates or supports negative updates such as deletions in a turnstile stream, that is the structure to consider.

Quantile Sketches: t-digest and DDSketch

Latency percentiles are the metric most dashboards chart and the one that cannot be averaged: the mean of per-host p99 values is not the fleet p99. A quantile sketch summarises a distribution in a few hundred numbers and merges across hosts.

The t-digest (Dunning and Ertl) keeps a sorted set of centroids, each a mean and a weight, and allows centroids near the tails to be small and those near the median to be large, so extreme quantiles like p99.9 stay accurate. Its error is bounded in rank space and is best at the tails, but the guarantee is empirical rather than a strict worst-case bound.

DDSketch (Masson, Rim and Lee, from Datadog, VLDB 2019) takes a different route: it buckets values on a logarithmic scale so that every reported quantile is within a chosen relative error of the true value, for example 1 percent. A 1 percent relative guarantee means a true p99 of 800 ms is reported between 792 and 808 ms. That is the kind of guarantee operations teams actually reason about. DDSketch merges by adding bucket counts, which is exact and associative. Choose t-digest for accuracy at extreme tails with rank-space semantics, and DDSketch when you need a provable relative-error bound and trivially simple merging.

Mergeability: Why Sketches Fit Distributed Systems

Mergeability is the property that makes probabilistic data structures a distributed-systems tool and not just a memory trick. If sketch(A) merged with sketch(B) equals sketch(A union B), you can aggregate in a tree: each shard summarises its own data, a mid-tier merges summaries, and the coordinator merges those. Network traffic is the size of a sketch per shard, not the size of the data.

Figure 4: Each shard keeps local sketches. Merging uses a cheap associative operation per type, bitwise OR, register-wise maximum or cell-wise addition, and the merged result answers global queries.

The merge operation differs per structure, and the preconditions are strict. All sketches being merged must share the same parameters and the same hash function with the same seed.

Structure	Merge operation	Precondition	What breaks if violated
Bloom filter	Bitwise OR	Same m, k and hash	Different sizes cannot be combined; a mismatched hash yields garbage membership
HyperLogLog	Register-wise max	Same p and hash	Different precision needs down-conversion to the lower p; different hash gives wrong union
Count-min sketch	Cell-wise add	Same w, d and per-row seeds	Counts land in unrelated cells and estimates become meaningless
DDSketch	Add bucket counts	Same relative accuracy and mapping	Bucket boundaries differ, error bound is lost
Cuckoo filter	No simple merge	Rebuild from fingerprints, subject to capacity	Partial-key positions make direct union unsafe near capacity

Merge is also what lets you design with time. A common pattern keeps one HyperLogLog per hour per dimension tuple, then answers “unique users last 7 days” by merging 168 sketches, which costs a few hundred kilobytes of reads and a trivial computation. The same hourly Bloom filters, ORed, answer “was this key seen in the window”, although a window that slides makes an OR-of-buckets filter the right choice and a single always-growing filter the wrong one, because a plain Bloom filter can never forget.

A related pattern appears in rate limiting. Per-key counters at the edge are a frequency problem, and approximate counting is one of the tools used in large limiter designs; the trade-offs between exact counters in Redis and approximate or local counters are discussed in our guide to distributed rate limiting with token bucket, GCRA, Redis and Envoy. The lesson transfers: when an over-count only makes you slightly stricter, a count-min style structure is an acceptable limiter state, and when an over-count would wrongly block a paying customer, it is not.

Sharding and filter placement

One more design question is where filters live relative to data. With hash-based placement, as in consistent hashing and rendezvous hashing, each shard owns a disjoint key range, so a per-shard filter is naturally sized for that shard’s n and never needs merging for membership checks. A resharding event moves keys between shards, and a Bloom filter cannot remove the departing keys. The practical answer is to rebuild the filter from the shard’s new key set during migration, not to try to patch it. Count-min and HyperLogLog sketches, in contrast, are usually keyed by time or dimension and survive resharding because they merge.

Trade-offs, Gotchas, and What Goes Wrong

The mathematics above is exact under assumptions that production systems routinely violate. Know which assumption each failure breaks.

Saturation. A Bloom filter sized for n keys that receives 3n keys does not degrade gracefully. Using the formula with m/n fixed at 9.59 bits for the original n, the false positive rate rises from 1 percent to roughly 43 percent at 3n with k = 7. Once more than half the bits are set, every additional key makes the filter worse quickly. Track the fill ratio (fraction of set bits) as a metric and alert at about 50 percent. For unbounded streams, use a scalable Bloom filter (a chain of filters with tightening error rates) or rotate filters by time window.

Weak or correlated hashes. All the bounds assume hashes behave like independent uniform random functions. Using a poor hash such as a simple string hash on structured IDs clusters bits, raises collisions and breaks HyperLogLog most visibly, since leading-zero counts depend on the high-quality randomness of every bit. If the same hash function feeds both the shard router and the filter, correlated bits can skew both. Use a well-mixed 64-bit hash, seed each structure independently and test distribution on your real key shapes.

Adversarial inputs. If attackers choose keys, they can craft items that collide in a Bloom filter or count-min sketch to force false positives or inflate counts. Published attacks on Bloom-filter-based systems exist in the research literature. The defence is a keyed hash (SipHash or HMAC-based) with a secret seed, so collisions cannot be precomputed. For anything exposed to untrusted input, such as a cache admission filter or a spam list, treat an unkeyed hash as a vulnerability.

Error compounding. Chaining approximate steps multiplies their error. A false positive rate of 1 percent in each of five sequential filters is fine; a Bloom-filtered join feeding an HLL distinct count feeding a ratio of two such counts has an error you must propagate explicitly. The ratio of two HyperLogLog estimates carries both relative errors, so conversion rates computed this way from 1 percent estimates have roughly 1.4 percent standard error before any bias.

Deletion and forgetting. Plain Bloom filters, HLL and count-min sketches cannot remove an element. Right-to-erasure obligations under privacy regimes sit awkwardly with structures that cannot forget. Mitigate by bucketing sketches by time and dropping whole buckets, or by building sketches from pseudonymous identifiers that you can rotate.

Hidden exactness assumptions in downstream code. The most common production bug is not mathematical. It is a function that returns “uniques” from a sketch, and a downstream dashboard that sums it across groups. Distinct counts do not add: sum of per-country uniques overstates global uniques for any user seen in two countries. Always merge sketches, never add estimates.

Cuckoo filter insertion failure. When the load factor nears the limit, inserts trigger long eviction chains and then fail. Reserve headroom (a target below 90 percent load), handle the failure path by growing and rebuilding, and keep the key source available to rebuild.

Practical Recommendations

Start from the question and the error direction, not from the structure you already know. If a wrong “maybe” costs only a wasted read, a Bloom filter is correct. If a wrong “yes” is expensive and a wrong “no” is tolerable, you need a different design altogether, because Bloom filters offer the opposite guarantee.

Size from the formulas and verify by measurement. Pick a target error from the cost of a false positive: if a wasted disk read costs 100 microseconds and a filter bit costs almost nothing, 10 bits per key at 1 percent is the usual sweet spot, with ribbon filters worth considering for immutable files when memory dominates. For distinct counts, 12 KB at 0.81 percent is the industry default for good reason, and precision 10 to 12 is adequate for coarse dashboards with huge numbers of dimension tuples.

Prefer library implementations for production, and use the code in this post to understand and to test. Apache DataSketches, the HLL++ implementations in your database engine and the filter policies in RocksDB have handled the bias correction, serialisation compatibility and speed work that a toy does not.

[ ] Write down the question and which error direction the application can tolerate
[ ] Compute size from the formula; record target false positive rate or relative error in the design doc
[ ] Use a seeded 64-bit hash, keyed (SipHash or similar) if inputs are untrusted
[ ] Standardise parameters (m, k, p, w, d, seed) across all shards so sketches merge
[ ] Expose fill ratio, estimated error and saturation as metrics with alerts at 50 percent fill
[ ] Merge sketches rather than adding estimates; never sum distinct counts
[ ] Bucket sketches by time so data can expire and sliding windows are possible
[ ] Load-test the false positive path: confirm the system is correct when the filter says “maybe”
[ ] Validate against an exact computation on a sample before trusting a number in a report

Frequently Asked Questions

What are probabilistic data structures used for?

They answer membership, distinct-count, frequency and percentile questions about huge or streaming datasets in small, constant memory. Typical uses include Bloom filters that skip disk reads in LSM-tree databases, HyperLogLog for unique-visitor counts, count-min sketches for heavy hitters and trending items, and t-digest or DDSketch for latency percentiles. They suit workloads where a bounded error is acceptable and exact answers would need memory proportional to the data.

How accurate is a Bloom filter?

Accuracy is a design choice. With optimal hashing, the false positive rate is about 0.6185 raised to the power of bits per element: roughly 1 percent at 9.6 bits per key, 0.1 percent at 14.4 bits and 0.01 percent at 19.2 bits. It never produces false negatives as long as the filter is not corrupted and no deletions are attempted. The rate holds only while you stay at or below the number of keys the filter was sized for.

What is the difference between a Bloom filter and a cuckoo filter?

Both give “definitely not” or “maybe” answers. A cuckoo filter stores short fingerprints in a cuckoo hash table, so it supports deletion and can be smaller at low false positive rates, but inserts can fail near full capacity and filters do not merge simply. A Bloom filter has simple bitwise-OR merging and never fails an insert, but cannot delete without moving to a larger counting variant.

How does HyperLogLog estimate cardinality in so little memory?

It hashes each element and tracks only the longest run of leading zeros per register, not the elements themselves. A rarer long run implies more distinct elements were seen. Splitting the stream across thousands of registers and combining them with a harmonic mean reduces variance. The relative standard error is about 1.04 divided by the square root of the register count, so 16,384 registers give roughly 0.81 percent.

Can a count-min sketch under-count?

No. Collisions only add to a counter, so every cell holds at least the true count of every key mapped to it, and the minimum across rows is therefore at least the true count. The estimate can exceed the truth by up to epsilon times the total stream length N, with probability at least 1 minus delta. Rare keys suffer a large relative error; heavy hitters are estimated very accurately.

Should I use a ribbon or xor filter instead of a Bloom filter?

Only for static key sets built once, such as immutable SSTables. They save roughly a quarter to a third of the space at equal false positive rate, but need the full key list at build time and more CPU to construct. RocksDB documents about 30 percent space savings from ribbon filters with 3 to 4 times the filter CPU. For sets that change continuously, stay with Bloom or cuckoo filters.