Rate Limiting in Distributed Systems
Learn how rate limiting works in distributed systems — token bucket, leaky bucket, sliding window, and Redis-backed enforcement.
Expected Interview Answer
Rate limiting caps how many requests a client, service, or API key can make within a time window, protecting backend systems from overload, abuse, and cascading failure, typically implemented with algorithms like token bucket, leaky bucket, or sliding window counters.
A token bucket algorithm fills a bucket with tokens at a fixed rate up to a maximum capacity, and each request consumes one token; if the bucket is empty the request is throttled, which naturally allows short bursts up to the bucket size while enforcing a steady average rate. A leaky bucket instead processes requests at a strictly constant output rate regardless of burst size, smoothing traffic but adding latency during spikes. A sliding-window counter tracks request counts over a rolling time window, giving more accurate limiting than a fixed window that can allow double the limit right at a window boundary. In distributed systems, rate limiting state must be shared across instances, commonly via a centralized store like Redis with atomic increment-and-expire operations, or via approximate local counters synced periodically for lower latency at the cost of some over-admission. Rate limiting is applied at the API Gateway for external clients, and can also protect internal services from noisy-neighbor traffic between microservices.
- Protects backend capacity from traffic spikes and abusive clients
- Enables fair usage across multiple tenants or API consumers
- Prevents cascading failure by shedding excess load early
- Gives predictable cost and capacity planning for downstream systems
AI Mentor Explanation
Rate limiting is like a bowler being restricted to a fixed number of overs in an innings — once the quota is used up, that bowler cannot bowl again no matter how well they are performing, protecting them from being overused. A token-bucket approach is like a bowler banking unused overs from an earlier match into a reserve, allowed to bowl a short burst of extra overs later up to a cap. A strict leaky-bucket approach is like a fixed over-rate rule that paces deliveries evenly through the day regardless of how fast the team wants to bowl. Either way, the limit exists to keep the bowling attack sustainable across a long tournament.
Step-by-Step Explanation
Step 1
Choose an algorithm
Pick token bucket for burst tolerance, leaky bucket for strict smoothing, or sliding window for accurate rolling limits.
Step 2
Pick a key
Rate-limit per API key, per client IP, per user, or per tenant, depending on what fairness boundary matters.
Step 3
Share state centrally
Use a store like Redis with atomic INCR/EXPIRE so limits are enforced consistently across many gateway or service instances.
Step 4
Respond and signal
Return HTTP 429 with a Retry-After header when the limit is exceeded, so well-behaved clients can back off correctly.
What Interviewer Expects
- Ability to name and compare token bucket, leaky bucket, and sliding window algorithms
- Understanding of why distributed rate limiting needs shared state (e.g. Redis)
- Awareness of fixed-window boundary problems and how sliding windows fix them
- Knowledge of proper client signaling via HTTP 429 and Retry-After
Common Mistakes
- Implementing rate limiting with only in-memory local counters in a multi-instance deployment
- Using a naive fixed window that allows double the limit at window boundaries
- Not returning a Retry-After header, leaving clients to guess when to retry
- Confusing rate limiting with throttling/backpressure applied only inside one process
Best Answer (HR Friendly)
“Rate limiting is how we make sure no single client or bad actor can overwhelm our systems by sending too many requests too fast. We track how many requests each client has made in a given time window, using a shared store like Redis so the limit is enforced correctly even across multiple servers, and once someone hits the limit we return a clear 429 response telling them when to try again.”
Code Example
# Atomically check-and-decrement a token bucket stored in Redis
redis-cli --eval rate_limit.lua rate:user:123 , 10 60
# rate_limit.lua (simplified token bucket):
# local tokens = tonumber(redis.call("GET", KEYS[1]) or ARGV[1])
# if tokens > 0 then
# redis.call("DECRBY", KEYS[1], 1)
# redis.call("EXPIRE", KEYS[1], ARGV[2])
# return 1 -- allowed
# else
# return 0 -- rejected, send HTTP 429
# endFollow-up Questions
- How would you implement rate limiting consistently across multiple gateway replicas?
- What is the boundary problem with a naive fixed-window rate limiter?
- How does token bucket differ from leaky bucket in handling burst traffic?
- What HTTP status code and headers should a rate-limited response include?
MCQ Practice
1. Which rate-limiting algorithm allows short bursts up to a set capacity while enforcing a steady average rate?
Token bucket accumulates tokens up to a max capacity, allowing bursts as long as tokens are available, while still capping the long-run average rate.
2. What problem does a naive fixed-window rate limiter have?
Requests clustered at the end of one window and the start of the next can together exceed the limit, which sliding-window counters avoid.
3. Why is a shared store like Redis commonly used for distributed rate limiting?
A centralized store with atomic operations ensures rate-limit counts are consistent even when requests are handled by different instances.
Flash Cards
What is rate limiting? — Capping how many requests a client can make in a time window to protect backend capacity.
Token bucket vs leaky bucket? — Token bucket allows bursts up to capacity; leaky bucket enforces a strictly constant output rate.
Why use Redis for distributed rate limiting? — It gives atomic, shared counters across multiple service instances.
What should a rate-limited response include? — HTTP 429 status with a Retry-After header.