What is Rate Limiting?
Rate limiting controls how many requests a client can make to a service within a time window, protecting against abuse, ensuring fair resource allocation, and preventing system overload.
A policy might allow 100 requests per hour, a burst of 10, or five concurrent requests. Those are different limits; choose the behavior before choosing the algorithm.
Why Rate Limit?
1. Reduce application-level abuse
Attacker sends 1,000,000 requests/second Without rate limiting: Server crashes With rate limiting: Block after 1,000 requests/second
2. Fair Resource Allocation
User A: 10,000 requests/min (excessive) User B: 10 requests/min (normal) Without limits: User A consumes all resources, User B gets errors With limits: Both get fair share
3. Cost Control
Cloud auto-scaling without limits: Request spike → 100 new servers → $10,000 bill With rate limiting: Request spike → Reject excess → 10 servers → $1,000 bill
4. Prevent Brute Force Attacks
Login API without limits: Attacker tries 1M passwords in 10 minutes Login API with limits: Attacker limited to 5 attempts/minute → 83 hours per 1M passwords
Rate Limiting Algorithms
The local Python examples demonstrate state accounting in one process. They omit locking, idle-key cleanup, and shared state. Add those before concurrent deployment; separate workers each enforcing the full limit multiply the total allowance.
1. Token Bucket
Tokens refill at constant rate. Each request consumes a token. Allows bursts.
Implementation:
import time
class TokenBucket:
def __init__(self, capacity, refill_rate):
self.capacity = capacity
self.refill_rate = refill_rate # tokens per second
self.tokens = capacity
self.last_refill = time.monotonic()
def allow_request(self):
# Refill tokens based on elapsed time
now = time.monotonic()
elapsed = now - self.last_refill
tokens_to_add = elapsed * self.refill_rate
self.tokens = min(self.capacity, self.tokens + tokens_to_add)
self.last_refill = now
# Try to consume a token
if self.tokens >= 1:
self.tokens -= 1
return True
return False
# Usage
limiter = TokenBucket(capacity=100, refill_rate=10) # 10 req/sec, burst of 100
for _ in range(150):
if limiter.allow_request():
process_request()
else:
return_429_error()
Pros:
- ✅ Allows traffic bursts (good UX)
- ✅ Smooth refill rate
- ✅ Memory efficient
Cons:
- ❌ Bursts can still overwhelm downstream services
Best for: User-facing APIs (good UX for occasional bursts)
2. Leaky Bucket
Requests enter a queue, processed at constant rate regardless of input.
Implementation:
on arrival:
reject if the bounded queue is full
otherwise enqueue the request with an expiry deadline
on scheduler tick:
if work is available and the next dispatch time has arrived:
dispatch at most the configured allowance
discard expired work
advance the next dispatch time
A background scheduler is required. Removing several queued items only when the next request arrives does not create a smooth output stream; it produces catch-up bursts.
Pros:
- ✅ Smooth, constant output rate
- ✅ Protects downstream services
Cons:
- ❌ Poor UX (bursts queued, adding latency)
- ❌ Queue can fill up and drop requests
Best for: Protecting backend systems from spikes
3. Fixed Window Counter
Count requests in fixed time windows (e.g., 100 requests per minute).
import time
from collections import defaultdict
class FixedWindowCounter:
def __init__(self, max_requests, window_size):
self.max_requests = max_requests
self.window_size = window_size # in seconds
self.counters = defaultdict(int)
def allow_request(self, user_id):
now = time.monotonic()
window = int(now // self.window_size)
key = f"{user_id}:{window}"
self.counters[key] += 1
if self.counters[key] <= self.max_requests:
return True
return False
# Usage
limiter = FixedWindowCounter(max_requests=100, window_size=60) # 100/min
Problem: Boundary Issue
Window 1: 09:00:00 - 09:00:59 Window 2: 09:01:00 - 09:01:59 User sends: - 100 requests at 09:00:59 ✅ (allowed, window 1) - 100 requests at 09:01:00 ✅ (allowed, window 2) Result: 200 requests in 1 second! (boundary spike)
Pros:
- ✅ Very simple
- ✅ Memory efficient
Cons:
- ❌ Boundary spike problem
- ❌ Uneven traffic distribution
Best for: Simple use cases with low traffic
4. Sliding Window Log
Keep timestamp of each request, count requests in sliding window.
import time
from collections import deque
class SlidingWindowLog:
def __init__(self, max_requests, window_size):
self.max_requests = max_requests
self.window_size = window_size
self.requests = defaultdict(deque)
def allow_request(self, user_id):
now = time.monotonic()
cutoff = now - self.window_size
# Remove old requests
while self.requests[user_id] and self.requests[user_id][0] < cutoff:
self.requests[user_id].popleft()
# Check if under limit
if len(self.requests[user_id]) < self.max_requests:
self.requests[user_id].append(now)
return True
return False
# Usage
limiter = SlidingWindowLog(max_requests=100, window_size=60)
Pros:
- ✅ No boundary issue
- ✅ Accurate
Cons:
- ❌ Memory intensive (stores all timestamps)
- ❌ O(N) complexity for cleanup
Best for: When accuracy is critical and traffic is moderate
5. Sliding Window Counter
Hybrid: combines fixed window efficiency with sliding window accuracy.
import time
class SlidingWindowCounter:
def __init__(self, max_requests, window_size):
self.max_requests = max_requests
self.window_size = window_size
self.counters = {}
def allow_request(self, user_id):
now = time.monotonic()
current_window = int(now // self.window_size)
previous_window = current_window - 1
# Weight of previous window
elapsed_in_current = now % self.window_size
previous_weight = 1 - (elapsed_in_current / self.window_size)
# Calculate weighted count
current_count = self.counters.get(f"{user_id}:{current_window}", 0)
previous_count = self.counters.get(f"{user_id}:{previous_window}", 0)
estimated_count = previous_count * previous_weight + current_count
if estimated_count < self.max_requests:
key = f"{user_id}:{current_window}"
self.counters[key] = current_count + 1
return True
return False
Pros:
- ✅ Memory efficient
- ✅ Smooths boundary spikes
- ✅ Good accuracy
Cons:
- ❌ Approximate (not exact)
Best for: Workloads that accept approximate window counts
Comparison Table
| Algorithm | Memory | Accuracy | Boundary Issue | Bursts Allowed | Best For |
|---|---|---|---|---|---|
| Token Bucket | Low | Good | No | ✅ Yes | User-facing APIs |
| Leaky Bucket | Medium | Perfect | No | ❌ No | Backend protection |
| Fixed Window | Very Low | Poor | ✅ Yes | Partial | Simple cases |
| Sliding Log | High | Perfect | No | Controlled | Critical systems |
| Sliding Counter | Low | Good | No | Partial | Production (recommended) |
Distributed Rate Limiting
Challenge
Request 1 → Server A (count = 1) Request 2 → Server B (count = 1) Result: Each server thinks usage is low, both allow Actual: User exceeded limit!
Atomic sliding-window admission in Redis
This example counts admitted requests in (now - window, now]. Use a new opaque request ID for every admission attempt so simultaneous timestamps do not collapse into one sorted-set member. The script uses Redis server time, keeping clients' clocks out of the decision.
-- KEYS[1]: per-principal key
-- ARGV[1]: positive integer limit; ARGV[2]: positive window in seconds
-- ARGV[3]: unique attempt ID generated by the caller
local key = KEYS[1]
local limit = tonumber(ARGV[1])
local window = tonumber(ARGV[2])
if not limit or not window or limit < 1 or window <= 0 then
return redis.error_reply('invalid limit or window')
end
local t = redis.call('TIME')
local now = tonumber(t[1]) + tonumber(t[2]) / 1000000
redis.call('ZREMRANGEBYSCORE', key, '-inf', now - window)
local count = redis.call('ZCARD', key)
if count >= limit then
return 0
end
redis.call('ZADD', key, now, ARGV[3])
redis.call('EXPIRE', key, math.ceil(window))
return 1
Validate configuration and principal keys before calling the script. Atomic execution on one Redis primary is not a guarantee of globally exact accounting through asynchronous failover. Decide whether a limiter outage fails open, fails closed, or uses a conservative local allowance. Bound key cardinality and monitor memory.
Provider limits are service contracts
API providers can combine rate limits, concurrency limits, daily quotas, and endpoint-specific rules. Do not infer their internal algorithm from an example response header. Consult GitHub's rate-limit documentation or Stripe's rate limits for those APIs rather than copying a fixed quota into a client.
When retrying, honor documented Retry-After guidance, add jitter where appropriate, and use a bounded retry budget. Retrying every rejected request immediately can sustain the overload you are trying to avoid.
Response Headers
Illustrative response fields (header names and semantics vary by API; Retry-After may accompany a 429 response):
@app.route('/api/resource')
def api_endpoint():
user_id = get_user_id()
if not limiter.allow_request(user_id):
return jsonify({'error': 'Rate limit exceeded'}), 429, {
'X-RateLimit-Limit': '100',
'X-RateLimit-Remaining': '0',
'X-RateLimit-Reset': str(int(time.monotonic() + 60)),
'Retry-After': '60'
}
# Process request
return jsonify({'data': 'success'}), 200, {
'X-RateLimit-Limit': '100',
'X-RateLimit-Remaining': '99',
'X-RateLimit-Reset': str(int(time.monotonic() + 60))
}
Interview Tips 💡
When discussing rate limiting in system design interviews:
- Ask about requirements: "What's the expected traffic pattern? Do we need to allow bursts?"
- Choose appropriate algorithm: "For user-facing API, Token Bucket allows bursts. For backend protection, Leaky Bucket..."
- Discuss distribution: "With multiple servers, we'd use Redis as centralized rate limit store..."
- Mention atomicity: "We'd use Lua scripts to ensure atomic increment and check..."
- User experience: "Return 429 with Retry-After header so clients know when to retry..."
- Multiple layers: "Rate limit at API gateway (global), service level (per-resource), and user level (fairness)..."
Related Concepts
- Token Bucket vs Leaky Bucket — Detailed algorithm comparison
- Redis Internals — Using Redis for distributed rate limiting
- API Gateway — Gateway-level rate limiting
- Backpressure — Handling overload at application level
- Load Balancing — Distributing rate-limited traffic
Source and boundary tests
Redis scripting documentation explains atomic script execution. Test two simultaneous requests at the last available slot, a burst across a fixed-window boundary, a limiter restart, and a backend outage. A rate limit cannot protect network capacity already saturated upstream; combine it with appropriate edge and concurrency controls.
Keep reading
API Gateway Pattern
The single entry point for microservices. Implementing rate limiting, authentication, and protocol translation/aggregation.
Chat Delivery: Durable Acknowledgments and Device Sync
Design a chat workflow with retry-safe message IDs, per-device receipts, offline queues and explicit encryption boundaries.
Circuit Breaker Pattern
A mechanism to prevent an application from repeatedly trying to execute an operation that's likely to fail.
Notification Delivery: Queues, Retries and Deadlines
Design a notification service around provider acceptance, recipient delivery, retry ambiguity, queue age and changing preferences.
Payment Workflows: Idempotency, Ledgers and Reconciliation
Trace a payment through an ambiguous timeout, concurrent retries, balanced ledger entries and evidence-based reconciliation.
Backpressure: Bound Work Before It Becomes a Backlog
Calculate queue growth, propagate bounded demand, and choose an explicit overflow policy using a runnable asynchronous queue example.