Designing a Rate Limiter: Token Bucket, Sliding Window and Redis

"Design a rate limiter" is a favourite system design question because it's small enough to finish in an interview, yet touches algorithms, distributed state, atomicity and failure handling. Here's a complete answer.

Step 1: clarify the requirements

• What's limited, and per what key? Requests per API key, per user, per tenant or per IP (often several at once).
• The limits: for example 100 requests per minute, bursts of up to 20.
• Where does it run? At the API gateway, inside each service, or both.
• Accuracy: is approximate OK (protection), or must it be exact (billing quotas)?
• Failure behaviour: if the limiter's store is down, allow (fail open) or deny (fail closed)?
• The response: HTTP 429 Too Many Requests with a Retry-After header.

Step 2: pick an algorithm

Fixed window counter

Count requests per key per fixed window (rl:user42:2026-09-26T10:15).

• ✅ Simplest; one counter per key.
• ❌ Boundary bursts: 100 requests at 10:15:59 and 100 more at 10:16:00 means 200 in 2 seconds.

Sliding window log

Store every request's timestamp (a Redis sorted set); count those in the last 60 s.

• ✅ Exact.
• ❌ Memory grows with the traffic (one entry per request).

Sliding window counter

Keep counts for the current and previous fixed windows, and weight the previous one by how much of it still overlaps: estimate = current + previous × (1 − elapsed/window).

• ✅ Smooths boundary bursts, with tiny memory. A great default.
• ❌ Approximate (usually within a few percent).

Token bucket

A bucket holds up to B tokens and refills at R tokens per second; each request takes one token.

• ✅ Allows controlled bursts (up to B) while enforcing the average rate R. Used widely (AWS API Gateway, Spring Cloud Gateway's Redis limiter).
• Two numbers to tune: capacity and refill rate.

Leaky bucket

Requests enter a queue that drains at a constant rate.

• ✅ Perfectly smooth output; good for protecting a fragile downstream system.
• ❌ Adds queueing latency; bursts wait instead of being served.

Step 3: make it distributed

With many API instances, the counters must be shared, so use Redis. The key requirement is atomicity: "read the tokens, compute, write back" must not interleave between instances. Run it as a Lua script, which Redis executes atomically:

-- KEYS[1] = bucket key; ARGV = capacity, refill_per_ms, now_ms, cost
local b = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local capacity, rate = tonumber(ARGV[1]), tonumber(ARGV[2])
local now, cost = tonumber(ARGV[3]), tonumber(ARGV[4])
local tokens = tonumber(b[1]) or capacity
local ts = tonumber(b[2]) or now
tokens = math.min(capacity, tokens + (now - ts) * rate)   -- refill since last call
local allowed = tokens >= cost
if allowed then tokens = tokens - cost end
redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate)) -- idle buckets expire
return allowed and 1 or 0

Design notes:

• Key design: rl:{tenant}:{apiKey}. The {…} hash tag keeps related keys on one Redis Cluster slot.
• One round trip per request (the script); use EVALSHA so the script isn't resent each time.
• Clock: use a single time source (the application's clock passed in, or Redis TIME) so instances with skewed clocks don't disagree.

Step 4: where to enforce it

1. Edge / WAF / CDN: coarse per-IP limits against abuse and DDoS.
2. API gateway: per-client and per-plan quotas (for example, Spring Cloud Gateway's RequestRateLimiter with Redis).
3. Inside services: protect expensive endpoints and scarce resources.
4. Outbound clients: respect partners' rate limits.

Step 5: failure handling and scale

• Redis unavailable? Most APIs fail open (allow, log, alert), since availability matters more than strict limits. Security-sensitive endpoints (login, OTP) fail closed. Add a local in-memory limiter as a backstop.
• Very high traffic: do the counting locally in each instance, and sync to Redis periodically (approximate but cheap), or shard the keys across a Redis Cluster.
• Hot keys: one huge tenant hammering one key can be split into sub-keys (key#0..N), with the limits divided.

Step 6: tell clients what happened

HTTP/1.1 429 Too Many Requests
Retry-After: 12
RateLimit-Limit: 100
RateLimit-Remaining: 0
RateLimit-Reset: 12

Clear headers let well-behaved clients back off instead of hammering you.

Follow-up questions this topic invites — and their answers

Q: Token bucket vs sliding window: which should I pick? A: Token bucket when you want to allow short bursts (typical for user-facing APIs); sliding window counter when you want smooth, fair limits with minimal memory. Both are fine answers if you explain the trade-off.

Q: Why not use INCR plus EXPIRE instead of Lua? A: That works for a fixed window. For token bucket or sliding window logic you need several operations to be atomic, and a Lua script (or a Redis transaction) guarantees that.

Q: How do you rate-limit per user across multiple regions? A: Either accept per-region limits (each region enforces its own share), or replicate counters asynchronously, accepting some overshoot. Globally exact limits across regions are expensive, because they need cross-region coordination.

Q: Rate limiting vs throttling vs load shedding? A: Rate limiting enforces per-client quotas; throttling usually means slowing or queueing requests rather than rejecting them; load shedding drops low-priority work when the system is overloaded, whoever the client is.

Practise more in our System Design interview playbook and the rate limiter case study.