Architect a geo-distributed Rate Limiting Engine

Question

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

Codemia · Accepted Answer

### Functional Requirements
1. **Request Tracking**: Track incoming requests per user per second across multiple geographic regions.
2. **Rate Limiting Policies**: Implement configurable rate limiting policies based on user role, region, and request type.
3. **Real-time Dashboard**: Provide a real-time dashboard for monitoring request rates and system performance metrics.
4. **Alerts and Notifications**: Trigger alerts when limits are approached or exceeded.

### Non-Functional Requirements
1. **Scalability**: Must handle millions of requests per second with low latency.
2. **Availability**: System must be highly available (99.99%) across geo-distributed locations.
3. **Consistency**: Eventual consistency is acceptable for rate limits but must ensure accuracy for user notifications.
4. **Latency**: Average request latency must remain under 100ms.

Assuming Booking.com handles approximately 10 million users daily, with each user making an average of 10 requests per minute:
1. **Requests per Second (RPS)**: 
   - Total requests = 10M users * 10 requests/minute = 100M requests/minute.
   - RPS = 100M / 60 = ~1.67M requests per second.
2. **Geo-Distribution**: If we consider 3 geo-regions (e.g., US, EU, Asia), we can distribute the load:
   - RPS per region = 1.67M / 3 = ~556K requests per second.
3. **Data Storage**: Assuming each request requires 1 KB of data for tracking, we would need about 1.67 TB of storage per day.

### Component Diagram
- **API Gateway**: NGINX or AWS API Gateway handling incoming requests.
- **Rate Limiting Service**: Custom microservice built in Go, utilizing a Redis cluster for in-memory rate tracking.
- **Database**: Cassandra for storing user request data with geo-distributed nodes.
- **Monitoring Tool**: Prometheus for real-time metrics and Grafana for dashboarding.
- **Notification Service**: AWS SNS for alerting users when limits are exceeded.

### Technology Choices
- **Redis**: For quick access and low-latency rate tracking.
- **Cassandra**: To ensure high availability and partition tolerance across geo-distributed locations.

### Schema Design
1. **User Requests Table** (Cassandra):
   - `user_id` (PK)
   - `region` (Clustering Key)
   - `request_type` (Clustering Key)
   - `timestamp` (Clustering Key)
   - `request_count` (Counter)

### Access Patterns
- **Query by User**: Retrieve request counts for a specific user in a region.
- **Query by Region**: Aggregate request counts across regions for dashboard metrics.

1. **Consistency vs Availability**: Opting for eventual consistency in user request tracking allows for higher availability across geo-distributed nodes but may lead to temporary inaccuracies in rate limits.
2. **Complexity vs Latency**: Integrating machine learning for predictive rate limiting adds complexity but can significantly optimize user experience by preemptively adjusting limits based on usage patterns. However, this may increase latency.
3. **Real-time vs Batch Processing**: Real-time processing ensures immediate feedback to users but requires more robust infrastructure; batch processing can reduce load but may delay user notifications.

Architect a geo-distributed Rate Limiting Engine

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