Archprimer
ArchitectureIntermediate 7 min read

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.

token-bucketsliding-windowredisdistributedthrottling

By Ratish Jain · Updated

Diagram with 5 components: Client, API Gateway, Redis, Service, 429 Reject. Connections: Client → API Gateway (1 · request); API Gateway → Redis (2 · check); API Gateway → Service (3 · allow); API Gateway → 429 Reject (3 · deny).
ClientGatewayCacheService
Gateway checks a Redis-backed counter before forwarding to services.

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

  1. 1Client request hits a gateway node's limiter middleware.
  2. 2The gateway derives a key (userId/API key + route) and looks up its policy.
  3. 3A Redis Lua script atomically reads and updates the counter/tokens.
  4. 4If under the limit, the request is forwarded to the upstream service.
  5. 5If over, the gateway returns 429 with a Retry-After header.
  6. 6Counters expire automatically at window end via TTLs.

Flow Diagram

Diagram with 6 components: Client, Gateway, Limiter, Counters, Upstream API, 429 Too Many. Connections: Client → Gateway (1 · request); Gateway → Limiter (2 · check); Limiter → Counters (3 · INCR); Limiter → Upstream API (4 · allow); Limiter → 429 Too Many (4 · 429).
ClientGatewayServiceCache
The gateway consults the limiter, which allows or returns 429.

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

Diagram with 5 components: Limiter, Shard Router, Redis Shard 1, Redis Shard 2, Redis Shard 3. Connections: Limiter → Shard Router (1 · hash key); Shard Router → Redis Shard 1 (2 · route); Shard Router → Redis Shard 2 (2 · route); Shard Router → Redis Shard 3 (2 · route).
ServiceCache
The limiter hashes each key and routes its counter to one Redis shard.

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

Pros
  • Token bucket cleanly allows bursts while bounding sustained rate.
  • Redis + Lua gives atomic, fast, shared counters.
  • Stateless gateways scale independently of the counter store.
Cons
  • 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 vs sliding window?

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.

How do you keep counters consistent across nodes?

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.

What happens if Redis goes down?

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.

60-Second Revision
  • →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.