Data engineering
Part 4 of 6 · Approximate AggregationsSketch Merge Pipelines — Incremental, Hierarchical & Cross-Shard Aggregation
Sketches only pay off when the pipeline merges them correctly: incrementally on a stream, hierarchically across regions, and across shards without double-counting. Interviewers want leaf-to-region-to-global and the retry failure mode.
- 1Gist
- 2Maps
- 3Q&A
- 4Sandbox
Voice readout needs Web Speech Synthesis in this browser.
How the tree must behave
Prefer
Idempotent hierarchical merge plus coverage
Leaves flush windowed sketches. Regions merge new ids only. Global queries one blob. Missing leaves show up as coverage, not as a quietly optimistic p99.
- Content-addressed merge keys (hash of leaf sketch + window).
- Exactly-once apply on at-least-once transport.
- Spark treeAggregate / Flink window + watermark is the batch/stream spelling.
Alternative
Re-merge on retry, or average sealed p99s
At-least-once without ids doubles weight. Averaging a late shard’s p99 with a sealed global p99 is the same lie as averaging shard percentiles.
- Different sketch types cannot merge.
- Partial region outage under-represents traffic.
- Too many keys is a cardinality problem, not a bigger merger.
Retry path this page exists to name
Merging is add-weights. Replaying the same leaf blob is not a no-op unless you key it.
- 1
Leaf flushes a window sketch
sketch_id from tenant, window, leaf, payload hash. - 2
Transport retries
At-least-once delivery. The blob arrives twice. - 3
Dedup hits
applied set contains the id. Merge is a no-op. - 4
No id check
Weight doubles. Quantiles shift. Dashboards lie.
Overview
Sketches only pay off when the pipeline merges them correctly: incrementally on a stream, hierarchically across regions, and across shards without double-counting. Interviewers ask for leaf → region → global and the failure modes: retries, late data, clock skew, partial coverage.
KLL and T-Digest math live on their pages. This page is topology + idempotency.
You should be able to:
- Draw the tree and place the dedup table.
- Explain tumbling vs sliding vs session for sketches.
- Say what you do when a region is dark.
Three merge patterns
- Incremental (online): one sketch per key/window;
update(x)per event; periodically snapshot. - Hierarchical: leaf sketches → regional merge jobs → global sketch for dashboards.
- Cross-shard / map-reduce: each partition emits a sketch; reducer tree-merges.
Push vs pull vs hybrid:
| Style | Where | Note |
|---|---|---|
| Push | Agents POST sketches to an aggregator (edge telemetry) | Backpressure when merger lags |
| Pull | Warehouse job SELECTs partition sketches and merges (BigQuery / Spark) | Deterministic tree if you want replay |
| Hybrid | Stream incremental plus nightly full rebuild from raw | Nightly exact on a sample is calibration, not the SLO path |
Windowing
- Tumbling: one sketch per
[t, t+W); merge closed windows only. - Sliding: heavier — multiple sketches or accept approximate overlap.
- Session: sketch per session key; merge only within the analysis scope.
Do not merge across windows unless the product explicitly wants a multi-window distribution. Usually keep windows sealed.
Idempotency (critical)
Merging is mathematically “add weights.” Replaying the same leaf blob without a merge-id key double-counts. Use:
- Content-addressed merge keys (hash of leaf sketch + window)
- Exactly-once sink / transactional outbox
- Dedup table of applied
sketch_ids (TTL ≥ window retention)
Symptom of a retry storm: sudden p99 move and weight doubling, while dedup_hit stays flat. Depth on bytes and alerts: ops.
Late data and out-of-order
- Allowed lateness: hold the window sketch open; merge late leaf updates before seal.
- After seal: side-channel correction sketch or accept bias — document it.
- Do not “average” a sealed p99 with a late shard’s p99.
Streaming spelling: seal when the watermark passes window + lateness (Flink-style). Clock / window mis-alignment across regions is an ops incident, not a sketch-math incident.
Cross-shard pitfalls
- Different sketch types cannot merge (KLL mixed with T-Digest).
- Mismatched k / compression: normalize before or after merge.
- Partial shard loss: global sketch under-represents traffic — monitor coverage %.
- Cardinality sketches (HLL) follow the same tree; still not for quantiles (hub-only).
Too many keys → too many sketches. Bound the label set; that lesson is metric cardinality.
Architecture (leaf → region → global)
Flow
- 1
1 Leaf flush window
- next2 Region merger
- relatedFail: retry same id without dedup
- 2
2 Region merger
- next3 Dedup sketch ids
- 3
3 Dedup sketch ids
- next4 Global sketch store
- 4
4 Global sketch store
- next5 Quantile API
- 5
5 Quantile API
- 6
Fail: retry same id without dedup
Lesson map
Sketch Merge Pipelines — Incremental, Hierarchical & Cross-Shard Aggregation
Sketches only pay off when the pipeline merges them correctly: incrementally on a stream, hierarchically across regions, and across shards without double-counting. Interviewers want leaf-to-region-to-global and the retry failure mode.
Architecture. Architecture
Select a node to see why it exists, or an edge to see the protocol, direction, effect, and consequence.
Mermaid export
flowchart TB l["1 Leaf flush window"] r["2 Region merger"] d["3 Dedup sketch ids"] g["4 Global sketch store"] l -->|1 Leaf flush window| r r -->|2 Region merger to 3 Dedup sketch ids| d d -->|3 Dedup sketch ids| g
Leaf → region first to save WAN and blast radius; then global.
Sandbox: hierarchical merge with dedup (Python)
Stand-in values for serialized KLL / T-Digest bytes. Real code calls sketch.merge(deserialize(bytes)).
Press Run. Snippets must be self-contained — no network, files, or native modules.
Same idea (TypeScript)
Press Run. Snippets must be self-contained — no network, files, or native modules.
Pitfalls
AZ-a flushes window 14:00 twice after a 502. Where does applied live — leaf, region, or global? If it lives only on the leaf, what happens when the leaf process dies and a new one retries the same bytes? Write the key.
Interview Q&A
Why leaf → region → global?
Answer
Bandwidth and blast radius. Merge locally before WAN. A bad region stays contained; global still needs coverage %.
Retry storm symptom?
Answer
Sudden p99 drop or rise and weight doubling — check sketch_id dedup. If dedup_hit is flat, you are double-counting.
Can I merge across windows?
Answer
Only if the product asks for a multi-window distribution. Usually keep windows sealed.
Spark pattern?
Answer
Aggregate a sketch UDAF per partition, then treeAggregate merge. Same associative combine as the online tree.
Streaming watermark?
Answer
Seal the sketch when the watermark passes window + allowed lateness. Late events after seal need a documented correction path.
Partial region outage?
Answer
Publish coverage = leaves_present / leaves_expected. Avoid a silently optimistic global under-count.
HLL in the same pipeline?
Answer
Same topology for NDV (distinct counts). Separate sketch type. Cardinality math stays hub-only on the map.
Link to metric cardinality?
Answer
Too many keys → too many sketches. Bound label sets. That lesson is metric cardinality.
Push or pull?
Answer
Push for edge telemetry; pull for warehouse reduce; hybrid if you want a nightly exact rebuild on a sample.
What goes in the idempotency key?
Answer
Tenant, window, leaf, payload hash — not only the leaf name. Depth: ops.