Rate limiter

A small problem with a lot to talk about: two algorithms with different trade-offs, a clean interface so callers don't care which one runs, and the clock passed in so the whole thing can be tested exactly.

1. The prompt

It's often a follow-on from the system design version (D02), which covers the distributed side. Here the focus is the classes and the algorithms in one process.

2. Clarify the requirements

Spend the first five minutes here. Ask, then write the answers down where the interviewer can see them.

3. The classes

4. How it works

The token bucket from the code, step by step.

5. Patterns and why

6. The code

Time is passed in as milliseconds. In production you'd inject a clock object, which amounts to the same thing.

from __future__ import annotations
import threading
from abc import ABC, abstractmethod
from collections import deque


class RateLimiter(ABC):
    """allow() answers one question: may this client make a request now? Time is passed in, so tests are exact."""

    @abstractmethod
    def allow(self, client: str, now_ms: int) -> bool: ...


class TokenBucket(RateLimiter):
    """Bursts up to `capacity`, then `refill_per_sec` requests a second on average."""

    def __init__(self, capacity: int, refill_per_sec: float) -> None:
        self.capacity, self.rate = capacity, refill_per_sec
        self.buckets: dict[str, tuple[float, int]] = {}   # client -> (tokens, last refill time)
        self.lock = threading.Lock()

    def allow(self, client: str, now_ms: int) -> bool:
        with self.lock:
            tokens, last = self.buckets.get(client, (float(self.capacity), now_ms))
            tokens = min(self.capacity, tokens + (now_ms - last) * self.rate / 1000)
            allowed = tokens >= 1
            if allowed:
                tokens -= 1
            self.buckets[client] = (tokens, now_ms)
            return allowed


class SlidingWindowLog(RateLimiter):
    """At most `limit` requests in any `window_ms`: exact, but stores one timestamp per request."""

    def __init__(self, limit: int, window_ms: int) -> None:
        self.limit, self.window = limit, window_ms
        self.logs: dict[str, deque[int]] = {}
        self.lock = threading.Lock()

    def allow(self, client: str, now_ms: int) -> bool:
        with self.lock:
            log = self.logs.setdefault(client, deque())
            while log and log[0] <= now_ms - self.window:
                log.popleft()
            if len(log) < self.limit:
                log.append(now_ms)
                return True
            return False


def show(name: str, limiter: RateLimiter, calls: list[tuple[str, int]]) -> None:
    print(name)
    for client, t in calls:
        print(f"  {client} at {t} ms: {'allowed' if limiter.allow(client, t) else 'rejected'}")


if __name__ == "__main__":
    show("token bucket (3 burst, 1/s)", TokenBucket(3, 1.0),
         [("alice", 0), ("alice", 0), ("alice", 0), ("alice", 0), ("bob", 0), ("alice", 1000), ("alice", 1000)])
    show("sliding window (2 per 1000 ms)", SlidingWindowLog(2, 1000),
         [("alice", 0), ("alice", 300), ("alice", 600), ("alice", 1001), ("alice", 1301)])

/** allow() answers one question: may this client make a request now? Time is passed in, so tests are exact. */
interface RateLimiter {
  allow(client: string, nowMs: number): boolean;
}

/** Bursts up to `capacity`, then `refillPerSec` requests a second on average. */
class TokenBucket implements RateLimiter {
  private buckets = new Map<string, { tokens: number; last: number }>();
  constructor(private readonly capacity: number, private readonly refillPerSec: number) {}

  // JavaScript runs one callback at a time, so no lock is needed inside one process.
  allow(client: string, nowMs: number): boolean {
    const b = this.buckets.get(client) ?? { tokens: this.capacity, last: nowMs };
    let tokens = Math.min(this.capacity, b.tokens + ((nowMs - b.last) * this.refillPerSec) / 1000);
    const allowed = tokens >= 1;
    if (allowed) tokens -= 1;
    this.buckets.set(client, { tokens, last: nowMs });
    return allowed;
  }
}

/** At most `limit` requests in any `windowMs`: exact, but stores one timestamp per request. */
class SlidingWindowLog implements RateLimiter {
  private logs = new Map<string, number[]>();
  constructor(private readonly limit: number, private readonly windowMs: number) {}

  allow(client: string, nowMs: number): boolean {
    const log = this.logs.get(client) ?? [];
    while (log.length && log[0] <= nowMs - this.windowMs) log.shift();
    this.logs.set(client, log);
    if (log.length < this.limit) {
      log.push(nowMs);
      return true;
    }
    return false;
  }
}

function show(name: string, limiter: RateLimiter, calls: [string, number][]): void {
  console.log(name);
  for (const [client, t] of calls) console.log(`  ${client} at ${t} ms: ${limiter.allow(client, t) ? "allowed" : "rejected"}`);
}

show("token bucket (3 burst, 1/s)", new TokenBucket(3, 1),
  [["alice", 0], ["alice", 0], ["alice", 0], ["alice", 0], ["bob", 0], ["alice", 1000], ["alice", 1000]]);
show("sliding window (2 per 1000 ms)", new SlidingWindowLog(2, 1000),
  [["alice", 0], ["alice", 300], ["alice", 600], ["alice", 1001], ["alice", 1301]]);

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.HashMap;
import java.util.Map;

/** allow() answers one question: may this client make a request now? Time is passed in, so tests are exact. */
interface RateLimiter {
    boolean allow(String client, long nowMs);
}

/** Bursts up to capacity, then refillPerSec requests a second on average. */
class TokenBucket implements RateLimiter {
    private static final class Bucket {
        double tokens;
        long last;

        Bucket(double tokens, long last) {
            this.tokens = tokens;
            this.last = last;
        }
    }

    private final int capacity;
    private final double refillPerSec;
    private final Map<String, Bucket> buckets = new HashMap<>();

    TokenBucket(int capacity, double refillPerSec) {
        this.capacity = capacity;
        this.refillPerSec = refillPerSec;
    }

    @Override
    public synchronized boolean allow(String client, long nowMs) {
        Bucket b = buckets.computeIfAbsent(client, c -> new Bucket(capacity, nowMs));
        b.tokens = Math.min(capacity, b.tokens + (nowMs - b.last) * refillPerSec / 1000);
        b.last = nowMs;
        if (b.tokens < 1) return false;
        b.tokens -= 1;
        return true;
    }
}

/** At most limit requests in any windowMs: exact, but stores one timestamp per request. */
class SlidingWindowLog implements RateLimiter {
    private final int limit;
    private final long windowMs;
    private final Map<String, Deque<Long>> logs = new HashMap<>();

    SlidingWindowLog(int limit, long windowMs) {
        this.limit = limit;
        this.windowMs = windowMs;
    }

    @Override
    public synchronized boolean allow(String client, long nowMs) {
        Deque<Long> log = logs.computeIfAbsent(client, c -> new ArrayDeque<>());
        while (!log.isEmpty() && log.peekFirst() <= nowMs - windowMs) log.pollFirst();
        if (log.size() < limit) {
            log.addLast(nowMs);
            return true;
        }
        return false;
    }
}

public class Main {
    static void show(String name, RateLimiter limiter, Object[][] calls) {
        System.out.println(name);
        for (Object[] c : calls) {
            String client = (String) c[0];
            long t = (Integer) c[1];
            System.out.println("  " + client + " at " + t + " ms: " + (limiter.allow(client, t) ? "allowed" : "rejected"));
        }
    }

    public static void main(String[] args) {
        show("token bucket (3 burst, 1/s)", new TokenBucket(3, 1.0), new Object[][] {
            {"alice", 0}, {"alice", 0}, {"alice", 0}, {"alice", 0}, {"bob", 0}, {"alice", 1000}, {"alice", 1000}});
        show("sliding window (2 per 1000 ms)", new SlidingWindowLog(2, 1000), new Object[][] {
            {"alice", 0}, {"alice", 300}, {"alice", 600}, {"alice", 1001}, {"alice", 1301}});
    }
}

Output (the same in all three languages)

token bucket (3 burst, 1/s)
  alice at 0 ms: allowed
  alice at 0 ms: allowed
  alice at 0 ms: allowed
  alice at 0 ms: rejected
  bob at 0 ms: allowed
  alice at 1000 ms: allowed
  alice at 1000 ms: rejected
sliding window (2 per 1000 ms)
  alice at 0 ms: allowed
  alice at 300 ms: allowed
  alice at 600 ms: rejected
  alice at 1001 ms: allowed
  alice at 1301 ms: allowed

7. Concurrency and edge cases

• Read-modify-write needs a lock: two threads reading the same token count would both take the last token. Python and Java lock per limiter here; a lock per client (or striped locks) scales better.
• Memory grows with clients. Evict idle clients (an LRU map, P01) or the map grows forever.
• Clock going backwards (a system clock adjustment) can create negative elapsed time; use a monotonic clock.
• Several servers each with their own limiter multiply the limit. Shared state belongs in Redis with an atomic script: see D02.

8. Follow-up questions

What interviewers ask once the core works, and a short answer for each.

How do you return how long to wait?

Token bucket: (1 − tokens) / rate seconds until the next token. Sliding log: the oldest timestamp plus the window, minus now.

Different limits per client tier?

Pass a limit policy (another strategy) that looks up capacity and rate by client.

How would you test it?

Inject time, then replay a list of (client, time) calls and compare with expected allow/reject, exactly like the demo.

Which would you choose?

Token bucket for most APIs (cheap, allows short bursts); sliding log when the limit must never be exceeded in any window.

9. Common mistakes

10. Check yourself

Your turn

1. Add Retry-After (10 min). Return how many milliseconds until the next request would be allowed.
2. Add a fixed window limiter (10 min). A third implementation of the same interface.
3. Evict idle clients (5 min). Drop clients not seen for an hour.