Rate Limiting Algorithms Explained: Token Bucket and More

A rate limiter restricts how many requests a client can make in a period. "Design a rate limiter" is also a very common interview question.

Why limit?#

• Stops abuse, such as password guessing and scraping.
• Protects services from overload, including accidental loops.
• Keeps things fair between customers.
• Controls costs, for example with paid APIs.

A rejected client gets status 429 Too Many Requests, with a Retry-After header.

Fixed window#

Count requests in each clock minute. It is simple, but allows a burst across a boundary:

class FixedWindow:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.counts = {}

    def allow(self, t):
        slot = t // self.window
        self.counts[slot] = self.counts.get(slot, 0) + 1
        return self.counts[slot] <= self.limit


fw = FixedWindow(limit=5, window=60)
times = [58] * 5 + [61] * 5
allowed = sum(fw.allow(t) for t in times)
print(f"{allowed} requests allowed within 3 seconds, with a limit of 5 a minute")

10 requests allowed within 3 seconds, with a limit of 5 a minute

Ten requests got through in three seconds, because they fell into two windows.

Sliding window#

A sliding window log stores each request's time, and counts those in the last minute. It is accurate, but uses more memory:

from collections import deque


class SlidingLog:
    def __init__(self, limit, window):
        self.limit, self.window = limit, window
        self.times = deque()

    def allow(self, t):
        while self.times and self.times[0] <= t - self.window:
            self.times.popleft()
        if len(self.times) < self.limit:
            self.times.append(t)
            return True
        return False


sl = SlidingLog(limit=5, window=60)
allowed = sum(sl.allow(t) for t in times)
print(f"{allowed} requests allowed")

5 requests allowed

A sliding window counter approximates this by weighing two fixed windows, which saves memory.

Token bucket#

This is the most popular method. A bucket holds tokens, and refills at a steady rate. Each request takes a token, and if none are left, it is rejected. Short bursts are allowed, up to the bucket's size:

class TokenBucket:
    def __init__(self, capacity, refill_per_second):
        self.capacity = capacity
        self.rate = refill_per_second
        self.tokens = capacity
        self.last = 0

    def allow(self, t):
        self.tokens = min(self.capacity, self.tokens + (t - self.last) * self.rate)
        self.last = t
        if self.tokens >= 1:
            self.tokens -= 1
            return True
        return False


bucket = TokenBucket(capacity=3, refill_per_second=1)
for t in [0, 0, 0, 0, 1, 1, 4]:
    print(f"t={t}: {'allowed' if bucket.allow(t) else 'rejected'}")

t=0: allowed
t=0: allowed
t=0: allowed
t=0: rejected
t=1: allowed
t=1: rejected
t=4: allowed

The burst of three passed, the fourth was rejected, and tokens returned over time.

Comparison#

Where does it live?#

Client --> API gateway [limiter] --> Services

Limit at the API gateway or load balancer if you can. Clients can also limit themselves, but never trust that alone. Limit by user ID or API key, with IP address as a fallback, because many users can share one IP.

Distributed limiting#

With many servers, counters must be shared. Redis is the usual choice, as it is fast and has atomic operations. A simple fixed window looks like this:

count = INCR rate:user42:202611051030
if count == 1: EXPIRE rate:user42:202611051030 60
if count > limit: reject

For a token bucket, read and update together in a Lua script, so that two servers cannot race.

Design choices in an interview#

• What happens if Redis is down? Fail open (allow traffic), or fail closed (block)? Most APIs fail open.
• Add little delay: a Redis call takes around a millisecond.
• Return headers such as X-RateLimit-Remaining, so that clients can behave well.
• Different limits for different plans.

Common mistakes#

Practice#

b = TokenBucket(capacity=2, refill_per_second=0.5)
print(sum(b.allow(t) for t in [0, 0, 0, 1, 2, 4]))

4

Key takeaway#

Next: Monoliths and Microservices.