Design a Rate Limiter (API Throttling)

Token bucket (the right default)
Each key has a bucket of N tokens, refilled at R tokens/second. Each request consumes 1 token. If the bucket is empty, deny. Pro: handles bursts naturally (full bucket = burst capacity). Pro: simple to implement. Pro: smooth refill. Used by AWS API Gateway, Stripe, Cloudflare.

Implementation in Redis:

• Store: (last_refill_timestamp, current_tokens) per key.
• On request: compute tokens = min(capacity, current + (now - last_refill) × R). If tokens >= 1, decrement, allow. Else deny.
• Atomic via Lua script.

Leaky bucket
Requests fill a bucket; bucket drains at constant rate. If the bucket overflows, deny. Functionally similar to token bucket but enforces a smooth output rate (good for protecting downstream systems from bursts). Used in network traffic shaping.

Fixed window counter
Count requests in 1-minute buckets. Reset to 0 each minute. Pro: trivial (single INCR). Con: 2x burst at window boundaries (100 at 0:59 + 100 at 1:00 = 200 in 1 second). Use only for coarse limits where this is acceptable.

Sliding window log
Store a timestamped log of every request per key. On new request, count entries in [now - window, now]. Pro: exact. Con: memory-heavy (store every request).

Sliding window counter (the practical exact-ish answer)
Combine fixed-window counter with weighted contribution from the previous window. count = current_window × elapsed_in_window + previous_window × (1 - elapsed_in_window). Pro: O(1) memory. Pro: avoids the 2x burst of fixed window. Pro: ~99% accurate. Used by Cloudflare, Snowflake (in places).

Recommendation in interviews: token bucket as the default; sliding window counter when you need closer-to-exact accuracy without per-request log overhead.

Naive single Redis instance: works until the instance falls over. The hard problem is sharing state across multiple decision-service nodes globally.

Approach 1: Centralized store (the simple right answer)
All decision nodes hit a shared Redis Cluster. Sharded by rate-limit key. INCR is atomic per key. Each rate-limit key lives on exactly one Redis shard.

• Latency: 1-2ms per decision (extra round trip to Redis).
• Failure: shard failure → keys on that shard are unenforced. Mitigation: replication.
• Cost: 50K keys × 1KB × 3x replication ≈ 150 MB. Trivial.

Approach 2: Local + async reconcile
Each decision node maintains its own counter. Periodically (every 100ms), nodes broadcast deltas to a central aggregator. Aggregator merges, redistributes. Works for relaxed accuracy.

• Latency: 0ms (purely local).
• Drift: counters can diverge by 100ms × node_count × per-node-rate. For 100 nodes at 10K rps, that's 1M requests of drift per cycle - too much for tight limits.

Approach 3: Predictive + central reconcile
Each node gets a per-node "budget" from the central aggregator (e.g., 1/N of the global limit). Spends locally. When budget runs low, requests more. This is how AWS API Gateway scales.

• Latency: 0ms in steady state.
• Drift: bounded by per-node budget size.
• Best for high-RPS limits where the centralized round-trip is too slow.

For interview: lead with centralized Redis (approach 1). Mention approach 3 as the "if we're at 10M+ rps and the round-trip is too expensive" answer.

Multi-region nuance: a global "100 rps per user" limit across regions requires either centralized state in one region (added latency) or accepting per-region limits that sum to the global cap. Most production systems accept per-region limits.

When the limit store is unreachable, the decision service has two options.

Fail-open
Allow the request. The service degrades to no rate limiting but stays responsive.

• Pro: protects user experience during a limit-store outage.
• Pro: doesn't cascade a limit-store outage into service unavailability.
• Con: malicious or buggy clients can exploit the outage to flood the service.

Fail-closed
Deny the request. The service degrades to "rate limit cannot be verified, denying for safety."

• Pro: deterministic behavior.
• Con: a 5-second limit-store blip turns into a 5-second outage of every protected endpoint. Cascading failure.

The right answer: fail-open by default for protective rate limiting (DDoS-style), fail-closed for billing-critical rate limiting (where exceeding the limit costs the company money).

Hybrid: local fallback
Each decision node maintains a small in-memory cache of "last known state" per key. If the limit store is unreachable, consult the local cache for an approximate decision. This catches the worst-case (user was at 99/100 a second ago, probably still over) without the full fail-closed cost.

Operational signal: monitor the rate of "store unreachable, falling back" events. A sudden spike means your limit store is degrading even if it hasn't fully failed.

Real APIs have plans (free, pro, enterprise) and per-endpoint limits (POST /charges has a different limit than GET /balance).

Rule structure

rule {
  name: "free_tier_global"
  match: { plan: "free" }
  limit: { rate: 100, period: "1m", burst: 20 }
}
rule {
  name: "free_tier_charges"
  match: { plan: "free", endpoint: "/charges" }
  limit: { rate: 10, period: "1m", burst: 5 }
}

A request matches multiple rules (free tier global + free tier charges); each rule's counter is consumed; if any rule denies, the request is denied. Return the strictest applicable limit's headers.

Hot-loading rules
Rules live in a config service (Consul, etcd, or a dedicated config DB). Decision service polls every 30s for updated rules. Local cache + ETag avoids re-fetching unchanged rules.

A/B testing limits
Want to test a tighter limit on 1% of users? Add a rule with a "user_id_hash mod 100 < 1" predicate. The decision service evaluates predicates in priority order; first match wins.

Per-endpoint overrides
Most endpoints share the global limit; expensive endpoints (search, export) get tighter limits. Define overrides as "additional" rules, not "replacements" - the global limit still applies, plus the endpoint-specific cap.

Interview signal: candidates who structure rules as a small DSL (not hard-coded if-else) score higher because it shows operational maturity.

Rate limiters interact with clients - response design matters.

Standard headers

• X-RateLimit-Limit: the configured rate (e.g., 100).
• X-RateLimit-Remaining: requests remaining in the current window.
• X-RateLimit-Reset: epoch timestamp when the window resets.
• Retry-After: seconds the client should wait before retrying. Set on 429 responses.

Status codes

• 429 Too Many Requests: standard. Include Retry-After.
• 503 Service Unavailable: only for fail-closed scenarios where the limiter itself is down.

Client-side behavior
Well-behaved clients respect Retry-After and back off. Misbehaving clients ignore it and hammer. The server must protect itself regardless.

Exponential backoff with jitter
Recommended client retry: wait Retry-After × (1 + random(0, 1)). Without jitter, multiple clients retry in lockstep and re-create the spike.

Webhooks and async clients
For webhooks (server-to-server), the receiver can return 429 to signal the sender to slow down. The sender must implement retry-with-backoff per the spec. Stripe's webhook delivery system implements this.

The interview gotcha: candidates often forget that the rate limiter still consumes a slot for the request that gets rate limited. Decide consciously - some limiters count denied requests against the limit (more aggressive); some don't (more forgiving).