Rate Limiter

1. What Is It?

A rate limiter controls how many requests a client can make to a service within a given time window. It's a traffic control mechanism that protects services from overload, prevents abuse, enforces fair usage, and enables different tiers of service (free vs. paid plans). Without a rate limiter, a single misbehaving client can saturate a server, degrading service for all users — or a misconfigured client loop can accidentally DDoS your own API.

Rate limiters are placed at the API gateway, load balancer, or within the service itself. In distributed systems, they require a centralized counter store (typically Redis) to count requests across multiple server instances. The choice of algorithm is the core design decision: the five main algorithms have different tradeoffs in memory usage, burst handling, and boundary accuracy.

2. How It Works

The Five Core Algorithms

Algorithm 1: Token Bucket

A bucket holds tokens up to a fixed capacity. Tokens are added at a constant refill rate. Each request consumes one token. If the bucket is empty, the request is rejected.

Capacity: 10 tokens  |  Refill rate: 5 tokens/sec

t=0s:   [●●●●●●●●●●] = 10 tokens (full)
         → burst: 10 requests fired immediately, all pass

t=0.2s: [          ] = 0 tokens
         → request rejected

t=1.0s: [●●●●●     ] = 5 tokens (1 second of refill)
         → 5 requests pass

Key property: Allows bursting up to bucket capacity. Idle time accumulates tokens, enabling a burst of requests above the sustained rate. This is how most real APIs work — Stripe allows brief bursts, then enforces a sustained rate.

Redis implementation (requires Lua for atomicity):

Copy
local tokens = tonumber(redis.call('HGET', key, 'tokens'))
local last_refill = tonumber(redis.call('HGET', key, 'last_refill'))
local now = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local capacity = tonumber(ARGV[3])

-- Add tokens accumulated since last refill
local elapsed = now - last_refill
local new_tokens = math.min(capacity, tokens + elapsed * refill_rate)

if new_tokens >= 1 then
    redis.call('HSET', key, 'tokens', new_tokens - 1, 'last_refill', now)
    return 1  -- allowed
else
    return 0  -- rejected
end

WHY Lua? The read-modify-write sequence must be atomic. Without Lua, two concurrent requests could both read tokens=1, both decide to proceed, and both write tokens=0 — counting one request but letting two through. Redis Lua scripts execute atomically.

Algorithm 2: Leaky Bucket

Requests queue in a FIFO buffer. The buffer drains at a constant rate. If the buffer overflows, requests are rejected.

Inflow: bursty  →  [=======]  →  Outflow: constant rate
                    bucket

Key property: Strictly uniform output rate — no bursting. Used for traffic shaping (smoothing out bursts). Used in Nginx's limit_req module (the burst parameter acts as the queue size).

Difference from Token Bucket: Token bucket allows accumulated tokens to be spent as bursts. Leaky bucket always processes at a constant rate — bursts are queued, not immediately served.

Algorithm 3: Fixed Window Counter

Time is divided into fixed windows (e.g., per minute). A counter per client is incremented on each request and reset at window boundaries.

Window size: 60s  |  Limit: 100 req/window

t=00:00 → counter = 0 (reset)
t=00:58 → counter = 99 (one more allowed)
t=00:59 → counter = 100 (limit reached — blocked)
t=01:00 → counter = 0 (reset! — new window)
t=01:00 → counter = 100 requests in 2 seconds straddling boundary
         ↑ PROBLEM: 200 requests in a 2-second span around the boundary

The boundary spike problem: A client can fire the full quota just before a window ends and the full quota again just after it resets, passing 2x the limit in a short real-time window.

Redis implementation (simplest — no Lua needed):

INCR user:123:2024010815  → counter
EXPIRE user:123:2024010815 60  → expire in 60s (only set on first request)

Algorithm 4: Sliding Window Log

Every request timestamp is stored in a sorted set. On each request, prune entries older than the window and check the count.

Window: 60s  |  Limit: 3 req/60s
Sorted Set: [12:00:10, 12:00:30, 12:00:55]

At 12:01:20, new request arrives:
  Prune timestamps < 12:00:20 → removes 12:00:10
  Remaining: [12:00:30, 12:00:55] → count = 2 < 3 → ALLOW
  Add 12:01:20 → [12:00:30, 12:00:55, 12:01:20]

Key property: Exact accuracy — no boundary spike problem. Every request is evaluated against the true sliding window.

Memory cost: O(N) per client where N = requests in window. At 1000 req/min across 100K clients = 100M entries in Redis. This is the primary weakness.

Redis implementation:

ZADD user:123 <timestamp> <timestamp>  -- add current request
ZREMRANGEBYSCORE user:123 0 <window_start>  -- prune old
ZCARD user:123  -- count requests in window

Algorithm 5: Sliding Window Counter (Hybrid)

Approximates sliding window using only two fixed-window counters.

Window: 60s  |  Limit: 100 req/60s
Currently 20% through the current minute

prev_window: 80 requests
curr_window: 15 requests

estimate = 80 × (1 - 0.20) + 15 = 64 + 15 = 79
→ Under 100 → ALLOW

At 75% through the current minute:
estimate = 80 × (1 - 0.75) + 15 = 20 + 15 = 35 → ALLOW

Key property: Memory-efficient (2 keys per client, not N), accurate enough for most applications. Cloudflare measured 0.003% error rate using this approach across 400 million requests.

Algorithm comparison:

Mermaid: Rate Limiter in Distributed Architecture

-+ResetFullscreen

Headers and Responses

Standard response for a rate-limited request:

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

{"error": "rate_limit_exceeded", "message": "Too many requests. Try again in 45 seconds."}

3. Variants & Comparisons

Where to Implement Rate Limiting

L4 vs L7 Rate Limiting

4. When to Use It (and When NOT To)

Use Rate Limiting When:

• Public APIs with SLAs: Protect your backend from a single client consuming all capacity. Enforces fair resource sharing.
• Authentication endpoints: Rate-limit /login and /register to 5–10 req/min to prevent brute-force and credential stuffing attacks.
• Pricing tiers: Free tier: 100 req/day; Pro tier: 10K req/day; Enterprise: unlimited. Rate limiting enforces the business model.
• Downstream service protection: If Service A calls Service B, rate limit A's calls to B to prevent cascade failures when A has a bug and fires 10K calls/sec.
• Cost control on expensive operations: LLM API calls, database-heavy queries, file processing — rate limit these to prevent cost overruns.

Design Decisions and Anti-Patterns:

• Don't rate limit synchronously at every layer: If API Gateway already rate-limits, adding rate limiting at every microservice too creates latency overhead without benefit. One enforcement point is usually enough.
• Fail open for infrastructure failures: If your Redis rate-limiter store goes down, don't reject all traffic. Stripe's approach: fail open — let requests through. Availability > correctness for rate limits.
• Respect the Retry-After header: Your rate limiter MUST return Retry-After in the response so clients can backoff properly instead of hammering the endpoint with retries.
• Don't use database as rate limit store: Rate limiting requires a fast, atomic counter store. Using PostgreSQL for counters creates lock contention under load. Redis is purpose-built for this.

5. Real-World Usage

Stripe — Token Bucket + Multiple Limiter Types

Stripe uses four rate limiters in combination backed by Redis with Lua scripts:

1. Request Rate Limiter (token bucket, ~25 req/s per API key by default): limits standard API call frequency
2. Concurrent Request Limiter (sorted set in Redis, max simultaneous in-flight requests): prevents a client from opening 1000 simultaneous connections
3. Fleet Usage Load Shedder (reserves capacity for payment endpoints): ensures /v1/charges always has headroom even during traffic spikes to /v1/events
4. Worker Utilization Load Shedder (sheds non-critical traffic during incidents): when servers are at >70% CPU, non-critical API calls (like listing webhooks) are rejected first

Fail-open policy: Redis outages do not block traffic — rate limiting errors are logged but requests pass through.

Cloudflare — Sliding Window Counter at Global Scale

Cloudflare's rate limiting spans hundreds of PoPs globally. The key insight: anycast routing ensures traffic from any IP consistently hits the same PoP, so counters stay local — no global coordination. Within each PoP, a Twemproxy cluster shards a memcache database. The sliding window counter uses two fixed windows with the weighted formula, achieving 0.003% error rate across 400M requests. Counter increments are fire-and-forget (async); once a client exceeds the limit, subsequent blocks are served from server memory without hitting memcache.

GitHub — Fixed Window, Per-Token Limits

GitHub uses simple fixed window counters with different limits by auth method:

• Unauthenticated: 60 requests/hour per IP
• Personal Access Token: 5,000 requests/hour per user
• OAuth App: 5,000 requests/hour per user (GitHub Apps owned by a GitHub Enterprise Cloud organization get up to 15,000/hour)

The simplicity of fixed-window works for GitHub because their API usage is fairly uniform — the boundary spike vulnerability is acceptable at GitHub's scale where legitimate clients don't deliberately exploit boundary timing.

6. Interview Cheat Sheet

5 Sentences to Show Deep Understanding

1. "The core tradeoff in rate limiter algorithm selection is memory vs. accuracy vs. burst handling: Token Bucket allows bursts and is memory-efficient but requires atomic Lua scripts; Sliding Window Log is perfectly accurate but O(N) memory per client; Sliding Window Counter approximates sliding window with only 2 counters and 0.003% error rate — the practical choice for most systems."

2. "In a distributed system, per-server counters are insufficient — a client could send 100 requests to each of 10 servers and bypass a 100-req/hour limit. Shared state in Redis is required, but this introduces latency (one Redis round-trip per request) and a single point of failure — mitigated by Redis Cluster and fail-open policies."

3. "Fixed Window is the simplest to implement (INCR + EXPIRE) but has the boundary spike problem: a client can fire the full quota at the end of one window and the full quota again at the start of the next, passing 2x the intended limit in a short window."

4. "Rate limiting should return 429 with a Retry-After header — without this, exponential backoff clients don't know when to retry, and naive retry loops will hammer the rate limiter instead of backing off intelligently."

5. "Stripe's four-layer rate limiting design separates concerns: the request-rate limiter handles steady-state API quotas, the concurrent-request limiter handles connection storms, and the load shedders handle degraded-system scenarios — each limiter targets a different failure mode."

Common Follow-Up Questions

Q: How would you design a rate limiter that works across a fleet of 50 servers? A: Centralized Redis as the shared counter store. Each request hits one of 50 servers; the server calls EVAL (Lua) on Redis to atomically check-and-increment the counter. Redis Cluster with 3+ nodes provides high availability. The latency cost is one Redis round-trip per request (~0.1–0.5ms) — acceptable for most APIs. For ultra-low-latency paths, use approximate counting with async increments (Cloudflare's approach).

Q: What happens if Redis goes down? A: Two strategies: (1) Fail open — allow all requests through, log that rate limiting is degraded (Stripe's approach — availability > correctness). (2) Fail closed — reject all requests with 429 (appropriate for security-critical endpoints like /login where brute force is a real threat). For most APIs, fail open is correct.

Q: How would you rate limit by user instead of by IP? A: Extract the user identifier from the request context — JWT token, API key in Authorization header, or session cookie — and use that as the Redis key prefix instead of IP. This requires rate limiting at L7 (after authentication), not L4. For unauthenticated endpoints, fall back to IP-based limiting.

Q: What is the "thundering herd" problem after rate limit expiry? A: When many clients are rate-limited simultaneously and the window resets, they all retry at the same moment, creating a request spike. Mitigations: (1) Jitter in Retry-After — return Retry-After: 45 ± random(10) so clients stagger their retries; (2) Token bucket instead of fixed window — gradual token refill naturally staggers request admission.

Connections to Other Building Blocks

• Redis (Key-Value Store): The backing store for distributed rate limiters. Uses atomic Lua scripts, INCR, ZADD, and EXPIRE commands.
• API Gateway & Reverse Proxy: Rate limiting is typically implemented as API Gateway middleware (Kong, AWS API Gateway, nginx). The gateway is the enforcement point.
• Message Queues: Instead of rejecting rate-limited requests, queue them for deferred processing. Useful when the SLA is eventual processing rather than immediate response.
• Circuit Breaker: Rate limiting and circuit breaking complement each other. Rate limiting protects the server from too many requests; circuit breaking protects the client from a failing server. Both are back-pressure mechanisms.
• Load Balancing: Rate limiting counters must be shared across all load-balanced instances — otherwise each server enforces its own limit independently.