Detailed component design

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

We prioritizes event timestamps over processing timestamps to more accurately reflect when ad clicks occur.

However, using event time can introduce delays when data transmits over networks or moves through queues.

To manage this, the design incorporates watermarking, which extends the aggregation window slightly to include events arriving just after the window’s close. This helps maintain high accuracy while keeping latency low.

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.

Submissions

Displaying Solutions with Scores Ranging from 1 to 10