Design a Rate Limiting for Expedia

Question

Design a event-driven rate limiting system that handles millions of requests. Discuss trade-offs in consistency, availability, and performance.

Codemia · Accepted Answer

### Functional Requirements:
1. **Rate Limiting**: The system should enforce rate limits on API calls to ensure that no user or service can exceed a defined number of requests per minute.
2. **Event-Driven Architecture**: The system must respond to requests in real-time using an event-driven model to ensure low latency.
3. **Multi-Tenancy**: Support rate limits for multiple clients (e.g., external partners, internal services) with different configurations.

### Non-Functional Requirements:
1. **Scalability**: Must handle millions of requests per second without degradation in performance.
2. **Fault Tolerance**: The system should remain operational even under partial failures.
3. **Global Availability**: The system should provide low-latency access globally, deploying across multiple regions.
4. **Monitoring and Alerting**: Implement logging and monitoring to track usage patterns and alert on unusual spikes in traffic.

Assuming Expedia handles about 10 million API requests per day:
- **Peak Load**: Let's estimate peak traffic at 100 requests per second (rps).
- **Rate Limit**: If we apply a rate limit of 100 requests per minute per user, we can estimate the number of active users.
- **Active Users**: Assuming an average of 5 requests per user per minute, this implies up to 1,200 concurrent users.

### Storage Needs:
- **Event Store**: Each request could generate logs of around 1KB. If we track the last 30 days of requests, this results in:
  - 10M requests/day * 30 days * 1KB = ~300GB of storage.

This estimation informs our storage and database design choices.

### Component Diagram:
1. **API Gateway**: Acts as a single entry point for clients, forwarding requests.
2. **Rate Limiter Service**: Centralized service implementing rate limiting logic.
   - **Technology**: Redis for in-memory data storage to track request counts efficiently.
3. **Event Queue**: Kafka for event-driven processing, allowing asynchronous handling of requests.
4. **Monitoring Service**: Prometheus for metrics collection and Grafana for visualization.
5. **Data Store**: A NoSQL database like DynamoDB for persistent storage of user request data and limits.

### Deployment:** Multi-region deployment using AWS with auto-scaling for resilience and load balancing.

### Schema Design:
1. **User Request Log Table**:
   - **user_id** (String) - Unique user identifier.
   - **timestamp** (DateTime) - Request timestamp.
   - **request_type** (String) - Type of request made (e.g., search, booking).
   - **count** (Integer) - Number of requests made by the user.

2. **Rate Limit Configuration Table**:
   - **user_id** (String) - Unique user identifier.
   - **limit** (Integer) - Maximum allowed requests per minute.
   - **window_start** (DateTime) - Start of the current rate limit window.

### Access Patterns:
- Frequent reads for current rate limits and logs, necessitating fast read capabilities.

### Architectural Decisions:
1. **Consistency vs. Availability (CAP Theorem)**: Prioritize availability and partition tolerance since rate limiting needs to remain operational during network partitions, accepting eventual consistency in user request counts.
2. **In-Memory vs. Persistent Storage**: Using Redis for fast access but ensuring eventual consistency with a fallback to a persistent store (DynamoDB) for recovery and audit.
3. **Monitoring vs. Performance**: Implementing monitoring tools (Prometheus) adds overhead; however, it is essential for operational visibility and alerting on anomalies.

### Phased Rollout Plan:
1. **MVP**: Launch a basic rate limiting service with a single region deployment and minimal monitoring.
2. **Phase 2**: Add multi-region support and enhanced logging.
3. **Phase 3**: Introduce custom limits per user and advanced alerting mechanisms.

Design a Rate Limiting for Expedia

Expedia

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

Submit Your Answer

Expedia 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