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

Picture the IRCTC Tatkal window opening at 10 AM. A few lakh people hit refresh at once, and a handful of scripts hit it a few hundred times a second each. Without a limiter, those scripts eat the capacity meant for everyone else, and your booking service falls over at the exact moment it matters.

"Design a rate limiter" is a favourite interview question because it looks small and isn't: algorithms, Redis, HTTP semantics, distributed consistency and failure handling, all in under an hour. Here is the answer a strong candidate gives, in interview order.

A rate limiter is a component that counts requests per client identity over time and blocks requests once that client exceeds an allowed rate. It protects services from overload, stops one noisy tenant starving the rest, slows brute-force and scraping, and keeps bills predictable.

Don't start drawing. Spend two minutes on requirements, because the right algorithm depends on them. Typical answers from an interviewer:

Functional requirements

• Limit per identity (user, API key, IP or tenant), optionally per route: POST /orders stricter than GET /products.
• Several rules at once, like 10 per second and 10,000 per day for the same key.
• Limits per plan tier, changeable without a deploy.
• Reject with HTTP 429 and tell the client when to retry.
• Allow short bursts (an app firing five calls on screen load) but not sustained abuse.

Non-functional requirements

• Low latency: it runs on every request, so it should add about a millisecond.
• Highly available: a limiter outage must not become an API outage.
• Distributed: limits hold across all gateway instances, not per machine.
• Approximately accurate: allowing 101 instead of 100 during a race is fine for most APIs.
• Observable: metrics on what each rule blocks, so you can tune limits.

Size the limiter itself, not just the product. Assume a public API with 10 million daily active users, a peak of 50,000 requests per second, and one limiter check per rule per request.

Memory is tiny; the ops rate drives the design. A Redis primary executes commands on one main thread and a Lua script costs more than a plain INCR, so 100,000 script calls per second is a reason to shard with Redis Cluster and keep headroom. Benchmark your own hardware with redis-benchmark instead of quoting a magic number.

Put the main limiter at the API gateway, backed by Redis, and add business-aware limits inside the services that need them. Each layer sees different information, so real systems use more than one.

• Client side: polite SDKs back off on 429, but you can never trust it; anyone can call your API with curl.
• Edge or CDN: cheap per-IP limits that stop floods early. It knows the IP, not the user or plan.
• API gateway: the usual home. It sees every request after auth, knows the API key and route, and keeps the logic out of each service.
• Middleware in a service: knows business context, like "3 OTP sends per phone number per 10 minutes".
• Service mesh sidecar: Envoy-style proxies apply a local token bucket and call a global rate limit service, covering service-to-service traffic too.

Know five algorithms: how each works and where it breaks. You'll be asked to compare two and pick one with a reason.

Fixed window counter

A fixed window counter keeps one counter per key per clock-aligned window (say, per calendar minute) and rejects requests once it passes the limit. One INCR and one integer, which is why everyone starts here.

The flaw is the boundary burst. With 100 per minute, a client sends 100 requests at 12:00:59 (allowed) and 100 more at 12:01:00 (allowed, new window). That is 200 requests in about two seconds. Worst case, a fixed window lets through 2x the limit within one window length.

Sliding window log

A sliding window log stores the timestamp of every accepted request, drops timestamps older than the window, and counts the rest. In Redis: a sorted set with ZREMRANGEBYSCORE, ZCARD and ZADD. It is exact. The cost is memory: 1,000 requests per hour means up to 1,000 entries per key. Great for low limits like 5 password resets per hour, bad for high-volume APIs.

Sliding window counter

A sliding window counter keeps fixed window counters but estimates the rolling rate by weighting the previous window by how much of it still overlaps the sliding window. The formula is: estimated count = previous window count x ((window length - time elapsed in current window) / window length) + current window count.

Example with 100 per minute: the previous minute had 80 requests, the current one has 30, and we are 15 seconds in. Estimate = 80 x (45 / 60) + 30 = 90, so allow. It assumes the previous window's traffic was spread evenly. Cloudflare reported that across 400 million requests from 270,000 sources, this wrongly allowed or limited only 0.003% of requests. Two integers per key for near-exact behaviour is a great trade.

Token bucket

A token bucket gives each key a bucket that holds up to a capacity of tokens, refills at a fixed rate, and charges one token per request; a request with no token available is rejected. Capacity controls the burst you allow, refill rate controls the sustained rate. A bucket with capacity 20 and refill 5 per second lets a client fire 20 requests instantly, then settle to 5 per second.

No timer is needed. Store the token count and last refill time, and on each request compute tokens = min(capacity, tokens + elapsed x rate). Stripe has written that its API uses token bucket limiters in Redis; it is the usual default because bursts are normal client behaviour.

Leaky bucket

A leaky bucket puts requests into a fixed-size queue that drains at a constant rate and drops new requests when full. Output is perfectly smooth, ideal in front of an SMS vendor with a hard per-second cap. The cost is latency, since requests wait in the queue. Used as a meter instead of a queue it behaves like a token bucket; GCRA (generic cell rate algorithm) is that variant, storing one timestamp per key.

Keep limiter state in a shared Redis cluster and run each check as one atomic Lua script, so every gateway sees the same counts. Per-instance memory fails: with 20 gateway pods, 100 per minute quietly becomes up to 2,000.

Why INCR then EXPIRE in two calls is racy

The classic first attempt at a fixed window looks like this. It has a bug that only shows up in production.

// Racy: two separate round trips
const count = await redis.incr(key);      // call 1
if (count === 1) {
  await redis.expire(key, 60);            // call 2
}
if (count > limit) return reject429();

If the pod dies or the network drops between call 1 and call 2, the key has no TTL. It never resets, and that user stays blocked forever once over the limit; the Redis docs flag this exact race. Token bucket in app code is worse: two pods both read "1 token left", both allow, both write 0. That check-then-act race admits more than the limit.

The fix is to move the read-modify-write into Redis. Redis runs a Lua script atomically, so no other command can touch the key halfway through. MULTI/EXEC fixes INCR plus EXPIRE but can't branch on values it reads, so token bucket needs a script.

Token bucket as an atomic Lua script

-- KEYS[1] = bucket key, e.g. rl:{key:ak_123}:post_orders
-- ARGV[1] = capacity (max tokens)
-- ARGV[2] = refill rate (tokens per second)
-- ARGV[3] = cost of this request (usually 1)
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])

-- Use the Redis server clock so every gateway agrees on "now"
local t   = redis.call('TIME')
local now = tonumber(t[1]) * 1000 + math.floor(tonumber(t[2]) / 1000) -- ms

local state  = redis.call('HMGET', KEYS[1], 'tokens', 'ts')
local tokens = tonumber(state[1])
local ts     = tonumber(state[2])
if tokens == nil or ts == nil then
  tokens = capacity
  ts = now
end

-- Lazy refill for the time that passed, capped at capacity
local elapsed = math.max(0, now - ts)
tokens = math.min(capacity, tokens + elapsed * rate / 1000)

local allowed  = 0
local retry_ms = 0
if tokens >= cost then
  tokens  = tokens - cost
  allowed = 1
else
  retry_ms = math.ceil((cost - tokens) * 1000 / rate)
end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
-- An idle bucket is full again after capacity/rate seconds; drop it then
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity * 1000 / rate) + 1000)

return { allowed, math.floor(tokens), retry_ms }

Details interviewers notice: the key arrives in KEYS, which Redis requires for scripts to work in a cluster. TIME inside a script that then writes is safe because Redis 5 made effects replication the default (Redis 7 dropped the old verbatim mode). The TTL frees idle buckets, and losing a full bucket costs nothing since a missing key starts full. Load the script with SCRIPT LOAD and call it with EVALSHA.

Key design: per user, IP, API key and route

The key decides what you are limiting. Use rl:{identity}:rule, where the braces are a Redis Cluster hash tag that keeps one identity's keys on one shard.

• Per API key (rl:{key:ak_123}:global): fairest for public APIs and maps directly to plan tiers.
• Per user and route (rl:{user:42}:post_orders): expensive writes get tighter limits than cheap reads.
• Per IP (rl:{ip:203.0.113.7}:login): the only option before auth. Carrier-grade NAT and campus networks put thousands of users behind one IP, so keep IP limits loose.
• Per tenant (rl:{tenant:acme}:global): an umbrella so one customer with 500 API keys can't take shared capacity.

Return HTTP 429 Too Many Requests with a Retry-After header saying how many seconds to wait, plus a short JSON body explaining which limit was hit. RFC 6585 defines 429 and says the response may include Retry-After; a well-behaved client waits that long instead of hammering you.

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 3
RateLimit-Policy: "burst";q=20;w=4, "daily";q=10000;w=86400
RateLimit: "burst";r=0;t=3

{"error":"rate_limited","rule":"burst","retry_after_seconds":3}

RateLimit and RateLimit-Policy come from the IETF HTTPAPI working group draft draft-ietf-httpapi-ratelimit-headers. As of October 2026 the latest is draft 11 (May 2026), still an Internet-Draft, not an RFC, so the syntax may change. RateLimit-Policy gives each policy a quota (q) and window in seconds (w); RateLimit reports remaining quota (r) and seconds until reset (t). If Retry-After is present, it takes precedence.

Older conventions are everywhere: many APIs, GitHub among them, send X-RateLimit-Limit, X-RateLimit-Remaining and X-RateLimit-Reset, and earlier draft versions used separate RateLimit-Limit, RateLimit-Remaining and RateLimit-Reset fields. In the interview, "429 plus Retry-After, and remaining-quota headers on every response" earns the credit.

For most APIs, fail open: if Redis doesn't answer within a tight timeout, allow the request and log it. Stripe describes catching limiter errors so a bug or Redis outage never blocks real traffic. A limiter protects availability; it shouldn't be the reason you lose it.

Fail closed where abuse costs more than a short outage: login, OTP, password reset, paid SMS. If knocking out Redis unlocks unlimited OTP guesses, failing open handed the attacker the door. Decide per endpoint.

1. 1

   Give the limiter a strict timeout

   Around 5 to 20 ms. A slow limiter adds latency to every request.

2. 2

   Add a circuit breaker

   After repeated failures, skip Redis briefly instead of paying the timeout each time.

3. 3

   Fall back to a local limiter

   Each gateway enforces global limit divided by instance count. Approximate, but far better than nothing.

4. 4

   Alert on fallback mode

   Otherwise you find out about the scraping problem from your monthly bill.

Check against a Redis cluster in the same region and sync usage between regions asynchronously, accepting a small, bounded over-admission. A single global Redis adds a cross-region round trip, often tens to hundreds of milliseconds, to every request.

• Static split: each region gets a share of the global limit (60% Mumbai, 40% Frankfurt). Simple, but unfair when traffic shifts.
• Async aggregation: regions ship usage deltas to an aggregator every second or so, which rebalances shares. Over-admission is bounded by about one sync interval of traffic.
• Local plus global: a coarse in-memory token bucket per instance absorbs spikes, and only survivors hit Redis. Envoy documents this two-stage pattern.

Hot keys

One giant customer, or one shared IP during a Big Billion Days sale, can aim tens of thousands of checks per second at one key, and in Redis Cluster one key lives on one shard. Fixes, cheapest first: cache "blocked until" in gateway memory so rejected clients stop hitting Redis; take tokens in batches (grab 10 per call, spend locally); or split the key into N sub-buckets with limit / N each.

Clock issues

If each gateway uses its own clock, a pod 300 ms ahead refills faster than its neighbours, and an NTP correction backwards gives negative elapsed time. Reading TIME from Redis, as the script does, gives one clock per key. Clamp elapsed at zero anyway.

Other things that go wrong

• Retry storms: clients retrying 429s instantly make overload worse. Send Retry-After; SDKs should back off with jitter.
• Checking too late: run the limiter before the expensive database or model call.
• Untested rules: dark launch new limits in log-only mode first, as Stripe recommends.

A rate limit (10 per second) protects infrastructure from bursts. A quota (10,000 per day or month) is a billing decision. Quotas can use a cheap fixed window with a daily key, since boundary bursts don't matter there, but need durable accounting in a database if they drive invoices.

Store tier limits as data (free: 60 per minute, pro: 600) in config the gateway caches, so limits change without a deploy. Stripe also runs a concurrent requests limiter capping in-flight requests per user, which protects slow endpoints better than a per-second count, plus load shedders that drop low-priority traffic when the fleet is hot. Good material when the interviewer asks "what else?".

• Jumping to Redis before asking what is being limited and why.
• Counting in each server's memory and calling it distributed.
• Picking a fixed window without mentioning the boundary burst.
• Limiting only by IP, punishing everyone behind one carrier NAT.
• Forgetting the limiter itself can fail.
• Returning 500 or 403 instead of 429.

Next, read up on caching: the same Redis cluster and hot key problems show up there. Then try this question on a board with a timer running, which is when gaps in your story show.