Rate Limiter
Design a distributed rate limiter using token bucket and sliding window algorithms with Redis-backed counters to enforce per-user and per-API request limits.
By Ratish Jain · Updated
Problem
A rate limiter protects services from abuse, accidental overload, and unfair usage by capping how many requests a client may make in a window. It must decide allow or reject in under a millisecond, apply consistently across a fleet of gateway nodes, and support flexible policies like *100 requests/minute per user* or *10K/sec per API key*.
The central challenge is making counters distributed and accurate: many gateway instances must share limit state without letting each node independently grant a full quota. A shared low-latency store like Redis holds the counters, and the algorithm choice trades precision against cost.
Functional Requirements
- Enforce limits per user, per API key, and per endpoint.
- Support multiple policies (e.g., burst + sustained rates).
- Return clear 429 responses with retry-after headers.
- Apply limits consistently across all gateway nodes.
- Allow configuration/updates of limits without redeploy.
Non-Functional Requirements
- Sub-millisecond decision latency; minimal request overhead.
- High availability — limiter must not become a single point of failure.
- Accurate enough to prevent significant over-admission.
- Horizontally scalable with the gateway fleet.
- Fail-open or fail-closed policy configurable per route.
Capacity Estimation
- Request volume
- 1M requests/sec across fleet
- Redis ops
- ~1M INCR/EXPIRE per sec
- Distinct keys
- 10M active users/keys
- Counter size
- ~50 bytes/key ≈ 500 MB in Redis
- Latency budget
- <1ms added per request
- Gateway nodes
- 100+ stateless instances
APIs
- POST /check
- allow(key, cost) -> {allowed, remaining, resetAt}
- PUT /policies
- setPolicy(scope, limit, window) -> {status}
- GET /usage/{key}
- usage(key) -> {count, limit, resetAt}
Components
- Gateway middleware: intercepts each request and invokes the limiter check.
- Redis counters: shared store holding per-key token/window state.
- Limiter logic: token bucket or sliding-window algorithm, run atomically (Lua script).
- Policy store: configurable limits per scope, hot-reloadable.
- Local cache: short-lived in-process counters to reduce Redis round-trips.
- Metrics: tracks allow/deny rates for tuning and alerting.
Request Flow
- 1Client request hits a gateway node's limiter middleware.
- 2The gateway derives a key (userId/API key + route) and looks up its policy.
- 3A Redis Lua script atomically reads and updates the counter/tokens.
- 4If under the limit, the request is forwarded to the upstream service.
- 5If over, the gateway returns 429 with a Retry-After header.
- 6Counters expire automatically at window end via TTLs.
Flow Diagram
Data / Storage Design
Counters live in Redis keyed by scope:key:window. Two common algorithms: the token bucket stores (tokens, lastRefill) and refills at a fixed rate — allowing bursts up to the bucket size while capping the sustained rate. The sliding window log/counter tracks request timestamps or weighted counts across adjacent fixed windows to avoid the boundary spikes of a naive fixed window.
To make read-modify-write atomic across concurrent gateways, the update runs as a Redis Lua script (single-threaded execution), preventing the race where two nodes both read count=99 and both admit. TTLs expire idle keys so memory stays bounded.
Data Model
Scaling Strategy
Gateways are stateless and scale horizontally; all shared state is in Redis. Redis itself scales via sharding/consistent hashing on the rate-limit key, so a given key always maps to one shard and its counter stays consistent.
To cut Redis load at very high QPS, nodes can keep a local token allocation — each gateway reserves a slice of the quota locally and only syncs with Redis periodically, trading small accuracy loss for far fewer round-trips. Hot keys can be pinned or handled with local caching plus approximate counting.
Bottlenecks & Failure Scenarios
- Redis becomes a bottleneck or SPOF — mitigate with sharding and replicas.
- Non-atomic counter updates cause over-admission under concurrency.
- Clock skew across nodes distorts sliding-window accuracy.
- Fixed-window boundary bursts allow ~2x the limit at edges.
- Redis outage — must choose fail-open (availability) or fail-closed (protection).
Design Tradeoffs
- Token bucket cleanly allows bursts while bounding sustained rate.
- Redis + Lua gives atomic, fast, shared counters.
- Stateless gateways scale independently of the counter store.
- Centralized Redis adds a network hop and a dependency.
- Sliding window is more accurate but costs more memory/CPU than fixed window.
- Local-allocation optimizations trade accuracy for lower latency.
Common Interview Questions
Token bucket permits bursts up to bucket capacity then throttles to the refill rate — good for smoothing spiky-but-bounded traffic. Sliding window enforces a stricter rolling count and avoids fixed-window boundary bursts, at higher memory/compute cost. Choose based on whether bursts are acceptable.
Store counters in a shared Redis and perform read-modify-write inside an atomic Lua script so concurrent gateways can't both admit on a stale read. Shard by key so each counter has a single authoritative shard.
You pick a policy per route: fail-open (allow traffic to preserve availability, risking overload) or fail-closed (reject to protect the backend). Local approximate counters can provide degraded limiting during the outage.
- →Rate limiter caps requests per key over a window, returning 429 when exceeded.
- →Token bucket allows bursts; sliding window is stricter and more accurate.
- →Redis holds shared counters; Lua scripts make updates atomic.
- →Shard counters by key; keep gateways stateless.
- →Decide fail-open vs fail-closed for Redis outages.
Related
Everything on Archprimer is connected — follow the graph.