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 Policy**: The service must support multiple rate limiting strategies, such as fixed window, sliding window, and token bucket.
2. **User Authentication**: Each request must be associated with a user or IP address for tracking limits.
3. **Real-time Monitoring**: The service should provide real-time metrics on rate limit usage and violations.
4. **Configuration Management**: Allow dynamic updates to rate limits without downtime.

### Non-Functional Requirements
1. **Scalability**: The service must handle millions of requests per second.
2. **Low Latency**: Responses to requests should be under 50 milliseconds.
3. **High Availability**: The service must be available 99.99% of the time.
4. **Data Persistence**: Rate limit data should be persisted for at least 30 days for audit and analysis purposes.

### Back-of-Envelope Calculations
1. **User Base**: Assume Shopify has around 1 million active merchants.
2. **Request Rate**: Each merchant generates about 100 requests per second on average during peak hours.
3. **Total QPS**: $1,000,000 \text{ merchants} \times 100 \text{ requests/second} = 100,000,000 \text{ requests/second (QPS)}$
4. **Data Storage**: Assume storing rate limit data for 30 days. If we store 1KB per user per request, we need:
   - $100,000,000 \text{ requests/second} \times 86400 \text{ seconds/day} \times 30 \text{ days} \times 1 \text{ KB} = 2592 \text{ TB} \text{ total storage required}$

### Component Diagram
- **API Gateway**: Handles incoming requests and routes them to the rate limiting service.
- **Rate Limiting Service**: Core service that enforces rate limits using a microservices architecture. Implemented in Node.js for efficient I/O operations.
- **Redis (or Memcached)**: Used for in-memory storage of rate limit counters for fast access. Supports TTL for automatic expiration.
- **PostgreSQL**: Used for persistent storage of rate limiting configurations and user data. Provides strong consistency for configuration management.
- **Monitoring Service**: Uses Prometheus and Grafana for tracking metrics and alerting on anomalies in request patterns.

### Schema Design
1. **Users Table**
   - `user_id` (Primary Key, UUID)
   - `api_key` (Unique, String)
   - `rate_limit` (Integer)
   - `created_at` (Timestamp)

2. **Rate Limit Counters (in Redis)**
   - Key: `rate_limit:<user_id>`
   - Value: Count of requests made in the current time window.
   - Expiration: Set to the length of the rate limit window (e.g., 1 minute).

### Access Patterns
- Frequent reads to check counters in Redis.
- Occasional writes to update counters and configurations in PostgreSQL.

### Architectural Decisions
1. **Consistency vs. Availability**: Opted for eventual consistency with Redis for performance, as immediate consistency is not critical for rate limits. This allows the service to handle spikes in request rates.
2. **Caching Strategy**: Using Redis allows for efficient in-memory access but introduces the risk of data loss during failures. However, this is mitigated with periodic synchronization to PostgreSQL.
3. **Scaling**: Chose a microservices architecture to allow independent scaling of the Rate Limiting Service based on load, rather than a monolithic design.
4. **Failure Handling**: Implement circuit breakers and retries for downstream services to ensure resilience. Use of distributed tracing for monitoring request paths to identify failure points.

Design a Rate Limiting Service

Shopify

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

Back-of-Envelope Calculations

Submit Your Answer

Shopify 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