System requirements

Functional:

1. User should be able to click an ad, and be redirected to the advertiser's website.
2. The advertiser must be able to gather the ad click metrics with a granularity of 1 min.

Non-Functional:

Scope of the system - Expecting about 10M active ads, with 100M clicks per ad every day, we can expect roughly about 10000 clicks per second.

1. The system should be scalable enough, to be able to handle about 10000 clicks per second.
2. The ad click metrics collected, must be accurate and the system should be fault tolerant.
3. Low Latency - We expect the advertisers to be able to extract the ad click metrics in as less time as possible.
4. Real time data collection - We would expect the system to be able to provide the metrics to the advertisers in as real time a way as possible.

Capacity estimation

1. Assume that there are 10M ads with about 100M clicks every day, which gives us = (100 * 10)*1000000/24*60*60 is roughly 10000 clicks per second.
2. Our system should be scalable enough to handle about 10000 clicks per second.

API design

The APIs will mostly be the

1. POST /click endpoint - When the user clicks on the ad, this endpoint is invoked by a POST request. This will redirect the user to the advertiser's website and will record the user click.

Database design

There will be two kinds of database that we can use here

1. A relational DB like MySQL to store the ad data - (Ad id, Ad campaign name, redirect URL for the ad, date created)
2. An Analytics Database(Online Analytics Processing) like SnowFlake, Redshift or BigTable to hold the aggregated data which the advertisers will be querying.

High-level design

At a high level, we would need the below components

1. Ad Placement Service - This will place the ad on the user page.
2. Click service - When user clicks on the ad placed by the ad placement service, we send the request to the /click endpoint, which will redirect the user to the advertiser's website and also track the click.
3. Click Processor- This collects the clicks and writes into a Kafka or Kinesis Queue
4. Kinesis Queue - This will hold the raw click data .
5. Flink - This is a streaming processor to aggregate the data from the kinesis queue
6. OLAP database - Flink writes the aggregated data to the OLAP database after post processing.
7. Analytics service - This helps in querying the click metrics and data from the OLAP database.

Request flows

When a user click comes in , below are the steps that are followed

1. The click processor puts the raw click data to the Kinesis or Kafka queue.
2. The Flink Stream processor aggregates the data from the queue.
3. The aggregated data is pushed into the OLAP database. The data has been aggregate based on adId, advertiser Id and timestamp.
4. The Advertisers query the OLAP database for the click metrics.

Detailed component design

Scalability

All the components like the Click Processor, Kafka/Kinesis , Flink and OLAP databases are easily scalable horizontally.

We can add more service instances for example for the click processor.

For Kafka/Kinesis, we can add more nodes.

For Flink, we can add more jobs/tasks.

For OLAP databases again, we can add more nodes.

Sharding

Sharding can be applied both at Kinesis queues and at Flink. So we can shard the queues based on the ad id. Flink can have one job per shard. That way we can optimise the parallel processors.

In case of hot shards, for example, an ad campaign by a really popular company can generate clicks to a particular shard. In order to optimise and distribute the keys across shards, we can generate a random number and append it to the Ad id, that way the raw click data for that ad can go to separate partitions. Partition key is the key to the shard here.

Trade offs/Tech choices

Choosing Stream Processing for the Click data instead of Batch Processing - this allows for more consistent real time data to be available for querying by advertisers.

Failure scenarios/bottlenecks

1. In order that the components are fault-tolerant, we have chosen most of the components in a way that they support good horizontal scaling.
2. For example, the click processor can be horizontally scaled by adding more instances.
3. The Flink and Kinesis queue both can be horizontally scaled. Both are also sharded based on the Ad Id.
4. The OLAP databases also can be scaled horizontally by adding more nodes.

Future improvements

1. Deduping the ad clicks - to ensure that an ad isn't clicked on multiple times by the same user, and we are collecting accurate data.

In addition to the ad id, the ad placement service can generate a unique key for every ad. When the user clicks on the ad, the click processor would check if the key exists in the cache. If it does, then the click is ignored. Otherwise it is written to the Kinesis stream and the unique key is written to the cache too. the cache can be a Redis or Memcache.

1. Reconciling the data - To ensure that the data between raw collection of data in the stream, and the data that has been aggregated by Flink and dumped into the OLAP database is correct.

To enable the reconcialtion process, we can have the raw data from Kinesis written to a S3 storage system. Spark can be used to batch process this raw data from S3 and aggregate it and compare with the stream processed data by Flink before dumping into the OLAP database.