Design a Rate Limiter

Requirements

A rate limiter caps how many requests a client can make in a time window, for example "100 requests per minute per API key". It protects services from abuse, noisy neighbours, runaway scripts and cost spikes.

Functional

• Limit requests by a key: user ID, API key, IP address, or a combination with the endpoint.
• Support multiple rules (e.g. 10/s burst and 1,000/hour sustained).
• Reject excess requests with HTTP 429 and tell the client when to retry.
• Rules are configurable without redeploying.

Non-functional

• Low overhead: adds at most a millisecond or two per request.
• Accurate across a distributed fleet: limits hold even when traffic hits many servers.
• Highly available: if the limiter fails, the API should keep working (usually fail open).
• Scalable: millions of keys, hundreds of thousands of checks per second.

Where to Place It

Most production systems combine a coarse per-IP limit at the edge with finer per-user or per-plan limits at the gateway or service.

Algorithms

Token bucket

A bucket holds up to capacity tokens and refills at rate tokens/second. Each request consumes a token; an empty bucket means reject. Allows short bursts up to capacity while enforcing the long-run average. Used by AWS API Gateway and Stripe.

Leaky bucket

Requests enter a FIFO queue that drains at a constant rate; when the queue is full, new requests are dropped. Produces a perfectly smooth output rate, ideal for protecting a fragile downstream, but bursts wait in the queue and add latency.

Fixed window counter

Count requests per key in fixed windows (e.g. user:42:2026-10-29T15:21). Reset at the window boundary. Very cheap, but allows up to 2× the limit around a boundary: 100 requests at 12:00:59 and 100 more at 12:01:00.

Sliding window log

Store a timestamp for every request (e.g. a Redis sorted set). On each request, drop timestamps older than the window and count the rest. Perfectly accurate, but memory grows with the limit: a 10,000/hour limit stores up to 10,000 entries per key.

Sliding window counter

Keep counts for the current and previous fixed windows and weight the previous one by how much of it still overlaps the sliding window:

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

With a limit of 100/min, 80 requests last minute, 30 so far, and 25% into the current minute: 80 × 0.75 + 30 = 90, so the request is allowed. Memory is O(1) per key and accuracy is very good in practice (it assumes requests in the previous window were evenly spread).

Comparison

Token bucket in Java

A single-node, thread-safe implementation that refills lazily on each call instead of using a background timer:

public final class TokenBucket {
    private final long capacity;
    private final double refillPerNano;
    private double tokens;
    private long lastRefillNanos;

    public TokenBucket(long capacity, double refillPerSecond) {
        this.capacity = capacity;
        this.refillPerNano = refillPerSecond / 1_000_000_000.0;
        this.tokens = capacity;
        this.lastRefillNanos = System.nanoTime();
    }

    public synchronized boolean tryConsume(int cost) {
        refill();
        if (tokens >= cost) {
            tokens -= cost;
            return true;
        }
        return false;
    }

    private void refill() {
        long now = System.nanoTime();
        tokens = Math.min(capacity, tokens + (now - lastRefillNanos) * refillPerNano);
        lastRefillNanos = now;
    }
}

Keep one bucket per key in a ConcurrentHashMap<String, TokenBucket> and evict idle buckets. This works for one server; a fleet needs shared state.

Distributed Design with Redis

flowchart LR
  C[Client] --> LB[Load Balancer]
  LB --> G1[Gateway 1]
  LB --> G2[Gateway 2]
  G1 --> RL{Within limit?}
  G2 --> RL
  RL -->|yes| S[Backend Service]
  RL -->|no| R429[HTTP 429 Too Many Requests]
  G1 -.->|EVALSHA script| RC[(Redis Cluster)]
  G2 -.->|EVALSHA script| RC
  CFG[(Rules Config)] -.-> G1
  CFG -.-> G2

Every gateway node checks and updates the same counter in Redis, so the limit holds no matter which node handles the request. Rules are loaded from a config store and cached in memory on each node.

The race condition

A naive "read, check, write" sequence breaks under concurrency:

1. Gateway A reads count = 99.
2. Gateway B reads count = 99.
3. Both decide "allowed" and write 100. Two requests got through, but the count increased by one.

Fixes:

• Atomic primitives: for a fixed window, INCR then EXPIRE (set TTL only when INCR returns 1). INCR is atomic, so no lost updates.
• Lua scripts: Redis runs a script atomically, so read-modify-write logic for token bucket or sliding window executes without interleaving.
• Avoid WATCH/MULTI optimistic transactions on hot keys: they retry heavily under contention.

Token bucket as a Lua script

-- KEYS[1] = bucket key
-- ARGV[1] = capacity, ARGV[2] = refill tokens/sec, ARGV[3] = now (ms), ARGV[4] = cost
local capacity = tonumber(ARGV[1])
local rate     = tonumber(ARGV[2])
local now      = tonumber(ARGV[3])
local cost     = tonumber(ARGV[4])

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

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

local allowed = 0
if tokens >= cost then
  tokens = tokens - cost
  allowed = 1
end

redis.call('HSET', KEYS[1], 'tokens', tokens, 'ts', now)
redis.call('PEXPIRE', KEYS[1], math.ceil(capacity / rate * 1000) * 2)
return { allowed, math.floor(tokens) }

• Load once with SCRIPT LOAD, call with EVALSHA to avoid resending the body.
• The PEXPIRE lets idle buckets disappear, keeping memory bounded.
• Clock skew: gateway clocks differ. Either use NTP-synced clocks and tolerate small drift, or read time inside the script with redis.call('TIME') so one clock is authoritative.

Scaling Redis

• Redis Cluster shards keys by hash slot; a single key's script runs on one shard, so atomicity holds. Keep all keys a script touches in the same slot (use hash tags like {user:42}).
• Hot keys (one huge tenant) can overload a shard: split the limit into N sub-keys with limit/N each, or add a local pre-check.
• Latency budget: one Redis round trip is ~0.5–1 ms in-region. For extreme scale, keep local token buckets and sync with Redis periodically, accepting slight over-admission.
• Multi-region: a single global counter adds cross-region latency. Common compromise: per-region limits (global limit split by expected traffic share) with asynchronous reconciliation.

Responding to Clients

Return HTTP 429 Too Many Requests with headers that let well-behaved clients back off:

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

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

• Retry-After is standard (seconds or an HTTP date).
• X-RateLimit-* headers are a widely used convention; an IETF draft standardizes RateLimit and RateLimit-Policy headers.
• Send the limit headers on successful responses too, so clients can self-throttle.
• Clients should retry with exponential backoff and jitter to avoid synchronized retry storms.
• Optionally shed or queue instead of rejecting (leaky-bucket style) for internal, latency-tolerant traffic.

Trade-offs

Interview Tips

• Clarify the key (user, IP, API key), the limits, and strict vs approximate before drawing anything.
• Walk through at least three algorithms with their weaknesses, then pick one; the fixed-window boundary burst is a classic follow-up.
• Explain the read-check-write race and how Lua scripts or atomic INCR solve it.
• Mention Redis Cluster hash tags, hot keys, and clock skew; they signal real-world experience.
• State the failure policy (fail open vs closed) explicitly.
• Finish with the client contract: 429, Retry-After, rate-limit headers, and backoff with jitter.
• Consider layered limits: per-IP at the edge for DDoS, per-user and per-endpoint cost limits deeper in.