Distributed Rate Limiter
IntermediateOverview
A distributed rate limiter caps how many requests each client may make in a time window, enforcing that limit consistently across every node of a horizontally scaled service rather than per instance. It protects backends from overload and abuse while adding negligible latency to each request.
Functional Requirements
- Allow or reject each incoming request according to a configured per-client limit (for example, N requests per second).
- Enforce a single global limit across all service nodes, not an independent limit per node.
- Support multiple rule scopes and tiers: per user, per API key, per IP address, and per endpoint.
- Return a standard rejection (HTTP 429) with a
Retry-Afterhint when a client exceeds its limit.
Non-Functional Requirements
- Low latency: the limit check must add no more than a few milliseconds to a request.
- High availability: the limiter must not become a single point of failure; it should degrade gracefully (fail-open) if the counter store is unreachable.
- Scalability: support millions of distinct clients and the service's full peak request rate.
Capacity Estimation
Assume 1 million active clients and a service peak of 100,000 QPS, where every request consults the limiter.
- QPS: every request triggers exactly one limit check, so the limiter handles ~100,000 checks/sec at peak (roughly 200,000/sec with headroom).
- Storage: each client needs a small counter record — a count plus a timestamp, about 100 bytes. 1e6 clients x 100 bytes = ~100 MB, which fits comfortably in memory; even 10 million clients is only ~1 GB.
- Bandwidth: each check is a small read-modify-write of roughly 200 bytes round-trip. 100,000 checks/sec x 200 bytes ~ ~20 MB/s ~ 160 Mbps of internal traffic to the counter store.
High-Level Architecture
The rate limiter operates as middleware within an API Gateway. When a request arrives, the gateway synchronously queries a centralized in-memory datastore (e.g., a Redis cluster) to check and decrement the client's remaining quota. If the quota is exceeded, the gateway immediately returns a 429 response. If not, the request is routed to the backend services.
Data Model
| Entity | Fields / Schema | Storage Choice |
|---|---|---|
| Counter | key = client id + window, count or tokens, last_refill_ts, ttl | In-memory key-value store (e.g., Redis), sharded across a cluster |
| Rule | rule_id, scope, limit, window | Config store, cached in each gateway node |
Detailed Design
Algorithms
- Token Bucket: A bucket holds tokens, refilling at a constant rate. Each request costs a token. Good for allowing burst traffic.
- Leaky Bucket: Requests are put into a queue that is processed at a constant rate. Good for smoothing out traffic completely.
- Fixed Window Counter: Simply counts requests from e.g., 12:00:00 to 12:01:00. Flaw: spikes at the edges of the window allow 2x traffic.
- Sliding Window Log: Keeps a timestamp of every request. Highly accurate but memory intensive.
- Sliding Window Counter: The standard approach. Combines fixed windows with a weighted overlap for accuracy without the memory footprint of logs.
Atomic Operations
In a distributed system, reading a count and then updating it is prone to race conditions if two gateway nodes do it simultaneously. The limiter must use atomic operations. In Redis, this is typically done using Lua scripts (which execute atomically) to read the current tokens, calculate refill, decrement, and save the new state in one round trip.
Rule Distribution
The rules (e.g., "Basic tier = 10/min, Premium tier = 100/min") are stored in a configuration database. They are pulled down and cached locally in memory by the API Gateway nodes to avoid querying a database for the rule definition on every request.
Bottlenecks & Solutions
The centralized Redis cluster handles the full QPS of the API Gateway, making it a critical bottleneck. To scale this, the Redis cluster is sharded using consistent hashing on the client ID. However, if a single client launches a massive DDoS attack, their single shard will melt down. To mitigate this, gateways can cache local blocks (e.g., locally blocking an IP for 10 seconds if it hits 429 locally) to shed load before it reaches Redis.