Rate Limiter#

Q: What is the difference between token bucket and leaky bucket?

Token bucket allows bursts up to the bucket size and refills at a steady rate. Leaky bucket smooths bursts into a constant output rate, like a queue with a fixed drain.

Q: How does a sliding window rate limiter work?

It tracks request timestamps in a window and counts how many fell in the last N seconds, giving accurate limits without the boundary spike of fixed-window counters.

Q: How do you build a distributed rate limiter with Redis?

Store per-key counters in Redis with TTL and update them atomically using INCR plus EXPIRE or a Lua script. All API servers read and decrement from the same shared state.

Q: What HTTP status and headers should a rate limiter return?

Return 429 Too Many Requests with X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, and Retry-After so clients can throttle themselves intelligently.

Q: Should I rate limit per user or per IP?

Both. Per-user limits enforce plan tiers. Per-IP limits block abuse from anonymous traffic and credential stuffing. Combine them with per-route rules for fine control.

Problem statement (interviewer prompt)

Design a rate-limiting layer for a public API used by millions of clients. Support per-key + per-IP + per-route limits with multiple plans (free 100/min, pro 10k/min), enforce limits accurately across a fleet of API servers, and add <1ms latency. Return standard headers.

flowchart LR
  C([Client])
  GW[API Gateway]
  RL[Rate Limiter<br/>token bucket]
  R[(Redis counters)]
  S[Service]
  C --> GW --> RL
  RL -->|allow| S
  RL -->|deny 429| C
  RL <--> R

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class C client;
    class GW edge;
    class S service;
    class R cache;
    class RL storage;

flowchart TB
  subgraph Client[Clients]
    A([App / Browser])
    M([Mobile])
    P((Partner API))
  end

  subgraph Edge[Edge Tier]
    LB[L7 LB / Envoy]
    GW[API Gateway]
  end

  subgraph RL[Rate Limit Layer]
    direction TB
    EX([Identity extractor<br/>API key / user / IP / tenant])
    POL[Policy lookup<br/>per route + plan]
    ALG[Algorithm<br/>token bucket / sliding window]
    LOCAL[Local in-memory<br/>per-pod allowance]
    SYNC[Async sync to central]
    HDR[Set headers<br/>X-RateLimit-Remaining<br/>Retry-After]
  end

  subgraph Central[Central Counter Store]
    R1[(Redis cluster<br/>Lua atomic ops)]
    R2[(Redis replica)]
  end

  subgraph Plans
    PDB[(Plans / Quotas DB)]
    CFG[Config service /<br/>dynamic update]
  end

  subgraph Algos[Algorithm catalog]
    TB[Token Bucket<br/>refill r tokens/s, cap b]
    LB1[Leaky Bucket<br/>smooths bursts]
    FW[Fixed Window<br/>simple, boundary spikes]
    SW[Sliding Log<br/>exact, memory heavy]
    SWC[Sliding Window Counter<br/>weighted approx]
  end

  subgraph Resp
    OK[200 / 2xx]
    DENY[429 Too Many Requests]
    DEG[Degrade<br/>shed lower priority]
  end

  A --> LB --> GW --> EX
  M --> LB
  P --> LB
  EX --> POL --> ALG
  PDB -.policies.-> POL
  CFG -.dynamic.-> POL
  ALG --> LOCAL
  LOCAL -. periodic sync .-> SYNC --> R1
  R1 --- R2
  ALG -->|allow| OK
  ALG -->|over limit| DENY
  ALG -->|priority| DEG
  ALG --> HDR
  Algos --- ALG

    classDef client fill:#dbeafe,stroke:#1e40af,stroke-width:1px,color:#0f172a;
    classDef edge fill:#cffafe,stroke:#0e7490,stroke-width:1px,color:#0f172a;
    classDef service fill:#fef3c7,stroke:#92400e,stroke-width:1px,color:#0f172a;
    classDef datastore fill:#fee2e2,stroke:#991b1b,stroke-width:1px,color:#0f172a;
    classDef cache fill:#fed7aa,stroke:#9a3412,stroke-width:1px,color:#0f172a;
    classDef queue fill:#ede9fe,stroke:#5b21b6,stroke-width:1px,color:#0f172a;
    classDef compute fill:#d1fae5,stroke:#065f46,stroke-width:1px,color:#0f172a;
    classDef storage fill:#e5e7eb,stroke:#374151,stroke-width:1px,color:#0f172a;
    classDef external fill:#fce7f3,stroke:#9d174d,stroke-width:1px,color:#0f172a;
    classDef obs fill:#f3e8ff,stroke:#6b21a8,stroke-width:1px,color:#0f172a;
    class A,M,EX client;
    class LB,GW edge;
    class POL,SYNC,HDR,CFG,FW,SW,SWC,OK,DENY,DEG service;
    class PDB datastore;
    class LOCAL,R1,R2 cache;
    class ALG,TB,LB1 storage;
    class P external;

Algorithm cheat sheet#

Algo	State per key	Allows burst	Notes
Token bucket	`(tokens, last_ts)`	yes (up to bucket size)	Most common; cheap
Leaky bucket	queue + drain rate	no, smooths	Like TB with bucket=1
Fixed window	count + window	spike at boundary	Easy
Sliding log	timestamps array	exact	Memory O(N)
Sliding counter	weighted avg of two fixed windows	approx, cheap	Cloudflare style

Distributed correctness#

Local-only counters drift; cross-pod inconsistencies allow short bursts.
Use Redis with Lua for atomic check-and-decrement.
Pre-fetch tokens in batches (e.g. 10 tokens/sync) to amortize Redis RTT.
Two-tier: local soft limit + central hard limit.

Identity / scope#

Per-IP (anti-abuse), per-API-key (paid plans), per-user, per-tenant, per-route, per-method.
Compound key: route:plan:user.

Failure mode#

Redis down → fail open (serve traffic) or fail closed (deny). Choose per route.
Stampede: many synced bursts - add jitter to Retry-After.

Glossary & fundamentals#

Concepts referenced in this design. Each row links to its canonical page; the tag column shows whether it is a high-level (HLD) or low-level (LLD) concept.

Tag	Concept	What it is	Page
`HLD`	Load balancer / GSLB	L4/L7 traffic distribution and failover	load-balancer
`HLD`	API gateway / BFF	single ingress, auth, rate limit, routing	api-gateway
`HLD`	CAP / PACELC	C vs A under partition; L vs C otherwise	cap-pacelc
`HLD`	Leader/follower replication	sync/semi-sync/async replication, failover	replication-leader-follower
`HLD`	Idempotency & retries	safe re-execution, backoff + jitter	idempotency-retries
`LLD`	Concurrency primitives	mutex, semaphore, RW lock, atomic, CAS	concurrency-primitives

Quick reference#

Functional#

Per-key allowance with refill rate r and burst capacity b.
Multiple scopes (IP, user, key, tenant, route).
Plan-aware quotas (free 100/min, pro 1000/min).
Standard headers: X-RateLimit-Limit/Remaining/Reset, Retry-After.

Non-functional#

Latency: < 1 ms added.
Throughput: 100k+ checks/s per node.
Centralized counters consistent within ~100 ms.

Token bucket pseudocode (atomic)#

allow(key, r, b, cost=1):
  now = T
  state = redis.HGETALL key  # tokens, last_ts
  delta = (now - last_ts) * r
  tokens = min(b, tokens + delta)
  if tokens >= cost:
     tokens -= cost
     redis.HSET key tokens=tokens last_ts=now
     return true
  return false

Run in a Lua script for atomicity.

Memory budget#

50 bytes / key. 10M unique keys = 500 MB → fits in one Redis shard.

Algorithms - when to pick#

Token bucket: burst-friendly APIs (Twitter, GitHub).
Leaky bucket: queueing systems (postal, network shaping).
Sliding window counter: large keyspace, cheap, "good enough" (Cloudflare, Stripe).
Sliding log: low-volume, exact requirements (audit).

Pitfalls#

Clock skew → token-bucket time math drift. Use single source (Redis TIME).
"Thundering retries" at Retry-After - jitter is mandatory.
IP-based limits killed by NAT / CGNAT.
Don't rate-limit health checks or critical control plane.

Refs#

Stripe rate-limiter blog post, Cloudflare sliding window blog, GCMD Token Bucket RFC2697, System Design Interview Vol 1 ch.4 (Alex Xu).

FAQ#

What is the difference between token bucket and leaky bucket?#