Architectural Breakdown & AnalysisFAANG Aligned
Rate limiters protect downstream APIs from denial-of-service, abuse, and resource exhaustion.
1. Core Algorithms
- Token Bucket: Bucket holds $N$ tokens refilling at rate $R$. Requests consume 1 token. Supports traffic bursts.
- Sliding Window Log: Stores timestamps of user requests in Redis Sorted Sets. Accurately counts requests in rolling window, but higher memory usage.
- Sliding Window Counter: Approximates requests by combining current fixed window count with weighted previous window count. Highly memory efficient.
2. Distributed Scaling & Race Conditions
To prevent race conditions when multiple API gateways check and update counters concurrently:
- Redis Cluster + Lua Scripts: Execute rate limit checks and counter increments in atomic Lua scripts inside Redis. This guarantees execution atomicity without network lock overhead.
- Local Gateway In-Memory Batching: Gateways enforce soft limits locally and sync counter deltas asynchronously to Redis.
WARNING — Race Conditions (Dirty Reads)
Without atomic Lua scripts or distributed locks, concurrent requests reading counter value 99 (limit 100) will both proceed, exceeding the quota.
Key Architectural Comparison
| Rate Limiting Algorithm | Burst Tolerance | Memory Footprint per Client | Concurrency Implementation | Industry Standard |
|---|---|---|---|---|
| Token Bucket | Allows bursts up to bucket capacity. | 16 bytes (Tokens + LastRefillTime). | Atomic Redis Lua script. | AWS API Gateway, Stripe. |
| Leaky Bucket | Strictly smooths output rate. | Queue buffer size. | Lock-based FIFO queue. | Egress packet shapers. |
| Fixed Window Counter | Allows $2\times$ burst at window boundary. | 8 bytes (Single counter integer). | Redis INCR + EXPIRE. | Basic tier rate limits. |
| Sliding Window Log | Mathematically exact rate. | High (Stores timestamp per request). | Redis Sorted Set (ZREMRANGEBYSCORE). | Strict financial security APIs. |