Recap — Token Bucket, Leaky Bucket, Sliding Window

# Token Bucket, Leaky Bucket, Sliding Window Rate limiting protects your system: from abuse, from accidental DDoS by clients, from cost runaway. Every production API needs it. ## Why rate limit - Prevent abuse / DDoS. - Enforce per-tier limits (free vs paid). - Protect downstream from overload. - Fairness across users. - Cost control (third-party APIs). ## Algorithm 1: Token bucket A bucket holds tokens. Tokens refill at a steady rate (e.g., 10/sec). Each request consumes a token. Empty bucket → reject (or queue). ``` Bucket capacity: 10 Refill rate: 5 tokens/sec Time 0: bucket has 10 tokens Request → consumes 1 → bucket has 9 ... Bucket has 0 → request rejected After 1 sec: bucket has 5 (refilled) ``` ```python class TokenBucket: def __init__(self, capacity, refill_rate): self.capacity = capacity self.refill_rate = refill_rate self.tokens = capacity self.last_refill = time.time() def allow(self): now = time.time() elapsed = now - self.last_refill self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate) self.last_refill = now if self.tokens >= 1: self.tokens -= 1 return True return False ``` Properties: - Allows bursts up to bucket capacity. - Averages to refill rate over time. - Simple, widely used. Use when: bursty traffic is OK; long-term rate matters. ## Algorithm 2: Leaky bucket A queue (the bucket) drains at a fixed rate (the leak). Incoming requests added to queue; if queue full, reject. ``` Queue capacity: 10 Leak rate: 5 req/sec Requests arrive faster than leak → queue fills Queue full → reject new requests ``` ```python class LeakyBucket: def __init__(self, capacity, leak_rate): self.capacity = capacity self.leak_rate = leak_rate self.queue = [] self.last_leak = time.time() def allow(self): now = time.time() elapsed = now - self.last_leak leaked = int(elapsed * self.leak_rate) self.queue = self.queue[leaked:] self.last_leak = now if len(self.queue) < self.capacity: self.queue.append(now) return True return False ``` Properties: - Smoothes traffic to constant output rate. - No bursts (rejects everything past leak rate). - Used in network packet shaping. Use when: downstream needs steady rate; bursts cause problems. ## Algorithm 3: Fixed window counter Count requests per fixed time window (e.g., per minute). ``` At minute boundary: reset counter Request: increment counter; if > limit, reject ``` ```python class FixedWindow: def __init__(self, limit, window_sec): self.limit = limit self.window_sec = window_sec self.count = 0 self.window_start = time.time() def allow(self): now = time.time() if now - self.window_start >= self.window_sec: self.count = 0 self.window_start = now if self.count < self.limit: self.count += 1 return True return False ``` Properties: - Simple, memory-efficient. - Edge effect: 2x burst possible at window boundary (1000 requests at 11:59:59 + 1000 at 12:00:01). Use when: simplicity matters; edge bursts acceptable. ## Algorithm 4: Sliding window log Store timestamp of each request; count those within the window. ```python class SlidingWindowLog: def __init__(self, limit, window_sec): self.limit = limit self.window_sec = window_sec self.requests = [] def allow(self): now = time.time() # Remove expired self.requests = [t for t in self.requests if now - t < self.window_sec] if len(self.requests) < self.limit: self.requests.append(now) return True return False ``` Properties: - Accurate; no edge bursts. - Memory-heavy: O(requests in window). Use when: accuracy matters; memory is OK. ## Algorithm 5: Sliding window counter (hybrid) Mix of fixed window and sliding log. Weight current + previous windows. ``` Effective count = current window count + (previous count × overlap fraction) ``` Accurate without storing every request. Most production-grade. ## Distributed rate limiting For multi-instance services: each instance has its own counter? No — Alice's request to instance 1 doesn't count toward her quota on instance 2. Solutions: ### Centralized: Redis ```python def allow(key, limit, window): pipe = redis.pipeline() pipe.incr(key) pipe.expire(key, window) count, _ = pipe.execute() return count <= limit ``` Atomic increment with TTL. All instances share state. Standard pattern. ### Distributed: per-instance approximation Each instance enforces limit/N. Approximate but cheap. ### Sticky routing Same user always routed to same instance. Maintains per-instance state correctly. ## Where to put the rate limiter ``` Client → CDN → LB / API Gateway → App → DB