23. Rate Limiting & Throttling

Rate limiting protects your service from abuse, accidental hammering, and runaway clients. It's also a productizable feature (per-tier quotas). The algorithms are simple; the operational details are where it gets interesting.

23.1 Why rate limit

Prevent abuse: stop bots, scrapers, brute-force attempts.
Fair sharing: no single tenant monopolizes the service.
Cost control: cap downstream LLM/API spend.
Stability: shed load before crashing.
Productize: free tier vs pro vs enterprise quotas.

23.2 Where to enforce

The further out, the better.

CDN / WAF: block at the edge before hitting your infra (Cloudflare, AWS WAF).
API gateway: per API key, per IP, per route.
Application: per user, per resource, per business rule.
Database: connection limits, query timeouts (last line of defense).

Enforce at multiple layers: CDN catches the obvious; gateway handles per-tenant; app handles fine-grained business rules.

23.3 Algorithms

Fixed window counter

Count requests per window (e.g., per minute). If count > N, reject. Reset at window boundary.

requests_in_minute = 0
on request:
  requests_in_minute++
  if requests_in_minute > 100: reject
on minute boundary: reset to 0

Pros: trivially simple. Cons: boundary problem. A burst at 11:59:59 + another at 12:00:01 → both pass, but 200 requests in 2 seconds. Doubles your effective limit at boundaries.

Sliding window log

Keep a list of timestamps. On request: drop timestamps older than window; if remaining count < N, allow and append.

Pros: precise. Cons: O(N) memory per key; expensive at scale.

Sliding window counter (approximate)

Approximation of sliding-window-log using two fixed windows.

Estimate = count(prev_window) * (1 - elapsed_in_current_window) + count(current_window).

Pros: O(1) memory; smooth. Cons: small approximation error; usually fine.

Token bucket

Bucket holds N tokens. Refill at rate R per second. Each request consumes 1 token. If empty, reject (or queue).

Pros: allows bursts up to bucket size; smooth average rate. Cons: requires per-bucket state.

on request:
  refill bucket based on time elapsed (cap at capacity)
  if tokens >= 1:
    tokens--
    allow
  else:
    reject

The most popular choice, used by AWS, Stripe, and many others.

Leaky bucket

Bucket has fixed-rate "leak." Requests fill the bucket; if it overflows, reject.

Pros: enforces constant rate (smooth output). Cons: no bursts allowed; some clients hate that.

Used in network traffic shaping (TCP).

Hierarchical / nested limits

Often combined: 100 req/sec AND 1000 req/min AND 10,000 req/hour.

Each request must pass all three levels.

23.4 Distributed rate limiting

A single server can use a local counter. With many servers, you need coordination.

Centralized counter (Redis)

Each request: INCR on a Redis key with expiry.

Atomic. Works across all servers.
Bottleneck: Redis hot key → single-shard limit (~100K ops/sec).
Mitigate: shard by user prefix; pre-aggregate locally.

Lua script for atomic check-and-increment:

local count = redis.call('INCR', KEYS[1])
if count == 1 then redis.call('EXPIRE', KEYS[1], ARGV[1]) end
if count > tonumber(ARGV[2]) then return 0 else return 1 end

Sliding window with Redis sorted sets

ZADD with timestamp; ZREMRANGEBYSCORE for old entries; ZCARD for count. Precise but expensive.

Token bucket in Redis

Store (tokens, last_refill_ts). Lua script atomically refills + decrements.

Global counters with eventual consistency

For very high-throughput limits where exact precision isn't needed: each server enforces a local soft limit; periodically sync with central. Hybrid approach used at Twitter, Cloudflare.

Stripe's approach

Per API key + per route. Uses a token-bucket variant; persists to Redis. Returns precise headers (X-Ratelimit-Limit, X-Ratelimit-Remaining, X-Ratelimit-Reset).

23.5 Headers and contracts

Standard headers on success:

X-RateLimit-Limit: 100
X-RateLimit-Remaining: 87
X-RateLimit-Reset: 1730000000  # epoch seconds

On rejection:

HTTP/1.1 429 Too Many Requests
Retry-After: 17

Well-behaved clients honor Retry-After. CDN/LB enforcement may use 503 + Retry-After instead.

23.6 Granularity

Common keys:

Per user / API key: most common.
Per IP: simplest; risky behind NAT/CDN (many users share IP).
Per (user, route): different limits per endpoint (e.g., /login strict, /healthz open).
Per tenant: multi-tenant SaaS.
Global: protect downstream service total capacity.

Apply multiple keys; reject if any limit breached.

23.7 What to do on rejection

Reject (429): simplest. Client retries.
Queue + delay: client doesn't care about latency; smooth load.
Shed gracefully: serve degraded response (cached, simplified).
Charge differently: paid tier gets through, free tier doesn't.

For login endpoints under brute force: slow down (throttle), don't reject (signals the attacker that account is real).

23.8 Special case: login / auth endpoints

Different threat model. Need:

Per-account rate limit (e.g., 5 attempts / 15 min).
Per-IP rate limit (combat distributed brute force).
Captcha after N failures.
Lockout with admin escalation for repeated abuse.
Slow hash (bcrypt, argon2) increases cost per attempt.

23.9 Rate limit vs concurrency limit

Rate: requests per time. Long-tail-friendly.
Concurrency: in-flight requests. Protects from slow operations piling up.

Both are useful. AWS API Gateway has both. Concurrency limit catches the case where each request is slow but the rate is "OK."

23.10 Backoff for clients

When a client hits 429, it should:

Honor Retry-After if present.
Exponential backoff with jitter: delay = min(cap, base * 2^attempt) ± random.
Cap retries: don't retry forever.
Different operations have different retriability: GETs always; POSTs only with idempotency keys.

Without jitter, retries from many clients sync up and create thundering herds.

23.11 Observability

Track:

429 rate per route, per tenant.
Top rate-limited clients.
"Almost rate-limited" (within 90% of limit) — early warning.
Limit breach by feature (signal: a tenant is hitting limits → upsell).

23.12 Quotas

A quota is a longer-term rate limit (e.g., 1M API calls per month). Enforced similarly but at coarser granularity. Often paired with billing.

Real-time enforcement: counter in Redis; reset monthly.
Soft limits: warn before hard cutoff.
Burst credits: unused minute-quota carries over.

23.13 Anti-patterns

Rate limit only on the app, not at the edge: bots saturate your stack before getting limited.
No retry-after: clients hammer immediately.
No shared state across instances: per-instance limits → effective limit = N × your intended limit.
Limit by IP only: NAT'd users blocked together.
Fixed-window only: edge bursts double the effective limit.
Silent rejection: 429 with no headers / docs → broken integrations.

23.14 Capacity sizing example

You want each user to do 10 req/sec; you have 1M users; peak factor 3×.

Aggregate peak: 1M × 10 × 3 = 30M req/sec... obviously not real. Realistic concurrent active users << total. Maybe 1% concurrent peak: 10K × 10 × 3 = 300K req/sec.
Redis can do ~100K ops/sec/node → need ~3 shards by hashing user_id.
Each instance also enforces a local soft cap to absorb bursts before central counter.

23.15 What an interviewer wants

Pick token bucket as default.
Discuss Redis as the central state.
Talk about hot key / sharding mitigation.
Mention headers: Retry-After, X-RateLimit-*.
Discuss multiple granularities (per-user + per-route + global).

Key takeaways

Token bucket is the default rate-limiting algorithm.
Centralize state in Redis; shard hot keys.
Enforce at multiple layers (CDN → gateway → app).
Always send Retry-After and rate-limit headers.
Login endpoints are special: throttle, don't reject; combine with captcha.