Design Rate Limiter

What are we designing? A distributed rate-limiting service that sits in front of our APIs and protects them from abuse. Every incoming request passes through the limiter, which decides in <1 ms whether to allow or reject (HTTP 429). Limits are per-user, per-API-key, per-IP, and per-route, with multiple windows (e.g. '100 req/min and 1000 req/hour per user').

Rate limiting is deceptively hard. The single-node case is trivial — a counter in memory. The distributed case — where requests hit any of N API servers and the limit must be enforced globally — is the actual interview question. Add the requirement that limits are bursty-but-fair (allow a short spike, not a steady stream) and you are in algorithm territory.

Functional requirements.

• Limit by any identity key: user_id, api_key, IP, route, or combination.
• Multiple limits per identity (e.g. 100/min AND 1000/hour AND 10000/day).
• Return HTTP 429 with Retry-After header on rejection.
• Soft and hard limits: warn at 80% of limit, reject at 100%.
• Dynamic limit configuration: change limits without redeploying.

Non-functional requirements.

• Latency: p99 < 1 ms added to each request (on the critical path of every API).
• Availability: 99.99% (a dead limiter blocks all traffic).
• Accuracy: exact (not approximate) for hard limits; a slight over-allowance on soft limits is acceptable.
• Scale: 1M req/sec peak across the cluster.
• Fail-open vs fail-closed: depends on the route. Auth/login must fail-closed (better to lock users out than let an attacker in); content fetch should fail-open (better to over-serve than to 5xx the homepage).

Non-goals. No bot detection (that's a separate WAF). No DDoS mitigation at L3/L4 (that's Cloudflare).

Capacity estimation. Assume 100K req/sec steady, 1M req/sec peak.

Latency budget. The limiter adds to EVERY request, so it must be sub-millisecond. That rules out a synchronous DB lookup; we need in-memory or a co-located Redis.

Memory per counter. A token-bucket entry is ~50 bytes (key + tokens + last_refill timestamp). If we limit 10M unique users across 5 windows each, that's 50M entries x 50 B = 2.5 GB. Fits easily in a Redis cluster.

Network. Every request is one Redis round trip. 1M req/sec x 1 round trip = 1M Redis ops/sec. A 6-node Redis cluster handles 1M ops/sec comfortably (each shard ~200K ops/sec).

Write bandwidth. Each limit check is a read-modify-write (decrement tokens). At 1M ops/sec that's 1M writes/sec to Redis — fine, but each write is to a different key, so we need cluster-mode sharding.

Hot-key risk. A single user/IP hammering us at 100K req/sec concentrates all their writes on one Redis shard. Mitigation: short-circuit at the edge (per-instance local limit of 10 req/sec per IP) before hitting Redis; this drops the Redis load by 100x for abuse.

APIs.

POST /v1/check
  body: { identity: {user_id, ip, route}, timestamp }
  resp: { allowed: bool, remaining: int, retry_after_ms?: int, limit_name: str }

GET  /v1/limits/{identity}                  -> current usage
PUT  /v1/config/{limit_name}                -> update limit (hot reload)

The limiter is typically deployed as a sidecar (Envoy, Istio) or an in-process library (Stripe's Rack::Attack). The HTTP API above is for a standalone service.

Response headers. Every API response includes rate-limit headers so clients can throttle themselves:

X-RateLimit-Limit:     100
X-RateLimit-Remaining: 73
X-RateLimit-Reset:     1700000000
Retry-After:           12          (only on 429)

Data model. The limiter's state lives in Redis.

Token bucket (per identity per window):

key:   rl:{limit_name}:{identity}     e.g. rl:per_user:u_42
value: HASH { tokens: float, last_refill: ts }
TTL:   window_size_seconds * 2        (auto-expire idle buckets)

Sliding window (alternative, more accurate):

key:   rl:sw:{limit_name}:{identity}
value: ZSET member=ts, score=ts      (every request adds its ts)
       ZREMRANGEBYSCORE 0 (now-window)    (drop old)
       ZCARD                                 (count current window)
TTL:   window_size_seconds

Configuration (Postgres, cached in Redis):

limits (
  name          VARCHAR PRIMARY KEY,    -- 'per_user_minute'
  identity_dim  VARCHAR,                -- 'user_id' / 'ip' / 'route'
  algorithm     VARCHAR,                -- 'token_bucket' / 'sliding_window'
  capacity      INT,
  refill_rate   FLOAT,                  -- tokens per second
  window_sec    INT,                    -- for sliding window
  fail_mode     VARCHAR                 -- 'open' / 'closed'
)

Configuration is hot-reloadable: the limiter polls Redis every 5s for config changes, or subscribes to a Redis Pub/Sub channel rl:config.

Deep dive: token bucket vs sliding window vs leaky bucket.

Token bucket. Each identity has a bucket of size capacity, refilled at refill_rate tokens/sec. Each request consumes 1 token; if the bucket is empty, reject. Pros: allows bursts (a full bucket of 100 tokens lets a user do 100 req in 0.1s). Cons: the first request after an idle period gets the full bucket, which can cause micro-bursts. This is the AWS API Gateway default.

Sliding window. Track every request's timestamp in a sorted set; on each new request, drop entries older than window, count remaining, reject if >= limit. Pros: exact — the limit is 'at most N in any rolling 60s'. Cons: O(N) memory per identity for the timestamps; expensive for high-volume keys. This is what Stripe uses for its API limits.

Sliding window counter (hybrid). Approximate sliding window by combining a current-window counter and a previous-window counter, weighted by overlap: est = curr + prev * (1 - elapsed/window). Pros: O(1) memory, ~87% accuracy. Cons: slight over/under-allowance at window boundaries. This is what Cloudflare uses and is our recommended default.

Leaky bucket. Requests enter a queue at any rate; the queue drains at a fixed rate. Pros: smooths out bursts into a steady stream (great for downstream protection). Cons: adds latency (queue wait); not a great fit for HTTP APIs. Used in telecom and by guava RateLimiter.

Atomicity in Redis. A naive GET tokens; DEC; SET is racy — two concurrent requests could both read 1 token and both decrement to 0, allowing 2 when the limit is 1. The fix is a Lua script: Redis executes the script atomically, so read-modify-write is single-threaded and safe. This is the only correct way to do rate limiting in Redis.

Distributed coordination. Even with Redis atomicity, two API instances checking the same user at the same instant both hit the same Redis shard — fine, that's atomic. The hard case is when Redis itself is partitioned. We use Redis Cluster with quorum reads (READWRITE on the primary) — if the primary is down we either fail-open or fail-closed per route's fail_mode.

Local L1 cache. Each API instance keeps a tiny per-instance token bucket that caps traffic at, say, 2x the global limit. This short-circuits 99% of requests (no Redis call) and bounds Redis load. The slight over-allowance (each of N instances allows the local limit, so total can be N x local) is acceptable for soft limits; the global Redis check still enforces the hard limit.

Bottlenecks and failure modes.

• Hot identity. A user (or attacker) at 100K req/sec concentrates writes on one Redis shard. Mitigation: the L1 local bucket short-circuits at, say, 100 req/sec per instance, so Redis only sees ~100 req/sec from that user regardless of how hard they hit us.

• Redis failure. If Redis dies, every limit check fails. Mitigation: fail-open for read-heavy routes (allow the request, log for later analysis); fail-closed for auth/payment routes. Run Redis Cluster with replicas + automatic failover.

• Clock skew. Sliding-window algorithms depend on timestamps; if an API server's clock is 5 minutes off, it could compute wrong window boundaries. Mitigation: use NTP on all hosts; pass the request timestamp from the gateway (single source of truth) rather than reading the per-instance clock.

• Memory growth. Each unique identity consumes ~50 bytes. 100M users x 5 windows = 25 GB. Mitigation: TTL every key (Redis auto-expires idle buckets after 2x window). LRU-evict the L1 cache.

• Cold-start latency. A new user's first request finds no bucket in Redis; we create it. Slight latency spike on first hit. Mitigation: pre-create buckets for known active users; accept the one-time cost.

• Config propagation lag. When you lower a limit, instances pick it up over 5 seconds (polling) — during which they apply the OLD limit. Mitigation: use Redis Pub/Sub for push notifications (sub-second propagation).

• Thundering herd on Redis recovery. After a Redis failover, all instances retry at once. Mitigation: jittered backoff; L1 cache absorbs most retries.

Scaling strategy and trade-offs.

Horizontal scale. The limiter is stateless per instance — every node can serve every request. Scale by adding instances. Redis Cluster scales by adding shards (sharded by identity hash).

Multi-region. Run an independent limiter + Redis per region. Cross-region global limits are not enforced strictly — a user hitting two regions can do 2x the limit. If you need global limits, async-replicate counters to a single authoritative region with periodic reconciliation (accepting over-allowance).

Hierarchical limits. Per-instance local bucket -> per-shard Redis -> global Redis. Each layer is cheaper and weaker; the deepest layer enforces the true global limit. This is the standard pattern for high-QPS limiters (Cloudflare, Stripe).

Algorithms per limit. Use sliding-window-counter as the default; switch to token bucket for bursty APIs (where short bursts should be allowed); switch to leaky bucket for protecting downstream systems that can't handle spikes.

Trade-offs made explicit.

• We chose Redis-backed over in-memory only — gained global accuracy, lost the sub-ms latency of pure local checks (mitigated by L1).
• We chose Lua scripts for atomicity — gained correctness, lost the ability to use Redis Cluster's MULTI/ACROSS multiple keys (single-shard only; we shard by identity so this is fine).
• We chose fail-open for read routes — gained availability during Redis outages, lost strict enforcement during those windows.
• We chose sliding-window-counter over true sliding window — gained O(1) memory, lost ~13% accuracy at window boundaries.

Mental model. Think of Design Rate Limiter as a deliberate boundary in a system. The boundary exists because something becomes harder to manage when everything is done in one place: latency, scale, failure isolation, consistency, cost, or team ownership. The useful question is not “what does Design Rate Limiter mean?” but “what pressure makes this boundary worth introducing, and what new failure mode does it create?”

Example: 10M requests/day ÷ 86,400 ≈ 116 requests/s average. Design for peak rather than average; a 10× peak is ≈ 1,160 requests/s.

Answer this without notes: When would you choose Design Rate Limiter, and when would you intentionally avoid it? Mention at least one bottleneck it addresses, one failure mode it introduces, and one alternative. Then quantify the workload you are designing for.

Numerical sanity check

When estimating capacity, distinguish average from peak. If average traffic is 4,000 RPS and the observed peak-to-average factor is 3×, design the first pass around roughly 12,000 RPS, then leave headroom for failure and growth.