Design a rate limiter service

Fixed window counter (count per calendar minute) is the cheapest: one INCR with TTL. Its flaw is the boundary burst: a client can send 100 at 12:00:59 and 100 at 12:01:00, so 200 in two seconds. Sliding window log stores every request timestamp in a sorted set and is exact, but memory grows with the limit (10,000/min means 10,000 entries per key), so it is too expensive at 50M keys. Sliding window counter keeps the current and previous window counts and estimates: count = current + previous × (overlap fraction). It is two small counters per key and Cloudflare reported that on real traffic only about 0.003% of requests were wrongly allowed or limited; this is the best default for 'N per minute' quotas. Token bucket stores tokens and last refill time; each request refills tokens lazily (elapsed × rate, capped at burst) then takes one. It allows controlled bursts and supports cost-based limits (an LLM call costs tokens equal to estimated usage). Leaky bucket smooths output to a constant rate and is really a queue, useful for protecting a downstream with fixed capacity, such as an SMS provider. Say which you choose and why; many systems use token bucket for per-second burst limits and sliding window for per-minute or per-hour quotas.

A naive implementation does GET count, compare, then SET count+1 from the API server. Two gateways can both read 99, both allow, both write 100, and the limit leaks. Under 1M req/s this is not rare. The fix is to make check-and-increment one atomic operation on the server holding the data. In Redis, a Lua script runs atomically on the shard: it reads the counters, decides, increments and sets TTL in one step, with no other command in between. For a simple fixed window, INCR is atomic by itself (INCR, then if result == 1 set EXPIRE; compare result to the limit). Keep all keys used by one script on one shard using a hash tag like rl:{k1}:..., because Redis Cluster rejects multi-key scripts across slots. Clock source matters too: use Redis server time (TIME command inside the script) or a monotonic time sent by the caller, not each gateway's wall clock, so windows align. Avoid distributed locks here: a lock per request would double the latency and become its own bottleneck.

At millions of requests per second, even 0.5 ms per Redis call adds up, and very hot keys (one big customer sending 50k/s) overload a single shard. Two techniques help. First, local pre-aggregation: each gateway keeps a local counter and syncs with Redis every 50-100 ms or every N requests, adding its local count in one INCRBY. Decisions between syncs use the last global count plus local count. You trade a small overshoot (bounded by gateways × sync interval × rate) for 10-100× fewer Redis calls; Stripe and Envoy-style designs use variants of this. Second, for very large limits, split the key into K sub-counters (k1#0..k1#7) spread across shards, each with limit/K, chosen at random per request; the sum is approximately right. For strict limits (OTP: 5/hour/phone) keep the exact central check, since the volume per key is tiny. A clear senior point: accuracy needs differ by rule, so the design supports both an exact path and an approximate fast path.

A central gRPC service is easy to update and to reason about, but adds a network hop. A library or Envoy filter inside each gateway talking directly to Redis removes a hop and a failure point, but spreads rule logic across many deployments. A common middle ground is a sidecar or in-gateway filter with rules pushed from a central config service, which is how Envoy's global rate limit works (it calls an external rate limit service) and what most API gateways offer.

If Redis is down, failing closed blocks all traffic, turning a cache outage into a full outage. Failing open keeps the business running but removes protection exactly when you may be under attack. Choose per rule: fail open for general API quotas, fail closed or fall back to a conservative local in-memory limit (limit ÷ number of gateways) for OTP sends, login attempts and payment creation, where abuse costs real money (each OTP SMS costs ~₹0.15-0.25).

Exact central counting gives correct limits but costs one Redis round trip per check and suffers on hot keys. Approximate local batching scales far better but can overshoot by a few percent. For customer-facing paid quotas, a small overshoot is usually acceptable; for fraud and security limits it is not.

A single enterprise customer at 100k req/s sends all increments to one Redis shard. Use local pre-aggregation or split counters across shards. Also add a per-gateway local limiter as a first line, so obviously over-limit traffic is dropped without any Redis call.

A DDoS with millions of random IPs creates millions of new keys and fills Redis memory. Keep TTLs short, put IP-level limiting at the CDN/WAF layer, and cap memory with an eviction policy (volatile-ttl) so the limiter degrades gracefully.

Redis Cluster promotes a replica within seconds. Counters written since the last replication may be lost, so a few clients get a little extra quota; acceptable. During failover, the per-rule fail_mode applies and a local in-memory limiter keeps the worst abuse in check.

This would block all traffic for a service. Prevent with validation (limits above a floor for broad rules), shadow mode first, staged rollout of rule versions, and a one-click rollback to the previous version in etcd.

Each region has its own Redis. A global limit of 1,000/min can be split per region by traffic share (e.g. 600 Mumbai, 400 Hyderabad) and rebalanced every minute, or regions sync counts asynchronously and accept short-term overshoot. A single global Redis would add 30-100 ms cross-region latency, which breaks the 2 ms budget.