All blueprints
- 01 Terminology Glossary
- 02 Real-Time Chat (WhatsApp)
- 03 Video Streaming (YouTube)
- 04 Low-Latency Systems
- 05 Ordered Message Queues
- 06 URL Shortener
- 07 Rate Limiter
- 08 Notification System
- 09 News Feed
- 10 Offline Messaging
- 11 Circuit Breaker
- 12 Self-Healing Infrastructure
- 13 Scaling to 5M Users
- 14 Handling 5M Requests
- 15 End-to-End Encryption
- 16 Real-Time React Dashboard
- 17 Fast-to-Slow File Transfer
- 18 Ride-Hailing (Uber, Ola)
- 19 Ticket Booking (BookMyShow)
- 20 Unique ID Generator
Blueprint 07 · 2 diagrams
Design a Distributed Rate Limiter
Distributed rate limiter
1. Summary
A rate limiter controls how many requests a client can send in a time period. It protects services from overload and abuse. In a distributed system, many servers must share the same count.
2. Requirements
- Limit requests by user, by IP address, or by API key.
- Support different rules (for example, 100 requests per minute).
- Add less than 5 ms of latency.
- Return HTTP 429 when a client is over the limit.
- Continue to work if the rate limiter store fails (fail open or fail closed by configuration).
3. Architecture
flowchart LR
C["Client"] --> GW["API gateway"]
GW --> RL["Rate limiter middleware"]
RL --> R[("Redis cluster: counters")]
RL --> RC["Rules config"]
RL -- "allowed" --> S["Backend services"]
RL -- "rejected" --> E["HTTP 429 + Retry-After"]
4. Algorithms
| Algorithm | How it works | Advantage | Disadvantage |
|---|---|---|---|
| Fixed window | Count requests in each fixed minute. | Simple. Low memory. | A burst at the window edge can double the rate. |
| Sliding window log | Keep a timestamp for each request. | Exact. | High memory. |
| Sliding window counter | Combine the current and previous window counts with a weight. | Good accuracy. Low memory. | Approximate. |
| Token bucket | Add tokens at a fixed rate. Each request uses one token. | Allows short bursts. | Two values to tune. |
| Leaky bucket | Process requests from a queue at a fixed rate. | Smooth output. | Bursts wait in the queue. |
Recommended: token bucket. AWS, Stripe, and many API gateways use it.
5. Token bucket
flowchart TB
RF["Refill: R tokens per second"] --> B[("Bucket: max B tokens")]
REQ["Request"] --> CH{"Token available?"}
B --> CH
CH -- "Yes: remove 1 token" --> OK["Allow"]
CH -- "No" --> NO["Reject 429"]
Procedure
- Read
tokensandlast_refill_timefor the key. - Calculate the new tokens:
elapsed × rate. - Add the new tokens. Do not go more than the bucket size.
- If
tokens ≥ 1, remove one token and allow the request. - If not, reject the request.
- Save the new values.
Do steps 1 to 6 in one Redis Lua script. Then the operation is atomic. Two servers cannot use the same token.
6. Distributed problems
- Race conditions: Use atomic Redis scripts.
- Latency: Keep a small local counter. Sync with Redis at intervals. This is less exact but faster.
- Many regions: Use a local limit in each region. Or accept approximate global limits.
7. Interview follow-up questions
- Where do you put the rate limiter: client, gateway, or service?
- What happens if Redis is not available?
- How do you give different limits to free and paid users?