Rate Limiter

1. Requirements

Functional:

1. Limit by multiple dimensions: per-user, per-IP, per-API-key, per-endpoint, global floor.
2. Multiple algorithms: token bucket, leaky bucket, fixed window, sliding-window counter (at least two in prod).
3. Configurable rules per tier/endpoint with runtime updates (no deploy).
4. Headers on every response: X-RateLimit-Limit/Remaining/Reset; 429 with Retry-After on exceed.
5. Audit trail of rule changes + top-offender visibility.

Non-functional:

Out of scope:

• Billing/metering (consumes limiter signals, separate system).
• WAF/bot detection (feeds blocklists in, separate system).
• Per-request cost weighting beyond simple integer costs (v2).

2. Capacity Estimation

Assumptions: 100 edge gateways × 10k req/s each = 1M checks/s; 10M distinct limit-keys active; rule evaluation = 1 Redis Lua call.

3. API Design

The limiter is enforcement middleware, not a CRUD product — but it exposes two surfaces:

# Internal check (gateway -> limiter sidecar/service, or embedded Lua call)
POST /v1/check
{ "key": "user:8123:POST:/api/v1/shorten",
  "cost": 1,
  "policy": { "algorithm": "token_bucket", "capacity": 100, "refill_per_sec": 10 } }

200 OK
{ "allowed": true, "remaining": 87,
  "limit": 100, "reset_ms": 1300 }

429 Too Many Requests
Retry-After: 2
{ "allowed": false, "remaining": 0, "reset_ms": 2000 }

• Response headers on every proxied response: X-RateLimit-Limit, -Remaining, -Reset, plus X-RateLimit-Policy for debuggability.
• Quota tiers compose: request must pass global → endpoint → user/IP checks (deny on first fail, debit only on full pass — or debit-all-then-refund; pick debit-on-pass and say why: no refund races).

4. Data Model & Storage

-- Redis key layout (token bucket), all with PEXPIRE = window cap
-- ratelimit:{scope}:{id}:{endpoint} -> HASH { tokens, ts, version }
-- Fixed/sliding counters: ratelimit:{...}:{window_start} -> INT with EXPIRE

• Redis persistence: AOF every second — losing 1 s of buckets on failover only over-admits slightly; acceptable per requirements. No RDB restores into prod (stale buckets under-admit).
• Gateway caches rules in memory (30 s TTL + version check) so rule reads never add a hop.

5. High-Level Design

Request path: client → L4 LB → API gateway (Envoy/nginx) → limiter check (embedded Lua over pooled Redis conn, rules from local cache) → allow: proxy to service with rate headers; deny: 429 immediately. Control path: admin → config service (Postgres) → pub/sub rule push → gateways.

• Gateway (enforcement point): runs the check inline before proxying; holds rule cache; implements fail-open/closed policy.
• Redis Cluster: one Lua eval per check — fetch bucket, refill by elapsed time, admit-or-deny, set TTL — atomically.
• Config service: rule CRUD, versioning, canary rollout, audit log.
• Analytics side-path: allow/deny counters → Kafka → ClickHouse → dashboards + auto-tune suggestions.
• Fallback: in-process leaky counter (per-gateway, approximate) when Redis is unreachable.

6. Deep Dives

6.1 Distributed token bucket on Redis (the exact mechanism)

All logic in one Lua script so fetch-refill-decide-store is atomic across 100 gateways:

tokens = min(capacity, stored + elapsed * refill_rate)
if tokens >= cost: tokens -= cost; allowed = 1
else: allowed = 0
store(tokens, now); PEXPIRE(key, ceil(capacity / refill_rate) * 2)
return {allowed, tokens}

Why this shape: elapsed-time refill needs no background timers; TTL = 2× drain time bounds memory (idle keys vanish); returning remaining lets the gateway set headers without a second round-trip. Burst = capacity, sustained = refill_rate — two knobs map directly onto product tiers ("100 burst, 10/s sustained"). Clock: use Redis server TIME inside Lua, not client clocks — eliminates client-skew over-admission. Precision: milliseconds; sub-ms refill rounds down (slightly strict, safe direction).

6.2 Sliding windows: fixed vs log vs counter

Counter formula: estimate = current_window_count + prev_window_count × overlap_fraction. Two integer keys with EXPIRE, one INCR + one GET pipelined — no Lua needed. Name the boundary-spike flaw of fixed windows in the interview; it's the classic follow-up.

6.3 Races, clocks, multi-DC, fail-open vs fail-closed

• Races: without Lua, read-refill-write interleaves across hosts over-admit 2–5× under contention. Lua (or EVALSHA) is the whole fix; keep scripts deterministic and under ~1 ms.
• Sticky routing alternative: route same user to same gateway and keep buckets in-process — zero Redis cost, but rebalancing + gateway loss corrupts limits; use only as degraded fallback, say so explicitly.
• Multi-DC: each DC enforces against local Redis with the global quota divided (e.g. 3 DCs → each gets limit/3 with 20% headroom borrowing). True global exactness needs cross-DC coordination (Linearizability per check ≈ death at 1M/s) — so we accept bounded over-admission and document the bound.
• Fail-open vs closed: read path (GET product data) → fail-open (serve, alert); mutating/billing paths → fail-closed (reject with 503 + metric). Decide per-endpoint in the rule, not globally.
• Per-user vs per-IP: users share NAT IPs (mobile carriers!) — pure IP limits cause collateral 429s. Policy: authenticated → limit by user ID (generous) + loose IP backstop (DDoS only); anonymous → stricter IP limit + captcha escalation path.

7. Bottlenecks, Trade-offs & Monitoring

First bottleneck at 10x: Redis shard hot-spotting on viral keys (one celebrity's key = one hash slot) — mitigate with local gateway pre-aggregation (probabilistic admission for ultra-hot keys) + slot splitting by appending :n shards for top-K keys. Next: gateway→Redis AZ bandwidth.

Interview one-liners

• Q: Why Lua? / A: Makes refill-and-debit atomic across all gateways; without it, concurrent checks over-admit several-fold.
• Q: Exact global limits across DCs? / A: No — divide quota per DC with headroom; exactness would cost a coordination round-trip per request.
• Q: Limiter is down — fail open or closed? / A: Per endpoint: reads fail open, money-mutations fail closed; either way, page on it.

Related

• Coordination Services — rule distribution, leader-free config push
• Linearizability — why we don't pay for exactness
• Stream Processing — deny/allow analytics pipeline
• Cache Patterns and Eviction — gateway rule cache behaviour
• URL Shortener case — a consumer of per-user quotas
• Search Autocomplete case — per-IP throttles on expensive prefix queries