Prompt and scope
This is a data-engineering and stream-processing interview question. The platform ingests billions of events, queries by hour, tenant, and region, and allows roughly 1% relative error for dashboards. Billing, quota enforcement, and audit reports still require exact values. Clarify the error budget, window type, lateness bound, need for set operations, and whether the identifier is personal data.
The question bank already covers streaming, hot partitions, and batch-versus-stream architectures. This prompt focuses on how a mergeable cardinality sketch changes distributed distinct-count cost rather than on one database product.
What the interviewer evaluates
- Whether you distinguish cardinality, membership, and frequency instead of treating HLL as a Bloom filter or Count-Min Sketch.
- Whether you explain fixed-size sketches per shard and register-wise maximum merging instead of adding local estimates.
- Whether you turn error, lateness, reset, privacy, and business exactness into testable contracts.
A weak answer says “use Redis HLL because it is small.” A strong answer gives an exact baseline, names approximation failure modes, and defines replay, sampling, and drift monitoring.
Clarifications before answering
- What error is acceptable? A dashboard may accept about 1%; billing or compliance reporting needs an exact path or a calibrated reconciliation path.
- Are queries fixed windows or arbitrary ranges? Hourly sketches suit fixed buckets; arbitrary ranges require mergeable buckets with explicit boundaries and retention.
- How late can events arrive? The lateness bound determines whether to reopen a bucket, retain raw events, or accept a finalization watermark.
- Are intersections, differences, or member listings required? HLL is strong for union cardinality; membership, intersection, or deletion needs another structure or exact recomputation.
A 30-second answer
“I would keep an exact set as the correctness baseline, but its memory, network shuffle, and cross-shard merge cost grow with unique users. If the dashboard accepts about 1% error, each shard maintains a fixed-precision HyperLogLog keyed by hour, tenant, and region. At query time I take the register-wise maximum across sketches and run one estimator; I never add local estimates. HLL answers approximate union cardinality, not membership, deletion, or an identity list. I use event time and a watermark to close buckets, accept bounded lateness, and send older corrections to exact replay. Finally I reconcile sampled closed buckets against exact counts and monitor relative error, empty buckets, duplicates, sketch merges, and privacy risk.”
Step-by-step deep answer
Step 1: Build the exact baseline.
Store a user-ID set for each (hour, tenant, region). It is exact, but shards must send many IDs or perform a global shuffle. Adding local COUNT(DISTINCT) values double-counts a user present on multiple shards.
Step 2: Describe HLL state.
Split a stable hash into a register index and a leading-zero rank. Each input updates only its register with a maximum rank. The estimator derives a cardinality from all registers and applies small-range corrections. Do not promise a universal error without naming precision, hash behavior, and the estimator range.
Step 3: Explain distributed merging.
Sketches for one dimension must use the same register count, hash convention, and encoding. Merge by taking the maximum in each register, not by adding estimates. Minute sketches can therefore roll into hourly answers without shuffling raw IDs.
for each event(user_id, bucket, tenant, region):
i, rank = hash_and_rank(user_id, precision)
sketch[bucket, tenant, region][i] = max(sketch[...][i], rank)
merged[i] = max(sketch_a[i], sketch_b[i])
estimate = hll_estimator(merged)Step 4: Handle lateness and windows.
Bucket by event time and use a watermark to mark buckets final. Accept updates only within the maximum lateness bound; send older events to raw-log replay or an exact correction table. HLL cannot remove one user, so revoking an event requires rebuilding the affected bucket.
Step 5: Separate approximate results from business correctness.
A reconciliation job samples closed buckets and computes truth with an exact set or offline SQL. Record relative error, bias direction, and dimensions with anomalies. Keep exact ledgers for billing, quotas, and privacy deletion; use sketches for low-cost observation or estimation.
Step 6: Control cost and privacy.
Bound dimension combinations, bucket retention, and sketches per tenant so high-cardinality labels cannot create unbounded state. Normalize hash input consistently and manage key rotation; authorize sketch access. A sketch is not an anonymization guarantee because aggregate size can still reveal a group.
High-quality sample answer
“I would first ask whether the result may be approximate. Exact sets fit billing and audit, but billions of events across shards and long windows make memory and shuffle expensive. For a dashboard with about 1% tolerance, each shard maintains an identically configured HLL per time bucket and dimension. A stable hash updates one register, and the query takes register-wise maxima before running the estimator; adding local estimates would count users twice.
I close event-time buckets with a watermark and keep a bounded lateness window. Corrections outside that window go through raw-log replay because HLL cannot delete one element. Metadata records precision, hash convention, and bucket boundaries so sketches remain mergeable. I monitor sketch size, merge latency, duplicate rate, and relative error, and reconcile sampled buckets with exact sets. Billing and compliance deletion remain exact; HLL is an analytics acceleration layer.”
Common mistakes
- Adding shard estimates → the same user can appear on several shards → merge registers, then estimate once.
- Claiming HLL can answer whether a user appeared → it stores a statistical summary → use a set or Bloom filter for membership and state false positives.
- Subtracting a late or deleted event from a sketch → a register maximum has no reversible contributor → rebuild the bucket or use an exact correction table.
- Merging arbitrary precision or hash formats → register meanings differ → store precision, hash, encoding, and version metadata.
- Treating a sketch as privacy protection → aggregate size can still leak group information → combine authorization, minimal dimensions, retention, and privacy review.
Follow-ups and responses
Follow-up 1: The business asks for any 37-day range. How do you bucket it?
Minute sketches create more state, but a query can merge contiguous minutes; hourly and daily sketches reduce reads for long ranges. Multi-level buckets need explicit, non-overlapping boundaries. The planner chooses the coarsest non-overlapping combination and fills cross-level edges with finer buckets.
Follow-up 2: A user deletion must take effect within 24 hours. Can HLL remain?
HLL cannot perform per-user deletion. Keep an erasable exact event index or encrypted mapping, rebuild affected buckets, and hide old versions at the dashboard layer; treat the sketch as non-authoritative. If regulation requires deletion evidence, use the exact deletion ledger and replay verification.
Follow-up 3: Error jumps from 1% to 8% after a merge. What do you inspect first?
Compare sketch metadata: precision, hash seed, register encoding, and version. Check whether a shard serialized an estimate instead of registers, merged the same input twice, or received an anomalous hash distribution. Reproduce a small set step by step with one shard, two shards, and a merge to isolate estimator or serialization defects.