System Design

Design Rate Limiter

Protect APIs with token bucket, sliding window, or leaky bucket — per user, IP, or API key across distributed servers.

Interview tip Compare algorithms with a table. Mention Redis INCR + TTL, Lua scripts for atomicity, and returning 429 with Retry-After header.

① Functional requirements

Define rules: {identifier, limit, window} e.g. 100 req/min per API key
On each request, return allow or deny before reaching backend
Support multiple rule dimensions: per key, per IP, per endpoint
Return HTTP 429 with Retry-After header when throttled
Admin API to create/update/delete rules at runtime
Expose metrics: throttle rate, top offenders

Out of scope (state in interview)

DDoS protection at network layer (WAF / Cloudflare)
Billing / quota enforcement with payment
Per-payload-size limits (only request count)
ML-based anomaly detection

② Non-functional requirements

Decision latency < 5ms p99 added to request path
Accurate across all gateway nodes (distributed consistency)
Highly available — limiter failure should not take down API
Support 50K+ RPS checks across cluster
Memory efficient — millions of keys with sparse activity

③ Back-of-the-envelope scale

Assumptions

50K RPS aggregate across all APIs
1M registered API keys; ~100K active/hour
Average 2 rate-limit checks per request (global + endpoint rule)
100K checks/sec → Redis must handle 100K+ ops/sec
Memory: sliding window log worst case 100 timestamps × 100K keys ≈ 80MB (bounded)
Rules config: ~10K rules, cached in gateway memory, refresh every 30s

Prefer approximate sliding window counter over per-request log storage — 1 Redis key per (identifier, window_bucket) with INCR + EXPIRE uses ~50 bytes per active key.

④ High-level architecture

Distributed Rate Limiter

Clients

API Gateway / Envoy (rate limit filter)

Rate Limiter Service (optional central)

Local LRU Cache (hot keys)

Redis Cluster (counters)

Rules Config Store (etcd / DB)

Backend Microservices

Request→Check local cache→Redis INCR→Allow / 429

Embed limiter in API gateway (Envoy rate limit service, Kong plugin) to avoid extra hop. Redis Cluster with hash tags per API key for locality. Lua script ensures atomic INCR + compare + TTL.

⑤ Data flow & execution path

End-to-end execution flow

① Client→② API / LB→③ Core services→④ Cache + DB→⑤ Message queue→⑥ Async workers

Sync path: validate → authorize → read/write primary store
Async path: publish domain events → consumers (email, analytics, search index)
Read-heavy path: CDN / edge cache → regional cache → DB replica
Failure path: retry with backoff, DLQ, idempotent handlers

In interviews, trace one user action through this diagram. State what is synchronous (user waits) vs asynchronous (background), and where you enforce idempotency.

⑥ API & interfaces

Endpoint / flow	Purpose	Notes
Internal: check(key, rule)	Allow/deny decision	Returns {allowed, remaining, resetAt}; called by gateway middleware
POST /admin/rules	Create rule	{scope, identifier_pattern, limit, window_sec, action}
GET /admin/rules/{id}	Read rule	For dashboard
GET /metrics/throttled	Observability	Prometheus: rate_limit_exceeded_total{key, rule}
gRPC RateLimitService/ShouldAllow	Low-latency check	Used by sidecar; batch checks supported

⑦ Data model & storage

rules: id, scope (global|key|ip|endpoint), pattern, limit, window_sec, action (reject|queue)

Redis keys: rl:{rule_id}:{identifier}:{window_bucket} → integer counter, TTL = window_sec

Token bucket variant: rl:tb:{id} → hash {tokens, last_refill_ts}

Store	What	Why
Redis Cluster	Request counters	Sub-ms; atomic Lua; TTL auto-expires stale keys
PostgreSQL / etcd	Rule definitions	Source of truth; gateways poll or watch changes
Local process cache	Hot key decisions	100ms TTL; reduces Redis load 60–80%

⑧ Deep dive — core components

Algorithm comparison

Fixed window: INCR key rl:user123:1692000000 (minute bucket). Simple, 1 Redis op. Flaw: 2× burst at window boundary (100 at 0:59 + 100 at 1:00).

Sliding window log: Store sorted set of timestamps per key. Accurate but O(n) memory per key. Use only for strict tiers.

Sliding window counter: Weighted avg of current + previous window: count = prev_count × (1 - elapsed/window) + curr_count. ~2 Redis keys, good accuracy, industry standard (Cloudflare, Stripe).

Token bucket: Refill tokens at steady rate; allow bursts up to bucket size. Best when burst tolerance is a product requirement. Implement with Redis hash + Lua atomic refill.

Distributed correctness

Race condition: two gateways read count=99, both allow request 100 and 101. Fix: atomic INCR in Redis Lua script — increment first, then compare to limit. Never read-then-write from app code.

Clock skew: use Redis TIME or centralized window buckets keyed by floor(timestamp/window), not local clock. For token bucket, store last_refill in Redis, not gateway.

Fail-open vs fail-closed

Fail-open (allow on Redis down): API stays up; risk of abuse during outage. Use for consumer APIs with other protections.

Fail-closed (deny on Redis down): safer for paid/premium tiers. Mitigate with local token bucket fallback (conservative limit) when Redis unreachable > 1s.

Hybrid: fail-open for 99% traffic, fail-closed for admin/write endpoints. Circuit breaker on Redis client with half-open retry.

Performance at 100K checks/sec

Batch checks: gateway collects N requests, single Redis pipeline MGET/MINCR. Local cache with stale-while-revalidate — if local says "5 remaining", skip Redis until 0.

Shard Redis by API key hash. Avoid hot keys from shared NAT IPs — use API key over IP when possible; for IP limits, use /24 subnet aggregation.

⑨ Trade-offs & alternatives

Decision	Option A	Option B	Pick when
Algorithm	Fixed window	Sliding window counter	Fixed for dev; sliding for production APIs
Placement	Gateway middleware	Dedicated sidecar	Gateway simpler; sidecar for polyglot meshes
Store	Redis	In-memory only	Redis for distributed; local only for single-node dev
On Redis failure	Fail-open	Fail-closed	Open for availability; closed for security
Burst	Token bucket	Strict sliding	Token bucket if product allows bursts

⑩ 45-minute interview script

0–5 min: Clarify dimensions (key, IP, endpoint), limits, and 429 contract
5–10 min: Compare algorithms — draw timeline of fixed-window edge burst
10–18 min: Architecture — gateway, Redis, rules store; diagram
18–28 min: Deep dive atomic Redis Lua script; sliding window counter math
28–35 min: Fail-open vs closed; local cache layer
35–40 min: Admin API, metrics, rule hot-reload
40–45 min: Scale to 100K checks/sec — pipelining, sharding

⑪ Likely follow-up questions

Question	Short answer
Fixed window burst at boundary?	100 req last second of window + 100 first second = 200 in 2 sec; fix with sliding window
How to rate limit by IP behind NAT?	Prefer API keys; for IP use X-Forwarded-For carefully; /24 subnet bucketing
Different limits per user tier?	Rule priority chain: check tier rule first, then global; merge in gateway config
Redis down?	Local fallback bucket at 50% limit; or fail-open with alert; never silent unlimited
Global rate limit across regions?	Central Redis (latency cost) or CRDT counters (complex); often per-region + global cap in single DC
How to test rate limiter?	Chaos: kill Redis; load test boundary; verify 429 Retry-After accuracy

⑫ Revision checklist

Named 3+ algorithms with pros/cons
Explained fixed-window boundary burst problem
Redis atomic INCR/Lua for distributed correctness
429 + Retry-After response contract
Diagram: gateway → Redis → backend
Fail-open vs fail-closed decision
Local cache to reduce Redis load
Rules admin without redeploy
Memory estimate per active key
Metrics for throttle rate monitoring

RedisalgorithmsAPI gatewaydistributed systems