Architect a high-throughput Ad Serving Engine

Question

Design a high-throughput ad serving system that handles millions of requests. Discuss trade-offs in consistency, availability, and performance.

Codemia · Accepted Answer

### Functional Requirements
1. **Ad Serving**: The system must serve ads based on user targeting criteria (demographics, interests, etc.) in real-time.  
2. **Ad Inventory Management**: Ability to manage ad campaigns, including creating, updating, and deleting ads.  
3. **Metrics Tracking**: Collection of metrics such as impressions, clicks, and conversions for reporting purposes.  
4. **User Interaction Logging**: Log user interactions with ads for optimization and analytics.

### Non-functional Requirements
1. **High Throughput**: The system should handle up to 1 million requests per second.  
2. **Low Latency**: Response time for ad serving should be less than 100 ms.  
3. **Scalability**: The architecture must support horizontal scaling to accommodate increased load.  
4. **Reliability**: The system should have a 99.9% uptime guarantee.  
5. **Data Consistency**: Eventual consistency is acceptable for ad inventory, but strong consistency is required for user interaction logging.

### Back-of-Envelope Calculations
1. **Estimated QPS**:  
   - Assume Reddit has 500 million daily active users.  
   - If each user makes 4 requests for ads on average, that results in:  
     $ 500,000,000 \text{ users} \times 4 \text{ requests/user} = 2,000,000,000 \text{ requests/day} $  
   - This translates to approximately 23,148 requests per second (QPS).

2. **Data Storage Needs**:  
   - Assume each ad has an average size of 1 KB and we expect to store 1 million ads.  
   - Total size: 1,000,000 ads * 1 KB = 1 GB.  
   - Metrics storage (impressions, clicks): If we log 1 event per ad served, that could lead to 2 billion logs per day = 25 GB/day.

3. **Bandwidth Requirements**:  
   - If each ad response is roughly 2 KB, the bandwidth required for serving ads would be:  
     $ 23,148 \text{ QPS} \times 2 \text{ KB} \times 3600 \text{ seconds} = 168.5 \text{ GB/hour} $  
   - This translates to around 4 TB/day.

### Component Diagram
- **Load Balancer**: Distributes incoming requests across multiple Ad Servers.  
- **Ad Servers**: Handle business logic for ad serving, querying ads based on user context.  
- **Cache Layer**: A distributed cache (e.g., Redis) to cache frequently accessed ad data for low-latency responses.  
- **Database**: Use a NoSQL database (e.g., Amazon DynamoDB) for storing ad inventory and user interactions.  
- **Analytics Processor**: A Kafka stream processor to handle logging and metrics collection asynchronously.  
- **CDN**: Content Delivery Network for serving static ad assets quickly.

### Technology Choices
- **Load Balancer**: NGINX or AWS ALB.  
- **Ad Servers**: Node.js or Go for high concurrency handling.  
- **Cache Layer**: Redis for in-memory caching.  
- **Database**: Amazon DynamoDB for scalability and performance.  
- **Message Queue**: Apache Kafka for handling asynchronous logging.

### Schema Design
1. **Ad Inventory Table** (DynamoDB)
   - **AdID** (Partition Key)  
   - **CampaignID**  
   - **TargetingCriteria** (JSON)  
   - **AdContent** (URL)  
   - **Status** (Active/Inactive)

2. **User Interaction Log Table** (DynamoDB)
   - **LogID** (Partition Key)  
   - **UserID**  
   - **AdID**  
   - **InteractionType** (Impression/Click)  
   - **Timestamp**

3. **Analytics Metrics** (Time-series data in a Data Lake)
   - **AdID**  
   - **Timestamp**  
   - **Impressions**  
   - **Clicks**

### Access Patterns
- The Ad Inventory table is frequently accessed for ad serving based on targeting criteria, hence the need for a highly available NoSQL database.

### Architectural Decisions
1. **Consistency vs Availability**:  
   - Chose eventual consistency for ad inventory updates to ensure high availability, allowing ads to be served even if some updates are not immediately reflected.  
   - Strong consistency for user interaction logging to ensure accurate metrics.

2. **Caching Strategy**:  
   - Using a distributed cache (Redis) to minimize database calls and reduce latency. This introduces a trade-off of cache invalidation complexity.

3. **Database Choice**:  
   - Selected DynamoDB for its scalability and low-latency access patterns suitable for high throughput but trade off complex querying capabilities.

4. **Asynchronous Processing**:  
   - Using Apache Kafka for logging user interactions allows for decoupling of ad serving from analytics processing, but introduces eventual consistency in metrics reporting.

Architect a high-throughput Ad Serving Engine

Reddit

What the Interviewer Expects

Key Topics to Cover

How to Approach This

Possible Follow-up Questions

Practice a Similar Problem on Codemia

Sample Answer

Requirements

Functional Requirements

Capacity Estimation

Back-of-Envelope Calculations

Submit Your Answer

Reddit Software Engineer Interview Guide

Related Questions

Design a high-throughput Inventory Management System

Design a low-latency Rate Limiting System

Design a fault-tolerant Payment System

Design a fault-tolerant Messaging System

Design Walmart Product Search