Design a Rate Limiter, Low Level Design (LLD) Interview
A rate limiter that runs inside one program. Three methods sit behind one interface. Each user gets their own limiter on first use. Limits depend on the user's plan. And a test clock lets you check the timing exactly.
Where it shows up
One of the most searched LLD problems in India. It is a common machine-coding question at Amazon, Flipkart, Uber, PhonePe, Razorpay and Atlassian. The system design version shares limits across many servers. That one is on a separate Rate Limiter system design page.
Why this is asked
It is small enough to write fully in one round. And it tests three things at once. First, can you put several methods behind one clean interface, and pick one by setting? Second, do you know how the methods differ? The big one is the burst a fixed window lets through at its edge. Third, can you make it safe with many threads, without one global lock that slows every request? A candidate who also makes time easy to control in tests stands out.
Requirements
Functional
- For each request, decide if a user may go ahead: allow(clientId) returns true or false.
- Limits are per user. One user's use never affects another user.
- Plans get different limits. For example, FREE gets 5 requests a second and PRO gets 50.
- Support several methods, picked by setting: token bucket, fixed window and sliding window log.
- A user's limiter is made the first time that user is seen.
Constraints & non-functional
- Thread safe: many threads can call allow for the same user at once, and the limit still holds exactly.
- No single global lock. Requests from different users must not wait for each other.
- Time comes from a Clock passed in. So tests can move time forward without sleeping.
- New methods can be added without changing the service.
- This runs on one server. Sharing limits across servers is the system design question, not this one.
Core classes & entities
RateLimiterService
The way in. It keeps one Limiter per user in a thread-safe map. It makes the Limiter on first use, with the rule for the user's plan. Then it asks it whether to allow the request.
attrs: perClient: ConcurrentHashMap<String, Limiter>, rules: Map<Tier, Rule>, algorithm: Algorithm, clock: Clock
methods: allow(clientId, tier): boolean
Limiter
The interface every method uses for one user. It answers one question: may this request go ahead?
methods: tryAcquire(): boolean
TokenBucket
Holds up to limit tokens and refills them steadily. Each request spends one token. It allows short bursts, then a steady rate.
attrs: capacity, refillPerMs, tokens, last
methods: tryAcquire()
FixedWindow
Counts requests in windows set by the clock, like each second. The count resets when a new window starts. It is simple and cheap. But it allows up to double the limit across a window edge.
attrs: windowStart, count, rule
methods: tryAcquire()
SlidingWindowLog
Keeps the times of recent allowed requests. It allows a new one only if fewer than limit happened in the last window. It is exact, but it uses memory for every request.
attrs: log: Deque<Long>, rule
methods: tryAcquire()
LimiterFactory
Makes the right Limiter for the chosen method. So the service never names a real class.
methods: create(algorithm, rule, clock): Limiter
Rule
A limit and the window it covers. For example, 5 requests per 1,000 ms.
attrs: limit, windowMillis
Clock
Gives the current time. SystemClock is used in real use. FakeClock is used in tests, so time can be moved forward exactly.
methods: nowMillis(): long
Relationships
- RateLimiterService → composition → Limiter. One limiter per user, owned by the service.
- Limiter → implements → TokenBucket. One class per method.
- Limiter → implements → FixedWindow. One class per method.
- Limiter → implements → SlidingWindowLog. One class per method.
- RateLimiterService → association → LimiterFactory. Used to make a limiter on a user's first request.
- RateLimiterService → aggregation → Rule. One rule per plan, set in the settings.
- TokenBucket → association → Clock. Every method reads time only through the clock it was given.
Design patterns used
Strategy in Limiter with TokenBucket, FixedWindow and SlidingWindowLog
The method is the part that changes. The service works the same with any of them.
Factory in LimiterFactory.create
It picks the method from a setting. The service never names a real class.
Passing time in in Clock, with SystemClock and FakeClock
Rate limiting is all about time. Passing the clock in makes every behaviour testable, exactly and instantly, with no sleeping.
Made on first use, per key in ConcurrentHashMap.computeIfAbsent
A limiter is made only for users who send requests. computeIfAbsent makes sure two first requests from one user never make two limiters.
Enums
Key API / methods
boolean allow(String clientId, Tier tier)True if the user may make this request now. It makes the user's limiter on first use, with the rule for their plan.
boolean Limiter.tryAcquire()Each method has its own version for one user. It locks only that user's limiter. So different users never block each other.
Limiter LimiterFactory.create(Algorithm a, Rule r, Clock c)Builds the chosen method with its rule and clock.
Code skeleton
import java.util.*;
import java.util.concurrent.*;
import java.util.concurrent.atomic.*;
// ---------- Enums ----------
enum Algorithm { TOKEN_BUCKET, FIXED_WINDOW, SLIDING_WINDOW_LOG }
enum Tier { FREE, PRO }
// ---------- Time is injected, so the limiter can be tested without sleeping ----------
interface Clock { long nowMillis(); }
final class SystemClock implements Clock { public long nowMillis() { return System.currentTimeMillis(); } }
final class FakeClock implements Clock {
private final AtomicLong t = new AtomicLong();
public long nowMillis() { return t.get(); }
void advance(long ms) { t.addAndGet(ms); }
}
// ---------- A rule: how many requests per how long ----------
record Rule(int limit, long windowMillis) {}
// ---------- The algorithm for ONE client. Each implementation guards its own state. ----------
interface Limiter { boolean tryAcquire(); }
final class TokenBucket implements Limiter {
private final int capacity; private final double refillPerMs; private final Clock clock;
private double tokens; private long last;
TokenBucket(Rule r, Clock c) {
capacity = r.limit(); refillPerMs = (double) r.limit() / r.windowMillis(); clock = c;
tokens = capacity; last = c.nowMillis();
}
public synchronized boolean tryAcquire() {
long now = clock.nowMillis();
tokens = Math.min(capacity, tokens + (now - last) * refillPerMs); // refill for the time that passed
last = now;
if (tokens >= 1) { tokens -= 1; return true; }
return false;
}
}
final class FixedWindow implements Limiter {
// Windows are aligned to the clock (0-1000 ms, 1000-2000 ms, ...), the usual fixed-window scheme.
private final Rule rule; private final Clock clock; private long windowStart = -1; private int count;
FixedWindow(Rule r, Clock c) { rule = r; clock = c; }
public synchronized boolean tryAcquire() {
long now = clock.nowMillis();
long start = now - now % rule.windowMillis();
if (start != windowStart) { windowStart = start; count = 0; } // a new window: forget the old count
if (count < rule.limit()) { count++; return true; }
return false;
}
}
final class SlidingWindowLog implements Limiter {
private final Rule rule; private final Clock clock; private final Deque<Long> log = new ArrayDeque<>();
SlidingWindowLog(Rule r, Clock c) { rule = r; clock = c; }
public synchronized boolean tryAcquire() {
long now = clock.nowMillis();
while (!log.isEmpty() && now - log.peekFirst() >= rule.windowMillis()) log.pollFirst(); // forget old requests
if (log.size() < rule.limit()) { log.addLast(now); return true; }
return false;
}
}
final class LimiterFactory {
static Limiter create(Algorithm a, Rule r, Clock c) {
return switch (a) {
case TOKEN_BUCKET -> new TokenBucket(r, c);
case FIXED_WINDOW -> new FixedWindow(r, c);
case SLIDING_WINDOW_LOG -> new SlidingWindowLog(r, c);
};
}
}
// ---------- The service: one limiter per client, created on first use ----------
final class RateLimiterService {
private final Map<Tier, Rule> rules; private final Algorithm algorithm; private final Clock clock;
private final ConcurrentHashMap<String, Limiter> perClient = new ConcurrentHashMap<>();
RateLimiterService(Algorithm a, Map<Tier, Rule> rules, Clock c) { this.algorithm = a; this.rules = rules; this.clock = c; }
boolean allow(String clientId, Tier tier) {
// computeIfAbsent is atomic: two first requests from one client cannot create two limiters
return perClient.computeIfAbsent(clientId, id -> LimiterFactory.create(algorithm, rules.get(tier), clock)).tryAcquire();
}
}
// ---------- Demo: every behaviour is checked ----------
public class RateLimiterDemo {
public static void main(String[] args) throws Exception {
Map<Tier, Rule> rules = Map.of(Tier.FREE, new Rule(5, 1_000), Tier.PRO, new Rule(50, 1_000));
FakeClock clock = new FakeClock();
RateLimiterService tb = new RateLimiterService(Algorithm.TOKEN_BUCKET, rules, clock);
check(count(tb, "alice", Tier.FREE, 10) == 5, "token bucket: a burst of 10 lets 5 through (bucket size 5)");
clock.advance(200);
check(count(tb, "alice", Tier.FREE, 10) == 1, "token bucket: 200 ms later exactly 1 token has refilled (5 per 1000 ms)");
check(count(tb, "bob", Tier.FREE, 10) == 5, "per client: bob has his own bucket, alice's use does not affect him");
check(count(tb, "carol", Tier.PRO, 60) == 50, "per tier: a PRO client gets 50");
FakeClock c2 = new FakeClock(); c2.advance(1_990); // t=1990, the last 10 ms of window [1000,2000)
RateLimiterService fw = new RateLimiterService(Algorithm.FIXED_WINDOW, rules, c2);
int endOfWindow = count(fw, "dave", Tier.FREE, 5);
c2.advance(20); // t=2010, window [2000,3000) has started
int startOfNext = count(fw, "dave", Tier.FREE, 5);
check(endOfWindow + startOfNext == 10, "fixed window: 10 requests pass within 20 ms across a window edge, double the limit");
FakeClock c3 = new FakeClock(); c3.advance(1_990); // the same two bursts, 20 ms apart
RateLimiterService sw = new RateLimiterService(Algorithm.SLIDING_WINDOW_LOG, rules, c3);
int a = count(sw, "erin", Tier.FREE, 5);
c3.advance(20);
int b = count(sw, "erin", Tier.FREE, 5);
check(a + b == 5, "sliding window log: the same edge burst is held to 5, the true limit");
RateLimiterService conc = new RateLimiterService(Algorithm.TOKEN_BUCKET, rules, new FakeClock());
ExecutorService pool = Executors.newFixedThreadPool(16);
AtomicInteger allowed = new AtomicInteger();
List<Callable<Void>> jobs = new ArrayList<>();
for (int i = 0; i < 1_000; i++) jobs.add(() -> { if (conc.allow("frank", Tier.PRO)) allowed.incrementAndGet(); return null; });
pool.invokeAll(jobs); pool.shutdown();
check(allowed.get() == 50, "concurrency: 1,000 requests from 16 threads at one instant, exactly 50 allowed");
}
static int count(RateLimiterService s, String id, Tier t, int n) { int ok = 0; for (int i = 0; i < n; i++) if (s.allow(id, t)) ok++; return ok; }
static void check(boolean ok, String what) { System.out.println((ok ? " ok " : " FAIL ") + what); if (!ok) System.exit(1); }
}
/* Output of this exact program (javac + java 21, 2026-09-25):
* ok token bucket: a burst of 10 lets 5 through (bucket size 5)
* ok token bucket: 200 ms later exactly 1 token has refilled (5 per 1000 ms)
* ok per client: bob has his own bucket, alice's use does not affect him
* ok per tier: a PRO client gets 50
* ok fixed window: 10 requests pass within 20 ms across a window edge, double the limit
* ok sliding window log: the same edge burst is held to 5, the true limit
* ok concurrency: 1,000 requests from 16 threads at one instant, exactly 50 allowed
*/How it works
Start from the interface, because everything hangs off it. allow(clientId, tier) returns true or false. Behind it, the service keeps one Limiter per user in a ConcurrentHashMap. It makes the Limiter the first time a user is seen, with the rule for that user's plan. computeIfAbsent makes this safe. Two first requests at the same moment cannot make two limiters for one user.
The method is a Strategy behind the Limiter interface. Here are the three methods. A token bucket holds up to limit tokens and refills them steadily. It spends one token per request. It allows short bursts, then a steady rate. It needs only two numbers per user. A fixed window counts requests in windows set by the clock, and resets at each edge. It is the simplest. But a user can send a full limit at the end of one window. Then they can send another at the start of the next. A sliding window log remembers the time of each allowed request. It allows a new one only if fewer than limit happened in the last window. It is exact, but it stores a time for every request.
The program shows this difference instead of just claiming it. The limit is 5 a second. It sends 5 requests 10 ms before a window edge, and 5 more 10 ms after. The fixed window lets all 10 through, double the limit. The sliding window log lets 5 through.
Threads are handled per user. Each limiter's tryAcquire locks only that one limiter. So requests from different users never wait for each other. Requests from the same user are handled one at a time. The program sends 1,000 requests for one PRO user, from 16 threads at once. It checks that exactly 50 are allowed.
Time comes from a Clock interface. In real use it is the system clock. In tests it is a FakeClock that the test moves forward by exact amounts. That is why every behaviour above can be checked exactly. Take the token refill as an example. The bucket is empty and the rate is 5 a second. 200 ms later, exactly one more request is allowed.
The interviewer may ask how this works across many servers. That is the system design version of the question. The per-user state moves to a shared store like Redis. The check and the update must happen in one step there. The Rate Limiter system design page covers it.
Edge cases & gotchas
- A burst right at a fixed window edge. 5 requests come at the end of one window. 5 more come at the start of the next. All 10 pass within 20 ms. That is double the limit. The program measures this. It also shows the sliding window log holding the same burst to 5.
- Two first requests from one user at the same moment. computeIfAbsent makes exactly one limiter, so the user never gets two buckets.
- Many threads for one user at once. Each limiter locks itself. So 1,000 requests at once allow exactly 50 on a limit of 50.
- A user who was quiet for a long time. The token bucket refills only up to its size. So an hour of silence does not allow an hour of requests at once.
- Memory. A sliding window log stores one time per allowed request, so a high limit uses a lot of memory. A token bucket stores two numbers per user.
- Users who never come back. A real version would remove idle limiters, so the map does not grow forever.
- The clock goes backwards, for example after a system time change. Use a steady clock in real use. This is another reason time sits behind an interface.