Handling Late and Out Of Order Data Questions

Design systems to handle events that arrive late or out of order. Implement watermarking, windowing strategies, and allowed lateness policies. Decide when to wait for late data vs. when to close windows.

HardTechnical

46 practiced

Formal semantics: define what it means for a windowed aggregation to be 'final' in the presence of allowed lateness and triggers. Provide examples showing non-deterministic outputs if watermarks are aggressive and how to reason about result correctness.

Sample Answer

Definition (formal): A windowed aggregation result for window W = [s,e) is "final" at processing time T iff the system guarantees no subsequent element with event-time in [s,e) will be accepted and no further triggers will fire that change the aggregation value. Practically that means: watermark(T) > e + allowed_lateness AND all trigger conditions that could mutate state (early, on-time, late) are exhausted or made inert.

Example showing non-determinism:- Window W = [00:00,00:10), allowed_lateness = 5m. Source emits events with event-times around 00:05.- If watermark advancement is conservative (advances to 00:16 only after buffering late arrivals), the final output at T when watermark>00:15 includes late events and is stable.- If an aggressive watermark policy jumps to 00:20 (e.g., due to clock skew or mis-configured watermark), elements arriving at processing time 00:12 with event-time 00:06 may be treated as "too late" and dropped — producing a different final aggregation. Different runs (or nodes) with different watermark progress produce non-deterministic final outputs.

Reasoning about correctness:- Watermark is a lower bound on event-time seen; correctness requires that watermark never over-approximate (i.e., claim more progress than true). Formally, determinism holds if for every execution the predicate (watermark(T) ≤ max_event_time_seen_up_to_T + ε) holds with ε≥0 small.- To guarantee deterministic final results: (1) choose allowed_lateness ≥ maximum out-of-orderness; (2) implement exactly-once state updates and durable storage for triggers; (3) make triggers deterministic (time- or count-based, not race-dependent); (4) treat watermark as advisory only if you need strict correctness—buffer until safe point or use late-arrival reconciliation (retractions/compactions).

Practical mitigations:- Increase allowed lateness or use "hold-until" based on source SLAs.- Emit retractions/updates (not only appends) so downstream can converge.- Use conservative watermark generation (e.g., max observed event-time minus max_skew).- Record provenance/diagnostics so you can replay and reconcile if aggressive watermarks caused drops.

Key takeaways:- "Final" = no future accepted events or triggers can change the window.- Aggressive watermarks break this guarantee and cause nondeterminism.- Correctness needs conservative watermarking, appropriate allowed-lateness, deterministic triggers, and robust state/IO guarantees (exactly-once, replay) to reason about and ensure finality.

HardSystem Design

44 practiced

Hard system design: build a scalable streaming analytics system that provides near-real-time dashboards while guaranteeing final daily aggregates are correct despite up to 24-hour lateness. Requirements: 100M events/min peak, multi-tenant, 3-second dashboard latency for provisional numbers, final numbers reconciled within 24 hours. Describe architecture, buffering, watermarking, storage, recompute, and reconciliation.

Sample Answer

Requirements clarification:- Ingest 100M events/minute peak (≈1.67M/sec) multi-tenant.- Dashboards must show provisional aggregates within 3s (low-latency, approximate but near real-time).- Final daily aggregates must be correct and reconciled within 24h even with events arriving up to 24h late.

High-level architecture:- Ingestion: Producers -> Kafka (partitioned by tenant+day) with schema registry (Avro/Protobuf).- Stream processing: Apache Flink (or Beam on Dataflow) for low-latency event-time processing with RocksDB state backend and checkpointing for fault tolerance.- Real-time materialized views: OLAP store optimized for fast rollups (ClickHouse, Druid, or ScyllaDB + cache) to serve dashboards (<3s).- Long-term storage: Append-only raw events in cloud object store (S3/GCS) and compacted Parquet partitions (tenant/date/hour).- Batch recompute: Spark/Beam batch jobs that reprocess the canonical raw events per day to compute final aggregates.- Reconciliation & correction: Dedicated service that diffs provisional vs final, issues correction messages/patches to materialized views and notifies stakeholders.

Key design details

1) Buffering & ingestion- Kafka as durable, scalable buffer. Partitioning scheme: tenant_id % N, plus time-based partition key to support partition-local consumers and bounded reprocessing.- Producers write with event timestamp; include metadata (ingest_time).- Use Kafka retention >= 48h (or longer) to enable reprocessing; also persist raw events to S3 for longer-term re-compute.

2) Event-time processing & watermarking- Use event-time semantics in Flink. Watermark strategy: watermark = max_observed_event_time - allowed_lateness_skew.- Allowed lateness setting: - For provisional dashboards: small watermark delay (e.g., 5–10s) to enable 3s latency targets while accepting some out-of-orderness; output provisional aggregates with “tentative” flag. - For final correctness: set a separate, max_allowed_lateness = 24h in the pipeline for side outputs that capture late events beyond provisional window but within 24h.- Implementation: maintain two window pipelines: - Low-latency windows (sliding/ tumbling as required) with aggressive watermarks produce provisional updates to OLAP store. - Late-event capture: side outputs + persistent sink to S3 and to a “late-event topic” in Kafka for later reconciliation.

3) Materialized views and serving layer- Real-time sink writes incremental aggregates to OLAP (upserts or rollup segments). Use write batching and per-tenant rollups to keep writes efficient.- Dashboards query OLAP for latest provisional numbers and show “last-updated” + provenance (tentative vs final).- Use cache (Redis) for very hot queries to meet 3s SLAs.

4) Storage & immutable raw store- Raw events persisted to S3 in partitioned Parquet (tenant/date/hour). This is the source-of-truth for final recomputation.- Write pipeline writes to Kafka and then asynchronously batches to S3 (exactly-once via producer idempotency + transactional sinks or at-least-once with dedup keys in Parquet).

5) Final daily recompute- At end-of-day + 24h window, run a deterministic batch job that: - Reads raw events from S3 for the target day (and the 24h late window). - Applies the same business logic + canonical aggregations (use the same codebase as stream logic or Beam portable runners to avoid logic drift). - Produces final aggregates and writes to a “final aggregates” table with immutable partitioning by day and tenant.- To guarantee correctness use partitioned, idempotent writes (write to staging table, then atomic swap / partition overwrite).

6) Reconciliation & corrections- Reconciliation service compares provisional aggregates (from OLAP) against final aggregates (batch output) per tenant/day/metric.- If delta > threshold: - Emit corrective updates (patch events) into Kafka “corrections” topic. - Stream processing consumer applies corrections to OLAP with idempotent upserts, and dashboards mark numbers as “final”.- Store reconciliation audit logs (who/when/delta) for SLA and debugging.

7) Exactly-once & consistency- Use Flink’s checkpointing + Kafka transactions (or two-phase commits) to achieve exactly-once semantics for state updates and sinks.- Use deduplication keys when writing raw events to S3 (e.g., event_id) to tolerate producer retries.

8) Multi-tenant considerations- Logical isolation: topics, partitions, quotas per tenant.- Resource isolation: Flink job slots, memory pools, and separate tenant quotas in OLAP.- Rate limiting and backpressure: producers get token buckets; reject or sample low-priority tenants under overload.- Billing/monitoring per tenant.

9) Scalability and performance- Kafka scaled to handle 1.7M messages/sec with adequate partitions and brokers. Use compression and batching.- Flink clustered with autoscaling; state sharding via keyBy(tenant+key).- OLAP: partition by tenant/date and roll segments; use compactions to keep queries fast.

10) Monitoring, alerts, and SLOs- Track lag (Kafka consumer lag), watermark progression, lateness histogram, reconciliation deltas.- SLOs: 3s for provisional dashboard percentiles; 24h reconciliation guarantee; SLA for reconciliation error thresholds.

Trade-offs and rationale- Two-path processing (low-latency provisional + full-batch final) balances latency vs correctness. Provisional provides near real-time UX; batch recompute guarantees correctness.- Using S3 as source-of-truth enables full deterministic reprocessing and audits at cost of storage and compute for recompute jobs.- Exactly-once across systems is hard; implementing idempotent writes + atomic partition swaps simplifies reconciliation.

Edge cases and operational notes- Late bursts >24h: decide policy (drop, accept via manual reprocess, or special correction pipeline).- Schema evolution: enforce schema registry and data-contracts; enforce validators at producers.- Logic drift: share library between stream and batch code; run nightly tests comparing sample outputs.- Tenant onboarding: set quotas and simulate load using synthetic traffic.

This architecture delivers 3s provisional dashboards using event-time streaming and aggressive watermarks, while guaranteeing final daily aggregates via deterministic batch recompute from immutable raw events and a reconciliation layer that patches provisional state to reach final correctness within 24 hours.

HardTechnical

57 practiced

Propose a machine-learning-based approach to predict watermark lag dynamically per topic, using historical arrival delays. Describe features you would use, the target label, training data generation, model choice, and how you'd integrate predictions into a production watermarking strategy.

Sample Answer

Approach summary: predict, per topic and time-window, the watermark lag (delay to wait past event-time) needed to achieve a target completeness (e.g., 99% of events arrived). Use historical arrival delays to produce labeled examples and run a scalable model that outputs a probabilistic lag (quantile). Integrate predictions into the streaming watermark generator with safety buffers and continuous feedback.

Features- Time features: topic, partition count, hour-of-day, day-of-week, holiday flag, recent window index (captures diurnal/weekly patterns).- Arrival-delay statistics (computed over sliding windows): mean, median, 90th/95th/99th percentiles, variance, count, skew.- Traffic/throughput: events/sec, bytes/sec, burstiness metrics (std of throughput), recent backpressure/retry counts.- System metrics: producer lag, consumer lag, avg processing latency, cluster CPU/memory utilization, network errors.- Event characteristics: avg event size, schema-change flag, fraction of late events historically.- Recent trend features: delta of percentile values vs prior windows, exponential moving averages.

Target label- Primary: lag_seconds required so that X% (e.g., 99%) of events for that topic-window have arrived (a per-window quantile). Alternatively predict the delay distribution and use the q-th quantile as label.- Optionally predict probability of missing >k events if using classification for SLA breaches.

Training data generation- From historical raw streams, for each event compute arrival_delay = ingestion_timestamp - event_timestamp.- For fixed windows (e.g., 5m windows) and per topic, aggregate arrival_delays into percentiles and counts; compute label = minimal lag such that cumulative fraction >= target completeness.- Produce one sample per (topic, window_end) with features derived from prior windows (lagged features) to avoid leakage.- Store training examples in a time-partitioned dataset (Parquet on S3 / BigQuery) and include metadata (pipeline version, schema) for lineage.- Handle concept drift by time-based train/validation splits and retaining recent data for retraining.

Model choice- Start with gradient-boosted trees (XGBoost/LightGBM/CatBoost) for tabular features; they are fast, interpretable (feature importance/SHAP), and support quantile/Pinball loss for direct quantile regression.- For temporal patterns, consider a sequence model (LSTM/Transformer) or a hybrid: GBDT on engineered time-series features.- Predict quantiles (e.g., 90/95/99) rather than mean to meet SLA. Use pinball loss and evaluate with pinball loss, calibration, and business metrics (late-event rate, watermark error).

Production integration- Real-time feature pipeline: compute features in streaming (Spark Structured Streaming/Flink) with stateful aggregations and write feature vectors to a low-latency store (Redis, RocksDB, or feature service).- Prediction service: lightweight REST/gRPC or embedded model in streaming job that returns the chosen quantile lag per topic-window.- Watermark controller: use predicted lag + safety buffer (adaptive; e.g., max(prediction, baseline_lag, min_sla_lag)). Support override rules per critical topics.- Feedback loop: each window compare actual completeness vs predicted; log discrepancies, compute slack; feed back into training dataset.- Monitoring & safeguards: alert if prediction error or late-event rate crosses threshold; fallback to conservative static lag if model unavailable.- Model ops: continuous training pipeline (Spark/XGBoost on cluster), daily retrain or on-drift trigger, canary rollout and A/B test: compare business metrics (latency reduction, SLA misses) before full rollout.

Evaluation & metrics- ML: pinball loss per quantile, RMSE for mean, calibration plots.- Business: percent windows meeting completeness target, reduction in end-to-end latency vs static lag, CPU/resource impact.- Robustness: track catastrophic underestimates and enforce safe upper bound.

Trade-offs- Quantile regression reduces missed events but may increase latency if set too conservative; balance with business cost of late events.- Complexity: sequence models can improve accuracy for volatile topics but cost more to serve; GBDT provides quick wins.

This design gives data engineers a scalable pipeline: compute features from historical and streaming data, train quantile models at scale, serve per-topic dynamic lags in streaming jobs, and close the loop with continuous monitoring and retraining.

EasyTechnical

42 practiced

You observe duplicated events caused by retries at the ingestion layer and some duplicates arrive late. Describe three practical deduplication strategies for streaming pipelines that must handle out-of-order and late arrivals. For each, list pros, cons, and required state or metadata.

Sample Answer

1) Event-key + time-window dedupe (stateful watermarking)- How: For each key, keep a sliding window of seen event IDs (or hash) for the allowed lateness period. Drop events whose ID is already in the window. Expire IDs after watermark + allowed lateness.- Pros: Simple, works with modest out-of-order and late arrivals; low CPU; easy to implement in Flink/Spark Structured Streaming.- Cons: Memory grows with cardinality × window; choice of allowed lateness is trade-off (miss late-but-valid vs. memory leak).- State/metadata: Per-key set of recent event IDs (or bloom filter) + timestamp of first seen; watermark/allowed-lateness config.

2) Sequence-number + highest-seen per key (monotonic seq)- How: Upstream assigns monotonic sequence numbers per key. Track highest-seen sequence per key; accept events with seq > last_seen or if seq ≤ last_seen but not yet committed (depending on idempotency).- Pros: Very low state (one number per key); deterministic ordering when seq is reliable; efficient for high volume.- Cons: Requires upstream coordination to assign sequence; cannot recover if sequences reused or missing; late arrivals with lower seq are duplicates and dropped even if earlier was lost.- State/metadata: Per-key highest sequence number, optionally a small buffer of recent lower seqs if reordering tolerated.

3) Exactly-once sinks with idempotent writes / transactional dedupe- How: Let sink (DB, OLAP) enforce uniqueness via primary key or use transactional upserts. Allow duplicates through stream but dedupe at write using event ID as unique key; use transactional commit to avoid partial writes.- Pros: Offloads dedupe to storage, scales with sharding, tolerant of arbitrary lateness; simple stream logic.- Cons: Higher sink load; requires idempotent/transactional storage (not always available); potential write amplification and increased latency.- State/metadata: Durable uniqueness index or table of processed event IDs (with TTL), or sink transaction log; no large in-memory state in stream.

EasyTechnical

50 practiced

List and contrast the main window types used in stream processing (tumbling, sliding, session). Given the following events (event_time in minutes): E1=2, E2=4, E3=7, describe which tumbling-5s windows and a session-window (gap=3) each event belongs to.

Unlock Full Question Bank

Get access to hundreds of Handling Late and Out Of Order Data interview questions and detailed answers.

Join thousands of developers preparing for their dream job.