Design a Rate Limiter (Class-Level)
You'll learn to
- -Explain token bucket and sliding window as two ways to say "no more than N requests in a time"
- -Show with numbers why a fixed-window counter lets a burst through at the boundary
- -State the honest limit of an in-memory limiter: it works in one process, not across a fleet of servers
A rate limiter says "no more than N requests in this much time", and refuses the extra ones. It protects a service from one noisy client, whether by accident or on purpose. The LLD version of this prompt asks for a single-process, in-memory limiter. That is a different and simpler problem from the distributed limiter you would design in an HLD round. Getting the algorithm and its edge cases right in a clean class is the point here.
Token Bucket
Picture a bucket that holds up to a fixed number of tokens, and a tap that drips new tokens in at a steady rate. Each request takes one token. If the bucket is empty, the request is refused. This allows a short burst, up to the bucket's size, while keeping the long-run average at the drip rate. For example, a bucket of 3 that refills 1 token a second lets 3 requests through at once, and then roughly one more per second.
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 counter" shape from the concurrency chapter. Two threads could both refill, both see a token, and both take it, handing out more requests than the bucket allows. The lock fixes this by making refill, check and decrement one atomic step instead of three.
Sliding Window Log
A sliding window log remembers the time of every request in the recent past. A new request is allowed only if fewer than the limit happened in the last window seconds. It uses more memory, because it stores every timestamp, but it avoids a flaw of the simpler fixed-window counter. A fixed-window counter resets to zero at fixed moments, such as every 10 seconds. A client could send the full limit just before a reset and the full limit again just after it, briefly doubling the effective rate.
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 FalseSee the Difference With Numbers
The demo below uses a fake clock so every result is exact. First the token bucket: three requests pass, a fourth is refused, and two seconds later two tokens have been added back. Then the same six requests, three just before the 10-second mark and three just after, go through a fixed-window and a sliding-window limiter, both set to 3 per 10 seconds.
Making the Algorithm Swappable
Both are Strategy implementations of one RateLimiter interface with allow_request() -> bool. Calling code can switch algorithms, through injection or a small factory, without changing whatever it protects.
Per-User Limits and the Path to Distribution
A likely follow-up: "each user should have their own limit". That is a small addition. Wrap the chosen strategy in a dictionary keyed by user id, and create a new limiter the first time a user is seen. Then name the honest limitation. This design lives in one process's memory, so it is correct for one server. A fleet of servers behind a load balancer would each enforce their own separate limit, multiplying the real limit by the number of servers, unless the counters move to a shared store such as Redis. That is a problem for an HLD round, not this one.
Saying "this is correct for one process; a distributed version needs a shared counter store" shows you know the difference between the LLD and HLD versions of a problem that sounds the same. It is 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.
Forge Level 41: Rate Limiter asks you to implement allow_request() with a deterministic, explicit-timestamp algorithm (no wall-clock dependence), graded by running your actual code against real test cases. It pairs with API Design's "Rate Limit Fortress" level for the same concept from the API-contract side.
Discussion0
Join the Discussion
Sign in to leave comments, reply to others, or like insights.
No comments yet. Be the first to start the thread!