Architecture & Core Algorithm:
- Goal: Protect downstream microservices from denial-of-service, abusive scraping, and cascading failures while maintaining sub-millisecond overhead.
1. Algorithm Selection:
- Token Bucket: Refills tokens at a steady rate up to capacity; allows bursts while enforcing average limits. Ideal for public REST APIs.
- Sliding Window Counter: Tracks timestamps in a sliding window to eliminate boundary-burst flaws of Fixed Window counters.
2. Distributed Implementation with Redis:
- Store counters in Redis using keys structured as ratelimit:{client_id}:{endpoint}.
- Execute token logic atomically using Redis Lua scripts to eliminate race conditions between concurrent requests.
- Data structure: Use Redis Sorted Sets (ZADD, ZREMRANGEBYSCORE, ZCARD) for sliding window logs, or two Redis keys with hash fields for token buckets.
3. System Integration & Tiering:
- Placement: Deploy rate limiter at the API Gateway layer (Envoy or Kong) before authentication or routing to internal clusters.
- Return Headers: Include X-RateLimit-Limit, X-RateLimit-Remaining, and Retry-After on HTTP 429 Too Many Requests.
- Graceful Degradation: If Redis fails, fail open with local in-memory fallback to avoid taking down all traffic.