Understanding rate limiting algorithms, implementation strategies, and when to apply rate limits in system design.
Finished this lesson?
Sign in to save your progress across devices.
Tip: use ← and → to move between lessons.
Was this lesson helpful?
Rehearse this with a Staff+ engineer
45-minute mock with a Staff+ engineer who interviews at your target company. Premium members save $20.
Rate limiting controls the number of requests a client can make within a time window. It protects your services from abuse, ensures fair usage, and prevents cascading failures.
Without rate limiting:
With rate limiting:
Rate limiting is both a security feature and a system design tool. It's essential for any public-facing API.
Rate limits can be applied at different levels:
| Rate Limiting Dimensions | |
|---|---|
| Name | Description |
| Per user/API key | Most common. Each authenticated user gets their own quota. |
| Per IP address | For unauthenticated traffic. Can be bypassed with rotating IPs. |
| Per endpoint | Different limits for different operations. Writes often more restricted than reads. |
| Global | Total requests to the service. Protects overall system capacity. |
| Per tenant | In multi-tenant systems. Ensures one tenant can't impact others. |
Tokens are added to a bucket at a fixed rate. Each request consumes a token. If no tokens available, request is rejected.
Bucket capacity: 10 tokens
Refill rate: 1 token/second
Request 1: 10 tokens → 9 tokens ✓
Request 2: 9 tokens → 8 tokens ✓
...
10 requests in 1 second: 0 tokens
Request 11: 0 tokens → REJECTED ✗
After 1 second: 1 token → Request allowed ✓
Pros: Allows bursts up to bucket size, smooth rate over time Cons: Slightly more state to maintain
Use when: You want to allow short bursts while maintaining average rate.
Requests enter a queue (bucket) and are processed at a fixed rate. If queue is full, requests are dropped.
Queue capacity: 10 requests
Process rate: 1 request/second
Requests queue up and are processed steadily.
If queue full, new requests are dropped.
Pros: Smooth, constant output rate Cons: Doesn't allow bursts, increased latency for queued requests
Use when: You need consistent, predictable throughput (e.g., API to a rate-limited downstream).
Count requests in fixed time windows (e.g., per minute). Reset at window boundary.
Window: 1 minute, Limit: 100 requests
12:00:00 - 12:01:00: 0/100, 1/100, ..., 100/100
12:00:55: 99th request ✓
12:00:56: 100th request ✓
12:00:57: REJECTED ✗
12:01:00: Counter resets → 0/100
12:01:01: 1/100 ✓
Pros: Simple, memory efficient Cons: Burst at window boundaries (200 requests possible in 2 seconds spanning windows)
Track timestamp of each request. Count requests in the past window.
Window: 1 minute, Limit: 100 requests
Requests at: [11:59:30, 11:59:45, 12:00:15, 12:00:20, ...]
At 12:00:30: Count requests from 11:59:30 to 12:00:30
Pros: Accurate, no boundary burst problem Cons: Memory intensive (stores all timestamps)
Hybrid approach. Weighted average of current and previous window counts.
Window: 1 minute, Limit: 100 requests
Previous window (11:59-12:00): 80 requests
Current window (12:00-12:01): 20 requests so far
Current position: 30 seconds into window (50%)
Estimated count = 20 + (80 × 50%) = 60 requests
Still under 100, allow request ✓
Pros: Memory efficient, reasonably accurate Cons: Approximation, not exact
| Algorithm Comparison | |
|---|---|
| Name | Description |
| Token Bucket | Allows bursts, smooth average rate. Best general-purpose choice. |
| Leaky Bucket | Constant output rate, no bursts. Best for rate-limited downstream. |
| Fixed Window | Simple, but boundary burst problem. Best for simplicity when bursts OK. |
| Sliding Window Log | Most accurate, high memory. Best when accuracy critical. |
| Sliding Window Counter | Good balance of accuracy and memory. Best for most production use. |
Choose the Right Algorithm
You're building a payment API that processes credit card transactions. The downstream payment processor allows 100 requests per second with no bursts. Which algorithm would you use?
Recommendation: Leaky Bucket
Why:
Implementation:
Alternative consideration: Token bucket with bucket size of 100 (matching the processor's limit) would also work, but leaky bucket is cleaner for this use case since we explicitly don't want bursts.
Single-server rate limiting is straightforward. Distributed rate limiting across multiple servers is harder.
All servers check/increment a shared counter.
Server 1 → Redis: INCR user:123:requests → 50
Server 2 → Redis: INCR user:123:requests → 51
Server 3 → Redis: INCR user:123:requests → 52
Pros: Accurate, consistent across servers Cons: Adds latency (Redis round-trip), Redis becomes critical path
Each server maintains local counters, periodically synced.
Server 1: local_count = 30
Server 2: local_count = 25
Server 3: local_count = 20
Effective limit per server = total_limit / num_servers
(Can allow slight over-limit during sync intervals)
Pros: Fast (no network hop for most requests) Cons: Can exceed limit during sync windows
Route same user to same server.
hash(user_id) % num_servers = server_index
User 123 always → Server 2
Pros: Simple local rate limiting works Cons: Uneven load distribution, failure handling complex
For most applications, centralized Redis-based rate limiting is the right choice. The added latency (1-2ms) is acceptable, and the accuracy is worth it.
# Redis-based token bucket
import redis
import time
class RateLimiter:
def __init__(self, redis_client, capacity, refill_rate):
self.redis = redis_client
self.capacity = capacity
self.refill_rate = refill_rate # tokens per second
def allow_request(self, key):
now = time.time()
bucket_key = f"ratelimit:{key}"
# Lua script for atomic operation
lua_script = """
local tokens = tonumber(redis.call('HGET', KEYS[1], 'tokens') or ARGV[1])
local last_update = tonumber(redis.call('HGET', KEYS[1], 'last_update') or ARGV[4])
local now = tonumber(ARGV[4])
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
-- Refill tokens based on time elapsed
local elapsed = now - last_update
tokens = math.min(capacity, tokens + elapsed * refill_rate)
if tokens >= 1 then
tokens = tokens - 1
redis.call('HSET', KEYS[1], 'tokens', tokens, 'last_update', now)
redis.call('EXPIRE', KEYS[1], ARGV[3])
return 1
else
return 0
end
"""
result = self.redis.eval(
lua_script, 1, bucket_key,
self.capacity, self.refill_rate, 3600, now
)
return result == 1
When rate limited, return helpful information:
HTTP/1.1 429 Too Many Requests
Retry-After: 30
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1640000000
{
"error": "Rate limit exceeded",
"message": "Too many requests. Please retry after 30 seconds.",
"retry_after": 30
}
| Rate Limiting Knowledge by Level | |
|---|---|
| Name | Description |
| Mid-Level (L4) | Know why rate limiting is needed. Understand basic token bucket concept. Can implement simple single-server rate limiting. |
| Senior (L5) | Choose appropriate algorithm with reasoning. Design distributed rate limiting with Redis. Handle edge cases (clock skew, failures). |
| Staff+ (L6+) | Design rate limiting infrastructure at scale. Consider multi-tenant fairness. Handle rate limit cascades. Discuss operational monitoring. |
| Engineering Manager | Define rate limit policies aligned with business (tiers, quotas). Plan capacity around rate limits. Understand customer impact of limits. |
"I'd use a token bucket algorithm with Redis as the shared counter. Each API key gets a bucket with a capacity (say, 100 requests) and a refill rate (10 requests/second). On each request, I atomically check and decrement the token count using a Lua script for consistency. If tokens are available, allow the request; otherwise, return 429 with Retry-After header."
"I'd use centralized rate limiting with Redis. All servers check the same Redis key for each user. Using a Lua script ensures atomicity—checking and decrementing happens in a single operation. The added latency is about 1-2ms, which is acceptable for the accuracy it provides."
"The system should fail open or fail closed depending on the use case. For most APIs, I'd fail open—allow requests when Redis is unavailable to maintain availability, but log for monitoring. For payment APIs or security-sensitive endpoints, I might fail closed or fall back to local rate limiting with conservative limits."
Rate limiters protect individual endpoints. Next, we'll look at API gateways, which provide rate limiting along with authentication, routing, and more at the edge of your system.