Rate Limiting Algorithms: Token Bucket vs Leaky Bucket
Unchecked ingress traffic will overwhelm backend compute engines. The Token Bucket algorithm permits controlled bursts up to bucket capacity while lazily refilling tokens at rate $r$ per second. The Leaky Bucket algorithm enforces a strict, smooth egress rate, discarding bursts or buffering them in a FIFO queue ๐ชฃ๐งโก.
import time
class TokenBucket:
def __init__(self, capacity, refill_rate):
self.capacity = float(capacity)
self.refill_rate = float(refill_rate)
self.tokens = self.capacity
self.last_ts = time.time()
def consume(self, amount=1.0):
now = time.time()
# Lazy token refill based on delta time
self.tokens = min(self.capacity, self.tokens + (now - self.last_ts) * self.refill_rate)
self.last_ts = now
if self.tokens >= amount:
self.tokens -= amount
return True
return False
limiter = TokenBucket(capacity=5, refill_rate=2)
print(f"Consumed token: {limiter.consume(1)} ๐")
# 100. Rate Limiting Algorithms: Token Bucket vs Leaky Bucket Allowing clients to trigger unlimited requests is an open invitation for accidental DDoS or abusive scraping. Without traffic shaping at the ingress boundary, a single misconfigured client loop can consume all database connection pools and starve legitimate users ๐. ```python # Rate Limiting Mechanics: # 1. Token Bucket: Tokens fill up to 'capacity' at 'refill_rate' tokens/sec. # - Allows sudden bursts (e.g. 50 parallel requests at page load). # - Rejects when bucket is empty (HTTP 429 Too Many Requests). # 2. Leaky Bucket: Requests enter a bucket with a hole at the bottom. # - Enforces perfectly uniform smoothing (e.g. exactly 10 reqs/sec). # - Good for protecting brittle downstream legacy APIs. ``` ### High-Performance Lazy Refill Amateur implementations spawn background timer threads or recurring cron jobs to increment token counters every second. At 100,000 active client IP keys, 100,000 background timers crush Python's memory and CPU. Master systems use **Lazy Time-Delta Math**: $$\text{new\_tokens} = \min\left(\text{capacity}, \text{current\_tokens} + \Delta t \times \text{refill\_rate}\right)$$ Update only when the client actually makes a request! $O(1)$ time, zero background threads, zero overhead โก๐ชฃ. --- ### Interactive Pop-Quiz ๐ง #### What is the key functional difference between Token Bucket and Leaky Bucket? - [ ] Token Bucket allows temporary bursts of traffic up to its bucket capacity, whereas Leaky Bucket smooths traffic to a rigid constant output rate ๐ชฃ - [ ] Token Bucket stores tokens on disk while Leaky Bucket stores tokens in the CPU L1 cache - [ ] Leaky Bucket requires root access to Linux network namespaces - [ ] Token Bucket only works on encrypted HTTPS connections --- ### Practical Challenge ๐ฏ Implement `TokenBucket(capacity: float, refill_rate: float)` with `allow(cost: float = 1.0) -> bool`. Calculate lazy replenishment as `min(capacity, tokens + elapsed * refill_rate)` on each call. Instantiate with capacity 3.0 and refill rate 10.0 tokens/sec. Consume 3 tokens successfully, assert the 4th is rejected, sleep 0.12 seconds, assert 1 token is accepted, and print the result. <details> <summary>Solution</summary> ```python import time class TokenBucket: def __init__(self, capacity: float, refill_rate: float): self.capacity = capacity self.refill_rate = refill_rate self.tokens = capacity self.last_refill = time.time() def allow(self, cost: float = 1.0) -> bool: now = time.time() elapsed = now - self.last_refill self.last_refill = now self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate) if self.tokens >= cost: self.tokens -= cost return True return False tb = TokenBucket(capacity=3.0, refill_rate=10.0) assert tb.allow(1.0) is True assert tb.allow(1.0) is True assert tb.allow(1.0) is True assert tb.allow(1.0) is False time.sleep(0.12) assert tb.allow(1.0) is True assert tb.allow(1.0) is False print("TokenBucket verified: burst consumption and lazy refill operational") ``` </details>