Token Bucket Rate-Limiting Algorithm
The Token Bucket algorithm limits API request bursts. Tokens replenish at a fixed rate up to capacity. Each incoming request consumes one token; if empty, the API drops requests with HTTP 429 Too Many Requests 🪣.
import time
class TokenBucket:
def __init__(self, capacity: int, fill_rate: float):
self.capacity = capacity
self.tokens = capacity
self.fill_rate = fill_rate # Tokens added per second
self.last_check = time.monotonic()
def allow_request(self) -> bool:
now = time.monotonic()
# Replenish tokens based on elapsed time:
self.tokens = min(self.capacity, self.tokens + (now - self.last_check) * self.fill_rate)
self.last_check = now
if self.tokens >= 1.0:
self.tokens -= 1.0
return True
return False # Rate limit exceeded! 🛑
bucket = TokenBucket(capacity=2, fill_rate=1.0)
print(bucket.allow_request()) # True (1st request)
print(bucket.allow_request()) # True (2nd request)
print(bucket.allow_request()) # False (429 Rate Limited!) 🛑
# 43. Token Bucket Rate-Limiting Algorithm The Token Bucket algorithm limits API request bursts. Tokens replenish at a fixed rate up to capacity. Each incoming request consumes one token; if empty, the API drops requests with HTTP 429 Too Many Requests 🪣. ```python import time class TokenBucket: def __init__(self, capacity: int, fill_rate: float): self.capacity = capacity self.tokens = capacity self.fill_rate = fill_rate # Tokens added per second self.last_check = time.monotonic() def allow_request(self) -> bool: now = time.monotonic() # Replenish tokens based on elapsed time: self.tokens = min(self.capacity, self.tokens + (now - self.last_check) * self.fill_rate) self.last_check = now if self.tokens >= 1.0: self.tokens -= 1.0 return True return False # Rate limit exceeded! 🛑 bucket = TokenBucket(capacity=2, fill_rate=1.0) print(bucket.allow_request()) # True (1st request) print(bucket.allow_request()) # True (2nd request) print(bucket.allow_request()) # False (429 Rate Limited!) 🛑 ``` Cloudflare, AWS API Gateway, and Stripe rate limiters use this exact Token Bucket math to protect servers from distributed denial-of-service (DDoS) traffic spikes! 🪣 --- ### Question What HTTP status code should an API return when a client exhausts their Token Bucket rate limit? 🧠- [ ] a. `429 Too Many Requests` 🛑 - [ ] b. `500 Internal Server Error` - [ ] c. `401 Unauthorized` - [ ] d. `404 Not Found` --- ### Challenge Create `TokenBucket(capacity=1, fill_rate=0.5)`. Verify first request returns `True` and immediate second request returns `False`. Print both results. 🎯 <details> <summary>Solution</summary> ```python import time class TokenBucket: def __init__(self, cap, rate): self.cap = cap; self.tokens = cap; self.rate = rate; self.last = time.monotonic() def allow(self): now = time.monotonic() self.tokens = min(self.cap, self.tokens + (now - self.last) * self.rate) self.last = now if self.tokens >= 1: self.tokens -= 1 return True return False tb = TokenBucket(1, 0.5) print(tb.allow()) print(tb.allow()) ``` </details>