Design a Rate Limiting for Reddit

Question

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

Codemia · Accepted Answer

### Functional Requirements
1. **Rate Limiting**: Implement individual rate limits for each user or API key based on predefined limits (e.g., 100 requests per minute).
2. **Multi-Tenant Support**: Support rate limiting across different subreddits and user tiers (e.g., regular users, premium users).
3. **Granularity**: Ability to set different rate limits for different endpoints (e.g., posting vs. commenting).
4. **Admin Dashboard**: Provide an interface for admins to adjust rate limits dynamically.
5. **Alerts**: Notify users when they are approaching their rate limits.

### Non-Functional Requirements
1. **Scalability**: System must handle millions of requests per second (QPS) efficiently.
2. **Low Latency**: Rate limiting checks should add minimal latency to user requests (ideally <10ms).
3. **High Availability**: Ensure system availability of 99.99%.
4. **Consistency**: Rate limits should be consistent across all servers to prevent abuse.
5. **Monitoring & Logging**: Capture metrics and logs for rate limiting events and performance.

### Back-of-Envelope Calculations
1. **User Base**: Assume 50 million active users on Reddit.
2. **Requests Per User**: Average of 10 requests per minute per user.
3. **Total Requests**: 
   - Total QPS = 50,000,000 users * 10 requests/minute / 60 seconds = ~8,333,333 requests/second.
4. **Rate Limit Events**: Assume 1% of the requests will trigger a rate limit check, which means we need to handle ~83,333 rate limit checks per second.
5. **Data Storage**: If we store rate limit data for 50 million users for a period of 30 days, 
   - Assuming each entry takes 64 bytes, total storage = 50,000,000 users * 30 days * 24 hours * 60 minutes * 60 seconds * 1 check/minute * 64 bytes = ~2.5 TB.

### Component Diagram
- **API Gateway**: Acts as the entry point for all requests, performing initial filtering and routing.
- **Rate Limiting Service**: A dedicated microservice responsible for checking and enforcing rate limits. Scalable with horizontal pods behind a load balancer (e.g., Kubernetes).
- **Redis Cache**: Used for fast access to rate limiting data, allowing quick reads/writes to store user request counts.
- **Database (e.g., PostgreSQL)**: For persistence of rate limit configurations and historical data.
- **Message Queue (e.g., RabbitMQ)**: For processing asynchronous notifications to users when limits are reached and for logging events.
- **Monitoring & Alerting (e.g., Prometheus + Grafana)**: To track performance and health metrics of the rate limiting system.

### Schema Design
1. **User Rate Limits Table**:
   - `user_id`: String (Primary Key)
   - `endpoint`: String (e.g., /post, /comment)
   - `request_count`: Integer
   - `reset_time`: Timestamp (when the limit resets)
   - **Indexes**: On `user_id` and `endpoint` for fast lookups.

2. **Rate Limit Configuration Table**:
   - `endpoint`: String (Primary Key)
   - `limit_per_minute`: Integer
   - `user_tiers`: JSON (e.g., {"regular": 100, "premium": 200})
   - **Indexes**: On `endpoint` for quick retrieval.

3. **Rate Limit History Table**:
   - `user_id`: String
   - `endpoint`: String
   - `timestamp`: Timestamp
   - `status`: String (e.g., "allowed", "blocked")
   - **Indexes**: On `user_id` and `timestamp` for analytics.

### Architectural Decisions
1. **Caching vs. Database**: Using Redis for caching rate limits provides speed but risks eventual consistency if not properly managed; the database ensures consistency but introduces latency.
2. **Consistency vs. Availability**: Opting for eventual consistency in rate limits can improve availability but could lead to temporary over-usage. Immediate consistency ensures that limits are enforced strictly but can lead to higher latency.
3. **Synchronous vs. Asynchronous Processing**: Choosing to process rate limit notifications asynchronously improves user experience by reducing immediate response time, but it complicates the failure handling mechanism.
4. **Horizontal Scaling vs. Vertical Scaling**: Implementing a microservices architecture allows for horizontal scaling of the rate limiting service but adds complexity in managing multiple instances and state across servers.

Design a Rate Limiting for Reddit

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