Rate Limiting

Distributed SystemsSeniorsystem-design

The Question

How do you implement rate limiting and what algorithms exist?

What a Strong Answer Covers

• Burst behavior of token
• smoothing of leaky
• all three named.

Senior-Level Answer

Rate limiting is a traffic control mechanism that restricts how many requests a client can make within a time window. It protects services from abuse, prevents resource exhaustion, and ensures fair usage across tenants.

The four main algorithms each make different trade-offs. **Fixed window** divides time into discrete buckets and counts requests per bucket. It's simple to implement but suffers from the boundary burst problem: a client can fire 2× the limit by straddling two windows (e.g., 100 requests at 00:59 and 100 more at 01:01).

**Sliding window log** keeps a timestamp log of every request and counts entries within the rolling window. It's precise but memory-intensive—O(requests) space per client. **Sliding window counter** approximates the sliding window by combining the current and previous fixed-window counts weighted by overlap. It's O(1) space with ~0.1% error, making it the practical default.

**Token bucket** gives each client a bucket that refills at a constant rate (e.g., 10 tokens/second, capacity 50). Each request consumes one token; excess requests are dropped or queued. It allows controlled bursting up to bucket capacity—good for APIs where brief spikes are legitimate.

**Leaky bucket** processes requests at a constant outflow rate regardless of arrival rate, smoothing traffic absolutely. It cannot burst, which makes it ideal for protecting downstream systems that can't handle spikes.

In distributed systems, rate limiting state must be shared. A single Redis instance with atomic INCR/EXPIRE works for small scale. For higher scale, use Redis Cluster or a dedicated rate-limit service. The key design decisions: where to store counters (Redis, Memcached, or in-process with gossip-based sync), what the key is (IP, user ID, API key, tenant), and how to handle Redis unavailability (fail open vs. fail closed).

Sliding window counter in Redis is implemented with two keys per window and an atomic Lua script, ensuring no race conditions. Response headers like `X-RateLimit-Limit`, `X-RateLimit-Remaining`, and `Retry-After` are standard UX. HTTP 429 Too Many Requests is the correct status code.

Key Differences

What Separates a 2/3 from a 3/3

Common Mistakes

• Confusing token bucket (allows bursting) with leaky bucket (constant rate, no burst)
• Describing only fixed window without mentioning the boundary burst vulnerability
• Ignoring distributed coordination — an in-process counter only works for single-node deployments
• Forgetting to address what happens when the rate-limit store is unavailable (fail-open vs fail-closed)

Follow-Up Questions

• How would you implement a sliding window counter in Redis atomically? — Think about using two keys (current and previous window), weighting the previous count by elapsed overlap, and wrapping in a Lua script to avoid race conditions.
• When would you choose leaky bucket over token bucket? — Leaky bucket smooths traffic to an absolute constant rate; use it when the downstream system cannot tolerate any burst. Token bucket is better when short legitimate bursts are acceptable.
• How do you rate-limit in a multi-region deployment without a central Redis? — Consider local in-process counters with periodic gossip sync, or accepting slight over-counting, or routing all requests for a key to the same region via consistent hashing.
• What HTTP status code and headers should a rate-limited response include? — 429 Too Many Requests, Retry-After (seconds until reset), X-RateLimit-Limit, X-RateLimit-Remaining.

Related Questions

• Consistent Hashing
• CDN
• Load Balancer — L4 vs L7
• Distributed Transactions — 2PC, Saga
• Exactly-once Delivery