Algorithm

Rate limiting

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.

Start the guide Discussions

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.

Highlights

Token bucket

Tokens refill at a steady rate and each request spends one, enforcing an average rate while allowing bursts up to the bucket's capacity.

Sliding windows

A timestamp log, or a weighted blend of two window counters, counts recent requests without the fixed window's boundary spike.

Keys and fairness

Separate limits per user ID, API key, IP address or endpoint stop any single client from monopolizing resources.

Distributed limits

Redis's atomic INCR and Lua scripts let many servers share one limit without race conditions.

Where it is used

Per-plan quotas on public APIs
Throttling login and password reset attempts
Capping spend on paid third-party APIs and SMS
Traffic protection in web servers and API gateways

Reference implementation

A token bucket

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.py

Step-by-step guide

Six chapters that take you from installation to the core ideas of Rate limiting.

Official docs and resources

Discussions

Start a discussion

Ask questions, share experience and trade opinions about Rate limiting.

No discussions yet. Start the first one.

0 comments