LLD: Rate Limiter

Big idea

A rate limiter answers one question per request: "may this client go ahead right now?" Several algorithms answer it with different trade-offs — token bucket allows bursts up to a cap, sliding window enforces a strict count per period. Hide them behind one allow(client) interface, inject the clock, and keep per-client state in a store you can swap for a shared one later.

Requirements

Functional

• allow(client_id) -> bool for each request.
• Limits configurable per rule (e.g. 5 requests per 10 seconds; free vs paid tiers).
• Choose the algorithm per rule.

Non-functional: O(1) or O(log n) per check; tiny memory per client; correct under concurrency; deterministic tests.

Out of scope: distributed coordination across servers (an extension — see the system-design rate limiting lesson).

Entities

RateLimiter (interface), TokenBucketLimiter, SlidingWindowLimiter, Rule (capacity, period), Clock (injected), per-client state (Bucket, deque of timestamps), and a LimiterRegistry choosing the rule per client tier.

Think of it like

A bucket by the door filled with entry tokens. Each visitor takes a token to enter; a staff member drops in a new token every few seconds, up to the bucket's size. A crowd can arrive at once and use the stockpile (a burst), but once it's empty, people wait for refills. The sliding window is the stricter bouncer who counts how many came in during the last ten minutes, exactly.

Class diagram

Key flow: a request through middleware

Code skeleton

from collections import deque

class FakeClock:
    def __init__(self): self.t = 0.0
    def now(self): return self.t


class TokenBucketLimiter:
    def __init__(self, capacity, refill_per_sec, clock):
        self.capacity, self.rate, self.clock = capacity, refill_per_sec, clock
        self.buckets = {}                              # client -> (tokens, last_refill)

    def allow(self, client):
        now = self.clock.now()
        tokens, last = self.buckets.get(client, (self.capacity, now))
        tokens = min(self.capacity, tokens + (now - last) * self.rate)   # lazy refill
        if tokens >= 1:
            self.buckets[client] = (tokens - 1, now)
            return True
        self.buckets[client] = (tokens, now)
        return False


class SlidingWindowLimiter:
    def __init__(self, limit, window, clock):
        self.limit, self.window, self.clock = limit, window, clock
        self.log = {}                                  # client -> deque of timestamps

    def allow(self, client):
        now = self.clock.now()
        times = self.log.setdefault(client, deque())
        while times and times[0] <= now - self.window:
            times.popleft()                            # forget requests outside the window
        if len(times) < self.limit:
            times.append(now)
            return True
        return False


clock = FakeClock()
bucket = TokenBucketLimiter(capacity=3, refill_per_sec=1, clock=clock)
window = SlidingWindowLimiter(limit=3, window=10, clock=clock)

def burst(limiter, n):
    return "".join("Y" if limiter.allow("ana") else "n" for _ in range(n))

print("t=0   bucket", burst(bucket, 5), "| window", burst(window, 5))
clock.t = 2
print("t=2   bucket", burst(bucket, 3), "| window", burst(window, 3))
clock.t = 10.5
print("t=10.5 bucket", burst(bucket, 4), "| window", burst(window, 4))
print("other client:", "Y" if bucket.allow("ben") else "n")

output
t=0   bucket YYYnn | window YYYnn
t=2   bucket YYn | window nnn
t=10.5 bucket YYYn | window YYYn
other client: Y

At t=2 the bucket has refilled two tokens, but the window still counts three requests in the last ten seconds — same limit, different shape of traffic allowed.

Watch it

Extensions and trade-offs

• Memory — the sliding log stores one timestamp per request; a sliding window counter (two fixed windows, weighted) is O(1) per client at slight inaccuracy.
• Distributed — keep state in a shared store with atomic increments (or a script that does read-modify-write atomically); otherwise each server enforces its own limit.
• Tiers — the registry picks a rule per plan; rules come from config (Open/Closed).
• Response — return 429 with a Retry-After header computed from the bucket.
• Placement — as middleware (Chain of Responsibility) or a Proxy in front of the handler.

Key terms

• Token bucket — Tokens refill at a fixed rate up to a cap; each request spends one.
• Sliding window log — Keep timestamps of recent requests and count those inside the window.
• Throttling — Rejecting or delaying requests that exceed the limit, typically with HTTP 429.
• Lazy refill — Computing tokens earned since the last request instead of running a timer.