Design a Rate Limiting Service

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**: Implement rate limiting based on client IP, user ID, or API key with configurable limits (e.g., 100 requests per minute).
2. **Burst Handling**: Allow short bursts above the limit, with a cooldown period to smooth traffic.
3. **Monitoring and Reporting**: Provide real-time metrics on usage, limits, and violations.
4. **Dynamic Configuration**: Enable the ability to change rate limits without downtime.

### Non-Functional Requirements:
1. **Scalability**: Support millions of requests per second with horizontal scaling.
2. **Low Latency**: Achieve response times under 100ms for rate limit checks.
3. **High Availability**: Ensure the service is available 99.99% of the time across multiple regions.
4. **Consistency**: Provide eventual consistency for dynamic configurations to minimize downtime.

Assuming Booking.com handles 50 million unique users per day and each user makes an average of 100 requests per day:
- **Daily Requests**: 50M users * 100 requests = 5 billion requests per day.
- **Requests per Second**: 5 billion requests / 86400 seconds = approximately 58,000 requests per second.
- **Rate Limiting Storage**: Assuming each user’s rate limit state (e.g., timestamps of requests) requires 100 bytes, we’d need around 5 billion * 100 bytes = 500 GB of storage.
- **Cache Needs**: If we aim for 90% cache hit ratio, we’d need to cache 450M user states, roughly 45 GB in memory assuming a similar size per entry.

### Component Diagram:
- **API Gateway**: Use NGINX or AWS API Gateway for initial request handling and routing.
- **Rate Limiting Service**: Implement using a microservice architecture with Node.js or Go for performance.
- **Data Store**: Redis for in-memory caching of rate limits; MongoDB for persistent storage of user limits and configurations.
- **Load Balancer**: Use AWS ELB to distribute requests across multiple instances of the Rate Limiting Service.
- **Monitoring**: Use Prometheus and Grafana for metrics and alerts.

### Deployment Strategy:
- Deploy in multiple AWS regions (e.g., us-east-1, eu-west-1) to ensure low latency and high availability.

### Rate Limiting Schema:
1. **User Rate Limits Table** (MongoDB):
   - `user_id` (String, Index)
   - `api_key` (String, Index)
   - `rate_limit` (Int)
   - `request_count` (Int)
   - `last_request_time` (Date)

2. **Request Log** (Redis):
   - Key: `user_id:timestamp`
   - Value: `request_data (JSON)`

### Access Patterns:
- For checking rate limits, query the User Rate Limits Table. If the user exceeds the limit, log the request in Redis for burst management.

1. **Consistency vs. Availability**: Opting for eventual consistency allows for quicker updates to rate limits but may lead to temporary discrepancies in user limits. This is acceptable given the high request volume and the need for scalability.
2. **Memory vs. Persistence**: Using Redis for rate limiting allows for fast access but risks losing state during failures. Implement a periodic backup to MongoDB to mitigate this risk.
3. **Latency vs. Throughput**: By allowing bursts temporarily, we can maintain throughput but may see higher latency during peak usage. This requires careful monitoring and tuning of the burst limits.

Design a Rate Limiting Service

Booking.com

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

Booking.com 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