Remix of Design a rate limiter

Source:
Company: Stripe, OpenAI, Meta
Difficulty: Medium

Problem statement

Design a service that limits how many requests each API client can make. It sits in front of every API endpoint at high traffic. Remix: limits must hold across three regions.

Requirements

Functional requirements

• Limit each client (API key, user, or IP) to N requests per window, per endpoint or tier.
• Return 429 Too Many Requests with Retry-After and X-RateLimit-Remaining headers.
• Rules change without a deploy (per-customer overrides for enterprise plans).

Non-functional requirements

• Adds under 2 ms p99 to every request; the limiter sits on the hot path.
• Works across many gateway instances, so counts must be shared.
• Fails open: if the limiter store is down, serve traffic rather than reject it.
• Roughly accurate is fine; a few percent over the limit at the edges is acceptable.

Back-of-the-envelope estimation

• 1M requests/s at peak across 200 gateway pods, 10M active keys.
• One counter per (key, rule, window) ≈ 50 bytes → 10M × 3 rules × 50 B ≈ 1.5 GB in memory. Fits in a small Redis cluster.

API design

Internal, called by the gateway: check(key, rule) → {allowed, remaining, reset_at}. Rules are config: {match: "POST /v1/charges", tier: "pro", limit: 100, window: "1s"}.

Data model

Redis keys rl:{rule}:{key}:{window_start} holding a count with a TTL of two windows. Rules live in a config store (e.g. a table plus a pushed cache in each gateway).

High-level design

flowchart LR
  C[Client] --> G[API gateway]
  G -->|check + incr| R[(Redis cluster)]
  G --> S[Service]
  CFG[Rules store] -. push .-> G

1. The gateway matches the request to rules from its in-memory rule cache.
2. It runs one Redis Lua script per rule that increments and reads in one round trip.
3. Allowed → forward; denied → 429 with headers.

Deep dives

Algorithm choice.

Sliding window counter: estimate = prev_count × (1 − elapsed/window) + curr_count.

Atomicity. Do the read-increment-compare in a Lua script so two gateways can't both take the last slot.

Hot keys. One huge customer can pin a Redis shard. Shard by key hash, and for the top keys keep a local token bucket per gateway with a share of the global limit (limit ÷ pods), synced every 100 ms.

Failure. Timeout of 5 ms on the Redis call; on timeout, allow and emit a metric. A circuit breaker stops calling Redis when it's down.

Multi-region. Keep limits per region (simplest), or divide the global limit across regions by traffic share and rebalance every few seconds.

Trade-offs

• Local-only counters are fastest but inaccurate with many pods; central Redis is accurate but adds a hop. The hybrid (local for hot keys, Redis otherwise) gets both.
• Fail open protects availability at the cost of letting abuse through briefly; for login endpoints, fail closed instead.