42. Design a Rate Limiter Service

Tests: distributed counter consistency, token bucket math, hot key strategies, latency budget.

42.1 Requirements

Functional

• Allow N requests per time window per (key, route).
• Reject (or queue) excess.
• Multiple algorithms supported (fixed window, sliding, token bucket).
• Configurable per tenant.

Non-functional

• Low latency (< 10 ms; rate limit check is on every request).
• High throughput (matches API gateway's QPS).
• High availability (rate limiter down ≠ service down).
• Accurate enough (small over-allow OK; under-allow not OK).

(See chapter 23 for algorithm details.)

42.2 Architecture

[ API gateway / app ]──RateLimit check──→[ Rate limiter svc ]
                                                  │
                                       [ Redis cluster (counters) ]
                                                  │
                                       [ Config store (rules) ]

42.3 Storage choice

Redis

The typical pick.

• INCR + EXPIRE is atomic.
• Sub-ms latency.
• Cluster mode for scale.

Limit: a single Redis key handles ~50-100K ops/sec. Hot keys (one tenant = whole limit) need sharding.

In-memory in app

Local enforcement; fast; not coordinated. Used as L1 in front of Redis.

Specialized: Lyft's Ratelimit

Open-source rate limiter using Redis backend, designed to plug into Envoy.

42.4 Algorithms

Token bucket (recommended default)

State: (tokens, last_refill_ts). Lua script atomically refills + checks.

local now = tonumber(ARGV[1])
local rate = tonumber(ARGV[2])
local capacity = tonumber(ARGV[3])
local data = redis.call("HMGET", KEYS[1], "tokens", "ts")
local tokens = tonumber(data[1]) or capacity
local ts = tonumber(data[2]) or now
local elapsed = now - ts
tokens = math.min(capacity, tokens + elapsed * rate)
if tokens >= 1 then
  tokens = tokens - 1
  redis.call("HMSET", KEYS[1], "tokens", tokens, "ts", now)
  redis.call("EXPIRE", KEYS[1], 3600)
  return 1
else
  return 0
end

Sliding window counter

Two windows: previous and current. Estimated count = prev_count * (1 - elapsed_in_current_window) + current_count.

Fixed window

Simplest. Boundary issues; double burst.

42.5 Hierarchical limits

A request must pass multiple checks:

• Per-API-key: 1000/min
• Per-route: /search 100/min
• Global: 1M/min for the cluster

Each layer is a separate counter; reject on any failure.

42.6 Hot key mitigation

A single tenant limit = a single Redis key.

• Local pre-check in app: maintain a local approximation; only call Redis when near limit.
• Sharded counter: for very high QPS tenants, split into N shards; aggregate periodically.
• Replicate read: if Redis becomes a bottleneck, use sampled reads + occasional truth.

42.7 Latency

Rate limit check is on the hot path. Must be fast.

• Co-locate Redis with app servers (same AZ).
• Use Redis Cluster; route to shard owning the key.
• Avoid cross-region for the counter.
• Pipelining if checking multiple keys in one request.

42.8 Failure handling

What if the rate limiter is down?

• Fail open: allow all requests. Easy to abuse.
• Fail closed: reject all. Outage during outage.
• Fail soft: use local approximation (last-known limits + small buffer).

Most production systems fail open with monitoring; depend on the assumption that brief abuse < customer impact of total reject.

42.9 Configuration

Limits per (tenant, route, time window) stored in a config service.

• Versioned.
• Pushed to rate limiters via watch / polling.
• Cached in process for fast lookup.

UI for product/support to adjust without deploys.

42.10 Headers

(See chapter 23.) X-RateLimit-* and Retry-After.

42.11 Quotas (longer windows)

Per-day, per-month limits. Same algorithms, longer keys ({tenant}:day:{date}).

For monthly quotas:

• Counter in Redis with monthly TTL.
• Reset job at month start (or rely on TTL expiration + reinit).
• Persist to DB periodically for billing accuracy.

42.12 Distributed sliding window log

(For when precision matters — e.g., financial APIs.)

Each request appends timestamp to a Redis sorted set. Count = ZCARD - ZREMRANGEBYSCORE of old entries.

Memory: O(N) per key. Expensive for high-volume keys.

42.13 Multi-region

Tenant lives in one region (canonical); limits per region.

For globally distributed tenants:

• Region-local enforcement (eventual consistency); rare cross-region drift.
• Or async aggregation to a global counter; fall back to local on aggregator failure.

42.14 Burst handling

Token bucket inherently allows bursts up to bucket size. Tune carefully:

• Larger bucket = more burst tolerance + worse fairness.
• Smaller bucket = strict but unfriendly to occasional spikes.

For login endpoints: small bucket (strict). For typical API: larger bucket.

42.15 Integration patterns

Envoy filter

Envoy has a built-in rate-limit filter that calls a service via gRPC. Lyft's RateLimit is the reference implementation.

App middleware

Library called by every endpoint. Cleanest for per-business-rule limits (e.g., "can't post more than 5 comments per minute on a thread").

CDN / WAF

Edge enforcement (Cloudflare WAF rate rules). Stops abuse before hitting your app.

Layer all three: edge for crude DDoS; gateway for per-tenant; app for fine-grained.

42.16 Sketch

[Client]──→[CDN(rate)]──→[Gateway(rate)]──→[App(business rules)]
                              │
                       [Rate limiter svc]
                              │
                       [Redis cluster]──→[Config service]

42.17 What an interviewer wants

• Token bucket as default.
• Redis as central state with Lua atomic ops.
• Hot key + hierarchical rate limit awareness.
• Standard headers, fail-open vs fail-closed trade-off.
• Multi-layer enforcement (edge / gateway / app).

Key takeaways

• Token bucket + Redis + Lua = the production answer.
• Hot key mitigation: local pre-check, shard the counter.
• Hierarchical limits combine to express realistic policies.
• Fail-open with monitoring is the safer default if RL goes down.
• Multi-layer enforcement provides defense in depth.