Why Rate Limiting is Critical
Rate limiting protects downstream APIs from denial-of-service (DoS) attacks, brute-force credential stuffing, abusive web scrapers, and cascading microservice failures. When limits are reached, the system responds with HTTP 429 Too Many Requests and a Retry-After header.
Comparison of Core Algorithms
flowchart TD
Req["Incoming API Request"] --> Alg{"Algorithm"}
Alg --> TB["Token Bucket: Refill rate + Bucket capacity"]
Alg --> LB["Leaking Bucket: Constant-rate FIFO queue"]
Alg --> FW["Fixed Window: Reset counter every minute"]
Alg --> SW["Sliding Window Log: Precise timestamps"]
Alg --> SWC["Sliding Window Counter: Memory-efficient interpolation"]
- Token Bucket: Tokens refill at a constant rate r up to capacity b. Allows bursts up to capacity while enforcing average rate. Used by Amazon AWS and Stripe.
- Fixed Window Counter: Counters reset at fixed intervals (e.g., top of every minute). Vulnerable to 2x burst traffic across window boundaries (e.g., 100 requests at 00:59 and 100 requests at 01:00).
- Sliding Window Counter (widely used, e.g., by Cloudflare): Blends the previous window counter with the current window counter based on timestamp overlap, providing smooth rate limiting with minimal memory footprint (O(1) memory per user).
Distributed Rate Limiting with Redis & Lua
In distributed setups with multiple API gateway instances, local in-memory counters fail because traffic is spread across servers. Redis provides shared state. To prevent race conditions between GET and INCR, atomic Lua scripts are executed directly on the Redis node.
Worked example: sizing a central limiter
The API tier has 60 gateway instances serving 300,000 requests per second at peak. Every request checks one bucket.
- A single Redis shard running a small Lua script sustains roughly 50,000 to 100,000 script calls per second before CPU saturates, since Redis runs commands on one thread.
- 300,000 checks per second therefore need about 4 to 6 primary shards (Redis Cluster, sharded by bucket key), plus replicas.
- Each check adds about 0.3 to 1 ms within one availability zone. For latency-critical paths, a lease model cuts Redis calls by about 50x: each gateway takes 50 tokens at a time and spends them locally, at the cost of possibly overshooting the limit by up to 50 tokens per gateway.
Architecture options
| Design | Accuracy | Latency | Failure impact | When to use |
|---|---|---|---|---|
| Local in-memory per instance | Limit x N instances in the worst case | Nanoseconds | None | Coarse protection, rough fairness, and a backstop |
| Central Redis with Lua | Exact for the algorithm | +0.3 to 1 ms | Must decide fail-open or fail-closed | Per-customer quotas, billing-relevant limits |
| Local leases from central | Overshoot bounded by lease size | Mostly local | Leases in hand keep working | Very high QPS gateways |
| Async gossip or sync | Eventually accurate; overshoot during sync | Local | Tolerant | Multi-region global limits |
Request path
sequenceDiagram
participant C as Client
participant G as API gateway
participant R as Redis shard for the key
participant S as Backend service
C->>G: GET /v1/orders with API key
G->>R: EVALSHA token_bucket key, rate, burst, now
R-->>G: allowed, remaining 42
G->>S: forward request
S-->>G: 200
G-->>C: 200 plus RateLimit headers
Note over G,R: If rejected, the gateway returns 429 with Retry-After and never calls the backend
Client-facing contract
- Return 429 Too Many Requests with
Retry-Afterin seconds. Many APIs also sendX-RateLimit-Limit,X-RateLimit-RemainingandX-RateLimit-Reset; the IETF draft standardisesRateLimitandRateLimit-Policyheaders. - Use 503 with Retry-After for load shedding, where the server is overloaded rather than the client being over its quota. The two situations need different client behaviour.
- Publish limits per plan and per endpoint, so customers can design their integrations to stay within them.