Detailed component design

[Senior level deep dive topics.]

Streaming vs Batching

We can combine real-time streaming for immediate aggregation with optional batch processing for historical data recalculations.

Stream processing handles incoming events in real-time, immediately updating click counts and top-clicked ads each minute.

By contrast, batch processing is reserved for recalculating aggregated data if errors are discovered, enabling retroactive corrections without impacting real-time processing.

This combined architecture, often called the Kappa architecture, avoids the complexity of dual paths (as in Lambda architecture) by using a single stream for both live and historical data.

Aggregation Windows

To calculate the top K ads per minute and click counts, the system employs tumbling windows, which divide time into fixed, non-overlapping intervals (one minute each).

This structure is efficient for minute-level aggregations, but the design faces a trade-off when aggregating over longer windows, like the last 5 or 10 minutes. Storing a larger K per minute (e.g., top 1000 or 2000 ads) enables approximating the top K over broader windows, though this comes with increased storage costs.

This "long tail" approach captures both popular and moderately clicked ads, providing more accuracy across multi-minute aggregations.

Event Time and Watermarking for Accurate Aggregation

Event Time and Watermarking are crucial techniques in data streaming systems to ensure accurate aggregation, especially when handling out-of-order events.

In our system, we prioritize using event time—the actual time when a user clicks an ad—over processing time, which reflects when the server processes the event.

This choice helps ensure that our aggregation accurately reflects real-world activity, even if some events are delayed in reaching the server.

However, relying on event time introduces a challenge. Network latency or queue delays can cause some events to arrive late, meaning they may miss the aggregation window they belong to (e.g., a click that occurred within one minute may arrive a few seconds late). To manage this, we implement watermarking.

A watermark is a threshold that extends the aggregation window slightly, allowing delayed events to still be counted if they arrive within a set period after the window's close.

For instance, if we have a one-minute aggregation window, a 10-second watermark would allow events arriving up to 10 seconds late to be included in the minute they occurred. This approach maintains high accuracy by accounting for network delays while keeping system latency low.

The length of the watermark is a trade-off: a longer watermark improves data accuracy by capturing more delayed events but introduces additional latency, while a shorter watermark reduces latency but may exclude some late events, potentially impacting accuracy. This flexibility helps us balance timely data aggregation with the need for precise metrics in real-time analytics.

Delivery Guarantees and Data Deduplication

Ensuring exactly-once delivery is crucial, given that ad click data directly influences billing. The first message queue (e.g., Kafka) supports this by buffering events and ensuring that each click is processed precisely once.

However, we also include a second message queue to handle aggregated results with the same level of reliability, preventing data loss or duplication in case of failures during storage.

To manage duplicates:

Client-side duplicates are ignored if they are identified as retries (possibly due to network issues).
Server-side duplicates are handled using acknowledgments, ensuring each click count is finalized before an offset is committed to Kafka.

Scaling Message Queue, Aggregation Service, and Database

To handle traffic growth, the system can independently scale its message queue, aggregation service, and database components.

The message queues use ad_id for partitioning, which allows multiple consumer groups to process different ad IDs in parallel, with a predefined number of partitions to reduce rebalancing needs.

Aggregation service scaling can be achieved through either multi-threading (allocating ad IDs to threads) or deploying nodes on resource managers like Hadoop YARN.

In the database layer, Cassandra’s horizontal scaling with consistent hashing efficiently distributes data across nodes and automatically rebalances when new nodes are added. High-traffic ad IDs are spread across more nodes to prevent any single node from becoming a hotspot.

Monitoring and Daily Reconciliation for Data Integrity

The system continuously monitors key metrics such as latency, queue size, and resource usage on aggregation nodes to help maintain optimal performance.

To further ensure data integrity, a batch reconciliation job runs at the end of each day, sorting events by event time and verifying that all events are accurately aggregated.

This reconciliation process helps confirm that any slightly delayed events are accounted for in the final data.

In our design we reuse the aggregation service to handle reconciliation by re-aggregating raw data during the reprocessing phase. This approach allows us to leverage the existing aggregation logic and infrastructure, ensuring consistency in how data is processed, both in real-time and during reconciliation.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10