Rate Limiter Design Token Bucket Sliding Window

Why Rate Limiter Design Never Goes Out of Style

Rate limiter design is one of the most durable system design interview questions because it compresses several hard problems into one 45-minute conversation: distributed state coordination, algorithm tradeoffs, and latency-vs-accuracy tuning. It’s also one of the few system design prompts where you can write actual working code on a whiteboard or shared editor, which is why in 2026 it appears in both architecture rounds and live-coding rounds.

The core requirement never changes: given a client identifier (user ID, API key, IP address), limit the number of requests it can make in a time window, and reject or queue requests once the limit is exceeded — with minimal added latency to every request, since the limiter sits in the hot path of every API call.

The Four Classic Algorithms

Token bucket: a bucket holds up to N tokens, refilled at a fixed rate (e.g., 10 tokens/second). Each request consumes one token; if the bucket is empty, the request is rejected or delayed. This allows short bursts up to the bucket capacity while enforcing a steady-state average rate. It’s the algorithm behind AWS API Gateway and most modern cloud rate limiters because it naturally tolerates bursty legitimate traffic (a user opening an app and firing 5 requests at once) without needing a separate burst-allowance parameter.

Leaky bucket: requests enter a fixed-size queue (the bucket) and are processed (“leaked out”) at a constant rate. Unlike token bucket, leaky bucket enforces a perfectly smooth outflow rate regardless of input burstiness — good for protecting downstream systems that genuinely cannot handle bursts (e.g., a legacy mainframe integration), but it adds queueing latency that token bucket avoids.

Fixed window counter: count requests in discrete time windows (e.g., 00:00-00:59, 01:00-01:59). Simplest to implement — a single counter with a TTL in Redis (INCR + EXPIRE) — but suffers a boundary burst problem: a client can send N requests at 00:59 and another N at 01:00, doubling the effective rate in a 2-second span straddling the window edge.

Sliding window log / sliding window counter: tracks exact request timestamps (log variant) or interpolates between adjacent fixed windows weighted by elapsed time (counter variant) to smooth out the boundary problem. The sliding window counter is the pragmatic middle ground — nearly as accurate as the log variant, at a fraction of the memory cost, since it stores two integers instead of a timestamp per request.

Worked Example: Token Bucket in Redis

A production-realistic implementation uses a Lua script for atomicity (avoiding race conditions between check-and-decrement across concurrent requests):

-- KEYS[1] = bucket key, ARGV[1] = capacity, ARGV[2] = refill_rate, ARGV[3] = now
local bucket = redis.call("HMGET", KEYS[1], "tokens", "last_refill")
local tokens = tonumber(bucket[1]) or tonumber(ARGV[1])
local last_refill = tonumber(bucket[2]) or tonumber(ARGV[3])
local elapsed = tonumber(ARGV[3]) - last_refill
tokens = math.min(tonumber(ARGV[1]), tokens + elapsed * tonumber(ARGV[2]))
if tokens < 1 then
  return 0
else
  redis.call("HMSET", KEYS[1], "tokens", tokens - 1, "last_refill", ARGV[3])
  return 1
end

Running this via EVALSHA guarantees the check-and-decrement happens atomically on the Redis server, avoiding the classic race condition where two concurrent requests both read “1 token remaining” and both decrement, over-admitting traffic. This atomicity detail is exactly the kind of follow-up an interviewer probes for after a candidate draws the high-level design — expect it.

Distributed Rate Limiting: The Real Hard Part

Rate limiting a single server is trivial (an in-memory counter). Rate limiting across a fleet of API servers behind a load balancer requires shared state — which is why nearly every production rate limiter in 2026 centralizes counters in Redis or a similar low-latency store, accepting the added network hop as the cost of consistency.

At extreme scale (hundreds of thousands of requests/second), even Redis becomes a bottleneck or single point of contention. The mitigation: shard rate limit keys across a Redis cluster by consistent hashing on client ID, and/or accept approximate rate limiting — each server maintains a local counter and syncs to a shared store every 100-500ms, trading strict accuracy for reduced network chatter. Most large-scale API gateways (Cloudflare, Stripe’s public documentation on their limiter) explicitly favor approximate distributed limiting over the network cost of a synchronous check on every single request.

Comparison: Rate Limiting Algorithms

Where to Put the Limiter: Gateway vs. Service vs. Client

Placing the limiter at an API gateway (Kong, Envoy, AWS API Gateway) centralizes policy and protects every downstream service uniformly, but adds a network hop and a potential single point of failure if the gateway’s limiter store goes down. Placing it per-service allows fine-grained, service-specific limits (a write-heavy endpoint might need stricter limits than a read endpoint) but duplicates the coordination logic across services. Client-side rate limiting (SDKs that self-throttle) is a courtesy, never a security boundary — always enforce server-side regardless of what the client claims to do.

FAQ

Q: Which algorithm should you default to in an interview if not told otherwise? A: Token bucket. It’s the industry-standard default (used by AWS, Stripe, and most cloud providers), handles bursty legitimate traffic gracefully, and is simple enough to implement correctly under interview time pressure. Mention sliding window counter as the alternative if the interviewer pushes on boundary accuracy.

Q: How do you rate limit by both IP address and user ID simultaneously? A: Maintain two independent limiter instances (two separate Redis key namespaces) and reject the request if either limit is exceeded. This catches both a single abusive IP hitting many accounts and a single compromised account being hit from many IPs — a detail interviewers specifically listen for when probing “what if the same user attacks from multiple IPs.”

Q: What HTTP response should a rate-limited request return? A: 429 Too Many Requests, with a Retry-After header indicating when the client can retry, and ideally X-RateLimit-Limit/X-RateLimit-Remaining headers so well-behaved clients can self-throttle proactively rather than hitting the limit repeatedly.

Rate limiter design rewards candidates who can name the tradeoffs precisely rather than reciting one algorithm as universally correct. The 0-to-1 SWE Interview Playbook (https://www.amazon.com/dp/B0H256Z1MF?tag=sirjohnnymai-20) includes a full whiteboard-to-code walkthrough of this exact problem, including the distributed-Redis follow-up questions interviewers ask after the happy path is drawn.