Merging Probabilistic Sketches Across Shards

Every structure in this cluster is a function of a set or a multiset, and the useful question in a distributed system is whether the function can be computed from partial results. A Bloom filter’s answer is a bitwise OR of the bit arrays; a HyperLogLog’s is a register-wise maximum; a Count-Min sketch’s is a cell-wise sum. Those three operations are not arbitrary — each is the operation under which the structure’s state is a homomorphism from the underlying set or multiset — and the structures that lack such an operation cannot be merged at all without giving up their guarantee.

Union as bitwise OR

Two Bloom filters built with the same $m$, the same $k$, and the same hash functions merge by OR-ing their bit arrays. The result is exactly the filter that would have been built from the union of the two key sets. No error is added beyond what the combined key count implies: the merged filter has the false-positive rate of a filter sized for $m$ holding $n_1 + n_2$ distinct keys, which may be far worse than either input’s rate if the inputs were each sized for their own share.

That last point is the sizing problem of distributed filters, and it has no local solution. If ten shards each hold a million keys and each builds a filter at ten bits per key, every shard’s filter is 1.25 MB with a 0.8% error, and the merged filter is also 1.25 MB but holds ten million keys. Its error is the formula of the single filter evaluated at $m/n = 1$ rather than $m/n = 10$: with $kn/m = 7$ the rate becomes $\left(1 - e^{-7}\right)^{7} \approx 99.4%$, so the merged filter accepts nearly every absent key and is useless. Correct distributed sizing requires every shard to allocate for the global key count, which costs ten times the memory per shard, or to accept a coarser error target.

The merge is also one-way. OR cannot be undone, so a shard that leaves the cluster cannot be removed from the merged filter. Recomputing from the remaining shards is the only repair, and that requires retaining their individual filters.

Counting Bloom filters merge by adding counters, with the same parameter requirement and the same sizing consequence. The addition must saturate at the counter maximum rather than wrap, which means the merged result can under-count a position and produce false negatives for keys that all shards agree are present. A four-bit counter that saturates during a merge has silently discarded the presence of a key. The counting filter therefore needs its counter width chosen for the merged load, not the per-shard load.

Maximum as the merge for cardinality

HyperLogLog merges by taking the maximum of corresponding registers. The maximum is exactly the operation the state records — each register holds the largest rank seen — so the merge is exact with respect to the union. The merged sketch is indistinguishable from one built by feeding both streams into a single instance.

The error, however, is not the error of either input. A merged sketch of $m$ registers has relative standard error $1.04/\sqrt{m}$ regardless of how many sketches were combined, so merging a thousand sketches does not degrade the estimate the way OR-ing a thousand Bloom filters does. That is the structure’s most useful distributed property: the sketch size is a function of the accuracy target alone, and the number of shards is irrelevant.

What does degrade is the bias correction. The empirical corrections fitted to a single sketch’s behaviour depend on the distribution of register values, and merging many sketches from skewed shards produces a distribution the correction table did not anticipate. The estimate remains unbiased to leading order but the residual bias can exceed the nominal error for heavily skewed partitions. The practical response is to merge and then apply the correction, rather than to correct each shard and average the results; averaging corrected estimates weights each shard equally, which is wrong when shards have very different cardinalities.

Intersection is where the algebra stops being useful. Set cardinalities satisfy $|A \cap B| = |A| + |B| - |A \cup B|$, and the formula applies to HyperLogLog estimates, but the errors of the three terms are independent and add. When the intersection is small relative to the union — the interesting case, since otherwise the two sets are nearly identical — the difference of two large numbers with independent errors has a relative error far larger than any of the inputs. Estimating an intersection this way is a subtraction of nearly equal noisy quantities, and the result can be negative. No merge operation recovers the intersection directly.

Addition for frequency sketches

Count-Min sketches merge by adding corresponding cells. The merged sketch is exactly the sketch of the concatenated stream, so the error bound applies with $N$ equal to the total of all shards. The same sizing issue appears: a grid sized for a per-shard stream has an additive error proportional to the total, so a hundred shards each sized for a million items produce a merged error of $\varepsilon \times 10^8$ rather than $\varepsilon \times 10^6$.

Addition also has a sign hazard that OR and maximum do not. If a shard emits negative updates — a retraction, a correction, a delta stream — the summed cell can be lower than the true count, and the one-sided guarantee inverts. Merging is only safe for non-negative updates unless every shard’s deltas are accounted for consistently. A merged cell that goes negative makes the minimum estimator return a number below the truth for every key that hashes there.

The merge is associative and commutative, which makes it usable in a tree or a gossip protocol: partial aggregates can be combined in any order and any grouping. It is also idempotent only if updates are non-negative and each is applied exactly once; a duplicated delta double-counts. At-least-once delivery between aggregators therefore requires either idempotent keys or a deduplication layer, and the sketch itself offers no help — it has no record of which updates it has seen.

The parameter agreement problem

All three merges assume the inputs share their parameters exactly. For a Bloom filter that means $m$, $k$, the hash function, the seed, and any layout choice such as blocking. For HyperLogLog it means the register count, the hash width, and the register encoding. For a Count-Min sketch it means $w$, $d$, and the row hash functions.

Every mismatch produces a silently wrong result rather than an error, because the merge operation — OR, max, add — is defined for any two arrays of the same length. Two HyperLogLog sketches with the same $m$ but different hash seeds will merge into a sketch whose registers mix ranks from unrelated keys. The estimate will be plausible and wrong, often badly. Two Count-Min sketches with the same dimensions but different row hashes will add cells belonging to different key sets, inflating every estimate by roughly the other stream’s mass.

Version skew is the common cause. A library that changes its default seed, its hash function, or its register encoding between releases will produce sketches that merge without complaint and estimate incorrectly. The remedy is to carry the parameters in the serialised header and refuse to merge mismatches, which is a policy decision the format must support. A sketch format without a header cannot be made safe by careful coding on the reader side.

There is a subtler case: identical parameters but different precision. A HyperLogLog built with four-bit registers and one built with six-bit registers cannot be merged register-wise even if both have the same $m$, because the packing differs. The dense-versus-sparse representation used by production implementations adds a second axis: a sparse sketch encodes empty registers compactly and must be converted to dense before a register-wise merge. Conversion is lossless, so the merge is correct, but the conversion cost is proportional to the full register count and can dominate a merge of many small sketches.

Merging and the guarantee

The distinction worth keeping is between merging states and combining estimates. Merging states is sound for union and sum because the state is a sufficient statistic for the underlying set or multiset; the merged state carries exactly the information a single pass would have produced. Combining estimates is sound only when the estimator is linear in the state, which none of these are — the minimum, the maximum, and the harmonic mean are all non-linear.

Averaging per-shard Bloom false-positive rates, for instance, says nothing about the merged filter’s rate, because the rate is exponential in the total key count. Averaging HyperLogLog estimates from shards of different sizes weights a thousand-element shard the same as a million-element one. Summing Count-Min estimates across shards is correct only if the shards’ key sets are disjoint, which is usually what partitioning guarantees and never what replication does.

Replication is the case where merge semantics bite hardest. If each of three replicas sees the full stream, summing their sketches triples every count and triples the estimate. Merging with a maximum — correct for HyperLogLog, since the state is a maximum already — is idempotent and gives the right answer. Merging with addition is not. Choosing the merge operation is therefore a statement about whether the inputs overlap, and the structure’s own algebra does not distinguish the cases.

The remaining open problem is deletion across shards. OR cannot be undone, maximum cannot be lowered, and addition cannot be reversed without the original delta. Sketches are additive monoids, not groups, and a distributed system that needs to retract a shard’s contribution has to either retain the shard’s state or rebuild. The aging strategies that make single sketches track a moving window are the same strategies that make shard removal tractable: keep the window small enough that discarding an old bucket is acceptable.