Design a Rate Limiting for Twitter/X

Question

Design a distributed 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 rate limits per user on actions such as posting tweets, liking tweets, and following accounts. 
2. **Global Limits**: Apply global rate limits to prevent abuse of the API, e.g., maximum requests per second across the platform.
3. **Dynamic Rate Limits**: Allow rate limits to adapt based on user behavior (e.g., higher limits for verified users).

### Non-Functional Requirements:
1. **Scalability**: The system should handle millions of requests per second, especially during peak usage times.
2. **Low Latency**: Rate limiting checks should occur with minimal delay, ideally under 10ms.
3. **High Availability**: The system should be operational 99.99% of the time, ensuring no downtime for rate limiting.
4. **Fault Tolerance**: The system should gracefully handle failures and provide consistent behavior.
5. **Real-Time Monitoring**: Provide dashboards for monitoring rate limit usage and alerting on abuse patterns.

To estimate the capacity:
- **Active Users**: Assume Twitter/X has approximately 400 million monthly active users.
- **Requests per User**: On average, each user makes about 10 requests per hour (likes, tweets, follows).
- **Total Requests per Second (QPS)**: 
  - Total requests per hour = 400 million users * 10 requests/user = 4 billion requests/hour.
  - Total requests per second = 4 billion requests/hour / 3600 seconds/hour ≈ 1.11 million QPS.

### Storage Estimate:
- If we maintain logs of rate limit usage per user for analytics, storing 1KB per user per day would require:
  - 400 million users * 1 KB/user/day = 400 GB/day.
- For a year's worth of data, approximately 146 TB would be needed.

### Components:
1. **API Gateway**: Handles incoming requests and forwards them to the rate limiting service.
2. **Rate Limiting Service**: Core service responsible for checking and enforcing rate limits using in-memory data stores.
3. **In-Memory Data Store**: Utilize Redis for fast access to user rate limit counters and configurations.
4. **Database**: Use PostgreSQL for persistent storage of user profiles, rate limit configurations, and abuse reports.
5. **Monitoring Service**: Utilize Prometheus and Grafana for real-time monitoring and alerting.
6. **Load Balancer**: Distributes incoming traffic evenly across multiple instances of the rate limiting service to ensure scalability.

### Technology Choices:
- **API Gateway**: NGINX or AWS API Gateway
- **In-Memory Store**: Redis
- **Database**: PostgreSQL
- **Monitoring**: Prometheus, Grafana
- **Load Balancer**: AWS Elastic Load Balancer

### User Rate Limit Schema:
```sql
CREATE TABLE user_rate_limits (
    user_id BIGINT PRIMARY KEY,
    action_type VARCHAR(50),  -- e.g., 'tweet', 'like', 'follow'
    request_count INT DEFAULT 0,
    last_request_time TIMESTAMP,
    rate_limit INT  -- max requests allowed per time window
);
```

### Access Patterns:
- **Reads**: Check current count and last request time to decide if the action can proceed.
- **Writes**: Increment the request count and update the last request timestamp. 
- **Indexes**: Index on `user_id` and `action_type` for quick lookups.

### Consistency vs. Availability:
- Opt for eventual consistency for user rate limit updates to ensure high availability. This means that there might be a slight delay in reflecting the latest request counts, especially during high traffic.

### Caching vs. Persistence:
- Use Redis for caching rate limits for fast access, but also persist the latest counts and configurations in PostgreSQL to handle server restarts and failures.

### Load Distribution:
- Implement sharding based on user ID to distribute the load evenly across multiple Redis instances, ensuring no single point of failure and improved performance.

### Dynamic Rate Limits:
- Implement logic to dynamically adjust rate limits based on user behavior, which introduces complexity but improves user experience for active users.

Design a Rate Limiting for Twitter/X

Twitter/X

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

Twitter/X 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