Design a Rate Limiter (Class-Level)
You'll learn to
- -Implement token bucket and sliding window rate limiters as swappable Strategy classes
- -Reason about per-user vs. global limits and where this class-level design would need to change for a distributed system
The LLD version of "design a rate limiter" asks for a single-process, in-memory implementation - a different (and simpler) problem than the distributed, multi-server rate limiter you might design in an HLD round. Getting the algorithm and its edge cases right at the class level is the actual point here.
Token Bucket
A bucket holds up to capacity tokens, refilling at a fixed rate over time. Each request consumes one token if available; if the bucket is empty, the request is rejected. This naturally allows short bursts up to the bucket's capacity while enforcing a steady average rate over time.
import time
import threading
class TokenBucketLimiter:
def __init__(self, capacity: int, refill_rate_per_sec: float):
self._capacity = capacity
self._refill_rate = refill_rate_per_sec
self._tokens = float(capacity)
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_request(self) -> bool:
with self._lock: # refill, check, and decrement as one atomic step
self._refill()
if self._tokens >= 1:
self._tokens -= 1
return True
return FalseThis is the exact "shared mutable counter" shape the concurrency chapter named as a canonical check-then-act race: two threads can both refill, both see tokens >= 1, and both decrement, handing out more requests than the bucket actually allows. The lock above closes that gap by making refill-check-decrement one atomic step instead of three.
Sliding Window Log
A sliding window log stores the timestamp of every request within the current window, and allows a new request only if the count within the last window_size seconds is below the limit. It is more memory-intensive (storing every timestamp) but avoids the "burst at window boundary" problem a naive fixed-window counter has, where a client could send limit requests right at the end of one window and another limit requests right at the start of the next, doubling the effective rate briefly.
import time
import threading
from collections import deque
class SlidingWindowLimiter:
def __init__(self, limit: int, window_seconds: float):
self._limit = limit
self._window = window_seconds
self._timestamps: deque[float] = deque()
self._lock = threading.Lock()
def allow_request(self) -> bool:
with self._lock: # trim, check, and append as one atomic step
now = time.monotonic()
while self._timestamps and self._timestamps[0] <= now - self._window:
self._timestamps.popleft() # drop timestamps outside the window
if len(self._timestamps) < self._limit:
self._timestamps.append(now)
return True
return FalseMaking the Algorithm Swappable
Both are Strategy implementations of the same RateLimiter interface (allow_request() -> bool), so a RateLimiterFactory or direct injection lets calling code switch algorithms without any change to whatever it protects - a natural, expected structure at this point in the course.
Per-User Limits and the Path to Distribution
A realistic follow-up: "each user should have their own limit, not one global limit." That is a small, additive change - wrap the chosen strategy in a dict keyed by user ID, constructing a new limiter instance per user on first request. Naming the honest limitation is worth doing explicitly: this whole design lives in one process's memory, so it works correctly for a single server, but a fleet of servers behind a load balancer would each enforce their own independent limit unless the counters move to a shared store like Redis - which is exactly the kind of problem an HLD round, not this LLD round, would ask you to solve.
Naming that boundary explicitly - "this is correct for a single process; a distributed version needs a shared counter store" - is a strong signal you understand the difference between the LLD and HLD versions of the same-sounding problem, which is exactly the distinction the very first chapter of this course drew.
Interview Signal is part of Pro
See a real weak answer next to a real strong one for this exact topic.
Quiz is part of Pro
Test what you just read with a short quiz, and bank the XP.