Design a rate limiter

“Design a rate limiter: each user may make at most 10 requests per second.” The low-level version is a class inside one service. The version spread across many servers is a system design question of its own.

A rate limiter decides, for each incoming request, “let it through” or “too many, try again later”. It protects a service from clients that send too much, by accident or on purpose.

The first version takes five minutes: a counter per user that resets every second. Everything after that is about what the counter gets wrong. At the edge of a second it lets twice the limit through. It remembers every client forever. It can’t apply two limits at once without wasting one of them. And with many threads, two requests can both take the last free slot.

The framework

1. 01Answer
2. 02Scope
3. 03Build
4. 04Full design
5. 05Stress
6. 06Wrap up

The answer in one minute

If you only have a minute, this is the design. The rest of the page explains how we get here.

1. Each client gets a token bucket. A bucket holds a few tokens and refills at a steady rate. A request takes one token, or is refused if the bucket is empty. Short bursts are allowed, but the rate over time can’t go above the limit.
2. The algorithm sits behind an interface. The token bucket is one kind of Bucket. A fixed window or a sliding window can be swapped in, rule by rule.
3. A request must pass every rule, all or nothing. For example, per user and per IP address. If one rule refuses, the tokens already taken from the other rules are given back.
4. Idle clients are forgotten. A bucket left alone for a full period is the same as a new one, so we can safely delete it. Memory grows with active clients, not with every client ever seen.
5. Each bucket has its own small lock. Taking a token is one step that can’t be split. A thread holds at most one bucket’s lock at a time, so threads can never block each other forever.

We’ll build this in four stages, then deal with many threads at once, and with many servers.

Scope it

Before drawing anything, we ask a few questions. Each answer changes a class. Anything that doesn’t, we assume and move on.

Interviewerminute 0

Design a rate limiter for our API.

What they are testing

Whether you ask what is limited (user, IP, endpoint), whether bursts are OK, and whether this is one process or many, before naming an algorithm. Opening with “token bucket in Redis” skips the question that decides the design.

Here are the questions that matter:

• Limited by what? Several rules: per user, per IP address, per endpoint. With only one rule, stage 3 goes away.
• Are short bursts OK? Yes, up to the limit, then a steady rate. If no bursts were allowed at all, we’d need a queue that releases requests evenly instead.
• What happens to a refused request? It’s refused right away, with a time to retry after. If refused requests had to wait in line, this would be a scheduler, not a limiter.
• One process or many? One first. Many is the follow-up, and it moves the state into a shared store like Redis.
• How many different clients? Millions, most seen only once. With a few known clients, we could keep their state forever.

These answers give us one promise that matters more than the others: no more than the limit ever gets through. Not at the edge of a time window, and not when many threads check at once. Three smaller promises come with it. Memory grows with active clients only. A check never waits for another client’s traffic. And time is passed in, so tests can check refills without sleeping.

We leave out queueing refused requests, billing quotas that must survive a restart, and the HTTP part. Turning a refusal into a 429 Too Many Requests response with a Retry-After header is one line in the web layer.

Go deeperThree more questions, and what each changes1 min

Question	We assume	If the answer were different
Do some requests cost more than one?	No, one token each	A cost per request means tryTake(n), and n above the cap is refused
Do limits change while running?	Rarely, on deploy	Live changes mean swapping the whole rule list in one step
Exact, or roughly right?	Exact within one process	Roughly right (a few percent over) allows cheaper multi-server designs

Common mistake

Designing a system when they asked for a class

Opening with Redis clusters, gateways and replication answers the system design question, not this one. In a low-level interview the limiter is a class with a check method. Mention the multi-server version, build the class, and come back to Redis at the end.

Build it

We’ll build the design in four stages. Each stage adds only the classes that a new requirement needs. In each diagram, the new parts are outlined, and the colors show what each class does (the key is under every diagram).

Stage 1: A counter per window

Interviewerminute 4

Start simple. One limit: 10 requests per second per user.

What they are testing

Whether you can get a working limiter up in a few minutes and then find its flaw yourself. The flaw at the window edge is the one they want you to name.

Start with the smallest thing that works. Cut time into one-second windows, lined up on the clock: 12:00:00, 12:00:01, and so on. Each client has a count for its current window. A request in a new window resets the count to zero. A request that would push the count past 10 is refused.

Stage 1: a fixed window per client

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JFixedWindowLimiter.javaPyfixed_window_limiter.pyC#FixedWindowLimiter.csGofixed_window_limiter.goTSfixed-window-limiter.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Fixed window: count each client's requests in the current window, and refuse once the
// count reaches the limit. Time is injected from the start: a limiter is all about time,
// and a test that sleeps is not a test.
class FixedWindowLimiter {
    private final int limit;
    private final long windowNanos;
    private final LongSupplier clock;                    // System::nanoTime in production
    private final Map<String, Window> windows = new HashMap<>();

    // One client's current window: when it started and how many requests it has seen.
    private static final class Window {
        long start;
        int count;
    }

    FixedWindowLimiter(int limit, Duration window, LongSupplier clock) {
        this.limit = limit;
        this.windowNanos = window.toNanos();
        this.clock = clock;
    }

    boolean allow(String client) {
        long now = clock.getAsLong();
        long start = now - Math.floorMod(now, windowNanos);  // windows line up: 12:00:00, 12:00:01...
        Window w = windows.computeIfAbsent(client, k -> new Window());
        if (w.start != start) {  // a new window has begun: the old count no longer matters
            w.start = start;
            w.count = 0;
        }
        // flaw 1: a client can send `limit` requests at 12:00:00.999 and `limit` more at
        // 12:00:01.000: twice the limit in one millisecond. Stage 2.
        if (w.count >= limit) return false;
        w.count++;
        return true;
        // flaw 2: every client ever seen keeps a Window forever. Stage 4.
    }
}

It’s cheap, just two numbers per client. But it has two flaws, and we leave them in on purpose.

The first is the edge. A client can send 10 requests at 12:00:00.999, and 10 more at 12:00:01.000. Both windows are within their limit. But that’s 20 requests in one millisecond, under a “10 per second” rule. Every window edge allows twice the limit.

The second is memory. Every client ever seen keeps an entry. A scanner that uses a new IP address for every request grows the map forever. Stage 2 fixes the edge, and stage 4 fixes the memory.

Stage 2: The algorithm behind an interface

Interviewerminute 8

Fix the burst at the window edge.

What they are testing

Whether you know the standard algorithms well enough to compare them by the burst they allow and the memory they need, and pick one for a reason. Listing names without the trade-offs is the weak version.

There are five standard algorithms. They differ in two ways: how big a burst they allow, and how much they store for each client.

Algorithm	How	Biggest burst	Stored per client
Fixed window	A count per window lined up on the clock	2× the limit at an edge	2 numbers
Sliding log	Keep each request’s time; count those in the last period	Exactly the limit	One time per request
Sliding window counter	This window’s count plus the last one’s, weighted by overlap	About the limit	3 numbers
Token bucket (our pick)	Tokens refill at a steady rate up to a cap; each request takes one	The cap, then the rate	2 numbers
Leaky bucket	Requests wait in a queue and leave at a fixed rate	None; smooths everything	A queue

The token bucket is our default. Picture a bucket that holds up to 10 tokens. Tokens drip in at 10 per second, and the bucket never holds more than 10. Each request takes one token. If the bucket is empty, the request is refused.

A client that has been quiet has a full bucket, so it can send 10 requests at once. That matches real clients: loading one page often fires ten calls together. But over any span of time, the rate can’t go above the limit, and there’s no window edge to take advantage of. The bucket stores two numbers: the tokens left, and when they were last counted.

Do we need a timer that adds tokens to every bucket? No. The refill is lazy: when a bucket is used, it works out how many tokens dripped in since the last use, and adds them. A million idle buckets cost no CPU at all.

We put the algorithm behind a Bucket interface with three methods: tryTake, refund (stage 3 needs it) and retryAfter. Choosing the algorithm for a rule is then choosing which kind of bucket to create. A BucketFactory creates the bucket the first time a client is seen. This is the Strategy pattern (one interface, one class per algorithm), and the Factory pattern for creating them.

Stage 2: buckets behind an interface

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JTokenBucket.javaPyfixed_window.pyC#TokenBucket.csGotoken_bucket.goTStoken-bucket.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// "permits per period", such as 10 per second. A value, so rules can share and compare it.
record Limit(int permits, Duration per) {
    static Limit of(int permits, Duration per) { return new Limit(permits, per); }
}

// What the caller needs to answer the request: yes or no, and when to try again.
// retryAfterNanos becomes the Retry-After header on an HTTP 429.
record Decision(boolean allowed, long retryAfterNanos) {}

// One client's allowance under one limit. An interface, because token bucket and fixed
// window (and sliding window, and leaky bucket) are interchangeable answers to
// "may this key go now?".
interface Bucket {
    boolean tryTake(long now);
    void refund(long now);          // gives a permit back when a later rule says no
    long retryAfterNanos(long now); // 0 if a permit is available now
}

// Holds up to `permits` tokens and refills continuously at permits/period. Each request
// takes one. A client may burst up to the capacity, but over any long stretch the rate
// can't exceed the limit, and there is no window edge to game.
class TokenBucket implements Bucket {
    private final double capacity;
    private final double refillPerNano;
    private double tokens;
    private long updatedAt;  // when `tokens` was last brought up to date

    TokenBucket(Limit limit, long now) {
        this.capacity = limit.permits();
        this.refillPerNano = limit.permits() / (double) limit.per().toNanos();
        this.tokens = capacity;  // a new client starts with a full bucket
        this.updatedAt = now;
    }

    // Lazy refill: no timer per bucket, just catch up when the bucket is used.
    // A million idle buckets cost no CPU at all.
    private void refill(long now) {
        if (now <= updatedAt) return;  // the clock didn't move (or went backwards): nothing to add
        tokens = Math.min(capacity, tokens + (now - updatedAt) * refillPerNano);
        updatedAt = now;
    }

    public boolean tryTake(long now) {
        refill(now);
        if (tokens < 1) return false;
        tokens -= 1;
        return true;
    }

    // Gives back a permit when a later rule refused the request. Never above capacity.
    public void refund(long now) {
        refill(now);
        tokens = Math.min(capacity, tokens + 1);
    }

    public long retryAfterNanos(long now) {
        refill(now);
        return tokens >= 1 ? 0 : (long) Math.ceil((1 - tokens) / refillPerNano);
    }
}

// The fixed-window algorithm behind the same interface: count requests in each window of the
// clock, and start again at each edge. Cheaper (two numbers, no floating point), and fine for
// long periods like "1,000 per day", where a burst at midnight is acceptable.
class FixedWindow implements Bucket {
    private final int limit;
    private final long windowNanos;
    private long start;
    private int count;

    FixedWindow(Limit limit, long now) {
        this.limit = limit.permits();
        this.windowNanos = limit.per().toNanos();
        this.start = now - Math.floorMod(now, windowNanos);
    }

    // Moves to the current window once time has passed the edge, and starts the count again.
    private void roll(long now) {
        long current = now - Math.floorMod(now, windowNanos);
        if (current != start) {
            start = current;
            count = 0;
        }
    }

    public boolean tryTake(long now) {
        roll(now);
        if (count >= limit) return false;
        count++;
        return true;
    }

    public void refund(long now) {
        roll(now);
        if (count > 0) count--;  // a refund after the window rolled has nothing to give back
    }

    public long retryAfterNanos(long now) {
        roll(now);
        return count < limit ? 0 : start + windowNanos - now;
    }
}

// Creates a bucket for a key seen for the first time. TokenBucket::new and FixedWindow::new
// both fit, which is how a rule picks its algorithm.
interface BucketFactory {
    Bucket create(Limit limit, long now);
}

// One limit for every key, with the algorithm plugged in.
class RateLimiter {
    private final Limit limit;
    private final BucketFactory algorithm;
    private final LongSupplier clock;
    private final Map<String, Bucket> buckets = new HashMap<>();

    RateLimiter(Limit limit, BucketFactory algorithm, LongSupplier clock) {
        this.limit = limit;
        this.algorithm = algorithm;
        this.clock = clock;
    }

    Decision check(String key) {
        long now = clock.getAsLong();
        Bucket b = buckets.computeIfAbsent(key, k -> algorithm.create(limit, now));
        return b.tryTake(now) ? new Decision(true, 0) : new Decision(false, b.retryAfterNanos(now));
    }
}

The retry time comes straight from the arithmetic. A bucket holding 0.3 tokens needs 0.7 more. At 10 tokens per second, that’s 70 ms. We return that time, so a polite client waits exactly long enough instead of retrying again and again.

What does the token bucket cost? After a quiet spell, it allows a burst of the full cap. A backend that can’t handle 10 requests at once won’t like that. And tokens are decimals, so the code must compare with “less than 1”, never “equals 0”, and cap the count on every refill.

Common mistake

A timer that refills every bucket

A scheduled task that adds tokens to every bucket on each tick does work for every client, on every tick, forever, even clients that never come back. And it drifts when the task runs late. Working out the refill from the time passed, when the bucket is used, is exact and costs nothing while idle.

Go deeperWhen would you pick the sliding window counter instead?1 min

When the limit must hold over every span of time with no burst above it, and memory per client matters. It keeps this window’s count and the previous window’s count. Then it estimates the count over the last full period as current + previous × (the part of the previous window still in range). For example, 30% into the current window, 70% of the previous window still counts.

It assumes the previous window’s requests were spread evenly, so it can be off by a little. But it never allows the 2× burst at the edge. Cloudflare reported it within a fraction of a percent of exact on real traffic.

Go deeperA token bucket, worked by hand1 min

Take a bucket of 10 tokens that refills at 10 per second, so one token every 100 ms.

• 12:00:00.000. The client is new, so the bucket is full: 10 tokens. It sends 10 requests at once. All pass, and the bucket is at 0.
• 12:00:00.050. An 11th request. 50 ms have passed, so 0.5 tokens dripped in. 0.5 is less than 1, so it’s refused. The retry time is (1 − 0.5) ÷ 10 per second = 50 ms.
• 12:00:00.100. It retries. Another 50 ms, another 0.5 tokens: exactly 1. It passes, and the bucket is back at 0.
• 12:00:05.100. After five quiet seconds, 50 tokens have dripped in. But the cap is 10, so the bucket holds 10, not 50. That cap is what stops a long quiet spell from turning into a huge burst.

Each step used only two stored numbers (tokens and the last time) and the current time. That’s all tryTake needs.

Stage 3: Several rules per request

Interviewerminute 15

We need 10 per second per user, and also 100 per minute per IP, because one office shares an IP.

What they are testing

Whether you notice that a request refused by one rule must not use up another rule’s token, and whether buckets are kept apart per rule. A refusal that silently drains a good user’s bucket is the bug they’re looking for.

A Rule has a name, a way to get a key from a request (the user ID, or the IP address), a limit, and an algorithm. The limiter holds a list of rules, and one bucket for each rule and key pair. A request goes through the rules in order and takes a token from each bucket.

The order creates a problem. Say the user rule takes a token, and then the IP rule refuses. The user has lost a token for a request that never ran. When a shared office IP is busy, this drains the buckets of good users, again and again.

So the check is all or nothing. If any rule refuses, every token taken so far is given back (refunded). The answer carries the refusing bucket’s retry time.

Stage 3: rules, keys and refunds

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JRateLimiter.javaPyrate_limiter.pyC#RateLimiter.csGorate_limiter.goTSrate-limiter.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// What a request looks like to the limiter: who sent it, from where, to which endpoint.
record Request(String userId, String ip, String endpoint) {}

// One limit, how to key it, and which algorithm enforces it. For example
// new Rule("user/second", Request::userId, Limit.of(10, Duration.ofSeconds(1)), TokenBucket::new)
record Rule(String name, Function<Request, String> keyOf, Limit limit, BucketFactory algorithm) {}

class RateLimiter {
    private final List<Rule> rules;
    private final LongSupplier clock;
    // One bucket per (rule, key). The rule name is in the key, so "ip:1.2.3.4" under two
    // rules is two separate buckets.
    private final Map<String, Bucket> buckets = new HashMap<>();

    RateLimiter(List<Rule> rules, LongSupplier clock) {
        this.rules = List.copyOf(rules);
        this.clock = clock;
    }

    // A request must pass every rule. All or nothing: if a later rule refuses, the permits
    // taken from earlier rules are given back, so a refused request uses up nothing.
    Decision check(Request r) {
        long now = clock.getAsLong();
        List<Bucket> taken = new ArrayList<>();
        for (Rule rule : rules) {
            String key = rule.name() + "|" + rule.keyOf().apply(r);
            Bucket b = buckets.computeIfAbsent(key, k -> rule.algorithm().create(rule.limit(), now));
            if (!b.tryTake(now)) {
                for (Bucket t : taken) t.refund(now);
                return new Decision(false, b.retryAfterNanos(now));
            }
            taken.add(b);
        }
        return new Decision(true, 0);
    }
}

Here it is step by step. User bo sends a request from IP 10.0.0.1. The user bucket gives a token, and the IP bucket refuses. So the limiter refunds the user bucket, which goes back to 5 tokens, and answers “refused, retry after 600 ms”.

Sequence: refused by the second rule

Scroll or pinch to zoom, drag to pan

• Color key
• Facade

Why take and then refund, and not check every bucket first and then take? Because “check then take” needs every bucket locked at once, or another request could take the token in between. Take then refund touches one bucket at a time. The cost is a tiny moment when a token is out of a bucket for a request that will be refused. Another request for the same user, in that same microsecond, might be refused too.

Common mistake

Keying buckets by the key alone

If a user rule and an endpoint rule both key by user ID, a map keyed only by "ana" makes the two rules share one bucket, and each request takes two tokens from it. Key each bucket by its rule and the key together.

Go deeperDoes the order of the rules matter?1 min

For correctness, no: refunds make it all or nothing whatever the order. For speed, yes. Put the rule most likely to refuse first, often the strictest per-IP rule. Then a refused request touches one bucket instead of several, and has nothing to refund.

Stage 4: Forgetting idle clients

Interviewerminute 20

A crawler hits us from a million different IPs, once each. What happens to memory?

What they are testing

Whether you can find a rule for deleting state that never changes a decision. “Keep the last N clients” works but can forget an active client and give it a fresh burst.

Every first request creates a bucket, and nothing ever removes one. A million one-off IPs leave a million buckets behind.

Here is the key idea: a bucket left alone for one full period is the same as a new bucket. A token bucket idle for one period has refilled completely. A fixed window has moved on to a new window. So if we delete it, and create a fresh one on the next request, no decision changes.

Each bucket now records when it was last used. A sweep removes buckets that have been idle for at least their rule’s period. It runs once every 10,000 checks, so its cost is spread across many requests.

Stage 4: tracked buckets and a sweep

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation
• New in this step

JRateLimiter.javaPyrate_limiter.pyC#RateLimiter.csGorate_limiter.goTSrate-limiter.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// A bucket plus when its key was last seen. A bucket left alone for one full period of its
// limit is back where a new one starts (a token bucket refills completely; a fixed window
// rolls over), so dropping it changes nothing.
final class Tracked {
    final Bucket bucket;
    final long idleAfterNanos;
    long lastSeen;

    Tracked(Bucket bucket, long idleAfterNanos, long now) {
        this.bucket = bucket;
        this.idleAfterNanos = idleAfterNanos;
        this.lastSeen = now;
    }
}

class RateLimiter {
    private static final int SWEEP_EVERY = 10_000;  // checks between sweeps; amortizes the scan
    private final List<Rule> rules;
    private final LongSupplier clock;
    private final Map<String, Tracked> buckets = new HashMap<>();
    private int checksSinceSweep;

    RateLimiter(List<Rule> rules, LongSupplier clock) {
        this.rules = List.copyOf(rules);
        this.clock = clock;
    }

    Decision check(Request r) {
        long now = clock.getAsLong();
        if (++checksSinceSweep >= SWEEP_EVERY) sweep(now);
        List<Bucket> taken = new ArrayList<>();
        for (Rule rule : rules) {
            Tracked t = buckets.computeIfAbsent(rule.name() + "|" + rule.keyOf().apply(r),
                    k -> new Tracked(rule.algorithm().create(rule.limit(), now), rule.limit().per().toNanos(), now));
            t.lastSeen = now;
            if (!t.bucket.tryTake(now)) {
                for (Bucket b : taken) b.refund(now);
                return new Decision(false, t.bucket.retryAfterNanos(now));
            }
            taken.add(t.bucket);
        }
        return new Decision(true, 0);
    }

    // Forget every key idle for a full period. So memory tracks the clients active in the
    // last period, not every client ever seen: a scan of one IP per request no longer grows
    // the map forever.
    void sweep(long now) {
        buckets.values().removeIf(t -> now - t.lastSeen >= t.idleAfterNanos);
        checksSinceSweep = 0;
    }

    int trackedKeys() { return buckets.size(); }
}

Memory now follows the clients that were active in the last period. Picture a crawler sending a million requests a minute, each from a new IP, under a one-second rule. It keeps a few tens of thousands of buckets alive (about one second of new IPs, plus those since the last sweep), not a million.

What does it cost? A sweep looks at every bucket, so it’s a short pause that grows with the number of clients. And during a flood of new clients within one period, memory still has no hard cap. A map with a fixed size limit would cap memory, but it would sometimes forget an active client, and hand it a fresh burst.

Common mistake

Removing a bucket that isn't idle yet

Deleting a bucket after a shorter idle time (“five seconds” for a per-minute rule) resets the client to a full bucket too early. A client that learns the timeout can wait it out and get a new burst every time. The safe idle time is the full period of the bucket’s own rule.

This is enough for a mid-level answer. The token bucket is correct, refills lazily, and sits behind an interface. The rest of the page is what makes it a senior answer.

The full design

Here is everything together. Each class is here because a requirement needed it.

Rate limiter: full class diagram

Scroll or pinch to zoom, drag to pan

• Color key
• Facade
• Entity
• Value object
• Enum
• Interface
• Implementation

</>rate-limiter· read only

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

Explorer

• JAllInOne.java
• src
• JBucket.java
• JBucketFactory.java
• JDecision.java
• JFixedWindow.java
• JLimit.java
• JRateLimiter.java
• JRequest.java
• JRule.java
• JTokenBucket.java
• JTracked.java

JAllInOne.java

AllInOne.javasrc/Bucket.javasrc/BucketFactory.javasrc/Decision.javasrc/FixedWindow.javasrc/Limit.javasrc/RateLimiter.javasrc/Request.javasrc/Rule.javasrc/TokenBucket.javasrc/Tracked.java

AllInOne.java

// The complete design, built from every stage on this page.

import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
import java.util.function.*;
import java.time.*;

// "permits per period", such as 10 per second. A value, so rules can share and compare it.
record Limit(int permits, Duration per) {
    static Limit of(int permits, Duration per) { return new Limit(permits, per); }
}

// What the caller needs to answer the request: yes or no, and when to try again.
// retryAfterNanos becomes the Retry-After header on an HTTP 429.
record Decision(boolean allowed, long retryAfterNanos) {}

// One client's allowance under one limit. An interface, because token bucket and fixed
// window (and sliding window, and leaky bucket) are interchangeable answers to
// "may this key go now?".
interface Bucket {
    boolean tryTake(long now);
    void refund(long now);          // gives a permit back when a later rule says no
    long retryAfterNanos(long now); // 0 if a permit is available now
}

// Holds up to `permits` tokens and refills continuously at permits/period. Each request
// takes one. A client may burst up to the capacity, but over any long stretch the rate
// can't exceed the limit, and there is no window edge to game.
class TokenBucket implements Bucket {
    private final double capacity;
    private final double refillPerNano;
    private double tokens;
    private long updatedAt;  // when `tokens` was last brought up to date

    TokenBucket(Limit limit, long now) {
        this.capacity = limit.permits();
        this.refillPerNano = limit.permits() / (double) limit.per().toNanos();
        this.tokens = capacity;  // a new client starts with a full bucket
        this.updatedAt = now;
    }

    // Lazy refill: no timer per bucket, just catch up when the bucket is used.
    // A million idle buckets cost no CPU at all.
    private void refill(long now) {
        if (now <= updatedAt) return;  // the clock didn't move (or went backwards): nothing to add
        tokens = Math.min(capacity, tokens + (now - updatedAt) * refillPerNano);
        updatedAt = now;
    }

    public boolean tryTake(long now) {
        refill(now);
        if (tokens < 1) return false;
        tokens -= 1;
        return true;
    }

    // Gives back a permit when a later rule refused the request. Never above capacity.
    public void refund(long now) {
        refill(now);
        tokens = Math.min(capacity, tokens + 1);
    }

    public long retryAfterNanos(long now) {
        refill(now);
        return tokens >= 1 ? 0 : (long) Math.ceil((1 - tokens) / refillPerNano);
    }
}

// The fixed-window algorithm behind the same interface: count requests in each window of the
// clock, and start again at each edge. Cheaper (two numbers, no floating point), and fine for
// long periods like "1,000 per day", where a burst at midnight is acceptable.
class FixedWindow implements Bucket {
    private final int limit;
    private final long windowNanos;
    private long start;
    private int count;

    FixedWindow(Limit limit, long now) {
        this.limit = limit.permits();
        this.windowNanos = limit.per().toNanos();
        this.start = now - Math.floorMod(now, windowNanos);
    }

    // Moves to the current window once time has passed the edge, and starts the count again.
    private void roll(long now) {
        long current = now - Math.floorMod(now, windowNanos);
        if (current != start) {
            start = current;
            count = 0;
        }
    }

    public boolean tryTake(long now) {
        roll(now);
        if (count >= limit) return false;
        count++;
        return true;
    }

    public void refund(long now) {
        roll(now);
        if (count > 0) count--;  // a refund after the window rolled has nothing to give back
    }

    public long retryAfterNanos(long now) {
        roll(now);
        return count < limit ? 0 : start + windowNanos - now;
    }
}

// Creates a bucket for a key seen for the first time. TokenBucket::new and FixedWindow::new
// both fit, which is how a rule picks its algorithm.
interface BucketFactory {
    Bucket create(Limit limit, long now);
}

// Every rule must agree before a request goes through. Each rule has its own bucket per client,
// kept in one map under a key like "rule|client". Safe to call from many threads.
class RateLimiter {
    // The sweep runs once every 10,000 checks, so its cost is spread thin.
    private static final int SWEEP_EVERY = 10_000;
    private final List<Rule> rules;
    private final LongSupplier clock;
    // Safe to read and insert from many threads; computeIfAbsent creates each bucket once,
    // so two first requests from a new client can't each get their own full bucket.
    private final ConcurrentHashMap<String, Tracked> buckets = new ConcurrentHashMap<>();
    private final AtomicInteger checksSinceSweep = new AtomicInteger();

    RateLimiter(List<Rule> rules, LongSupplier clock) {
        this.rules = List.copyOf(rules);
        this.clock = clock;
    }

    // Each rule takes a permit from this client's bucket. On the first no, the permits taken by
    // earlier rules are given back, so a refused request costs the client nothing, and the
    // answer says when to retry.
    Decision check(Request r) {
        long now = clock.getAsLong();
        if (checksSinceSweep.incrementAndGet() >= SWEEP_EVERY) sweep(now);
        List<Tracked> taken = new ArrayList<>();
        for (Rule rule : rules) {
            Tracked t = buckets.computeIfAbsent(rule.name() + "|" + rule.keyOf().apply(r),
                    k -> new Tracked(rule.algorithm().create(rule.limit(), now), rule.limit().per().toNanos(), now));
            boolean ok;
            // One lock per bucket: refill, check and take happen as one step, and two clients
            // never wait for each other. We hold at most one bucket lock at a time, so the
            // rules can't deadlock however they overlap.
            synchronized (t) {
                t.lastSeen = now;
                ok = t.bucket.tryTake(now);
            }
            if (!ok) {
                for (Tracked p : taken) synchronized (p) { p.bucket.refund(now); }  // same lock as the take
                synchronized (t) { return new Decision(false, t.bucket.retryAfterNanos(now)); }
            }
            taken.add(t);
        }
        return new Decision(true, 0);
    }

    // Removal re-checks idleness under the bucket's lock, so a key that was just used
    // survives. A request that fetched the entry a moment before it was removed can still
    // take from the orphaned bucket: that client gets at most one extra permit, once.
    void sweep(long now) {
        checksSinceSweep.set(0);
        buckets.forEach((key, t) -> {
            synchronized (t) {
                if (now - t.lastSeen >= t.idleAfterNanos) buckets.remove(key, t);
            }
        });
    }

    // How many buckets are in memory. Tests use it to watch the sweep work.
    int trackedKeys() { return buckets.size(); }
}

// What a request looks like to the limiter: who sent it, from where, to which endpoint.
record Request(String userId, String ip, String endpoint) {}

// One limit, how to key it, and which algorithm enforces it. For example
// new Rule("user/second", Request::userId, Limit.of(10, Duration.ofSeconds(1)), TokenBucket::new)
record Rule(String name, Function<Request, String> keyOf, Limit limit, BucketFactory algorithm) {}

// A bucket plus when its key was last seen. A bucket left alone for one full period of its
// limit is back where a new one starts (a token bucket refills completely; a fixed window
// rolls over), so dropping it changes nothing.
final class Tracked {
    final Bucket bucket;
    final long idleAfterNanos;
    long lastSeen;

    Tracked(Bucket bucket, long idleAfterNanos, long now) {
        this.bucket = bucket;
        this.idleAfterNanos = idleAfterNanos;
        this.lastSeen = now;
    }
}

Read onlyJava 21Every file builds in CI11 files198 lines

Explorer

• Pyall_in_one.py
• rate_limiter
• Pybucket.py
• Pydecision.py
• Pyfixed_window.py
• Pylimit.py
• Pyrate_limiter.py
• Pyrequest.py
• Pyrule.py
• Pytoken_bucket.py
• Pytracked.py

Pyall_in_one.py

all_in_one.pyrate_limiter/bucket.pyrate_limiter/decision.pyrate_limiter/fixed_window.pyrate_limiter/limit.pyrate_limiter/rate_limiter.pyrate_limiter/request.pyrate_limiter/rule.pyrate_limiter/token_bucket.pyrate_limiter/tracked.py

all_in_one.py

Read onlyPython 3.12Every file builds in CI10 files200 lines

Explorer

• C#AllInOne.cs
• src
• C#Decision.cs
• C#FixedWindow.cs
• C#IBucket.cs
• C#Limit.cs
• C#RateLimiter.cs
• C#Request.cs
• C#Rule.cs
• C#TokenBucket.cs
• C#Tracked.cs

C#AllInOne.cs

AllInOne.cssrc/Decision.cssrc/FixedWindow.cssrc/IBucket.cssrc/Limit.cssrc/RateLimiter.cssrc/Request.cssrc/Rule.cssrc/TokenBucket.cssrc/Tracked.cs

AllInOne.cs

Read onlyC# · .NET 10Every file builds in CI10 files178 lines

Explorer

• Goall_in_one.go
• Gobucket.go
• Gobucket_factory.go
• Godecision.go
• Gofixed_window.go
• Golimit.go
• Gorate_limiter.go
• Gorequest.go
• Gorule.go
• Gotoken_bucket.go
• Gotracked.go
• Gowindow.go

Goall_in_one.go

all_in_one.gobucket.gobucket_factory.godecision.gofixed_window.golimit.gorate_limiter.gorequest.gorule.gotoken_bucket.gotracked.gowindow.go

all_in_one.go

Read onlyGo 1.24Every file builds in CI12 files250 lines

Explorer

• TSall-in-one.ts
• src
• TSbucket-factory.ts
• TSbucket.ts
• TSdecision.ts
• TSfixed-window.ts
• TSlimit.ts
• TSrate-limiter.ts
• TSredis-like.ts
• TSredis-token-bucket.ts
• TSrequest.ts
• TSrule.ts
• TStoken-bucket.ts
• TStracked.ts

TSall-in-one.ts

all-in-one.tssrc/bucket-factory.tssrc/bucket.tssrc/decision.tssrc/fixed-window.tssrc/limit.tssrc/rate-limiter.tssrc/redis-like.tssrc/redis-token-bucket.tssrc/request.tssrc/rule.tssrc/token-bucket.tssrc/tracked.ts

all-in-one.ts

Read onlyTypeScript, strictEvery file builds in CI13 files238 lines

Three ideas hold it together:

• What is limited, and how, are separate. A Rule says which key and which limit. A Bucket enforces it. Adding a sliding window touches neither the rules nor the limiter. The buckets are the Strategy pattern, and BucketFactory is the Factory pattern.
• Buckets know nothing about clocks or keys. They’re given now as an argument, so each bucket is plain arithmetic that a test can check with plain numbers.
• A decision is all or nothing. Either every rule’s bucket gave up a token, or none did. To callers, RateLimiter is a simple front door with one method, check(request) (a facade).

Stress it

The design works for one thread. But a server calls check from thousands of request threads at once. And later, from many servers.

Two threads, one last token

Interviewerminute 26

Thousands of request threads call check at once. Make it safe.

What they are testing

Whether you find both races (inside a bucket, and when a bucket is created), and lock so that two clients never wait for each other. Then whether you notice that holding several bucket locks at once can block forever.

There are two races, meaning two places where threads can interfere.

The first is inside a bucket. A bucket has one token left. Two threads refill it at the same moment, both see 1 token, and both take it. The bucket has handed out a token it didn’t have. So “refill, check, take” must run as one step that no other thread can split.

The second is in the map. A new client sends its first two requests at the same moment. Both threads look for the client’s bucket, find nothing, and each creates one. Each bucket is full, so the client gets two bursts. So “look up, or create” must also be one step.

The clearly correct fix is one global lock. check takes one lock for the whole limiter. That fixes both races. But every check, from every client, now waits in one line.

The better fix is a lock per bucket. A thread-safe map creates each bucket in one step: if two threads ask at once, both get the same bucket. Then each take and each refund runs under that bucket’s own small lock. Two different clients never wait for each other.

Option	How	Threads wait when
1. One global lock	check holds one lock	Always: one check at a time
2. Lock per bucket (our choice)	Thread-safe map; each bucket’s take under its own lock	Only when they share a bucket
3. Lock-free	Pack tokens and time into one atomic number; retry on conflict	Never, but retries under heavy use
4. Redis script	The bucket lives in Redis; a script refills and takes	One network round trip per check

JRateLimiter.javaPyrate_limiter.pyC#RateLimiter.csGorate_limiter.goTSredis-like.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

// Every rule must agree before a request goes through. Each rule has its own bucket per client,
// kept in one map under a key like "rule|client". Safe to call from many threads.
class RateLimiter {
    // The sweep runs once every 10,000 checks, so its cost is spread thin.
    private static final int SWEEP_EVERY = 10_000;
    private final List<Rule> rules;
    private final LongSupplier clock;
    // Safe to read and insert from many threads; computeIfAbsent creates each bucket once,
    // so two first requests from a new client can't each get their own full bucket.
    private final ConcurrentHashMap<String, Tracked> buckets = new ConcurrentHashMap<>();
    private final AtomicInteger checksSinceSweep = new AtomicInteger();

    RateLimiter(List<Rule> rules, LongSupplier clock) {
        this.rules = List.copyOf(rules);
        this.clock = clock;
    }

    // Each rule takes a permit from this client's bucket. On the first no, the permits taken by
    // earlier rules are given back, so a refused request costs the client nothing, and the
    // answer says when to retry.
    Decision check(Request r) {
        long now = clock.getAsLong();
        if (checksSinceSweep.incrementAndGet() >= SWEEP_EVERY) sweep(now);
        List<Tracked> taken = new ArrayList<>();
        for (Rule rule : rules) {
            Tracked t = buckets.computeIfAbsent(rule.name() + "|" + rule.keyOf().apply(r),
                    k -> new Tracked(rule.algorithm().create(rule.limit(), now), rule.limit().per().toNanos(), now));
            boolean ok;
            // One lock per bucket: refill, check and take happen as one step, and two clients
            // never wait for each other. We hold at most one bucket lock at a time, so the
            // rules can't deadlock however they overlap.
            synchronized (t) {
                t.lastSeen = now;
                ok = t.bucket.tryTake(now);
            }
            if (!ok) {
                for (Tracked p : taken) synchronized (p) { p.bucket.refund(now); }  // same lock as the take
                synchronized (t) { return new Decision(false, t.bucket.retryAfterNanos(now)); }
            }
            taken.add(t);
        }
        return new Decision(true, 0);
    }

    // Removal re-checks idleness under the bucket's lock, so a key that was just used
    // survives. A request that fetched the entry a moment before it was removed can still
    // take from the orphaned bucket: that client gets at most one extra permit, once.
    void sweep(long now) {
        checksSinceSweep.set(0);
        buckets.forEach((key, t) -> {
            synchronized (t) {
                if (now - t.lastSeen >= t.idleAfterNanos) buckets.remove(key, t);
            }
        });
    }

    // How many buckets are in memory. Tests use it to watch the sweep work.
    int trackedKeys() { return buckets.size(); }
}

Why is this correct? The map’s “get or create” step (computeIfAbsent in Java, GetOrAdd in C#, a map lock in Python and Go) means every thread gets the same bucket for a key. Each take and each refund runs under that bucket’s lock, so a bucket never gives away the same token twice.

And there’s one more rule: a thread holds at most one bucket lock at a time. It takes from one bucket, lets go of its lock, then moves to the next. Refunds also go one at a time. Why does that matter? If a thread held bucket A’s lock and waited for B’s, while another thread held B and waited for A, both would wait forever. That’s called a deadlock. With only one lock held at a time, it can’t happen.

What does it cost? A very busy client, say 50,000 requests a second, makes its threads queue on its one bucket lock. A lock-free version avoids that, but it’s harder to get right, and it retries a lot in exactly that busy case.

Common mistake

Locking every rule's bucket before taking

Taking all the locks first, then checking, then taking, sounds safe. But if one request locks rule A’s bucket before rule B’s, and another request locks them in the other order, each can hold one lock and wait for the other forever. Take, let go, refund on failure: one lock at a time.

Go deeperThe sweep, while requests are running1 min

The sweep is the delicate part. It checks again that a bucket is idle while holding that bucket’s lock. And it removes the map entry only if the entry is still that same bucket.

There’s still one small gap. A request may fetch a bucket just before the sweep removes it. That request takes from the removed bucket, and the next request creates a new, full one. The worst case is one extra token for that client, once. That’s acceptable for a limiter. Making it exact would need the map’s lock on every check, which is a big cost for a tiny gain.

Go deeperHow each language does the locking1 min

Java uses a ConcurrentHashMap and a lock per bucket. Python and Go use one lock for the map and one per bucket. C# uses ConcurrentDictionary and the Lock type.

TypeScript in one Node process has no thread race, since each check runs to the end before the next starts. So its stage 5 solves the race Node does have: many copies of the service behind a load balancer, each counting only its own traffic. The bucket moves into Redis. A small Lua script does the refill and take as one step, because Redis runs a script without mixing it with other commands.

Go deeperTwenty servers, one limit2 min

Say the service runs on 20 servers, and each one enforces 10 per second. The real limit is 200 per second per user, because each server only sees its own requests. There are three common fixes:

• Divide the limit by the number of servers. Each server allows 0.5 per second. It’s cheap, but it’s wrong when traffic is uneven, or when servers are added and removed.
• Sticky routing. The load balancer always sends a user to the same server. It works until that server goes down, or one server gets all the busy users.
• A shared store. The buckets move into Redis, and every server checks the same bucket. This is the usual answer. Our Bucket interface stays the same; only where the numbers live changes.

The shared store costs one network round trip per check, and adds something that can fail. So decide in advance what happens when Redis is down. For most APIs, fail open: let requests through, since a short time without limits is better than an outage. For login attempts, fail closed: refuse, since password guessing is exactly what the limit stops.

How you’d prove it works

Each test protects one promise:

• The fixed window really does let twice the limit through at an edge. Writing this test shows the flaw instead of just claiming it.
• The token bucket refills at exactly the limit’s rate, and reports the right retry time.
• A request refused by one rule leaves every other rule’s bucket untouched.
• Idle clients are forgotten after one full period.
• Under 16 threads, exactly the limit gets through.

The thread test freezes the clock, so no tokens drip in. It sends 1,000 requests from 16 threads at a bucket of 100 tokens. Exactly 100 must be allowed. More than 100 means a token was taken twice, or the client got two buckets. Freezing time is what makes an exact check possible.

Go deeperThe tests in five languages2 min

JMain.javaPytest_clock.pyC#Program.csGotest_clock.goTSexample.ts

JavaPythonC#GoTypeScript

JavaPythonC#GoTypeScript

static final Duration SECOND = Duration.ofSeconds(1);
long now = 0;                         // the test's clock, in nanoseconds
LongSupplier clock = () -> now;

Rule perUser(int permits, BucketFactory algorithm) {
    return new Rule("user", Request::userId, Limit.of(permits, SECOND), algorithm);
}

Request from(String user) { return new Request(user, "10.0.0.1", "/api"); }

@Test
void fixedWindowLetsTwiceTheLimitThroughAtTheEdge() {
    RateLimiter rl = new RateLimiter(List.of(perUser(10, FixedWindow::new)), clock);
    now = SECOND.toNanos() - 1_000_000;   // 1 ms before the window ends
    for (int i = 0; i < 10; i++) assertTrue(rl.check(from("ana")).allowed());
    now = SECOND.toNanos();               // the next window
    for (int i = 0; i < 10; i++) assertTrue(rl.check(from("ana")).allowed());
    // 20 requests in 1 ms under a "10 per second" limit: the flaw the token bucket fixes.
}

@Test
void tokenBucketRefillsAtTheLimitRateAndSaysWhenToRetry() {
    RateLimiter rl = new RateLimiter(List.of(perUser(10, TokenBucket::new)), clock);
    for (int i = 0; i < 10; i++) assertTrue(rl.check(from("ana")).allowed());  // the burst
    Decision d = rl.check(from("ana"));
    assertFalse(d.allowed());
    assertEquals(100_000_000L, d.retryAfterNanos());  // one token every 100 ms
    now += 100_000_000L;
    assertTrue(rl.check(from("ana")).allowed());
}

@Test
void aRefusedRequestUsesUpNoOtherLimit() {
    // 5 per second per user, and 1 per second per IP. Bo is refused by the IP rule...
    Rule perIp = new Rule("ip", Request::ip, Limit.of(1, SECOND), TokenBucket::new);
    RateLimiter rl = new RateLimiter(List.of(perUser(5, TokenBucket::new), perIp), clock);
    assertTrue(rl.check(new Request("ana", "10.0.0.1", "/")).allowed());
    for (int i = 0; i < 5; i++) assertFalse(rl.check(new Request("bo", "10.0.0.1", "/")).allowed());
    // ...so his user bucket was refunded every time and is still full on a new IP.
    for (int i = 0; i < 5; i++) assertTrue(rl.check(new Request("bo", "10.0.0." + (i + 2), "/")).allowed());
}

@Test
void concurrentRequestsNeverExceedTheLimit() throws Exception {
    // 100 permits, 16 threads, 1,000 requests at one frozen instant: exactly 100 may pass.
    RateLimiter rl = new RateLimiter(List.of(perUser(100, TokenBucket::new)), clock);
    ExecutorService pool = Executors.newFixedThreadPool(16);
    CountDownLatch start = new CountDownLatch(1);
    List<Future<Boolean>> results = new ArrayList<>();
    for (int i = 0; i < 1_000; i++) {
        results.add(pool.submit(() -> { start.await(); return rl.check(from("ana")).allowed(); }));
    }
    start.countDown();
    int allowed = 0;
    for (var f : results) if (f.get()) allowed++;
    pool.shutdown();
    assertEquals(100, allowed);
}

@Test
void idleKeysAreForgottenAfterOneFullPeriod() {
    RateLimiter rl = new RateLimiter(List.of(perUser(10, TokenBucket::new)), clock);
    for (int i = 0; i < 1_000; i++) rl.check(from("user-" + i));  // a scan: one request per user
    now += SECOND.toNanos();                                      // one full period later
    rl.sweep(now);
    assertEquals(0, rl.trackedKeys());                            // nothing kept for them
}

Go deeperEvery edge case, and where it is handled2 min

Case	What happens	Where
First request from a new client	A full bucket is created in one step	computeIfAbsent
Clock goes backwards	Refill ignores it; no tokens added or removed	refill check
Long idle, then a burst	Tokens capped at the bucket’s size, never more	refill
Refused by the second rule	The first rule’s token refunded	check
Refund after the window moved on	Fixed window: nothing to refund; the count stays at 0	FixedWindow.refund
Refund would go over the cap	Capped at the bucket’s size	TokenBucket.refund
Limit with 0 tokens	Should be rejected up front (left out of the stage code)	Limit
Bucket swept while a request holds it	At most one extra token for that client	sweep
Redis down (many servers)	Fail open for most APIs; fail closed for login attempts	the caller’s policy

Wrap up

The decisions, and what each one costs

Decision	We chose	We gave up
Algorithm	Token bucket by default, behind a Bucket interface	A perfectly smooth rate: bursts up to the cap
Refill	Lazy, from the time passed, when used	Nothing; idle buckets cost no CPU
Several rules	Take from each, refund all on any refusal	A microsecond where a token is out for nothing
Bucket identity	Keyed by rule and key together	A little more memory for repeated keys
Memory	Sweep buckets idle for one full period	A short pause; no hard cap during a flood
Thread safety	Thread-safe map, lock per bucket, one lock at a time	A very busy client queues on its one lock
Many servers	Buckets in Redis with a Lua script	A round trip per check and a new way to fail

Go deeperGenuinely different designs, and when to pick them2 min

Leaky bucket as a queue. Requests go into a queue with a size limit, and a worker releases them at a fixed rate. Nothing is refused until the queue is full, and the backend sees a perfectly smooth rate. It suits calls you make to a partner’s API with a strict limit. It doesn’t suit protecting your own API, because a waiting request holds a connection open.

GCRA (generic cell rate algorithm). A token bucket stored as a single time: when the next request is allowed. A check compares now with that time and moves it forward. One number per client and one atomic update, which is why some Redis modules and API gateways use it.

Limiting requests in progress, not per second. Limit how many requests a client has running at once, with a counter per client. It protects a backend whose cost is time spent, not requests started, and it adjusts on its own when the backend slows down.

How to spend 45 minutes

• 0 to 3. The key, bursts, one process or many, how many clients.
• 3 to 5. The promises. Name “never more than the limit, at an edge or under threads” as the hard one.
• 5 to 25. The fixed window and its edge, the algorithm table and the token bucket (code it fully), several rules with refunds, then the sweep.
• 25 to 27. Walk through the full diagram: rules say what, buckets say how.
• 27 to 36. The two races, a lock per bucket, one lock at a time, then many servers.
• 36 to 45. One extension, usually tiers or cost per request, then your own questions.

If time is short, describe the sweep in a sentence. Always code the token bucket completely. It’s the part that gets checked line by line.

Follow-up questions

Interviewerminute 37

Premium users get 100 per second. Some endpoints cost 10 tokens each.

What they are testing

Whether each change lands in one place: the rule picks the limit, the bucket takes n tokens. And whether you spot the new edge case: a request that costs more than the bucket can ever hold.

Most extensions fit into one place:

Extension	What changes	Touches the limiter?
Sliding window counter	A new Bucket	No
Limits per tier	Rule.limitFor(request) instead of one Limit	One line
Requests costing n tokens	tryTake(now, n); refuse outright when n is above the cap	One argument
Different limits per endpoint	A rule whose key includes the endpoint	No
Metrics (refusals per rule)	A counter where check refuses, labelled by rule name	One line
Many servers	Buckets in Redis behind the same Bucket idea	The storage

Go deeperAdding tiers and request costs, step by step2 min

Start with tiers. Premium users get 100 per second, everyone else 10. Where should that decision live? Not in the bucket: a bucket only knows its cap and its rate. And not in the limiter, which only walks the rules. It belongs in the rule, because the rule already reads the request.

1. The rule picks the limit. Rule gets a method limitFor(request). For the user rule, it looks at the user’s tier and returns 10 or 100.
2. The bucket is created with that limit. When a user is seen for the first time, the factory builds their bucket with their own limit. After that, nothing else changes.
3. What if a user upgrades? Their old bucket still has the old limit. The simplest answer: put the tier in the bucket’s key, like ana:premium. The upgrade creates a new bucket, and the old one is swept when it goes idle.

Now costs. A search costs 10 tokens, a simple read costs 1.

1. Take n tokens. tryTake(now) becomes tryTake(now, n). The refill is the same. The check becomes “do I have at least n?”, and the retry time is “how long until I have n?”.
2. Refund n tokens. If a later rule refuses, the refund gives back the same n.
3. Refuse what can never pass. If a request costs 20 tokens and the bucket holds at most 10, waiting will never help. Refuse it with a clear error, not a retry time, or the client will retry forever.

Go deeperThree more follow-up questions2 min

Interviewer asksShould a refused request return 429 or 503?

429 Too Many Requests, with a Retry-After header from the decision: the client caused it and can fix it by waiting. 503 means the server is overloaded whoever is calling, which is load shedding, a different tool. Many APIs also return RateLimit-Remaining and RateLimit-Reset on every response, so clients can slow down before they’re refused.

Interviewer asksA client retries immediately every time it's refused. What happens?

Each retry is refused and takes no token. But it still costs a check and a network round trip. If it’s abusive, add a penalty rule: refusals themselves count against a slower, longer limit, and a client over that is blocked for minutes.

Interviewer asksHow do you limit by user before you know who the user is?

In many systems, login is checked after the limiter. So the first rule keys by IP, which is known as soon as the request arrives, and it protects the login endpoint itself. Once the user is known, the per-user rules apply. Login attempts get their own strict rule, keyed by the username being tried, to slow down password guessing from many IPs.

Further reading

• Strategy pattern, Factory pattern
• Thread safety basics, Rate limiting
• Design a distributed rate limiter, the system design version of this question
• Design an LRU cache, which also keeps per-key state that must be evicted
• Cloudflare: How we built rate limiting capable of scaling to millions of domains, the sliding window counter in production
• Stripe: Scaling your API with rate limiters, four kinds of limiters and why each exists
• Redis: Scripting with Lua, why a script runs as one step