Design a large-scale Rate Limiting Platform

Question

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

Codemia · Accepted Answer

### Functional Requirements
1. **Rate Limiting Policies**: Support various rate limiting strategies (e.g., per user, per IP, per application).
2. **Dynamic Configuration**: Ability to change rate limits in real-time without downtime.
3. **Monitoring and Reporting**: Provide metrics on usage, including hits, remaining requests, and blocked requests.
4. **Authentication**: Integrate with Snapchat's existing user authentication system to identify users and their associated rate limits.

### Non-Functional Requirements
1. **Scalability**: Must handle millions of requests per second (QPS) effectively.
2. **Low Latency**: Response time for rate limiting checks should be under 10ms.
3. **High Availability**: System should be available 99.99% of the time.
4. **Consistency**: Eventual consistency is acceptable for rate limits to allow for dynamic updates in a distributed system.

Assuming Snapchat has approximately 500 million daily active users (DAUs). If each user generates about 10 requests per minute on average:

- **Total Requests per Day**: 500 million * 10 requests/minute * 1440 minutes = 72 trillion requests/day.
- **Peak QPS Calculation**: Assuming peak traffic is 20% of daily traffic, we can estimate:
  - 72 trillion requests/day * 0.2 = 14.4 trillion requests/peak period (approximately 5 hours).
  - Peak QPS = 14.4 trillion / (5 * 3600) = ~800,000 requests/second.
- **Storage Needs**: Each rate limit configuration might take up to 1 KB. If we have 1 million unique rate limit configurations:
  - Required Storage = 1 million * 1 KB = ~1 GB for configs.

### Component Diagram
- **API Gateway**: Route incoming requests to the appropriate rate limiting service.
- **Rate Limiting Service**: Core service responsible for applying rate limiting policies. Scales horizontally based on load.
- **Distributed Cache (Redis)**: Used for fast lookups of rate limits and storing usage counts. Can handle high throughput.
- **Database (Cassandra)**: Stores persistent rate limit configurations and user data for long-term storage.
- **Monitoring Service (Prometheus + Grafana)**: Collects metrics and logs from the Rate Limiting Service and other components.
- **Load Balancer**: Distributes traffic evenly across multiple instances of the Rate Limiting Service.

### Schema Design
1. **User Rate Limit Table** (Cassandra)
   - `user_id (PK)` (UUID): Unique identifier for the user.
   - `limit` (INT): Maximum requests allowed.
   - `reset_time` (TIMESTAMP): When the limit resets.
   - `current_count` (INT): Current count of requests made.

2. **Rate Limiting Policy Table**
   - `policy_id (PK)` (UUID): Unique identifier for the policy.
   - `policy_type` (STRING): Type of rate limiting (user, IP, app).
   - `max_requests` (INT): Max requests allowed.
   - `time_window` (INT): Time window for the limit in seconds.

### Architectural Decisions
1. **Consistency vs. Availability**: Given the need for real-time rate limiting, we prioritize availability over strong consistency. Using a distributed cache allows for quick checks, but may lead to stale data.
2. **Caching Strategy**: Chose Redis as a distributed cache due to its high performance and ability to handle rapid reads/writes. However, this introduces potential cache invalidation issues, which must be managed carefully.
3. **Database Choice**: Cassandra provides excellent write performance and horizontal scalability, making it a good fit for storing rate limit configurations, but comes with eventual consistency trade-offs.
4. **Load Balancing**: Utilizing a load balancer ensures that the rate limiting service can scale horizontally, but it also adds a single point of failure unless configured with redundancy.

Design a large-scale Rate Limiting Platform

Snapchat

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

Snapchat 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