Design a Rate Limiter

Description

A rate limiter decides, for each request, whether a client is still within its allowance - "at most 100 requests per minute per user" - and it sits in front of nearly every public API. The design question is which algorithm counts usage (fixed window, sliding log, sliding window counter, token bucket), how it stays correct with many threads, and what changes when many servers share one limit. This skill builds the algorithms behind one interface and makes them thread-safe and testable.

"At most 100 requests per minute per user" sounds like a counter, and the first version is one:

Map<String, Integer> countThisMinute = new HashMap<>();   // a background thread clears it every minute

boolean allow(String user) {
    int n = countThisMinute.getOrDefault(user, 0);
    if (n >= 100) return false;
    countThisMinute.put(user, n + 1);
    return true;
}

count_this_minute: dict[str, int] = {}     # a background thread clears it every minute

def allow(user: str) -> bool:
    n = count_this_minute.get(user, 0)
    if n >= 100:
        return False
    count_this_minute[user] = n + 1
    return True

A client that sends 100 requests at 12:00:59 and another 100 at 12:01:00 gets 200 through in about a second - the window reset in between. Two threads can read n = 99 together and both allow request 100 and 101. The map grows with every IP address that ever called. The clearing thread, the real clock and the scheduler make it untestable. And the day the API runs on five servers, each server's counter allows 100, so a client gets 500.

We'll go from simple to more technical:

1. The algorithms and what each allows: fixed window, sliding log, token bucket.
2. A token bucket in code, with lazy refill and an injected clock.
3. Concurrency: per-key atomicity without a global lock.
4. Production concerns, bugs and the memory-accuracy tradeoff.

The approach

1. Clarify. Limit per what - user, API key, IP, endpoint? How many requests over what period, and are short bursts acceptable? When limited: reject (HTTP 429) or queue and delay? One server or many?
2. Model. A RateLimiter interface - boolean tryAcquire(String key) - with one class per algorithm. Per-key state in a concurrent map. Time from an injected Clock.
3. API. tryAcquire(key) returns true and counts the request, or false and counts nothing.
4. Core. Pick the algorithm by what the limit means (below); make each key's check-and-update atomic; create each key's state exactly once.

The pieces in code

A token bucket needs no timer thread: it refills lazily, when a request arrives, from the time that has passed.

private final class Bucket {
    private long tokens = capacity;                 // starts full
    private long lastRefill = clock.millis();

    synchronized boolean take() {                   // one lock per key
        long now = clock.millis();
        long gained = (now - lastRefill) / refillMillis;
        if (gained > 0) {
            tokens = Math.min(capacity, tokens + gained);
            lastRefill += gained * refillMillis;    // keep the unfinished part of an interval
        }
        if (tokens == 0) return false;
        tokens--;
        return true;
    }
}

public boolean tryAcquire(String key) {
    return buckets.computeIfAbsent(key, k -> new Bucket()).take();   // exactly one bucket per key
}

import threading
from collections.abc import Callable


class _Bucket:
    def __init__(self, capacity: int, refill_millis: int, clock: Callable[[], int]):
        self._capacity = capacity
        self._refill_millis = refill_millis
        self._clock = clock
        self._tokens = capacity                    # starts full
        self._last_refill = clock()
        self._lock = threading.Lock()              # one lock per key

    def take(self) -> bool:
        with self._lock:
            now = self._clock()
            gained = (now - self._last_refill) // self._refill_millis
            if gained > 0:
                self._tokens = min(self._capacity, self._tokens + gained)
                self._last_refill += gained * self._refill_millis   # keep the unfinished part of an interval
            if self._tokens == 0:
                return False
            self._tokens -= 1
            return True


def try_acquire(self, key: str) -> bool:
    with self._buckets_lock:                       # exactly one bucket per key
        bucket = self._buckets.get(key)
        if bucket is None:
            bucket = self._buckets[key] = _Bucket(self._capacity, self._refill_millis, self._clock)
    return bucket.take()

• Integer refill. gained counts whole intervals; advancing lastRefill by exactly those intervals keeps the leftover progress. Setting lastRefill = now instead throws away up to one interval every time - a token due at 2000 ms arrives at 2500.
• The cap (Math.min(capacity, ...)) is what makes capacity the maximum burst: an hour of silence buys capacity requests, not thousands.
• computeIfAbsent on a ConcurrentHashMap creates a key's bucket atomically. "get, and put if missing" lets two threads each create a bucket for a new key - and each bucket starts full. (Python's nearest equivalent, dict.setdefault(key, Bucket()), is atomic in CPython but builds a throwaway bucket on every call - so the Python tab takes a small lock around get-or-create instead.)

A sliding log keeps the times of allowed requests and drops the ones that have left the window:

synchronized (log) {
    long now = clock.millis();
    while (!log.isEmpty() && log.peekFirst() <= now - windowMillis) log.pollFirst();
    if (log.size() >= limit) return false;          // denied: not recorded
    log.addLast(now);
    return true;
}

def try_acquire(self, key: str) -> bool:
    log = self._log_for(key)                       # this key's allowed times, oldest first
    with self._lock_for(key):
        now = self._clock()
        while log and log[0] <= now - self._window_millis:
            log.popleft()
        if len(log) >= self._limit:
            return False                           # denied: not recorded
        log.append(now)
        return True

A request at time s counts while now - window < s, so it leaves exactly one window later. Recording denied requests too would lock out a client that keeps retrying - forever, as long as it retries.

Concurrency

if (tokens > 0) tokens-- is a check-then-act: two threads can both see one token and both take it. Two ways to make it atomic:

• A lock per key - synchronized on the bucket, as above. Different keys never wait for each other; one global lock around the whole limiter would serialize every request in the API.
• A lock-free loop - keep the state in an AtomicLong and retry compareAndSet(old, new) until it succeeds. It avoids blocking under heavy contention, at the cost of packing refill time and tokens into one atomic value. (Python's standard library has no compare-and-set; a lock per key is the Python answer.)

Across servers, in-process locks don't help at all: the counter has to live in one shared store. Redis is the usual choice - INCR plus an expiry for a fixed window, or a small Lua script that does the token-bucket refill-and-take atomically on the server.

Where you'll see it

Rate limiting usually lives at the edge: API gateways (AWS API Gateway throttles with a token bucket; nginx's limit_req uses a leaky bucket) and service meshes. A limited request gets HTTP 429 Too Many Requests with a Retry-After header - a token bucket can compute exactly how long until the next token. Per-key state is kept in a cache that evicts idle keys (a full bucket carries no information, so forgetting it is free). And distributed limiters must decide what to do when the shared store is unreachable: fail open (allow, and risk overload) or fail closed (deny, and risk an outage of your own making).

Which tool for which job?

Common mistakes

Check yourself

Try to answer before opening each one - recalling beats re-reading.

1. A fixed-window limiter allows 100 requests per minute. What's the most it can let through in two seconds, and why?

2. A token bucket has capacity 1 and refills every 1000 ms. A request at t = 0 takes the token; the next arrive at 1500 and 2000. With lastRefill = now, which of those are allowed - and with lastRefill += gained * interval?

3. Eight threads send the first-ever request for a new API key at the same instant, and the limit is 1. How can more than one get through, and what fixes it?

Key takeaways

• Choose the algorithm by what the limit means: token bucket for "burst plus rate", sliding window for "at most N in any window", fixed window only when boundary bursts don't matter.
• Denied requests don't count; token buckets refill lazily in whole intervals and cap at capacity.
• Make each key's check-and-update atomic (a lock per key or CAS) and create per-key state with computeIfAbsent.
• Inject the clock: refill and window tests move time instead of sleeping.
• Several servers need one shared counter (e.g. Redis with atomic scripts) - or they multiply the limit.