Skip to content
LLD Learn/Case Studies: Data-Structure-Heavy Systems
Browsing as a guest. Sign in to save your progress and earn XP as you complete chapters.

Design a Rate Limiter (Class-Level)

5 min read

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.

Token bucket - allows bursts, enforces an average rate
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 False

This 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.

Sliding window log - precise, at the cost of memory
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 False

See 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.

Press Run: the fixed window lets all six through in 2.3 seconds, the sliding window stops three

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.

Ready to Build This?

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.

Sign In to ScaleDojo

No comments yet. Be the first to start the thread!