Rate limiting protects services from abuse, overload, and cascading failures. But the algorithm choice determines whether you block legitimate traffic, allow bursts, or create unfairness. This article compares the four canonical algorithms and explains why the sliding window log is gaining popularity.
Fixed Window Counter
The simplest approach: count requests in fixed time windows (e.g., 1-minute intervals):
import time
class FixedWindowRateLimiter:
def __init__(self, max_requests: int, window_seconds: int):
self.max_requests = max_requests
self.window_seconds = window_seconds
self.counters = {} # window_key → count
def allow(self, key: str) -> bool:
window = int(time.time() // self.window_seconds)
window_key = f"{key}:{window}"
if window_key not in self.counters:
self.counters[window_key] = 0
if self.counters[window_key] >= self.max_requests:
return False
self.counters[window_key] += 1
return True
# Problem: boundary burst
# Window: [00:00, 01:00), limit: 100 requests
# Request 99 at 00:59:59 → allowed
# Request 100 at 00:59:59 → allowed
# Request 1 at 01:00:00 → allowed (new window)
# Request 2 at 01:00:01 → allowed
# Total: 102 requests in 2 seconds — burst exceeds limitSliding Window Log
Track the timestamp of every request and count requests within the window:
import time
from collections import defaultdict
class SlidingWindowLog:
def __init__(self, max_requests: int, window_seconds: int):
self.max_requests = max_requests
self.window_seconds = window_seconds
self.requests = defaultdict(list)
def allow(self, key: str) -> bool:
now = time.time()
window_start = now - self.window_seconds
# Remove expired timestamps
self.requests[key] = [
t for t in self.requests[key] if t > window_start
]
if len(self.requests[key]) >= self.max_requests:
return False
self.requests[key].append(now)
return True
def retry_after(self, key: str) -> float:
"""Seconds until oldest request expires from window."""
if not self.requests[key]:
return 0
oldest = min(self.requests[key])
return max(0, oldest + self.window_seconds - time.time())
# Accurate: no boundary burst
# Cost: O(n) memory per key (stores all timestamps)
# For 1000 req/min limit: stores up to 1000 timestamps per keySliding Window Counter (Hybrid)
Combine fixed window counters with interpolation for a memory-efficient sliding window:
class SlidingWindowCounter:
def __init__(self, max_requests: int, window_seconds: int):
self.max_requests = max_requests
self.window_seconds = window_seconds
self.prev_count = {}
self.curr_count = {}
self.curr_window = {}
def allow(self, key: str) -> bool:
now = time.time()
curr_window = int(now // self.window_seconds)
prev_window = curr_window - 1
# Initialize current window
if self.curr_window.get(key) != curr_window:
self.prev_count[key] = self.curr_count.get(key, 0)
self.curr_count[key] = 0
self.curr_window[key] = curr_window
# Weighted count: overlap ratio × previous + current
overlap = 1 - (now % self.window_seconds) / self.window_seconds
weighted = self.prev_count[key] * overlap + self.curr_count[key]
if weighted >= self.max_requests:
return False
self.curr_count[key] += 1
return True
# Memory: O(1) per key (two counters)
# Accuracy: ~99% (small error at boundaries)
# Best of both worlds: no burst, minimal memoryToken Bucket
Allows controlled bursts by refilling tokens at a fixed rate:
import time
class TokenBucket:
def __init__(self, capacity: int, refill_rate: float):
"""
capacity: maximum burst size
refill_rate: tokens added per second
"""
self.capacity = capacity
self.refill_rate = refill_rate
self.tokens = capacity
self.last_refill = time.time()
def allow(self, tokens_needed: int = 1) -> bool:
self._refill()
if self.tokens >= tokens_needed:
self.tokens -= tokens_needed
return True
return False
def _refill(self):
now = time.time()
elapsed = now - self.last_refill
self.tokens = min(
self.capacity,
self.tokens + elapsed * self.refill_rate
)
self.last_refill = now
# Usage:
# capacity=100, refill_rate=10/sec
# Allows burst of 100, then sustains 10/sec
# Perfect for APIs: burst for legitimate traffic, sustained limit for abuse# Token bucket in distributed systems:
# Store tokens and timestamp in Redis
import redis
class DistributedTokenBucket:
def __init__(self, redis_client, key, capacity, refill_rate):
self.r = redis_client
self.key = key
self.capacity = capacity
self.refill_rate = refill_rate
def allow(self, tokens=1) -> bool:
lua_script = """
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local now = tonumber(ARGV[3])
local requested = tonumber(ARGV[4])
local data = redis.call('HMGET', key, 'tokens', 'last_refill')
local token_count = tonumber(data[1]) or capacity
local last_refill = tonumber(data[2]) or now
-- Refill tokens
local elapsed = now - last_refill
token_count = math.min(capacity, token_count + elapsed * refill_rate)
if token_count >= requested then
token_count = token_count - requested
redis.call('HMSET', key, 'tokens', token_count, 'last_refill', now)
redis.call('EXPIRE', key, math.ceil(capacity / refill_rate) * 2)
return 1
end
return 0
"""
return self.r.eval(lua_script, 1, self.key,
self.capacity, self.refill_rate,
time.time(), tokens) == 1Leaky Bucket
Processes requests at a constant rate, queuing excess requests:
from collections import deque
class LeakyBucket:
def __init__(self, capacity: int, leak_rate: float):
self.capacity = capacity
self.leak_rate = leak_rate # requests processed per second
self.queue = deque()
self.last_leak = time.time()
def allow(self, request) -> bool:
self._leak()
if len(self.queue) < self.capacity:
self.queue.append(request)
return True
return False # queue full → reject
def _leak(self):
now = time.time()
elapsed = now - self.last_leak
leaked = int(elapsed * self.leak_rate)
for _ in range(min(leaked, len(self.queue))):
processed = self.queue.popleft()
process_request(processed)
self.last_leak = now
# Leaky bucket: constant output rate regardless of input burst
# Good for: traffic shaping, network packet scheduling
# Bad for: API rate limiting (adds latency for queued requests)tradeoff / Token Bucket vs Sliding Window
For most API rate limiting, use a token bucket with Redis for distributed coordination. The burst tolerance handles legitimate traffic spikes while the sustained rate prevents abuse.
Token bucket is better for APIs where legitimate bursts are expected (page loads triggering many requests). Sliding window is better for strict rate limiting where burst tolerance is unacceptable (financial APIs, abuse prevention).
Synthesis
Fixed window is simplest but allows 2× burst at boundaries. Sliding window log is most accurate but memory-intensive. Sliding window counter balances accuracy and efficiency. Token bucket allows controlled bursts. Leaky bucket provides constant output rate. Choose based on burst tolerance, memory budget, and precision requirements.