Design a Rate Limiter: Token Bucket, Sliding Window and Distributed Limits

The rate limiter is one of the few system design questions where the interviewer expects you to write real code. It is small enough to finish in an hour yet touches algorithms, concurrency, distributed state and API design. That makes it a favourite at Indian product companies and FAANG India offices for SDE-2 and senior loops. This guide gives you all five algorithms with runnable code, the Redis implementation that survives concurrency, and the architecture decisions around it.

Why rate limit at all? To protect services from overload (a buggy client in a retry loop, a scraper, a DDoS), to enforce commercial quotas (free tier gets 100 calls per minute), to control cost (every SMS OTP costs money), and to stop abuse like credential stuffing on login. Every Indian fintech that sends OTPs learns that last one quickly.

Requirements and Scale

Functional

• Limit requests per key per time window, with rules like "100 requests/minute per API key" and "5 OTP sends/hour per phone number".
• Multiple rules per request (per-user and per-IP and global) evaluated together.
• Rules configurable without redeploys.
• Clients are told they are throttled and when to retry.

Non-functional

• Low latency: the check adds at most a millisecond or two to every request.
• Highly available: the limiter must never become the reason the API is down.
• Accurate enough: small overshoot (a few percent) is acceptable for most limits; strict accuracy is needed only for costly actions.
• Works across many stateless API servers and possibly multiple regions.

Back-of-the-envelope

Assume 1M requests/sec at peak across the API fleet, 50M distinct keys active per day, and two rules checked per request. That is 2M limiter operations per second. A single Redis node handles on the order of 100K+ simple operations per second, so a cluster of a few dozen shards (keyed by limiter key) is needed. Memory: token bucket state is two numbers per key, roughly 100 bytes in Redis including overhead; 50M keys × 100 B = 5 GB, trivial. A sliding window log with a 1,000-requests/hour limit, in contrast, could store up to 1,000 timestamps per key; at 50M keys that is not feasible, which is the main reason that algorithm is reserved for small limits.

Where to Place the Rate Limiter

The interview answer: layer them. Coarse IP limits at the edge, per-API-key quotas at the API gateway, and business limits like "3 failed UPI PIN attempts" inside the owning service. Rate limiting also pairs with circuit breakers and backoff: the limiter protects you from clients, circuit breakers protect you from your dependencies.

The Five Rate Limiting Algorithms

All five implement allow(key) → bool. The Python versions below are single-process and use time.monotonic(); the Redis section makes them distributed. Throughout, assume a limit of 10 requests per 60 seconds unless stated.

1. Token Bucket Algorithm

Each key has a bucket holding up to capacity tokens. Tokens refill continuously at rate per second. A request takes one token; if none are left, it is rejected. Capacity controls the maximum burst; rate controls the long-run average. Stripe's engineering blog has described using token buckets in Redis for its API, and AWS API Gateway documents its throttling in token-bucket terms (rate plus burst).

import time

class TokenBucket:
    def __init__(self, capacity, refill_per_sec):
        self.capacity = capacity
        self.rate = refill_per_sec
        self.buckets = {}                      # key -> (tokens, last_ts)

    def allow(self, key, cost=1):
        now = time.monotonic()
        tokens, last = self.buckets.get(key, (self.capacity, now))
        # lazy refill: add tokens for the time elapsed since last check
        tokens = min(self.capacity, tokens + (now - last) * self.rate)
        if tokens >= cost:
            self.buckets[key] = (tokens - cost, now)
            return True
        self.buckets[key] = (tokens, now)
        return False

limiter = TokenBucket(capacity=10, refill_per_sec=10 / 60)   # 10/min, burst 10

Note the lazy refill: no background timer adds tokens. We compute how many would have been added since the last request. That is what makes token bucket O(1) time and two numbers of space per key.

import java.util.concurrent.ConcurrentHashMap;

public final class TokenBucketLimiter {
    private static final class Bucket {
        double tokens;
        long lastNanos;
        Bucket(double tokens, long lastNanos) { this.tokens = tokens; this.lastNanos = lastNanos; }
    }

    private final double capacity;
    private final double refillPerNano;
    private final ConcurrentHashMap<String, Bucket> buckets = new ConcurrentHashMap<>();

    public TokenBucketLimiter(double capacity, double refillPerSecond) {
        this.capacity = capacity;
        this.refillPerNano = refillPerSecond / 1_000_000_000.0;
    }

    public boolean tryAcquire(String key) {
        long now = System.nanoTime();
        Bucket b = buckets.computeIfAbsent(key, k -> new Bucket(capacity, now));
        synchronized (b) {                      // lock per key, not global
            double refilled = (now - b.lastNanos) * refillPerNano;
            b.tokens = Math.min(capacity, b.tokens + Math.max(0, refilled));
            b.lastNanos = Math.max(b.lastNanos, now);
            if (b.tokens >= 1.0) {
                b.tokens -= 1.0;
                return true;
            }
            return false;
        }
    }

    public static void main(String[] args) {
        TokenBucketLimiter l = new TokenBucketLimiter(3, 1);   // burst 3, 1/sec
        for (int i = 0; i < 5; i++) System.out.print(l.tryAcquire("u1") + " ");
        // true true true false false
    }
}

Dry run of the Java demo: the bucket starts with 3 tokens. Five calls arrive within microseconds, so refill is about zero. Calls 1–3 consume the 3 tokens; calls 4 and 5 find fewer than 1 token and are rejected. One second later a single token will have refilled.

2. Leaky Bucket Algorithm

Picture a bucket with a hole: requests pour in at any rate, but leave (get processed) at a fixed rate. If the bucket (a FIFO queue of size capacity) is full, new requests overflow and are dropped. The output is perfectly smooth, which is what you want when the downstream system is fragile, such as a legacy bank API or an SMS vendor with a fixed TPS contract.

There are two variants. As a queue, requests are actually delayed and processed by a worker at the leak rate. As a meter, you only track the bucket's water level and reject when it is full, which behaves like a token bucket viewed upside down.

import time

class LeakyBucket:
    def __init__(self, capacity, leak_per_sec):
        self.capacity = capacity
        self.leak = leak_per_sec
        self.state = {}                        # key -> (water_level, last_ts)

    def allow(self, key):
        now = time.monotonic()
        level, last = self.state.get(key, (0.0, now))
        level = max(0.0, level - (now - last) * self.leak)   # drain
        if level + 1 <= self.capacity:
            self.state[key] = (level + 1, now)
            return True
        self.state[key] = (level, now)
        return False

The queue form is what NGINX's limit_req module implements (it is documented as a leaky bucket), with a burst parameter for the queue size and nodelay to process queued requests immediately.

3. Fixed Window Counter

Divide time into windows (each minute) and keep a counter per key per window. Increment; reject when it exceeds the limit. In Redis it is two commands: INCR and EXPIRE.

import time

class FixedWindow:
    def __init__(self, limit, window_sec):
        self.limit, self.window = limit, window_sec
        self.counts = {}                       # (key, window_id) -> count

    def allow(self, key):
        window_id = int(time.time() // self.window)
        k = (key, window_id)
        self.counts[k] = self.counts.get(k, 0) + 1   # (old windows need cleanup)
        return self.counts[k] <= self.limit

4. Sliding Window Log

Store the timestamp of every accepted request per key. On each request, discard timestamps older than now − window, and allow if fewer than limit remain. It is exact for any rolling window, with no boundary burst, but memory is O(limit) per key.

import time
from collections import deque

class SlidingWindowLog:
    def __init__(self, limit, window_sec):
        self.limit, self.window = limit, window_sec
        self.logs = {}                         # key -> deque of timestamps

    def allow(self, key):
        now = time.monotonic()
        log = self.logs.setdefault(key, deque())
        while log and log[0] <= now - self.window:
            log.popleft()                      # evict expired entries
        if len(log) < self.limit:
            log.append(now)
            return True
        return False

Good for low, high-stakes limits: 5 OTPs per hour per phone, 3 password resets per day. Bad for 10,000 requests per minute per API key.

5. Sliding Window Counter

The practical favourite. Keep fixed-window counts for the current and previous window, and estimate the rolling count by weighting the previous window by how much of it still overlaps the rolling window:

estimate = prev_count × (1 − elapsed_in_current / window) + curr_count

Worked example: limit 100/minute. The previous minute had 80 requests; the current minute has 30 so far; we are 15 seconds into it. The rolling window covers the last 45 seconds of the previous minute (75% of it) plus the current 15 seconds. Estimate = 80 × 0.75 + 30 = 90 → allow. Counting this request, 10 requests fit at this instant (taking the estimate from 90 to 100); the 11th is rejected because accepting it would push the estimate to 101.

import time

class SlidingWindowCounter:
    def __init__(self, limit, window_sec):
        self.limit, self.window = limit, window_sec
        self.counts = {}                       # key -> {window_id: count}

    def allow(self, key):
        now = time.time()
        cur_id = int(now // self.window)
        elapsed = now - cur_id * self.window
        c = self.counts.setdefault(key, {})
        prev = c.get(cur_id - 1, 0)
        cur = c.get(cur_id, 0)
        estimate = prev * (1 - elapsed / self.window) + cur
        if estimate + 1 > self.limit:
            return False
        c[cur_id] = cur + 1
        for wid in [w for w in c if w < cur_id - 1]:
            del c[wid]                         # keep only two windows
        return True

It assumes requests in the previous window were evenly spread, so it can be slightly off, but analyses published by Cloudflare of this approach on their traffic found the error to be very small in practice. Two counters per key, no boundary burst: that is why many production limiters use it.

Algorithm Comparison Table

Redis + Lua: An Atomic Distributed Rate Limiter

With 200 stateless API servers, limiter state must be shared. The naive Redis approach has a race:

Server A: GET tokens:u1  → 1
Server B: GET tokens:u1  → 1
Server A: SET tokens:u1 0   (allowed)
Server B: SET tokens:u1 0   (allowed)   ← two requests spent one token

Fix it by moving the whole read-compute-write into a Lua script, which Redis executes atomically (no other command runs on that shard mid-script). It also saves round trips: one EVALSHA instead of several commands.

-- KEYS[1] = bucket key, e.g. "rl:tb:apikey_42"
-- ARGV[1] = capacity, ARGV[2] = refill tokens per second, ARGV[3] = cost
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local cost     = tonumber(ARGV[3])

-- use Redis server time so API servers' clock skew does not matter
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 then
  tokens = capacity
  ts = now
end

local elapsed = math.max(0, now - ts)
tokens = math.min(capacity, tokens + elapsed * rate / 1000)

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

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
-- expire idle buckets once they would be full again anyway
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity * 1000 / rate) + 1000)

-- Lua numbers become integers in replies, so send tokens as a string
return { allowed, tostring(tokens), retry_after_ms }

Calling TIME inside a script that then writes is safe on modern Redis (5.0+ replicates script effects rather than the script, and 7.0 made that the only mode). On older versions, pass the timestamp from the client instead and accept small skew.

-- KEYS[1] = "rl:swl:otp:+919800000000"
-- ARGV[1] = window ms, ARGV[2] = limit, ARGV[3] = now ms, ARGV[4] = unique request id
local window, limit = tonumber(ARGV[1]), tonumber(ARGV[2])
local now = tonumber(ARGV[3])
redis.call('ZREMRANGEBYSCORE', KEYS[1], 0, now - window)
if redis.call('ZCARD', KEYS[1]) < limit then
  redis.call('ZADD', KEYS[1], now, ARGV[4])
  redis.call('PEXPIRE', KEYS[1], window)
  return 1
end
return 0

import redis

r = redis.Redis(host="localhost", port=6379)
TOKEN_BUCKET_LUA = open("token_bucket.lua").read()
token_bucket = r.register_script(TOKEN_BUCKET_LUA)   # uses EVALSHA under the hood

def allow(api_key, capacity=100, per_sec=100 / 60):
    allowed, tokens, retry_ms = token_bucket(
        keys=[f"rl:tb:{api_key}"], args=[capacity, per_sec, 1])
    return allowed == 1, float(tokens), int(retry_ms)

In Redis Cluster, every key a script touches must hash to the same slot; with one key per script that is automatic. For multi-key scripts use hash tags like rl:{apikey_42}:minute. The Redis deep dive covers sorted sets and cluster slots in more detail.

Distributed Rate Limiting at Scale

A central Redis is accurate but adds a network hop and a dependency to every request. At very high volume, consider these options:

Hot keys

One huge customer making 50K requests/sec on one key concentrates all load on one Redis shard. Mitigations: local pre-filtering (once a key is clearly over limit, reject locally for the rest of the second without asking Redis), splitting a key's quota across sub-keys, or batching token grabs (take 100 tokens at a time and spend them locally).

Multi-region

A truly global, exact limit across Mumbai and Singapore regions requires cross-region coordination on every request, which costs 50+ ms. Usually you accept per-region limits (global limit divided by regions, or weighted by traffic) and asynchronously reconcile. Say this explicitly: exact global limits and low latency are in tension.

Failure modes

• Redis down: fail open with a conservative in-memory local limit, and alert. Blocking all traffic because the limiter's cache failed converts a minor incident into an outage.
• Fail closed only for limits whose purpose is preventing costly abuse: OTP SMS, login attempts, money movement.
• Set tight client timeouts (a few ms) on limiter calls so a slow Redis does not slow every API request.

HTTP 429, Retry-After and RateLimit Headers

When a request is rejected, return 429 Too Many Requests (defined in RFC 6585) and tell clients how to behave:

HTTP/1.1 429 Too Many Requests
Content-Type: application/json
Retry-After: 12
X-RateLimit-Limit: 100
X-RateLimit-Remaining: 0
X-RateLimit-Reset: 1760000000

{ "error": "rate_limited", "message": "Limit of 100 requests per minute exceeded. Retry in 12s." }

• Retry-After is standard HTTP (seconds or a date). The Lua script above computes it from the token deficit.
• X-RateLimit-* headers are a widespread convention (GitHub and many others use them). The IETF has a draft standardising RateLimit and RateLimit-Policy header fields; mentioning it shows you are current, but do not claim it is a final RFC.
• Send the remaining-quota headers on successful responses too, so good clients slow down before hitting the wall.
• Do not use 503 for client throttling; 503 means the server is unhealthy and causes different retry behaviour in clients and load balancers.

Pair 429s with client-side exponential backoff with jitter, otherwise all throttled clients retry at the same instant and create a new spike. More API status code nuances are in REST API interview questions.

Rate Limiter Architecture

rules:
  - id: public-api-free
    match: { plan: free }
    key: api_key
    algorithm: token_bucket
    capacity: 20
    refill_per_sec: 1.67          # 100/min
  - id: otp-send
    match: { path: /v1/otp/send }
    key: phone_number
    algorithm: sliding_window_log
    limit: 5
    window: 1h
    on_store_failure: deny        # fail closed: SMS costs money
  - id: global-search
    match: { path: /v1/search }
    key: ip
    algorithm: sliding_window_counter
    limit: 600
    window: 1m

Gateways cache the rules in memory and refresh on change, so a rule lookup never hits a database. Every decision emits a metric; a spike in denials for one key is often your first signal of a scraper or a broken client integration.

What Interviewers Look For

• Clarify the limit semantics: per user or per IP? Hard or soft? Is a burst acceptable? Which accuracy is acceptable?
• Know at least three algorithms with trade-offs, and be able to code token bucket and sliding window counter cold.
• Spot the race condition in distributed counting and fix it with Lua (or INCR for fixed windows, which is atomic by itself).
• Discuss fail-open vs fail-closed and latency budget for the check.
• Return proper 429 responses with Retry-After.

Follow-up questions to prepare

• "How would you implement different limits for free vs paid plans?" Rule matching on plan, with per-plan capacity and refill.
• "How would you rate limit during a flash sale?" Combine per-user limits with a global admission queue; see flash sale checkout design.
• "How do you avoid penalising users behind one NAT IP (a college campus)?" Prefer authenticated keys over IP; use generous IP limits only as an outer layer.
• "Can clients game a token bucket?" They can burst up to capacity by design; size capacity for what the backend can absorb.

A rate limiter also makes a great warm-up for related designs: a distributed cache (same sharding and hot-key issues) and an API gateway (where the limiter usually lives). If you can write the Lua script and explain every line, you are well ahead of most candidates who stop at "use Redis".

Frequently Asked Questions

Pranjal Jain

Ex-Microsoft SDE · IIT Kanpur · Founder of Prepflix. Helps engineers crack startup and product company interviews across India.