设计在线广告平台

System requirements

Functional:

I will focus on aggregating ad clicks by users.

User sees ads while visiting a web site.

User clicks an ad.

Advertisers can learn the following information about the ad:

• Given a time window (let's say by second), how many clicks it got.
• Information about users: distribution of users based on age, gender, geo location.
• Contextual information of the clicks: which website it was posted in.

Non-Functional:

Response time. I think advertisers make real time decision based on how an ad is doing, so it is important to give feedback in seconds instead of minutes.

Scalablity.

Availability.

Consistency: I do not think ACID like consistency is important for this use case.

Privacy is important. All the categories of users are treated by large groups so that no individuals can be specified.

Capacity estimation

Let's say there are 1B DAU in the platform.

Generating 5B ad clicks per day.

Let's say each click generates 1KB of data.

So that's 5B * 1KB = 5TB of data each day.

9PB of data in 5 years.

API design

# API for data gathering, called by clients

Click(client metadata (cookies, IP addresses, browser string), ad_ID, timestamp)

This API is used by client to report a user clicked on an ad.

# API for advertisers. An advertiser can be human or an automated system.

get_stats(time_from, time_to, ad_ID):

This API returns aggregated stats for a particular advertisement, in the given time period. E.g.,

[

time_from: ,

time_to: ,

num_users: 1000,

gender: {male: , female: , LGBTQ+),

age: {15:, 20:, 25: , ...},

top_websites: [],

]

Database design

First, we need a database to store all the clicks.

Cassandra would be a good data store because it handles many small writes very well. It is horizontally scalable.

Write Path:

1. write click events to Cassandra.
2. A job takes these events, aggregates them, and put more queryable data in database (this can also be Cassandra)

Read Path:

1. Advertiser reads aggregated stats of clicks, e.g., number of users, aggregated stats.

High-level design

Client request first goes to CDN. CDN is used primarily for protection against DoS attacks.

I split Write Server as a microservice because it has a specific job - receive a huge number of clicks and store them in Cassandra. It is critical to do this write path well, so let's have an independent service for this.

It is important to parallelize Write Service servers and Cassandra nodes for scalability. Primary partition key should be ad ID. I think ad ID would probably have some locality (e.g. an ad would have a target country), so it would help keeping computation and storage in a geographic area that is close to users. But this causes a hot key problem if one ad is hugely popular. Therefore, we need a secondary key, perhaps client IP address, to distribute the load evenly. We will use consistent hashing algorithm to make sure load is distributed evenly among the nodes.

At first, I would have Writer Server write directly to Cassandra. If it turns out that Cassandra cannot keep up with the number of writes coming in, we would introduce a message queue between Writer Server and Cassandra to absorb bursty traffic. We should measure performance before doing this optimization.

Context Mapping service receives client data (e.g. IP address, browser string, cookies) to try to understand what kind of user the click belongs to (e.g. age, gender, preferences). Aggregation Service uses Context Mapping Service to link a click to such information.

Because there will be billions of clicks, Aggregation service does not want to go to Context Mapping Service for each click. Therefore, once it reads the mapping information from Context Mapping Service, it stores the information in Redis Cache. For subsequent clicks from the same user, it would get this information from the cache. The cache entry should expire in some time, e.g., 10 minutes.

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

I would like to think more about aggregation.

Basically Aggregation Service's to count up.

1. For every click (e.g. at 10:00, user clicked Nike shoes ad)
2. Identify the contextual information of this click (e.g. user's age is 40-45, gender is male, etc.)
3. Increase the number associated with category in a specified time unit (time 10:00, age group 40-45 gets an increase, and gender group male gets in increase).

The resulting data structure is not huge. So it should be stored in Redis Cache for quick read & write access.

Read Service reads this data from Redis Cache.

Trade offs/Tech choices

Should Aggregation Service execute an algorithm described above on every single click? Or should it act on a summary?

Executing it on every click would be beneficial in giving a real time update for the advertiser. It is one of the requirements.

Therefore, I would design:

• Write Service to write a message in Message Queue
• Aggregation Service pulls a message from the Message Queue, and runs aggregation algorithm.

Failure scenarios/bottlenecks

It is possible for Write Service to succeeds to write to Cassandra, but fails to write to Message Queue, introducing inconsistency.

However, I would NOT try to make the write to Cassandra and write to the Message Queue atomic (e.g. by 2 phase commit or by Change Data Capture). Instead, I would monitor if Message Queue is missing any messages from Write Server. If the error rate is low (e.g. less than 0.1%), I think it is acceptable, and this is a good choice to maintain high write throughput.

Future improvements

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