Design a Rate Limiter

Design a rate limiter that restricts the number of requests a client can make to an API within a time window. Support multiple limiting strategies and work correctly in a distributed environment.

Capacity Estimation

For 10M users, each making up to 100 req/min:

• Peak QPS: 10M × 100 / 60 ≈ 16.7M requests/sec
• Counter storage: 10M users × 1 counter × 8 bytes ≈ 80 MB in Redis — trivially fits in memory

Architecture

API Request
    │
    ▼
[Rate Limiter Middleware]
    │  checks Redis
    ├── Allowed → forward to API handler
    └── Denied  → 429 Too Many Requests

[Redis Cluster]
  key: ratelimit:{userId}:{window}
  value: request count
  TTL: window size

Algorithm comparison (implementation level)

• Token bucket: a bucket holds up to N tokens, refilled at a fixed rate; each request consumes one token, rejected if the bucket is empty. Allows bursts up to the bucket size, simple to reason about — the most commonly used approach in practice.
• Sliding window log: stores a timestamp per request in a sorted structure; a request is allowed if the count of timestamps within the trailing window is under the limit. Perfectly accurate, but memory cost grows with request volume (one entry per request in the window).
• Sliding window counter: approximates the sliding log using two fixed windows (current + previous) and a weighted count between them — far cheaper than storing every timestamp, with a small, bounded accuracy tradeoff.
• Fixed window counter: simplest — a counter per fixed time window (e.g. per-minute), reset at each boundary. Cheapest, but allows up to 2x the limit in a short burst spanning a window boundary (all requests at the end of one window plus all at the start of the next).

Distributed rate limiting with Redis: making the check-and-increment atomic

A naive GET count then INCR from the application has a race window between two app servers checking simultaneously — both could read "under limit" before either increments. Two fixes:

INCR ratelimit:{userId}:{window}
EXPIRE ratelimit:{userId}:{window} <window_seconds>   -- only on first increment

INCR itself is atomic in Redis, but the INCR + conditional EXPIRE pair is not — the standard fix is a Lua script, which Redis executes atomically as a single operation:

local current = redis.call("INCR", KEYS[1])
if current == 1 then
  redis.call("EXPIRE", KEYS[1], ARGV[1])
end
return current

Running this via EVAL guarantees the increment-and-maybe-expire happens as one atomic unit, closing the race window entirely.

Integration

The rate limiter is middleware, not an API itself. Response headers:

X-RateLimit-Limit: 100
X-RateLimit-Remaining: 42
X-RateLimit-Reset: 1735689600
Retry-After: 37    (only on 429)

Redis Data Model

Fixed window counter:

SET ratelimit:user123:1735689600 0 EX 60
INCR ratelimit:user123:1735689600

Sliding window log (more accurate, more memory):

ZADD ratelimit:user123 <timestamp> <requestId>
ZREMRANGEBYSCORE ratelimit:user123 0 <now - window>
ZCARD ratelimit:user123

Use a Redis Cluster to distribute the keyspace. Each rate limiter instance talks to the same Redis cluster, so limits are enforced globally across all API servers.

• Fixed window is simple but allows burst at window boundary (50 req at end of window + 50 at start of next = 100 in 2 seconds).
• Sliding window log is accurate but uses more memory (one entry per request vs. one counter).
• Token bucket smooths bursts and is the most flexible — used by most cloud providers.

Where to enforce the limit: client SDK vs gateway vs per-service

• Client SDK: cheapest (no network hop to check), but trivially bypassable — a malicious or buggy client can simply not enforce it. Only useful as a courtesy/UX signal, never as the actual control.
• API gateway: enforced centrally, before any backend service sees the request — the most common choice for a system-wide limit, since it's a single enforcement point that can't be bypassed by any individual service.
• Per-service: allows different limits per service/endpoint (a search endpoint might need a stricter limit than a health check), at the cost of duplicated enforcement logic and each service needing its own path to the shared rate-limit store (e.g. Redis).

Production systems commonly layer these: a coarse gateway-level limit as the primary defense, with finer per-service limits for specific expensive endpoints.

Multi-tenant / per-API-key dynamic rules

A production API gateway rarely enforces one global limit — different tenants (or pricing tiers) need different limits, and those limits need to be changeable without a redeploy. This means the rate limit rule itself (not just the counter) needs to be looked up dynamically per request: GET ratelimit-rule:{tenantId} from a fast config store (Redis, or an in-memory cache refreshed periodically from a config service) rather than hardcoded in application code. A common addition here is a quota (a longer-window cap — e.g. 1M requests/month) layered on top of the short-window rate limit (100 req/min) — the two serve different purposes: rate limiting protects against short bursts, quota enforcement protects the billing/business model, and a gateway often needs to check both independently.

Gateway-specific failure isolation

Since a gateway-level limiter sits in front of every request to every backend service, its own reliability matters more than a per-service limiter's would — a gateway rate limiter that adds significant latency or becomes unavailable affects the entire system, not just one endpoint. This is why the fail-open-vs-fail-closed decision (see Failure Scenarios below) is especially consequential at the gateway layer, and why the Redis dependency backing it needs its own health checks (Health Checks) feeding into the gateway's own resilience posture (a circuit breaker around the Redis call itself, defaulting to fail-open on timeout, is a common production pattern).

Redis is the single source of truth. Use Redis Cluster for horizontal scaling and Redis Sentinel for failover.

If Redis is unavailable: fail open (allow all requests) or fail closed (deny all). Most APIs choose fail open to avoid an outage becoming a complete blackout.

Follow-up questions this case invites — and their answers

Q: Token bucket or sliding window: which should I choose? A: A token bucket allows controlled bursts (up to the bucket size) while enforcing an average rate, which suits most APIs and is cheap to store (a token count and a timestamp). Sliding-window counters give smoother, more precise limits over an exact time window, avoiding the burst at fixed-window boundaries. Many systems use a token bucket for per-client limits, and a sliding window where fairness at boundaries matters.

Q: How do you enforce a limit consistently across many API servers? A: Keep the counters in a shared, fast store such as Redis, and update them atomically, with a Lua script or atomic increments with expiry, so concurrent requests on different servers can't both slip through. To cut latency, servers can also keep small local token allowances that they refill from the central store, trading a little precision for fewer round trips.

Q: What should happen if the rate-limit store is down? A: Decide explicitly between failing open (allow requests, protecting availability but temporarily losing protection) and failing closed (reject requests, protecting backends but causing an outage). Most public APIs fail open with local, per-server fallback limits, and alert. Sensitive endpoints such as login can fail closed.

Q: How should the API tell clients they're being limited? A: Return HTTP 429 Too Many Requests, with a Retry-After header, and ideally headers showing the limit, the remaining quota and the reset time. That lets well-behaved clients back off precisely, instead of hammering the endpoint with retries.

Q: At which layer should rate limiting happen? A: Usually in several. Edge or CDN limits absorb abusive floods cheaply. The API gateway enforces per-client and per-key quotas. Individual services protect their own expensive operations and dependencies. Each layer handles a different threat, and a single layer is rarely enough.

Q: How do you rate-limit fairly by user rather than by IP? A: Key the limit by authenticated identity (API key, user ID or tenant) whenever possible, since many users can share one IP (offices, mobile carriers) and one attacker can use many IPs. Apply IP-based limits only to unauthenticated endpoints, with generous thresholds and additional signals.