Back to Notes

Design a Rate Limiter (LLD)

1. Problem & How This Differs From the HLD Version

The [[Rate Limiter]] HLD page covers the distributed systems version — Redis, atomicity across gateway instances, fail-open/closed at scale. This page is the class-design version asked in a machine-coding round: implement the token bucket algorithm itself as clean, extensible, in-process Python — no Redis, no network. The algorithmic core (token bucket math) is identical; what's being tested here is API design and object modeling, not distributed systems.

2. Requirements

Functional: allow(client_id) -> bool — return whether a request is permitted right now. Support different limits per client or per rule. Refill tokens continuously over time (not in discrete resets).

Non-functional: O(1) per check (no scanning). Thread-safe. Extensible to different algorithms (token bucket vs sliding window) without rewriting the caller.

3. Class Diagram

classDiagram
    class RateLimitStrategy {
        <<interface>>
        +allow(client_id) bool
    }
    class TokenBucket {
        -float capacity
        -float tokens
        -float refill_rate
        -float last_refill
        +allow() bool
        -_refill()
    }
    class SlidingWindowLog {
        -deque timestamps
        -int limit
        -float window_seconds
        +allow() bool
    }
    class RateLimiter {
        -dict~str,RateLimitStrategy~ buckets
        -Lock lock
        +allow(client_id) bool
    }
    RateLimitStrategy <|.. TokenBucket
    RateLimitStrategy <|.. SlidingWindowLog
    RateLimiter "1" --> "*" RateLimitStrategy

4. Design Pattern: Strategy

The algorithm (token bucket, sliding window, leaky bucket — see [[Rate Limiter]] for the full comparison) is swappable behind one interface, so RateLimiter never branches on algorithm type — see [[OOD Design Patterns]]. This is the same reasoning as pricing in [[Parking Lot]].

5. Implementation

import time
import threading
from abc import ABC, abstractmethod
from collections import deque


class RateLimitStrategy(ABC):
    @abstractmethod
    def allow(self) -> bool: ...


class TokenBucket(RateLimitStrategy):
    def __init__(self, capacity: float, refill_rate: float):
        self.capacity = capacity
        self.tokens = capacity
        self.refill_rate = refill_rate      # tokens added per second
        self.last_refill = time.monotonic()
        self._lock = threading.Lock()

    def _refill(self) -> None:
        now = time.monotonic()
        elapsed = now - self.last_refill
        self.tokens = min(self.capacity, self.tokens + elapsed * self.refill_rate)
        self.last_refill = now

    def allow(self) -> bool:
        with self._lock:
            self._refill()
            if self.tokens >= 1:
                self.tokens -= 1
                return True
            return False


class SlidingWindowLog(RateLimitStrategy):
    """Exact sliding window — trades memory (O(rate)) for zero boundary-burst error."""
    def __init__(self, limit: int, window_seconds: float):
        self.limit = limit
        self.window_seconds = window_seconds
        self.timestamps: deque[float] = deque()
        self._lock = threading.Lock()

    def allow(self) -> bool:
        with self._lock:
            now = time.monotonic()
            cutoff = now - self.window_seconds
            while self.timestamps and self.timestamps[0] < cutoff:
                self.timestamps.popleft()
            if len(self.timestamps) < self.limit:
                self.timestamps.append(now)
                return True
            return False


class RateLimiter:
    """Per-client rate limiting, pluggable algorithm, lazy bucket creation."""
    def __init__(self, strategy_factory):
        self._strategy_factory = strategy_factory   # callable: () -> RateLimitStrategy
        self._buckets: dict[str, RateLimitStrategy] = {}
        self._lock = threading.Lock()

    def allow(self, client_id: str) -> bool:
        with self._lock:
            if client_id not in self._buckets:
                self._buckets[client_id] = self._strategy_factory()
        return self._buckets[client_id].allow()


# Usage: 10-token bucket refilling at 2 tokens/sec, one bucket per client
limiter = RateLimiter(strategy_factory=lambda: TokenBucket(capacity=10, refill_rate=2))
limiter.allow("client_123")

6. Why time.monotonic(), Not time.time()

time.time() reflects wall-clock time, which can jump backward (NTP correction, manual clock change) — a backward jump would make elapsed negative, corrupting the refill math (or worse, granting a huge refill on a forward correction). time.monotonic() is guaranteed non-decreasing on a single machine, which is exactly the property a duration calculation needs and wall-clock time doesn't guarantee.

7. Concurrency

  • Each TokenBucket/SlidingWindowLog has its own lock — contention is per-client, not global. Two different clients' allow() calls never block each other.
  • RateLimiter._buckets dict mutation (lazy creation on first request) is the one shared structure — locked briefly just for the check-and-insert, then released before calling into the per-client strategy's own lock. This avoids holding a global lock for the actual rate-check logic.
  • Race in the lazy-creation check-then-act: without the outer lock, two threads could both see client_id not in self._buckets and both construct a fresh bucket, with one overwriting the other (losing whatever state the first had accumulated, though for a brand new client this is harmless — worth noting it'd matter more if bucket construction had side effects).

8. Edge Cases

  • Fractional tokens: TokenBucket.tokens is a float, not an int — deliberate, since refill_rate may not divide evenly into whole tokens per check interval. Comparing tokens >= 1 (not == capacity) and subtracting exactly 1 per allowed request keeps the fractional remainder correct for the next refill.
  • Clock not advancing between two rapid calls — elapsed can be 0 or very near 0; _refill() handles this gracefully (adds ~0 tokens), no special-casing needed.
  • Client never seen before — lazily creates a fresh bucket at full capacity rather than requiring pre-registration; the trade-off is a burst-friendly first request for every new client, which is usually the desired behavior (a new client isn't already "in debt").

9. Extensibility

  • Per-endpoint limits, not just per-client: change the RateLimiter key from client_id alone to a composite (client_id, endpoint) key — zero change to TokenBucket/SlidingWindowLog themselves.
  • Different limits per client tier: the strategy_factory becomes a function of client_id (look up the client's tier, return a TokenBucket configured for that tier) instead of one fixed lambda — still zero change to the strategy classes.
  • Swap to leaky bucket: implement a new RateLimitStrategy subclass (FIFO queue, drain at fixed rate) — RateLimiter doesn't change at all, the entire payoff of the Strategy pattern.

10. Interview Drills

  1. Why is each client's bucket independently locked instead of one global lock? — A global lock would serialize every client's rate check against every other client's, even though they're logically independent — turning an O(1)-per-client operation into a system-wide bottleneck under concurrent load from many different clients.
  2. How would you bound memory when there are millions of distinct clients, most of whom stop making requests? — Add a TTL/last-accessed timestamp per bucket and a background sweep (or lazy check-on-access) that evicts buckets idle beyond some threshold — the in-process analogue of Redis key expiry in the HLD version.
  3. Compare this to the distributed version — what changes and why? — In-process, one lock per client is enough because there's only one instance of memory to coordinate. Distributed (see [[Rate Limiter]]), multiple gateway instances need a shared store (Redis) and atomic operations (Lua script) because "one lock per client" no longer applies across separate processes/machines.

Cross-links

[[Rate Limiter]] · [[OOD Design Patterns]] · [[Parking Lot]] · [[Caching & Redis]]