shreyansh

Rate Limiting and Throttling

30-Second Glance

  • Rate limiting protects availability and cost: one abusive client must never convert into a full-tier outage or a surprise bill.
  • Token bucket (bursty, average-rate) is the default; sliding-window counter when you need strict "no more than N per minute" edges; fixed window only with short windows or where boundary bursts don't matter.
  • Distributed enforcement needs a shared counter — Redis + Lua (~1 ms per decision) is the standard answer; purely local limiters over-admit by up to N× across N nodes.
  • Enforce as far out as possible (edge/WAF → gateway → service), and always answer 429 + Retry-After with X-RateLimit-* headers.
  • Throttling (slow down) vs load shedding (drop excess): shed at the edge, degrade gracefully inside (cached/stale responses over errors).

Algorithms

Algorithm Mechanics Burst behavior Memory Fit
Token bucket Bucket holds ≤ C tokens, refills at R/s; request consumes 1, denied if empty Allows bursts up to C at line rate, then steady R/s O(1) per key Default. APIs that tolerate bursts (Stripe-style: burst + sustained rate)
Leaky bucket Requests queue and drain at fixed R/s; overflow drops Smooths to constant rate — no bursts out O(queue) Egress shaping (metered webhooks, NTP-like steady outputs); rarely the ingress answer
Fixed window Counter per key:window (e.g. 60 s); reset each window Boundary burst: 2N back-to-back at window edges O(1) Cheap coarse limits (per-minute quotas) where 2× edge bursts are harmless
Sliding-window log Store each request timestamp (Redis ZSET); count last W seconds Exact, no boundary burst O(N requests) — expensive for hot keys Low-rate precise limits (password attempts: 5/min exact)
Sliding-window counter Weighted blend of previous + current fixed windows Near-exact, no boundary spike O(1) Strict per-minute/hour API quotas at scale — the production sweet spot

Worked numbers: "100 req/min + burst 20" as a token bucket = capacity 20, refill ~1.67 tokens/s; as fixed window it permits 200 requests straddling a boundary — if that breaks the DB, you needed sliding-window. GCRA (Generic Cell Rate Algorithm — theoretically clean leaky-bucket variant used by several Redis limiters) is worth one namedrop if pressed on correctness.

loading diagram…

Distributed Enforcement with Redis

A single box can count in memory; a fleet cannot — 10 nodes each allowing 100/min admit 1,000/min globally. Shared-state patterns:

  1. Fixed window with INCR + EXPIRE: INCR key:minute → if 1, EXPIRE 60; deny past N. Two round-trips, tiny race on expiry — fine for coarse limits.
  2. Token bucket / sliding-window-counter in Lua: one atomic script reads state, computes refill/weighting, writes back, returns allow/deny + retry-in. ~0.5–1 ms intra-AZ; atomicity kills the check-then-set race. This is the answer to "how do you make it exact."
  3. Sliding-window log with ZSET: ZREMRANGEBYSCORE old entries, ZCARD, ZADD now, EXPIRE — exact, but a 10k-rps key stores 10k entries/window; cap with trimming and reserve for low-rate keys.
  4. Approximation at scale: local per-node buckets synced periodically (over-admits bounded by sync lag), or sticky-route limit keys through consistent hashing (see Scaling Out and Load Balancing) so each key has one counter owner. Cloudflare-style edge enforcement does exactly this per-PoP with hierarchical sync.

Failure mode to state: if Redis is down, fail open or closed? Public read APIs usually fail open (availability over strictness, alert loudly); auth/payment paths fail closed or fall back to conservative local limits.

Where Enforcement Lives

Tier Mechanism Why there
Edge / CDN / WAF Per-IP/ASN rules, bot scores, geo blocks (Cloudflare, AWS WAF rate-based rules ~2k–10k req/5 min thresholds) Kills volumetric/DDoS traffic at zero origin cost; coarsest granularity
Gateway Per-API-key / per-plan quotas, per-route buckets (Kong, API GW usage plans) Business limits live here: free vs paid tiers, per-customer fairness
Service Per-user/per-resource semantic limits (5 password tries, 1 payout/min), concurrency caps (bulkheads) Only the service knows what "expensive" means for its domain
Client Exponential backoff + jitter on 429/5xx (AWS-style: min(cap, base × 2^attempt) + full jitter) Prevents retry storms from turning a blip into an outage

Headers are part of the contract: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset, and Retry-After on 429. Differentiate per-user (fairness), per-key/plan (monetization), and global (protect-the-tier) limiters — a global concurrency cap with queueing at the gateway is what stands between a flash sale and cascading timeouts, usually backed by async absorption via queues.

Trade-offs

Approach Pros Cons Use when
Token bucket Burst-tolerant; O(1); industry default Burst sizing is a guess; needs tuning General API rate limits
Sliding-window counter Strict edges without log cost; O(1) Slightly more math; Lua script to maintain Paid quotas, "exactly N/min" SLAs
Fixed window Trivial (INCR+EXPIRE) 2× boundary bursts Coarse internal limits
Sliding-window log Exact O(N) memory per hot key Low-rate precision (login attempts)
Local-only limiters Zero latency/cost; no dependency Over-admit up to N× nodes Single-node services, or failover fallback
Redis + Lua centralized Exact globally; ~1 ms New critical dependency; hot-key contention at extreme rps Multi-node fleets needing real fairness

Interview One-Liners

  • Q: Design "100 requests/minute per API key" across 20 gateway nodes.
    A: Sliding-window counter in Redis via one Lua script per decision (~1 ms); local-only counters would over-admit up to 20×.
  • Q: Token bucket or leaky bucket for a public REST API?
    A: Token bucket — clients burst legitimately (page loads, retries); leaky bucket is for shaping steady egress like webhook delivery.
  • Q: What's wrong with fixed windows?
    A: Boundary bursts: N requests at :59.9 plus N at :00.1 = 2N in a second. Acceptable for coarse quotas, fatal for DB-bound endpoints — use sliding-window there.
  • Q: Redis (rate-limit store) is down. Fail open or closed?
    A: Reads: fail open with conservative local caps + paging alert; auth/payments: fail closed or local-strict. State the blast radius either way.
  • Q: A user retries aggressively on 500s and amplifies an outage. Fix?
    A: Client backoff with jitter + gateway circuit breaking + idempotency keys so the retries that do arrive are harmless (see API Design).
  • Q: Throttling vs load shedding?
    A: Throttle (queue/slow) when the work is valuable and delay-tolerant — shed (429 fast) at the edge when the tier itself is at risk; never queue unboundedly.