Design a geo-distributed Rate Limiting System

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. **Rate Limiting**: The system must limit the number of requests from a single user to prevent abuse, with configurable limits per endpoint.
2. **Geo-Distribution**: The system should handle requests from different geographical locations and apply different rate limits based on local regulations or policies.
3. **Real-time Monitoring**: Provide real-time metrics and alerts on request rates, breaches, and performance.
4. **Integration with Existing Systems**: Seamlessly integrate with Zillow’s existing API infrastructure and user authentication systems.

### Non-Functional Requirements
1. **Scalability**: The system should support up to 10 million requests per second during peak times.
2. **Low Latency**: The system must respond to requests within 100 milliseconds.
3. **Availability**: The system should have 99.99% uptime.
4. **Consistency**: Strong consistency is required for rate limit enforcement across distributed nodes.

To estimate capacity, consider the following:
- **Peak Requests**: Assume 10 million requests per second at peak.
- **Geo-Distribution**: Spread across 5 regions (e.g., US East, US West, Europe, Asia, and Australia).
- **User Base**: Assume 100 million active users.

### Calculation
- Each region needs to handle 2 million requests per second.
- If each request requires an average of 10 ms processing time, we need to ensure that our servers can handle 1000 requests per second per server.
- Therefore, each region would require at least 2000 servers at peak capacity, assuming a 50% buffer for redundancy and failover.

### Component Diagram
1. **API Gateway**: Handles incoming requests and routes them to the appropriate service.
2. **Rate Limiting Service**: Central service responsible for enforcing rate limits, utilizing Redis for fast in-memory data storage.
3. **Geo-Distributed Cache**: Using a CDN like Cloudflare to cache rate limit information regionally to reduce latency.
4. **Monitoring and Analytics**: A tool like Prometheus for metrics collection and Grafana for visualization.
5. **Database**: Use a distributed NoSQL database like Cassandra for user data and rate limit configurations, ensuring high availability and scalability.

### Technology Choices
- **API Gateway**: AWS API Gateway
- **Rate Limiting**: Redis with Lua scripting
- **Monitoring**: Prometheus and Grafana
- **Database**: Apache Cassandra

### Schema Design
1. **User Table**: Contains user identifiers, geographical location, and current request counts.
   - `user_id` (UUID): Primary Key
   - `geo_region` (String): Geographical region
   - `request_count` (Integer): Number of requests in the current window
   - `last_request_time` (Timestamp): Last request timestamp

2. **Rate Limit Table**: Configurations for different endpoints and user types.
   - `endpoint` (String): API endpoint
   - `user_type` (String): e.g., Free, Premium
   - `limit` (Integer): Number of requests allowed
   - `time_window` (Integer): Time window for the limit in seconds

### Access Patterns
- Frequent reads for checking user limits and counts, infrequent writes for updating limits.

### Architectural Decisions
1. **Consistency vs. Availability**: Opt for eventual consistency in user request counts to ensure high availability across geo-distributed nodes. This helps in maintaining performance under high load.
2. **Rate Limiting Granularity**: Choose user-level rate limiting over IP-level to prevent abuse from shared IPs while accommodating different user tiers (free vs. premium).
3. **Data Freshness vs. Latency**: Utilize a caching layer to serve rate limit data quickly, accepting potential staleness in favor of reduced latency for end-users.
4. **Experimentation and A/B Testing**: Implement feature flags to enable A/B testing of different rate-limiting strategies, allowing for iterative improvements in the system.

Design a geo-distributed Rate Limiting System

Zillow

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

Zillow 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