Released · improving
Algorithm
Rate limiting caps how many requests a user or IP can make per time window. Learn token bucket, sliding window, leaky bucket and Redis-based limiters.
A rate limiter controls how many requests are accepted within a period of time. You define a key, a limit and a window, such as "100 requests per minute per user", and requests beyond that are rejected or delayed. The classic algorithms are fixed window, sliding window log, sliding window counter, token bucket and leaky bucket, and they differ in accuracy, memory use and how they treat bursts.
Nearly every feature exposed to the outside world, from public APIs to login, payments and messaging, sits behind a rate limiter. It shields servers from traffic spikes and runaway retry loops, keeps one user from monopolizing shared capacity and slows down brute-force attacks. It is also a staple of system design interviews, where you are expected to explain the trade-offs and how to run a limiter across many servers.
Start by writing a fixed window counter and watching it let twice the limit through around a window boundary, then fix that with a sliding window and a token bucket. From there, learn to test with an injected clock, return HTTP 429 with Retry-After, and share a limit across servers with Redis INCR, EXPIRE and Lua scripts.
Tokens refill at a steady rate and each request spends one, enforcing an average rate while allowing bursts up to the bucket's capacity.
A timestamp log, or a weighted blend of two window counters, counts recent requests without the fixed window's boundary spike.
Separate limits per user ID, API key, IP address or endpoint stop any single client from monopolizing resources.
Redis's atomic INCR and Lua scripts let many servers share one limit without race conditions.
TokenBucket refills at rate tokens per second and holds at most capacity tokens. allow() adds all the tokens earned since the last call in one step (lazy refill), then spends one if enough are available. Running the script lets the first 5 calls through as a burst and rejects the next 3; after a 1.1-second pause, two more pass. Time is measured with time.monotonic(), which never goes backwards.
token_bucket.py
import time
class TokenBucket:
"""Allow bursts of up to `capacity` requests, refilled at `rate` tokens per second."""
def __init__(self, rate: float, capacity: float) -> None:
self.rate = rate
self.capacity = capacity
self.tokens = capacity
self.updated = time.monotonic()
def allow(self, cost: float = 1.0) -> bool:
now = time.monotonic()
self.tokens = min(self.capacity, self.tokens + (now - self.updated) * self.rate)
self.updated = now
if self.tokens >= cost:
self.tokens -= cost
return True
return False
if __name__ == "__main__":
bucket = TokenBucket(rate=2, capacity=5) # 2 requests per second, bursts of 5
print([bucket.allow() for _ in range(8)]) # 5 x True, then 3 x False
time.sleep(1.1) # about 2.2 tokens come back
print(bucket.allow(), bucket.allow(), bucket.allow()) # True True False
python token_bucket.pySix chapters that take you from installation to the core ideas of Rate limiting.
Ask questions, share experience and trade opinions about Rate limiting.
No discussions yet. Start the first one.
0 comments
Sign in · Sign in to leave a comment.
Be the first to comment.