Designing a Rate Limiter
A rate limiter restricts how many requests a client (identified by user ID, API key, or IP) can make within a time window, protecting backend services from abuse, accidental retry storms, and noisy-neighbor overload. Designing one for a single process is straightforward — an in-memory counter suffices — but designing one for a distributed system with many stateless API servers behind a load balancer is a genuinely hard problem: the limiter's state (request counts) must be shared and updated atomically across all servers handling a given client's traffic, without adding significant latency to every request.
Cricket analogy: Like an umpire tracking how many overs a bowler has bowled to prevent exceeding the quota — easy for one umpire to count, but hard when multiple umpires across grounds must share one accurate count for the same bowler.
Where state lives: the core architectural decision
If each API server keeps its own local counter, a client can exceed the global limit by simply spreading requests across servers behind a round-robin load balancer. The standard fix is centralizing counters in a fast shared store — typically Redis — which every API server reads and writes on each request using an atomic increment-and-check operation (e.g., Lua script or Redis's built-in INCR with EXPIRE). This adds a network hop per request but keeps the check accurate and the API tier stateless. At very high scale, some systems accept eventual consistency and use local counters synchronized periodically, trading strict accuracy for lower latency.
Cricket analogy: Like assigning a single official scorer with a shared scorebook that every ground's umpire must check and update atomically, rather than each umpire keeping a private tally a bowler could exploit by switching ends.
Algorithm choices
Fixed window counters reset a counter every N seconds; they're simple but allow a burst of up to 2x the limit at window boundaries (e.g., a client sends the full quota at the end of one window and the full quota again at the start of the next). Sliding window log stores a timestamp per request and counts requests in the trailing window; it's accurate but memory-heavy at scale. Sliding window counter approximates the sliding log by weighting the previous and current fixed windows, giving good accuracy with fixed memory. Token bucket allows a burst up to bucket capacity while enforcing a steady average rate — tokens refill at a fixed rate and each request consumes one; this is the most widely used algorithm in production because it naturally accommodates bursty legitimate traffic. Leaky bucket instead smooths bursts into a constant output rate, useful when downstream systems need strictly uniform load.
Cricket analogy: Like a bowler's over-quota resetting every 6 balls (fixed window, allowing a burst of bouncers right at the reset), versus tracking every ball's exact timestamp in a trailing window (sliding log, precise but heavy), versus a token bucket letting a bowler save up a few extra yorkers for a big over while still averaging the agreed pace.
# Token bucket rate limiter backed by Redis, using an atomic Lua script
# Keeps: tokens (float), last_refill_timestamp
LUA_SCRIPT = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2]) -- tokens per second
local now = tonumber(ARGV[3])
local requested = 1
local data = redis.call('HMGET', key, 'tokens', 'timestamp')
local tokens = tonumber(data[1]) or capacity
local last_ts = tonumber(data[2]) or now
local delta = math.max(0, now - last_ts)
tokens = math.min(capacity, tokens + delta * refill_rate)
if tokens >= requested then
tokens = tokens - requested
redis.call('HMSET', key, 'tokens', tokens, 'timestamp', now)
redis.call('EXPIRE', key, 3600)
return 1 -- allowed
else
redis.call('HMSET', key, 'tokens', tokens, 'timestamp', now)
return 0 -- rejected
end
"""
# Executed atomically via EVAL so concurrent servers never race on the same bucketStripe's public API rate limiter and GitHub's API both return standard headers (X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset or Retry-After) so well-behaved clients can self-throttle instead of hammering the endpoint until rejected — a good rate limiter design communicates its state, not just enforces it.
A frequent design mistake is rate limiting purely at the application layer without a fast-fail edge/gateway layer. If every request — even ones that will be rejected — pays the cost of hitting an app server and a database, an attacker can still exhaust compute resources through sheer request volume. Rate limiting should happen as early as possible, ideally at the API gateway or load balancer, before expensive downstream work occurs.
- Distributed rate limiting requires shared, atomically-updated state (commonly Redis) so limits are enforced consistently across all API servers.
- Fixed window counters are simple but allow boundary bursts up to 2x the configured limit.
- Token bucket is the most common production algorithm because it allows legitimate bursts while enforcing a steady average rate.
- Sliding window counter approximates sliding log accuracy with fixed, bounded memory usage.
- Rate limiting should happen as early as possible in the request path (gateway/edge) to avoid wasting downstream resources on requests that will be rejected.
- Returning rate-limit headers lets well-behaved clients self-throttle instead of retrying blindly.
Practice what you learned
1. Why do per-server local counters fail to enforce a global rate limit correctly in a load-balanced API cluster?
2. What is the main weakness of the fixed window counter algorithm?
3. Why is token bucket commonly preferred over leaky bucket for public-facing APIs?
4. Why should rate limiting ideally be enforced at the API gateway/edge rather than only deep in application code?
5. What operation does the Lua-script-based Redis token bucket implementation rely on to stay correct under concurrent requests?
Was this page helpful?
You May Also Like
Designing a URL Shortener
A classic system design interview problem that exercises encoding schemes, key generation at scale, database sharding, and redirect performance under heavy read load.
Circuit Breakers and Bulkheads
Resilience patterns that stop cascading failures — circuit breakers halt calls to a failing dependency, while bulkheads isolate resource pools so one failure cannot exhaust everything.
Load Balancing Algorithms
Surveys the algorithms load balancers use to distribute traffic across backend servers, from simple round robin to adaptive least-connections and consistent hashing.
Rate Limiting Strategies
Techniques for controlling how many requests a client or service can make in a given time window, protecting systems from overload and abuse.
Related Reading
Related Study Notes in Software Engineering
Browse all study notesMicroservices Study Notes
Software Architecture · 30 topics
Software EngineeringTesting & TDD Study Notes
Software Testing · 30 topics
Software EngineeringDesign Patterns Study Notes
Software Design · 30 topics
Software EngineeringSoftware Engineering Study Notes
Python · 75 topics
Software EngineeringGit & Version Control Study Notes
Bash · 40 topics