Back
+25 XP
Concept

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 ๐Ÿชฃ๐Ÿ’งโšก.

python
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>

Checkpoint

What is the key functional difference between Token Bucket and Leaky Bucket? ๐Ÿง 

Practice

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. ๐ŸŽฏ

Terminal
01
Tap code blocks below to assemble
Available Blocks