Rate Limiting Algorithms: Token Bucket, Leaky Bucket and Sliding Windows

Rate limiting controls how many requests a client can make in a period of time. It protects services from abuse and accidental overload, keeps usage fair between customers and controls costs. The algorithm you choose determines how smoothly limits are enforced and how much memory you need.

Fixed window counter

Count requests in fixed intervals, for example per minute. If the count exceeds the limit, reject until the next window.

Pros: very simple and memory-efficient. Cons: allows bursts at window boundaries. A client can send the full limit at the end of one minute and again at the start of the next, doubling the rate briefly.

Sliding window log

Store a timestamp for every request. On each new request, drop timestamps older than the window and count what’s left.

Pros: precise, with no boundary bursts. Cons: memory grows with request volume, which is expensive at high traffic.

Sliding window counter

A compromise: combine the current and previous fixed windows, weighting the previous window by how much of it still overlaps the sliding window.

estimated = current_count + previous_count × (overlap fraction)

Pros: smooth limits with little memory. Cons: an approximation, though usually a good one.

Token bucket

A bucket holds up to capacity tokens and refills at a steady rate. Each request takes a token; if the bucket is empty, the request is rejected or delayed.

import time

class TokenBucket:
    def __init__(self, capacity, refill_per_sec):
        self.capacity = capacity
        self.tokens = capacity
        self.rate = refill_per_sec
        self.updated = time.monotonic()

    def allow(self):
        now = time.monotonic()
        self.tokens = min(self.capacity, self.tokens + (now - self.updated) * self.rate)
        self.updated = now
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False

Pros: allows short bursts up to the bucket size while enforcing an average rate; memory-efficient. This is why it’s one of the most widely used algorithms. Cons: two parameters to tune.

Leaky bucket

Requests enter a queue that drains at a constant rate. When the queue is full, new requests are dropped.

Pros: produces a perfectly smooth outflow, useful for protecting fragile downstream systems. Cons: bursts are queued or dropped rather than served quickly, adding latency.

Comparison

Rate limiting in distributed systems

When a load balancer spreads requests across many servers, local counters aren’t enough. Common approaches:

• A shared store such as Redis holds counters or token state.
• Atomic updates, using Lua scripts or atomic increments, prevent race conditions between servers.
• Approximate local limits with periodic synchronisation can reduce latency at very large scale.
• Limits at several layers: the edge or CDN, the API gateway and individual services.

Communicating limits to clients

• Return HTTP 429 Too Many Requests when a limit is exceeded.
• Include a Retry-After header telling clients when to try again.
• Consider headers that report the limit and remaining quota.
• Document limits clearly, and design clients to retry with exponential backoff and jitter, using idempotency keys so a retried write doesn’t run twice.

AI APIs are a good real-world example: they often limit both requests and tokens per minute, which is one reason some teams choose to run models locally for heavy internal workloads.

Rate limiting is a favourite deep-dive topic in interviews; see our system design interview framework.

Frequently asked questions

Which rate limiting algorithm is best?

For most APIs, token bucket or sliding window counter. Choose leaky bucket when you need a perfectly smooth outflow.

What should I rate limit by?

Common keys are API key, user ID and IP address. Many systems combine several, with different limits for different endpoints.

What’s the difference between rate limiting and throttling?

Rate limiting rejects requests over a limit; throttling slows them down or queues them. The terms are often used interchangeably.