System requirements

Functional:

• allow user to click on an ad
• collect the stats of the clicks including
  • the total number of clicks in the past x minute/sec

Non-Functional:

• latency, ads aggregation needs to be near real-time, otherwise the data is not that useful
• availability
• consistency, not that important, it's ok to be slightly out of sync, eventual consistency is good enough
• correctness, not that strict, ok to miss a click or two, but the aggregation result should be correct
  • handle duplicate events
  • handle late arrived events

Capacity estimation

assume 500M DAU, each clicks 5 ads daily. each clicks generates 1kb data.

TPS: 500M * 5 /24/3600= 29000 TPS

Storage: 500M * 5 * 365 * 1kb = 912.5TB/year

API design

• post click(metadata, user_id, timestamp, ad_id)
• get v1/ads/{ad_id}/count
  • body: from, to
  • return the count of clicks on the given ad in the past n minutes.
• get v1/ads/topClicks
  • body: from, to, n
  • return the top k ads clicked in the past n minutes.

Database design

The aggregated data is related to time, read write heavy, we can use a time-series database.

The raw data is write heavy, but not read heavy since it's mainly used as a backup. We can choose NoSQL to optimize the write performance.

raw data

• ad_id
• timestamp
• ip
• location
• user_id

aggregated data - count by minute

• ad_id
• click_minute
• count

aggregated data - top clicked ads

• from
• to
• aggregate_at
• most_clicked_ads

High-level design

• collect queue - store the input click events
• aggregation service - read the input events, aggregate the event by minute, and calculate the top clicked events in the last minute.
• aggregate queue - store the aggregated events
• db writer - one set of writers to pull from the collect queue, store the raw events in to raw data database. Another set to pull from the aggregate queue and store the aggregated events to the aggregate data database

Request flows

Explain how the request flows from end to end in your high level design. Also you could draw a sequence diagram using the diagramming tool to enhance your explanation...

Detailed component design

Aggregate service

We can use map reduce to aggregate the events. We have two use cases.

1. top n clicks in the last minute
2. the total clicks of each ad in the last minute

For use case 1, for an aggregation service node, we internally have a mapper that distributes events to different workers, the workers aggregates the count by ad_id, then the reducer calculates the total count for each ad.

For use case 2, for an aggregation service node, we internally have a mapper that distributes events to different workers, the workers aggregates the count by ad_id, calculates the local top 100 ads, then the reducer calculates the global top 100 ads.

To scale up, we can have a zookeeper manages a set of aggregation service, ads are routed to different aggregation service based on id range.

Late arriving events

Events can arrive late in async flows, to handle that, we uses watermark, which slightly extends the window size to accomodate for events arrive late. We can also add a reconciliation service to compare the raw data and aggregation data to fix any problems.

Trade offs/Tech choices

• we can aggregate the events either by the timestamp the ad is clicked or the timestamp the ad is processed. Considering we want to make sure the aggregation results is accurate, we aggregate by the timestamp ad is clicked.
• for watermark, we choose a small size like 15 sec to avoid too much overhead. For events arriving too late, we rely on the reconciliation job nightly to fix the discrepancy.

Failure scenarios/bottlenecks

Try to discuss as many failure scenarios/bottlenecks as possible.

Future improvements

What are some future improvements you would make? How would you mitigate the failure scenario(s) you described above?