Design a rate limiter that allows N requests per client per minute. Write the class.

Start by rejecting the obvious one

The first design anyone reaches for is a counter per client per minute: on each request, increment; if the count exceeds the limit, reject; reset the counter when the minute rolls over.

It is easy, it is cheap, and it has a specific flaw worth naming before the interviewer does. A client limited to 100 per minute sends 100 requests at 10:00:59 and another 100 at 10:01:00. Both windows are individually within limit, and the server absorbed 200 requests in about a second — twice the rate the limiter exists to enforce, at exactly the burst the downstream system is least able to handle.

A sliding log fixes it by keeping the timestamp of every request and counting those within the last minute. Exactly correct, and it stores one timestamp per request per client, which for any meaningful traffic is more memory than the requests themselves were worth.

Token bucket

The design that gets the correctness without the storage. Each client has a bucket that holds up to capacity tokens and refills at a constant rate. A request consumes one token; no token, no request.

The insight that makes it cheap is that you never run a refill process. Store the token count and the time it was last updated, and compute the refill on arrival from the elapsed time. Two numbers per client, no timers, no background thread, and the arithmetic is exact regardless of how long the client was idle.

public final class TokenBucketLimiter {
    private final long capacity;
    private final double tokensPerNano;
    private final Map<String, Bucket> buckets = new ConcurrentHashMap<>();

    public TokenBucketLimiter(long capacity, long refillPerMinute) {
        this.capacity = capacity;
        this.tokensPerNano = refillPerMinute / 60_000_000_000.0;
    }

    public boolean tryAcquire(String clientId) {
        Bucket bucket = buckets.computeIfAbsent(clientId, id -> new Bucket(capacity));
        // Refill and consume must be one atomic step. Two threads that each
        // read 1 token remaining would otherwise both be allowed through.
        synchronized (bucket) {
            long now = System.nanoTime();
            double refilled = (now - bucket.lastRefillNanos) * tokensPerNano;
            bucket.tokens = Math.min(capacity, bucket.tokens + refilled);
            bucket.lastRefillNanos = now;
            if (bucket.tokens < 1.0) return false;
            bucket.tokens -= 1.0;
            return true;
        }
    }

    private static final class Bucket {
        double tokens;
        long lastRefillNanos = System.nanoTime();
        Bucket(long initial) { this.tokens = initial; }
    }
}

Three details in there are the ones being marked.

System.nanoTime() rather than currentTimeMillis(), because the wall clock can step backwards when NTP corrects it, and a negative elapsed time makes the refill arithmetic produce nonsense.

The lock is per bucket, not on the whole limiter. Clients are independent, so a single lock would serialise every request in the process for no reason. ConcurrentHashMap handles the map; the small critical section handles one client.

The refill and the consume are inside the same critical section. Splitting them is the classic bug: two threads each read the same one remaining token and both proceed. A limiter that lets a request through under concurrency is not a limiter, and this is the single most common thing candidates get wrong.

Capacity is the burst policy

Capacity and refill rate are separate knobs and that is the point. Capacity equal to the per-minute limit permits the whole minute's allowance instantly and then a slow trickle. Capacity of 20 on a refill of 5 per second permits a burst of 20 and then sustains 5 — which is usually what an API actually wants, since real clients are bursty and a strictly smooth limiter rejects reasonable traffic.

If you want no burst at all, capacity of 1 with the appropriate rate gives you a leaky bucket, which shapes traffic into an even stream.

The leak, and the thing beyond the process

The map grows forever. Every client that ever made one request holds an entry, and for a public API that is unbounded memory — a slow leak that will not appear in any test and will appear in production some weeks later.

Eviction is part of the design, not a refinement. A bounded cache with expiry after idle time is the straightforward answer, and the correctness argument is pleasant: a bucket idle for longer than it takes to refill completely is indistinguishable from a fresh one, so discarding it loses nothing.

The other honest limitation is scope. This limiter is per process, so twelve instances behind a load balancer enforce twelve times the limit. Say that out loud, because a candidate who does not is often assumed not to have noticed. The distributed version moves the counter to a shared store — Redis with an atomic script that performs the same refill-and-consume in one round trip — and accepts a network hop on every request, which is why per-instance limits with the rate divided by the instance count is a common and defensible approximation.

Refill lazily from a timestamp and the whole thing is two numbers per client with no timers. Split the refill from the consume and you have a rate limiter that leaks requests under exactly the load it exists to survive.