Theory
Distributed Rate Limiting
📋 Overview
A distributed rate limiter enforces request limits across a horizontally scaled cluster of servers. In a microservices architecture, a single user’s requests may hit multiple different API nodes; therefore, a centralized or coordinated approach is required to ensure that the global limit is not exceeded. It is a vital defense mechanism against DoS attacks, scraping, and resource exhaustion.
🏗️ Core Principles & Characteristics
- Centralized State: Storing counters in a fast, shared data store like Redis or Memcached.
- Algorithms:
- Token Bucket: Tokens added at a fixed rate; requests consume tokens.
- Leaky Bucket: Requests enter a queue and are processed at a steady rate.
- Sliding Window Log: Stores timestamps of all requests; highly accurate but memory-intensive.
- Sliding Window Counter: A hybrid approach using fixed windows and weighted averages.
- Atomic Operations: Using Redis
INCRor Lua scripts to prevent race conditions during counter updates.
⚖️ Trade-offs: Pros & Cons
- Pros:
- Global Accuracy: Ensures a user can't bypass limits by switching servers.
- Service Protection: Prevents downstream services from being overwhelmed.
- Fairness: Prevents "noisy neighbors" from hogging shared resources.
- Cons:
- Latency: Adds a round-trip to the central store (e.g., Redis) for every request.
- Single Point of Failure: If the central store goes down, the rate limiter might fail open (allowing all) or fail closed (blocking all).
- Contention: High-traffic keys in Redis can become bottlenecks.
🌍 Real-World Implementation
- API Gateways: Kong, Tyk, and AWS API Gateway have built-in distributed rate limiting.
- Service Mesh: Istio uses a "Quota" system to limit traffic between services.
- Stripe: Uses a sophisticated distributed rate limiter based on the Token Bucket algorithm with Redis.
💡 Interview "Gotchas" & Tips
- Race Conditions: How do you handle two simultaneous requests updating the same counter? (Answer: Redis + Lua script).
- Performance Optimization: Discuss local batching where servers decrement a local counter and sync with the global store every $N$ requests or $X$ milliseconds.
- Hard vs. Soft Limits: Differences between strict rejection (429 Too Many Requests) and throttling (slowing down).
- The "Fail Open" Strategy: In many systems, it's better to let traffic through if the rate limiter fails rather than breaking the entire app.
📐 Suggested Architecture Primitives
- Redis (with Lua): The industry standard for distributed counters.
- API Gateway: The ideal place to enforce rate limits before requests hit the backend.
- Sidecar Proxy (Envoy): For service-to-service rate limiting in K8s.
Canvas