Why distributed analytics needs mergeable sketches

Combine compact summaries across hosts and time windows without replaying raw events, while preserving explicit error guarantees.

Mergeable sketches for analytics

A mergeable summary lets workers combine retained state without sending every original event to one reader. Regions, shards and time buckets can each produce a summary, then supply it to a larger report.

We'll choose a summary by its query, compare a merged build with one pass over the input, and see what happens when a partition arrives twice.

Start with the query

Required answer Candidate Detail it must preserve --- --- --- Approximate distinct IDs HLL Compatible identity and hash observations Estimated frequency of a supplied key Count-Min Sketch Counter mass and matching row hashes Frequent items A frequent-items sketch Candidate identities and its frequency guarantees Latency percentiles A suitable quantile sketch Distribution evidence and observation weights Exact integer-set operations Roaring bitmap Exact integer membership

Roaring is a compressed exact set representation, not an approximate count. HLL supports union, while other distinct-count families, such as Theta, support additional set operations. These choices are not interchangeable simply because all can combine stored state.

Local summaries reduce transport and allow precomputed rollups or “last N buckets” queries. They can also rebuild a larger rollup from retained smaller summaries. A new metric or dimension may still require raw events: a summary cannot restore information it never kept.

We split the twelve document-ID occurrences used in the HLL lesson into a left partition containing the first six and a right partition containing the remaining six. Their arrival occurrences are disjoint, although some document IDs appear in both. Processing their union gives twelve occurrences and nine distinct IDs under the same string-identity rule.

For Bloom filters, merge corresponding bits with logical OR. If either input has set a position, the combined filter sets it. For HLL, merge corresponding registers by maximum. Each combined register then holds the strongest observation seen by either partition.

For a count-min sketch, add corresponding counters. Each counter receives the sum of the contributions assigned to it by both partitions. That operation represents combined event mass only when each contribution belongs in the intended population with the multiplicity being added.

These rules require compatible layouts. The Bloom filter needs the same array length, probe count, hash scheme, and input encoding. HLL needs the same precision, hash width, and register interpretation. Count-min needs matching matrix dimensions and row hashes. Matching payload size alone does not establish compatibility.

The local merge path

Our replay builds each summary separately for the two partitions, merges them, and compares their retained states against a single pass over the whole stream. It also attempts incompatible merges, which its wrappers explicitly reject. No network transport or distributed coordination is implemented here.

The diagram separates the observed partition summaries from the external contribution receipts used later in the replay. A receipt identifies a partition already included in a total; it is application state, with a different role from hash registers or shared counters.

A reservoir holds a fixed-size uniform sample of arrivals. Combining samples needs the original population sizes as well as the retained items.

Consider a capacity-one reservoir from a left partition with one original item and another from a right partition with three original items. The left sample always contains its sole item. The right sample chooses each of its originals with probability one third.