Protecting the Service
A rate limiter is a gatekeeper. Without one, a single misbehaving client — whether a buggy retry loop, a DDoS attack, or a misconfigured scraper — can exhaust your service's resources and cause an outage for everyone. Rate limiters are one of the most important defensive mechanisms in distributed systems.
You may be asked to implement one from scratch in an interview. There are three main algorithms, each with different trade-offs.
1. Token Bucket (Burst-Capable)
Think of it like a subway turnstile that refills tokens over time. You can save up tokens and spend them in a burst, but once they're gone, you wait.
import time
class TokenBucket:
def __init__(self, capacity, refill_rate):
self.capacity = capacity # Max tokens (burst limit)
self.refill_rate = refill_rate # Tokens added per second
self.tokens = capacity # Start full
self.last_refill = time.time()
def allow_request(self):
now = time.time()
elapsed = now - self.last_refill
# Add tokens for time elapsed, but don't exceed capacity
self.tokens = min(
self.capacity,
self.tokens + elapsed * self.refill_rate
)
self.last_refill = now
if self.tokens >= 1:
self.tokens -= 1
return True # Request allowed
return False # Request denied
- Allows bursts up to
capacitytokens. - Use case: APIs where occasional bursts are acceptable (e.g., a user uploading a batch of files).
2. Leaky Bucket (Constant Output Rate)
Think of it like a bucket with a hole in the bottom. Requests pour in at any rate, but they drip out at a constant, controlled rate. If the bucket overflows, requests are dropped.
from collections import deque
class LeakyBucket:
def __init__(self, capacity, leak_rate):
self.capacity = capacity # Max queue size
self.leak_rate = leak_rate # Requests processed per second
self.queue = deque()
self.last_leak = time.time()
def allow_request(self):
now = time.time()
elapsed = now - self.last_leak
# Drain the queue based on elapsed time
leaked = int(elapsed * self.leak_rate)
for _ in range(min(leaked, len(self.queue))):
self.queue.popleft()
if leaked > 0:
self.last_leak = now
if len(self.queue) < self.capacity:
self.queue.append(now)
return True # Request queued and allowed
return False # Bucket full — request dropped
- Enforces a strictly constant output rate — no bursts.
- Use case: Protecting a slow downstream database that cannot handle spikes.
3. Sliding Window Counter (High Precision)
Track the exact timestamps of recent requests. Count how many fall within the last N seconds.
from collections import deque
class SlidingWindowRateLimiter:
def __init__(self, limit, window_seconds):
self.limit = limit
self.window = window_seconds
self.timestamps = deque()
def allow_request(self):
now = time.time()
cutoff = now - self.window
# Remove timestamps outside the window
while self.timestamps and self.timestamps[0] < cutoff:
self.timestamps.popleft()
if len(self.timestamps) < self.limit:
self.timestamps.append(now)
return True
return False
- Most accurate — no boundary artifacts from fixed windows.
- Con: Memory scales with request volume (stores every timestamp). At 100K req/sec, this is 100K timestamps per second per client.
Interviewers often ask: "What's the difference between Token Bucket and Leaky Bucket?" The key distinction is output behavior. Token Bucket allows bursts — if you have 10 tokens saved, you can send 10 requests instantly. Leaky Bucket enforces a smooth, constant output rate regardless of how many requests arrive. A follow-up question is often: "Which would you use to protect a database?" The answer is Leaky Bucket — databases are sensitive to sudden spikes, so you want to smooth traffic, not permit bursts.