LLD: Rate Limiter¶

Difficulty: Advanced | Time: 40–50 minutes

This is the single-process, class-level version of rate limiting. For how this scales across multiple servers with a shared counter store, see Rate Limiting.

1. Problem Statement¶

Design an in-process rate limiter that a service can use to throttle requests per client — a client being an API key, a user ID, or an IP address. The limiter must support multiple algorithms (token bucket, sliding window log, sliding window counter, fixed window) behind one clean interface, and expose a single method — allow_request(client_id) -> bool — that middleware can call on every incoming request.

2. Requirements¶

Functional (in scope):

• Per-client limits: each client is tracked and throttled independently
• A single, algorithm-agnostic entry point: allow_request(client_id) -> bool
• Support swapping the underlying algorithm (token bucket, sliding window, etc.) without changing any caller
• Thread-safe under concurrent calls, including many concurrent calls for the same client

Explicitly out of scope for v1: distributed coordination across multiple processes or machines — a shared counter store (Redis, etc.), clock synchronization between nodes, and the "10 pods × local limit = 10× the intended rate" problem are all covered in Rate Limiting. This page is deliberately scoped to one process, one shared-memory address space, one clock.

3. Entities¶

RateLimiter (the Strategy interface), TokenBucketLimiter and SlidingWindowCounterLimiter (concrete algorithms), and per-client state — TokenBucketState / WindowState — held in a map keyed by client_id.

4. Class Design¶

classDiagram
    class RateLimiter {
        <<interface>>
        +allow_request(client_id)* bool
    }

    class TokenBucketLimiter {
        -rate: float
        -capacity: float
        -buckets: Dict~str, TokenBucketState~
        -map_lock: Lock
        +allow_request(client_id) bool
        -_get_state(client_id) TokenBucketState
    }

    class SlidingWindowCounterLimiter {
        -limit: int
        -window_seconds: float
        -windows: Dict~str, WindowState~
        -map_lock: Lock
        +allow_request(client_id) bool
        -_get_state(client_id) WindowState
    }

    class TokenBucketState {
        +tokens: float
        +last_refill: float
        +lock: Lock
    }

    class WindowState {
        +prev_count: int
        +curr_count: int
        +curr_window_start: float
        +lock: Lock
    }

    RateLimiter <|.. TokenBucketLimiter
    RateLimiter <|.. SlidingWindowCounterLimiter
    TokenBucketLimiter *-- TokenBucketState : one per client_id
    SlidingWindowCounterLimiter *-- WindowState : one per client_id

Why per-client state is a separate object with its own lock, not a field on the limiter itself: the limiter instance is shared across every client; the state (tokens, last_refill, or window counts) is not. Modeling TokenBucketState as its own small object — one per client_id, each with its own Lock — is what makes per-client locking possible instead of a single lock serializing every client through the same limiter. This mirrors Parking Lot's per-spot lock, not LRU Cache's single whole-structure lock — the reasoning for which is in Concurrency below.

5. Patterns Applied¶

• Strategy is the entire point of this exercise: RateLimiter is an interface, and TokenBucketLimiter / SlidingWindowCounterLimiter / a future FixedWindowLimiter are interchangeable implementations. Middleware depends on RateLimiter.allow_request() and never knows which algorithm is behind it — swap the algorithm by swapping the constructor argument, with zero edits to any call site. See Design Patterns.
• The real content of this problem isn't the pattern — it's the algorithm trade-off the pattern is hiding behind one interface:

Token bucket. A bucket holds up to capacity tokens, refilled at rate tokens/second; each request consumes one. Refill is computed lazily — on each allow_request call, from elapsed wall-clock time since the last check — rather than via a background thread ticking a counter, which is both an O(1) trick (no timer thread, no wasted wakeups for idle clients) and simpler to reason about (no separate thread touching shared state). Allows bursts up to capacity by design — an idle client that's been accumulating tokens can legitimately spend them all at once, which is a feature (see Edge Cases) not a bug. Memory: O(1) per client (two numbers: tokens, last_refill). This is the default choice when burst tolerance is acceptable.

Sliding window log. Store the exact timestamp of every request in the current window (e.g. in a per-client deque or sorted set); on each check, drop timestamps older than window_seconds and compare the remaining count to the limit. Fully accurate — no boundary-spike artifact, no approximation — but memory is O(requests-in-window) per client, which is the real cost: a client sending 10,000 req/window needs a structure holding 10,000 timestamps, indefinitely, as long as they keep that rate up. This is the right choice only when exactness is a hard requirement (e.g. billing-relevant quotas) and per-client request volume is bounded.

Sliding window counter (approximate). Keep two fixed-window counters per client — the just-completed window and the current one — and estimate the sliding count as curr_count + prev_count × (fraction of previous window still "in" the sliding view). O(1) memory per client (two integers plus a window-start timestamp), and in practice close enough to exact that it's the standard production compromise: cheap like fixed window, without fixed window's boundary-spike vulnerability (a client can no longer send limit requests at 00:00:59.999 and limit more at 00:01:00.001 for 2×limit in 2ms, because the weighted previous-window count still counts against them).

Fixed window counter. One integer per client, reset every window_seconds. Cheapest of all (O(1) memory, one comparison), but has the boundary-spike problem above. Mentioned for completeness; not implemented below since sliding window counter dominates it at nearly the same cost.

The table in Rate Limiting covers the same four algorithms at the distributed-systems layer (Redis-backed); the trade-offs above are the same shape, just paid for in local memory and lock contention instead of Redis round-trips and network partitions.

6. Core Code¶

from abc import ABC, abstractmethod
from dataclasses import dataclass, field
from threading import Lock
import time


class RateLimiter(ABC):
    @abstractmethod
    def allow_request(self, client_id: str) -> bool: ...


# ---------------------------------------------------------------------------
# Token Bucket
# ---------------------------------------------------------------------------

@dataclass
class TokenBucketState:
    tokens: float
    last_refill: float
    lock: Lock = field(default_factory=Lock)


class TokenBucketLimiter(RateLimiter):
    def __init__(self, rate: float, capacity: float):
        self.rate = rate                     # tokens added per second
        self.capacity = capacity             # max tokens a bucket can hold
        self._buckets: dict[str, TokenBucketState] = {}
        self._map_lock = Lock()              # protects _buckets structure only, not bucket contents

    def _get_state(self, client_id: str) -> TokenBucketState:
        # fast path: bucket already exists, no need to hold the map lock
        state = self._buckets.get(client_id)
        if state is not None:
            return state
        with self._map_lock:                 # slow path: creating a new client's bucket must be atomic
            state = self._buckets.get(client_id)
            if state is None:
                state = TokenBucketState(tokens=self.capacity, last_refill=time.time())
                self._buckets[client_id] = state
            return state

    def allow_request(self, client_id: str) -> bool:
        state = self._get_state(client_id)
        with state.lock:                     # per-client lock — other clients proceed uncontended
            now = time.time()
            elapsed = now - state.last_refill
            if elapsed > 0:                  # guards against a backward clock jump (see Edge Cases)
                state.tokens = min(self.capacity, state.tokens + elapsed * self.rate)
                state.last_refill = now

            if state.tokens >= 1:
                state.tokens -= 1
                return True
            return False


# ---------------------------------------------------------------------------
# Sliding Window Counter (approximate)
# ---------------------------------------------------------------------------

@dataclass
class WindowState:
    prev_count: int = 0
    curr_count: int = 0
    curr_window_start: float = field(default_factory=time.time)
    lock: Lock = field(default_factory=Lock)


class SlidingWindowCounterLimiter(RateLimiter):
    def __init__(self, limit: int, window_seconds: float):
        self.limit = limit
        self.window_seconds = window_seconds
        self._windows: dict[str, WindowState] = {}
        self._map_lock = Lock()

    def _get_state(self, client_id: str) -> WindowState:
        state = self._windows.get(client_id)
        if state is not None:
            return state
        with self._map_lock:
            state = self._windows.get(client_id)
            if state is None:
                state = WindowState()
                self._windows[client_id] = state
            return state

    def allow_request(self, client_id: str) -> bool:
        state = self._get_state(client_id)
        with state.lock:
            now = time.time()
            elapsed_in_window = now - state.curr_window_start

            if elapsed_in_window >= self.window_seconds:
                windows_passed = int(elapsed_in_window // self.window_seconds)
                if windows_passed == 1:
                    state.prev_count = state.curr_count
                else:
                    state.prev_count = 0     # more than one window idle — previous window is stale
                state.curr_count = 0
                state.curr_window_start += windows_passed * self.window_seconds
                elapsed_in_window = now - state.curr_window_start

            prev_weight = max(0.0, 1 - elapsed_in_window / self.window_seconds)
            estimated = state.curr_count + state.prev_count * prev_weight

            if estimated < self.limit:
                state.curr_count += 1
                return True
            return False

Both limiters share the same two-tier locking shape: a _map_lock that protects only the structure of the client dictionary (inserting a never-seen client), and a per-client lock that protects that client's counters. A request for client A never blocks on a request for client B — see Concurrency below for why that split matters.

7. Edge Cases¶

8. Concurrency¶

This is the crux of the exercise: many threads call allow_request(client_id) concurrently, frequently for the same client_id (a single hot API key hammering the service), and the design has to stay correct without letting the lock itself become the bottleneck.

Per-client lock granularity, not a global lock. Each TokenBucketState / WindowState carries its own Lock. Two threads handling requests for different clients never block each other — they acquire different locks and proceed fully in parallel. This is the same reasoning as Parking Lot's per-spot lock over a lot-wide lock: contention should be scoped to the smallest unit that actually shares mutable state, and unrelated clients share nothing. A single lock around the whole limiter — the LRU Cache approach — would be wrong here for the opposite reason it was right there: LRU's get mutates a shared list on every call, so every operation genuinely needs exclusive access to the same structure; here, per-client state is genuinely independent, so a shared lock would serialize unrelated clients for no correctness reason at all.

The two-tier lock split (_map_lock vs per-client lock) is what makes this work without a race on client creation. The very first request from a never-before-seen client_id needs to atomically check-and-insert into self._buckets — that's a real race (two threads both see the key missing, both create a fresh TokenBucketState, one overwrites the other, and a token or two is silently lost from whichever state loses the race). _get_state's double-checked pattern — an unlocked fast-path read, then re-checking under _map_lock before inserting — closes that window (race conditions) while keeping the map lock held only for the rare "first request from this client" case, not every request. See Locks for the general check-then-act pattern this follows.

Where per-client locking itself becomes the bottleneck. Per-client granularity solves cross-client contention, but does nothing for a single extremely hot client — if one API key alone is generating 500K req/s, every one of those requests still serializes on that one client's lock, and lock acquisition/release overhead can become the actual ceiling on throughput for that client, independent of the rate limit's own math. The next step past a Lock here is a lock-free implementation: represent tokens as an atomic value and update it with compare-and-swap (read the current value, compute the refilled-and-decremented value, atomically swap only if nothing else changed it in between, retry on failure) instead of a mutex. Python's GIL makes this a less pressing concern for a pure-Python implementation than it would be in Go, Java, or C++, but the principle — thread safety without locks via CAS — is the right answer to name when an interviewer pushes on "what if the lock itself is now the bottleneck."

9. Extensibility¶

Interview Questions¶

Key Takeaways¶

Previous: Car Rental | Next: Logger