Rate Limiting Strategy - Token Bucket, Leaky Bucket & Sliding Window

Description
Rate limiting strategy: token bucket, leaky bucket, sliding window with distributed considerations.

---

Design a rate limiting strategy for a distributed API. Every rate limiter choice is a tradeoff between accuracy, memory, and distributed coordination. THREE ALGORITHMS, ONE DECISION: 1. TOKEN BUCKET - Best for bursty traffic - Each user gets a bucket holding N tokens - Tokens refill at R per second - Request consumes 1 token. Empty bucket = 429 - Pro: allows short bursts up to bucket size - Con: two users can consume same burst simultaneously - Memory: 2 integers per user 2. LEAKY BUCKET - Best for steady throughput - Requests enter FIFO queue of max size N - Processed at constant rate R/sec - Overflow = 429 - Pro: perfectly smooth outflow - Con: no burst capability, requests wait - Memory: queue per user 3. SLIDING WINDOW LOG - Most accurate - Store timestamp of each request per user - Count requests in [now - window, now] - Pro: exact count, no burst loophole - Con: O(N) memory per user per window - Hybrid: sliding window counter, O(1) memory DISTRIBUTED CONSIDERATIONS: - Local (in-process): fast, inconsistent - Centralized (Redis): consistent, adds latency, SPOF risk - Distributed (CRDT): eventual consistency Headers: X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset. On 429: Retry-After. OUTPUT: Recommended algorithm, storage backend, response headers, failure-mode behavior.

Copy Optimize