System Design Problems
Design a Rate Limiter
A rate limiter controls the rate of requests a client can send to an API. It protects services from abuse, ensures fair resource usage, and prevents cascading failures. Systems like Cloudflare, AWS API Gateway, and Kong implement distributed rate limiting at massive scale.
- Protection â Prevent DoS attacks and API abuse
- Fairness â Ensure equitable resource allocation across clients
- Throttling â Gracefully degrade service under overload
A rate limiter sits between the client and the server, deciding whether to allow or reject each request based on the client's recent request history.
Requirements
Functional Requirements
- Limit requests per client per time window
- Support different rate limits per API endpoint
- Support different limits per client tier (free, pro, enterprise)
- Return HTTP 429 (Too Many Requests) when limit exceeded
- Provide rate limit headers in responses
- Support distributed rate limiting across multiple servers
Non-Functional Requirements
- Latency: Rate limit check in < 1ms
- Accuracy: Allow slight over-limit (within 1%) rather than blocking valid requests
- Availability: Rate limiter failure should fail open (allow requests)
- Scalability: Handle millions of clients and thousands of API endpoints
API Design
GET /api/v1/rate-limit/status
Response: {
"client_id": "user_123",
"limit": 1000,
"remaining": 742,
"reset_at": "2026-06-20T11:00:00Z",
"retry_after": 0
}
// Response headers
X-RateLimit-Limit: 1000
X-RateLimit-Remaining: 742
X-RateLimit-Reset: 1687267200
Retry-After: 30 // Seconds until next request allowed
Rate Limiting Algorithms
Token Bucket
Sliding Window Counter
Algorithm Comparison
| Algorithm | Memory | Accuracy | Burst Handling | Complexity |
|---|---|---|---|---|
| Token Bucket | O(1) | Good | Allows bursts | Simple |
| Sliding Window Log | O(n) | Exact | No bursts | Complex |
| Fixed Window | O(1) | Boundary issues | Allows bursts | Simplest |
| Sliding Window Counter | O(1) | Good | Smooth | Moderate |
Distributed Rate Limiting
Single vs Distributed
For single-server rate limiting, an in-memory counter suffices. For distributed systems, use Redis:
Race Condition Handling
In distributed systems, race conditions can allow more requests than the limit:
Practice Exercises
-
Design: How would you implement rate limiting that accounts for different API endpoint costs (e.g., a search query costs 5 units, a simple GET costs 1 unit)?
-
Distributed: If you have 10 API servers and a rate limit of 1000 requests/minute per client, what is the worst-case over-limit due to race conditions? How would you mitigate it?
-
Trade-offs: Compare token bucket and sliding window counter for an API that needs to support occasional bursts (10x normal rate for 5 seconds).
-
Edge Case: How would you handle rate limiting for a client that uses multiple IP addresses (e.g., behind a NAT)? Design a client identification strategy.
What to Learn Next
-> Rate Limiting Deep dive into rate limiting algorithms and distributed implementation.
-> Load Balancing Distributing requests across multiple API servers.
-> API Design REST conventions, error handling, and HTTP status codes.
-> Caching Strategies Redis caching patterns for distributed counters.
-> Proxy and Reverse Proxy Rate limiting at the proxy layer (nginx, Envoy).
-> Microservices Service mesh rate limiting and circuit breaking.