Distributed Rate Limiter

Functional

• Limit the number of requests a client can make in a time window (e.g. 100 requests/minute per API key).
• Rules are configurable per endpoint, per client tier and per dimension (user id, API key, IP).
• Rejected requests get a 429 with headers that tell the client when to retry.
• Limits apply across the whole fleet, not per server: 100/min means 100/min no matter which server handles the request.
• Operators can change limits without redeploying.

Non-functional

• Added latency on the request path must be tiny: p99 < 2 ms for the limit check.
• High availability: the limiter must never take the API down. Decide explicitly what happens when the limiter's state store is unreachable.
• Accuracy: a few percent over-admission under contention is acceptable; a 2× burst at window edges is not.
• Memory per tracked client must be small, since there can be tens of millions of keys.

Out of scope

• DDoS mitigation at the network layer (that lives in the CDN/WAF).
• Billing and quota accounting over months (a different system with exact counts).

Assumptions

• 10M daily active API clients, 1M concurrently active in any given minute.
• Fleet handles 100K requests/s at peak; every request does one limit check.
• One rule per request on average, two counters per rule for sliding window.

Throughput on the state store

• 100K checks/s × 1 atomic operation each = 100K ops/s. A single Redis node does ~100K–200K simple ops/s, so plan 2–4 shards for headroom, more if you run Lua scripts that touch several keys.
• With client-side batching (pre-aggregation, see deep dives) this can drop 10× to ~10K ops/s.

Memory

• Per key: key string (~40 B) + counter (8 B) + window timestamp (8 B) + Redis overhead (~50 B) ≈ 100 B.
• 1M active clients × 2 keys × 100 B ≈ 200 MB. Even 10M clients ≈ 2 GB. Fits one Redis node; shard for throughput, not for memory.
• Sliding window log instead: 100 req/min × 8 B timestamps × 1M clients ≈ 800 MB per minute of history. This is why the log is only for low-volume limits.

Latency budget

• Same-AZ Redis round trip ≈ 0.3–0.5 ms. Lua script execution ≈ 10–50 µs. Total ≈ 1 ms, which meets the p99 < 2 ms target with one round trip. Two round trips (read then write) would not, and would also be racy.

Rule storage

• Thousands of rules, a few hundred bytes each: kilobytes. Cache the whole rule set in every server's memory and refresh every ~30 s.

Internal check API (called by the gateway or middleware)

• allow(key: string, ruleId: string, cost = 1) → { allowed: boolean, limit, remaining, resetAt, retryAfter? }
• The key is built from the dimension, e.g. "user:123", "ip:203.0.113.5" or "apikey:abc:endpoint:/search".
• cost lets expensive endpoints consume more than one token.

Client-facing behaviour

• 429 Too Many Requests when rejected.
• Headers on every response: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset (epoch seconds). On 429 add Retry-After (seconds).
• Response body: { error: "rate_limited", retryAfter: 12 }.

Rule management API (operators)

• PUT /v1/rules/{ruleId} with { dimension, match: { endpoint?, tier? }, limit, windowSeconds, burst?, algorithm }
• GET /v1/rules, DELETE /v1/rules/{ruleId}.
• Rules are versioned; servers pull the latest version on a timer or get a push via a config channel.

Notes

• Never return a 429 without Retry-After: clients will hammer you with immediate retries.
• Soft-limit mode: log and allow but do not reject. Use it to dry-run a new rule before enforcing.

Counter state (Redis, ephemeral)

• Token bucket: key → { tokens: number, lastRefillMs: number }. Store as a hash or two fields packed into one string.
• Sliding window counter: two keys, "{key}:{currentWindow}" and "{key}:{previousWindow}", each an integer with EXPIRE = 2 × window.
• Keys expire automatically; nothing needs a cleanup job.

Rule store (durable, tiny)

• rule_id (PK), dimension (user | api_key | ip), match (endpoint pattern, tier), limit, window_seconds, burst, algorithm, mode (enforce | log), version, updated_at.
• Lives in a relational DB or a config service (etcd, Consul). Read-heavy, written rarely.

Audit / metrics (append-only)

• Rejections are emitted as events { key, rule_id, ts } to a stream for dashboards and abuse detection. Do not write these synchronously to a database.

Storage choice

• Redis for counters: in-memory, single-threaded per shard so Lua scripts run atomically, sub-millisecond, TTLs built in.
• Memcached would also work for fixed windows (incr + expire) but lacks Lua, so sliding windows and token buckets get racy.
• A SQL database is wrong here: 100K read-modify-write transactions per second on hot rows is exactly what relational row locks are bad at.

Control path

• Operators write rules through a rules service into a durable store.
• Every gateway instance polls the rules service every ~30 s (or subscribes to a change feed) and swaps its in-memory rule set atomically.

Observability path

• The middleware emits allow/reject counters to the metrics pipeline and rejection events to a stream for abuse dashboards.

Why the gateway?

• One implementation, one place to tune. Services stay stateless and simple. Service-specific limits are still possible: the gateway knows the route, so rules can match on endpoint.

Why Redis is on the critical path, and what that costs

• One extra network hop per request (~1 ms). The alternative, local counters, cannot give a fleet-wide limit. The deep dives cover how to survive Redis being slow or down.

1. Token bucket maths and the atomic Lua script

• Bucket of capacity B (burst), refilled at r tokens/second. For 100 req/min with burst 20: r = 100/60 ≈ 1.67 tokens/s, B = 20.
• On each request: tokens = min(B, tokens + (now − lastRefill) × r); if tokens ≥ cost then tokens −= cost and allow, else reject with retryAfter = (cost − tokens) / r.
• Doing GET then SET from the app is a race: two servers read tokens = 1 and both allow. Put the whole read-compute-write in a Lua script: EVALSHA script 1 key now rate burst cost. Redis runs it atomically on the shard, so the counter is exact.
• Store tokens and lastRefill in one hash; set EXPIRE to the time it takes to refill fully so idle keys disappear.

2. Sliding window counter with two keys

• Fixed windows allow 2× bursts: 100 at 0:59 and 100 at 1:01. Sliding window log fixes it exactly but stores a timestamp per request.
• Approximation: keep a counter for the current window and the previous window. estimated = prev × (1 − elapsedFractionOfWindow) + current. For a 60 s window at 1:15, elapsed fraction is 0.25, so estimated = prev × 0.75 + current.
• Two INCRs and two EXPIREs, or one Lua script. Memory is two integers per key. Error is bounded and small for uniform traffic; interviewers accept it as the production answer.

3. Fail open or fail closed?

• Redis unreachable or slow (timeout at ~5 ms): fail open means allow everything and log; fail closed means reject everything.
• Default to fail open for public APIs: a limiter outage should not become an API outage. Protect the backends with a local fallback limiter (per-server token bucket with limit / N servers) so you are not fully unprotected.
• Fail closed for security-sensitive limits (login attempts, OTP verification), where over-admission is worse than downtime.
• Use a circuit breaker: after K consecutive Redis errors, stop calling Redis for a few seconds and use the local fallback, then probe.

4. Rate limit headers and client behaviour

• X-RateLimit-Limit (the cap), X-RateLimit-Remaining, X-RateLimit-Reset (epoch seconds when the window resets or the bucket is full). On 429: Retry-After in seconds, rounded up.
• Clients should back off with jitter; document it. Without Retry-After, a mobile fleet retrying every second turns a limit into a self-inflicted DDoS.
• Return the headers on allowed responses too, so well-behaved clients can pace themselves and never see a 429.

5. Multiple dimensions, hot keys and local pre-aggregation

• Limit by user and by IP at once: evaluate each rule, allow only if all pass, and decrement all. If the second rejects after the first incremented, you over-counted by one; accept it or run both in one Lua script with both keys on the same shard (use hash tags like {user:123}).
• Hot keys: one abusive client at 50K req/s hits one Redis shard. Mitigation: once a key is over its limit, cache the rejection locally for the rest of the window (the gateway knows resetAt), so Redis is not asked again.
• Pre-aggregation for very high limits (e.g. 1M/min for a partner): each gateway batches its local count and flushes to Redis every 100 ms with INCRBY. Accuracy drops to ±(servers × flush interval × rate) but Redis load drops 10–100×.

6. Distributed clocks and window boundaries

• Use Redis TIME inside the Lua script as the clock, not each server's clock, so all servers agree on window boundaries and refill maths.

Summary of decisions

• Sliding window counter by default, token bucket where bursts are a feature; both as atomic Lua scripts in Redis.
• Centralised Redis for accuracy, with a local per-server fallback limiter and a circuit breaker for availability.
• Fail open for public APIs, fail closed for auth-sensitive endpoints.
• Enforcement at the gateway with rules cached in memory and refreshed every 30 s.
• Full X-RateLimit-* and Retry-After headers on every response.

What was given up

• Exactness: the sliding window counter is an approximation, and multi-dimension checks can over-count by one.
• Rule changes take up to 30 s to apply everywhere.
• One extra hop on every request.

With more time

• Per-client dynamic limits driven by abuse scores, global quotas over days/months in a separate accounting system, and a dry-run mode that reports what each new rule would reject before enforcing it.