Design an API Rate Limiter

Question

Design a distributed rate limiting system. Compare token bucket, sliding window, and fixed window algorithms. Cover distributed coordination, race conditions, and how to handle rate limiting across multiple data centers.

Codemia · Accepted Answer

### Functional Requirements
1. **Rate Limiting**: The API should limit the number of requests a user can make within a specified time period (e.g., 100 requests per minute).
2. **User Identification**: Rate limits should be applied per user or per API key.
3. **Granular Control**: Ability to set different limits for different API endpoints.
4. **Monitoring and Alerts**: Provide metrics on request counts and limit breaches.

### Non-Functional Requirements
1. **Scalability**: The system should scale horizontally to handle increased traffic and more users.
2. **Low Latency**: Rate limiting decisions should be made with minimal delay (ideally < 10ms).
3. **High Availability**: The system should remain available even in the event of a partial failure.
4. **Consistency**: Rate limits should be consistent across multiple data centers.

Assuming Meta has approximately 2 billion active users and an average of 5 API calls per user per day:

1. **Total API Calls**: 
   - Daily: 2 billion users * 5 calls/user = 10 billion calls/day
   - Hourly: 10 billion calls / 24 hours ≈ 416 million calls/hour
   - Per second: 416 million calls / 3600 seconds ≈ 115,000 calls/second

2. **Rate Limit Configuration**: If we limit users to 100 requests/minute:
   - This means each user could theoretically make 1.67 requests per second.
   - With 2 billion users, the max theoretical load could reach 3.34 billion requests/second, necessitating efficient rate limiting mechanisms.

### Component Diagram
![Rate Limiter Architecture](https://example.com/rate_limiter_architecture.png)

1. **API Gateway**: Initial entry point for all API requests, responsible for routing.
2. **Rate Limiter Service**: Core service implementing the rate limiting logic using a token bucket algorithm for its flexibility and efficiency in burst traffic.
3. **Redis Cluster**: Used for shared state across distributed services, ensuring fast access to rate limit counters and user state.
4. **Monitoring Service**: Collects metrics and logs from the rate limiter and API gateway to provide real-time analytics and alerting.
5. **Data Centers**: Distributed across multiple geographic regions, ensuring low latency and redundancy.

### Rate Limiter Schema
1. **UserRateLimit** Table:
   - `user_id` (string): Unique identifier for the user
   - `api_key` (string): API key associated with the user
   - `endpoint` (string): API endpoint being accessed
   - `request_count` (int): Current count of requests made in the current time window
   - `last_request_timestamp` (timestamp): Last request time to calculate remaining limits
   - `limit` (int): Rate limit for the user for this endpoint
   - `reset_time` (timestamp): Time when the count resets

This schema allows for quick access and updates to the rate limit state for each user and endpoint.

1. **Token Bucket vs. Sliding Window**: 
   - Chose Token Bucket for its ability to smooth out bursts of traffic while providing a consistent average rate limit. Sliding Window could lead to more complex calculations and storage overhead.
2. **Redis for State Management**: 
   - Using Redis provides fast access and is well-suited for counters. However, it introduces a single point of failure and latency in distributed scenarios, which we mitigate through Redis clustering.
3. **Data Center Coordination**: 
   - Implementing a distributed coordination mechanism using Redis to maintain state consistency across data centers, which helps avoid race conditions but adds latency due to network calls.
4. **Trade-off Between Consistency and Availability**: 
   - Opting for eventual consistency for user rate limits to enhance availability, knowing that the system can tolerate minor discrepancies in request counts.

Design an API Rate Limiter

Meta

How to Approach This

Sharpen Your Skills on Codemia

Sample Answer

Requirements

Functional Requirements

Capacity Estimation

Submit Your Answer

Meta 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