Rate Limiter

A rate limiter caps how many requests a client can make in a time window, e.g. 300 requests per minute per user. Requests over the limit get a "429 Too Many Requests" response. The LLD version focuses on the algorithm's data structure and on the race condition at its heart: check the count, then record the request.

Requirements#

The limiter needs to decide, explain and clean up:

1. When a user's request arrives, allow it if they're under quota; otherwise reject it.
2. Quota: N requests per rolling window per user (e.g. 300 per 60 seconds).
3. Tell rejected callers how long to wait (retry_after) and allowed callers how many requests remain.
4. Old timestamps must be evicted so memory doesn't grow forever.

Actor: API clients (users).

Clarifications

• One service to protect; limits are per user.
• Algorithm: sliding window log (exact) rather than token bucket (see trade-offs).
• Edge cases: first request ever, exactly at the limit, window just expired.

Out of scope: distributed rate limiting across many servers, UI.

Core entities#

Three small classes are enough:

Relationships#

RateLimiter does all the work:

• RateLimiter uses User (by id) and returns RateLimitResult.
• RateLimiter owns one deque and one lock per user.

Key flows#

One method handles every request; a second keeps memory in check.

allow_request(user):

1. Take the user's lock.
2. Evict timestamps older than now - window from the front of the deque.
3. If the deque has fewer than threshold entries, append now and allow; remaining = threshold - len.
4. Otherwise reject; retry_after = oldest + window - now (when the oldest request falls out of the window).

Only allowed requests are stored, so a user who keeps hammering while blocked still recovers once their window drains.

clean_up(): a periodic sweep evicts old timestamps for all users and drops users with empty deques.

Code#

A sliding-window-log limiter with one deque and one lock per user:

import threading
import time
from collections import defaultdict, deque
from typing import Deque, Dict


class User:
    def __init__(self, user_id: str, name: str):
        self.id = user_id
        self.name = name


class RateLimitResult:
    def __init__(self, allowed: bool, remaining: int, retry_after: float):
        self.allowed = allowed
        self.remaining = remaining
        self.retry_after = retry_after

    def __repr__(self):
        return (f"RateLimitResult(allowed={self.allowed}, "
                f"remaining={self.remaining}, "
                f"retry_after={self.retry_after:.1f})")


class RateLimiter:
    def __init__(self, threshold: int, window_seconds: int):
        self.threshold = threshold
        self.window_seconds = window_seconds
        self.user_requests: Dict[str, Deque[float]] = defaultdict(deque)
        self.locks: Dict[str, threading.Lock] = defaultdict(
            threading.Lock)
        # Guards creating and removing per-user entries
        self._registry_lock = threading.Lock()

    def _lock_for(self, user_id: str) -> threading.Lock:
        with self._registry_lock:
            return self.locks[user_id]

    def allow_request(self, user: User) -> RateLimitResult:
        # Evict -> check -> append is check-then-act, so it must be
        # atomic per user. A per-user lock means different users never
        # block each other.
        with self._lock_for(user.id):
            now = time.monotonic()  # monotonic: immune to wall-clock changes
            q = self.user_requests[user.id]

            while q and q[0] <= now - self.window_seconds:
                q.popleft()

            if len(q) < self.threshold:
                q.append(now)
                return RateLimitResult(True, self.threshold - len(q), 0.0)

            # Rejected: q has >= threshold >= 1 entries, so q[0] exists
            return RateLimitResult(False, 0, q[0] + self.window_seconds - now)

    def clean_up(self) -> None:
        now = time.monotonic()
        with self._registry_lock:
            # Snapshot: don't iterate a dict others may modify
            user_ids = list(self.user_requests)
        for user_id in user_ids:
            with self._lock_for(user_id):
                q = self.user_requests.get(user_id)
                if q is None:
                    continue
                while q and q[0] <= now - self.window_seconds:
                    q.popleft()
                if not q:
                    del self.user_requests[user_id]


if __name__ == "__main__":
    alice = User("u1", "alice")
    limiter = RateLimiter(threshold=3, window_seconds=60)
    for i in range(5):
        print(i, limiter.allow_request(alice))
    # 0-2 allowed (remaining 2, 1, 0); 3-4 rejected with retry_after ~60s

Extensions and trade-offs#

The sliding window log is exact but memory-hungry. Know the alternatives:

• Pluggable algorithms: put allow_request behind a RateLimitStrategy interface so the service can switch algorithms per endpoint.
• Different limits per tier: look up the threshold by user plan instead of using one global value.
• Distributed limiting: across many servers, keep counters in a shared store like Redis (e.g. a sorted set per user for the log, or INCR with expiry for a fixed window), and make the check-and-record atomic with a Lua script or transaction.
• Memory: the log stores up to N timestamps per active user. At 300/min that's fine; at 10,000/s switch to a counter or token bucket.
• Clock: time.monotonic() avoids surprises when the system clock jumps; across machines you need a shared notion of time.

Key takeaways#

• Sliding window log: a per-user deque of allowed timestamps, evicted lazily on each call.
• Store only allowed requests so blocked users recover when the window drains.
• retry_after = oldest + window - now.
• Evict → check → append is a check-then-act; lock it per user.
• Know the other algorithms and when to switch (memory, bursts, distribution).