SyntaxPilot
Courses/Low-Level Design/Lesson 68
Video coming soonThis lesson’s video is being made

Start with the notes below; the video appears here as soon as it is on YouTube.

Low-Level Design · Lesson 68 of 90

Design a rate limiter

rate limitingtoken bucketleaky bucketfixed window countersliding window logsliding window counterper-user and per-API limitsRateLimiter interfacestrategy per algorithmthread-safe countersclock injection for tests

These are the notes for Low-Level Design (LLD) episode 68: designing a rate limiter, the code that says "slow down, you've asked too many times". It's a favourite interview question because there are five classic algorithms, each with a trade-off. We make the design testable with clock injection, then build the fixed window counter, sliding window log, sliding window counter, token bucket and leaky bucket, put them behind a RateLimiter interface (a Strategy per algorithm) with per-user and per-API limits, and make the counters thread-safe.

How the code was run: every program was saved as Main.java in a fresh folder and run with javac Main.java && java -cp . Main on OpenJDK 21. Every output below is the real output, pasted exactly. The users (Asha, Ravi), APIs and limits are made up for teaching.

1. The problem: the sweet shop on Diwali morning

At the sweet shop In software
500 people arrive at the door at once A flood of requests to an API
Everyone pushes in; the counter jams The server is overloaded; everyone's requests fail or crawl
A guard lets in only 5 people a minute Rate limiting: a limit on requests per unit of time
One big family can't take all 5 places Per-user limits: everyone gets a fair share

2. What rate limiting is

  • Request: one call from a client (an app, a browser, a bot) to a server.
  • API (application programming interface): a door into a server that programs call, e.g. /login, /search, /otp.
  • Rate: how many requests arrive in some time, e.g. 5 a minute.
  • Rate limiting: refusing requests above an allowed rate.
  • Why: protect the server from floods, stop someone guessing a 6-digit OTP by trying a million codes, and give every user a fair share.
  • On the web, a refused request gets HTTP 429 Too Many Requests (defined in RFC 6585, section 4), and the server may add a Retry-After header saying how long to wait before trying again (MDN: 429 Too Many Requests).
  • Our core method: boolean tryAcquire(): true = go ahead, false = refused.

3. Clock injection: testing time without waiting

If the limiter calls System.currentTimeMillis() inside, a test of "5 a minute" must wait a real minute, and can't choose the moment.

  • Clock: an interface with one method, long millis(), the current time in milliseconds.
  • Clock injection: the limiter receives a Clock in its constructor instead of asking the system. This is dependency injection (episode 16) applied to time.
  • Production passes a real clock (System.currentTimeMillis()); tests pass a FakeClock whose time is set by hand.

4. Fixed window counter

Divide time into fixed windows (10:00, 10:01, ...). Count requests in the current window; reset the count when a new window starts.

interface Clock { long millis(); }                       // where "now" comes from
class FakeClock implements Clock {                      // a clock a test can move by hand
    private long now = 0;
    public long millis() { return now; }
    void set(long hh, long mm, long ss) { now = ((hh * 60 + mm) * 60 + ss) * 1000; }
}
class FixedWindowLimiter {                              // at most `limit` requests per window
    private final int limit;  private final long windowMs;  private final Clock clock;
    private long window = -1;  private int count = 0;
    FixedWindowLimiter(int limit, long windowMs, Clock clock) {
        this.limit = limit;  this.windowMs = windowMs;  this.clock = clock; }
    boolean tryAcquire() {
        long w = clock.millis() / windowMs;              // which window are we in? 10:00, 10:01, ...
        if (w != window) { window = w;  count = 0; }     // a new window: the counter starts again
        if (count < limit) { count++;  return true; }
        return false; }
}
public class Main {
    public static void main(String[] args) {
        FakeClock clock = new FakeClock();
        FixedWindowLimiter otp = new FixedWindowLimiter(5, 60_000, clock);   // OTP: 5 per minute
        int allowed = 0;
        clock.set(10, 0, 59);  for (int i = 0; i < 5; i++) if (otp.tryAcquire()) allowed++;
        clock.set(10, 1, 0);   for (int i = 0; i < 5; i++) if (otp.tryAcquire()) allowed++;
        System.out.println("10:00:59 and 10:01:00: " + allowed + " allowed in 1 second (limit 5 a minute)");
        clock.set(10, 1, 30);  System.out.println("10:01:30, one more: " + otp.tryAcquire());
    }
}

Real output:

10:00:59 and 10:01:00: 10 allowed in 1 second (limit 5 a minute)
10:01:30, one more: false

10 allowed in 1 second with a limit of 5 a minute: the last 5 of one window and the first 5 of the next sit side by side. This is the boundary burst: fixed windows all reset at the same moment, so up to 2 × limit fit around an edge.

5. Sliding windows: the log and the counter

A sliding window always looks at the last 60 seconds counted back from now, so there is no edge to squeeze through.

  • Sliding window log: keep the time of every allowed request in a queue (a Deque). On each request, drop times older than the window; allow if fewer than limit remain. Exact, but memory grows with the limit.
  • Sliding window counter: keep only this window's count (curr) and the last window's (prev). If we are a quarter of the way into this window, three quarters of the last window still overlap the last 60 seconds, so estimate prev × 0.75 + curr. Two numbers, an estimate that assumes the last window's requests were spread evenly.
import java.util.*;
interface Clock { long millis(); }
class FakeClock implements Clock { long now;  public long millis() { return now; } }
class SlidingLog {                              // remembers the time of every allowed request
    final int limit;  final long win;  final Clock clock;  final Deque<Long> times = new ArrayDeque<>();
    SlidingLog(int limit, long win, Clock c) { this.limit = limit;  this.win = win;  clock = c; }
    boolean tryAcquire() {  long now = clock.millis();
        while (!times.isEmpty() && times.peekFirst() <= now - win) times.pollFirst();   // older: forget
        if (times.size() < limit) { times.addLast(now);  return true; }
        return false; } }
class SlidingCounter {                          // only two counters: this window and the last one
    final int limit;  final long win;  final Clock clock;  long window = 0;  int curr = 0, prev = 0;
    SlidingCounter(int limit, long win, Clock c) { this.limit = limit;  this.win = win;  clock = c; }
    boolean tryAcquire() {  long now = clock.millis(), w = now / win;
        if (w != window) { prev = (w == window + 1) ? curr : 0;  curr = 0;  window = w; }
        double overlap = 1.0 - (double) (now % win) / win;      // how much of the last window still counts
        if (prev * overlap + curr < limit) { curr++;  return true; }
        return false; } }
public class Main { public static void main(String[] args) {
    FakeClock clock = new FakeClock();
    SlidingLog log = new SlidingLog(5, 60_000, clock);
    SlidingCounter counter = new SlidingCounter(5, 60_000, clock);
    for (long t : new long[]{59_000, 60_000, 90_000, 119_000, 125_000}) {    // seconds 59, 60, 90, ...
        clock.now = t;  int a = 0, b = 0;
        for (int i = 0; i < 5; i++) { if (log.tryAcquire()) a++;  if (counter.tryAcquire()) b++; }
        System.out.printf("t=%3d s: 5 tries -> log %d allowed, counter %d allowed%n", t / 1000, a, b); }
    System.out.println("the log keeps " + log.times.size() + " timestamps; the counter keeps 2 numbers"); } }

Real output:

t= 59 s: 5 tries -> log 5 allowed, counter 5 allowed
t= 60 s: 5 tries -> log 0 allowed, counter 0 allowed
t= 90 s: 5 tries -> log 0 allowed, counter 3 allowed
t=119 s: 5 tries -> log 5 allowed, counter 2 allowed
t=125 s: 5 tries -> log 0 allowed, counter 1 allowed
the log keeps 5 timestamps; the counter keeps 2 numbers
Time Log (exact) Counter (estimate) Why
59 s 5 5 Fresh
60 s 0 0 The burst at 59 s is still inside the last 60 s: no boundary burst
90 s 0 3 Counter: 5 × 0.5 + curr < 5 allows 3
119 s 5 2 Log: the 59 s requests are now 60 s old; counter: window 2 already has 3
125 s 0 1 Log: 5 from 119 s; counter: 5 × 0.92 + 0 < 5 allows 1

The memory bill: with 1,000 a minute and 1,000,000 users, the log could hold 1,000,000,000 timestamps; the counter holds 2 numbers per user.

6. Token bucket and leaky bucket

Real life Algorithm
A bowl at the door holds 5 entry tokens; you take one to enter Token bucket: capacity = 5 tokens, each request spends one
One new token every second, never more than 5 Refill rate
A clay matka with a small tap: pour fast, it drips out at one speed Leaky bucket: requests wait in a queue and are served at a fixed rate
The matka is full: extra water spills A full queue: the request is refused
  • Token bucket: allows short bursts (up to the capacity) and an average rate (the refill rate). "Lazy refill": no timer thread; when a request arrives, add elapsed ÷ refill interval tokens, capped at the capacity.
  • Leaky bucket (as a queue): output is smooth, exactly one per interval, however bursty the input.
import java.util.*;
interface Clock { long millis(); }
class FakeClock implements Clock { long now;  public long millis() { return now; } }
class TokenBucket {                          // a bowl of tokens; one more drops in every `everyMs`
    final long capacity, everyMs;  final Clock clock;  double tokens;  long last;
    TokenBucket(long cap, long everyMs, Clock c) {
        capacity = cap;  this.everyMs = everyMs;  clock = c;  tokens = capacity;  last = c.millis(); }
    boolean tryAcquire() {  long now = clock.millis();
        tokens = Math.min(capacity, tokens + (double) (now - last) / everyMs);  last = now;  // refill
        if (tokens >= 1) { tokens--;  return true; }               // a token = permission for 1 request
        return false; } }
class LeakyBucket {                          // a queue with a hole: requests drip out at a fixed rate
    final int capacity;  final long everyMs;  final Clock clock;  final Deque<String> q = new ArrayDeque<>();
    long last;
    LeakyBucket(int cap, long everyMs, Clock c) { capacity = cap;  this.everyMs = everyMs;  clock = c; }
    boolean offer(String r) { leak();  if (q.size() < capacity) { q.addLast(r);  return true; }  return false; }
    void leak() {  long now = clock.millis();
        while (!q.isEmpty() && now - last >= everyMs) {
            last += everyMs;  System.out.println("  at " + last / 1000 + " s leaky serves " + q.pollFirst()); }
        if (q.isEmpty()) last = now; } }
public class Main { public static void main(String[] args) {
    FakeClock clock = new FakeClock();
    TokenBucket token = new TokenBucket(5, 1000, clock);  LeakyBucket leaky = new LeakyBucket(5, 1000, clock);
    int t = 0, q = 0;
    for (int i = 1; i <= 8; i++) { if (token.tryAcquire()) t++;  if (leaky.offer("req" + i)) q++; }
    System.out.println("0 s, burst of 8: token serves " + t + " now; leaky queues " + q + ", rejects " + (8 - q));
    clock.now = 3_000;  t = 0;  for (int i = 0; i < 5; i++) if (token.tryAcquire()) t++;
    System.out.println("3 s, 5 more tries: token serves " + t + " (3 tokens dripped back in)");
    clock.now = 6_000;  leaky.leak(); } }

Real output:

0 s, burst of 8: token serves 5 now; leaky queues 5, rejects 3
3 s, 5 more tries: token serves 3 (3 tokens dripped back in)
  at 1 s leaky serves req1
  at 2 s leaky serves req2
  at 3 s leaky serves req3
  at 4 s leaky serves req4
  at 5 s leaky serves req5

7. One interface, many algorithms, per-user and per-API

The obvious way is one big RateLimiter with an if/else on an algorithm name and one counter for the whole app: a single bot uses up Asha's limit too, and /login gets the same limit as /search.

The fix: - RateLimiter interface with tryAcquire(); one class per algorithm. This is the Strategy pattern (episode 34): the algorithm is an object you can swap. - A registry: rules maps an API to a Supplier<RateLimiter> (a function that makes a new limiter); limiters maps "user API" to that user's own limiter, created on first use with computeIfAbsent.

import java.util.*;  import java.util.function.Supplier;
interface Clock { long millis(); }
class FakeClock implements Clock { long now;  public long millis() { return now; } }
interface RateLimiter { boolean tryAcquire(); }          // Strategy: one method, many algorithms
class FixedWindow implements RateLimiter {
    final int limit;  final long win;  final Clock clock;  long w = -1;  int n;
    FixedWindow(int limit, long win, Clock c) { this.limit = limit;  this.win = win;  clock = c; }
    public boolean tryAcquire() {  long cur = clock.millis() / win;
        if (cur != w) { w = cur;  n = 0; }
        if (n < limit) { n++;  return true; }  return false; } }
class TokenBucket implements RateLimiter {
    final double cap, perMs;  final Clock clock;  double tokens;  long last;
    TokenBucket(double cap, double perSec, Clock c) { this.cap = tokens = cap; perMs = perSec / 1000; clock = c; }
    public boolean tryAcquire() {  long now = clock.millis();
        tokens = Math.min(cap, tokens + (now - last) * perMs);  last = now;
        if (tokens >= 1) { tokens--;  return true; }  return false; } }
class RateLimiterRegistry {                              // one limiter per user, per API
    private final Map<String, Supplier<RateLimiter>> rules = new HashMap<>();   // API -> how to make one
    private final Map<String, RateLimiter> limiters = new HashMap<>();          // "asha /login" -> its own
    void rule(String api, Supplier<RateLimiter> make) { rules.put(api, make); }
    boolean allow(String user, String api) {
        return limiters.computeIfAbsent(user + " " + api, k -> rules.get(api).get()).tryAcquire(); } }
public class Main { public static void main(String[] args) {
    FakeClock clock = new FakeClock();  RateLimiterRegistry r = new RateLimiterRegistry();
    r.rule("/login",  () -> new FixedWindow(3, 60_000, clock));      // 3 tries a minute
    r.rule("/search", () -> new TokenBucket(10, 10, clock));         // bursts of 10, 10 a second
    for (String[] call : new String[][]{{"asha", "/login"}, {"ravi", "/login"}, {"asha", "/search"}}) {
        int ok = 0;  for (int i = 0; i < 5; i++) if (r.allow(call[0], call[1])) ok++;
        System.out.println(call[0] + " " + call[1] + ", 5 tries: " + ok + " allowed"); } } }

Real output:

asha /login, 5 tries: 3 allowed
ravi /login, 5 tries: 3 allowed
asha /search, 5 tries: 5 allowed

8. Thread-safe counters

A server handles many requests at once on many threads. if (tokens > 0) tokens--; is check-then-act: two threads can both see a token and both take it, and tokens-- itself is read-modify-write. That's a race condition (episode 46).

  • Fix 1: synchronized: only one thread at a time runs tryAcquire.
  • Fix 2: AtomicLong + compareAndSet (lock-free): "set it to t - 1 only if it is still t"; if another thread changed it first, read again and retry. This is compare-and-swap (CAS).
import java.util.*;  import java.util.concurrent.atomic.*;
interface RateLimiter { boolean tryAcquire(); }
class UnsafeBucket implements RateLimiter {               // 10,000,000 tokens, no refill: at most that many
    private long tokens = 10_000_000;
    public boolean tryAcquire() { if (tokens > 0) { tokens--;  return true; }  return false; }   // check, then act
}
class SafeBucket implements RateLimiter {
    private long tokens = 10_000_000;
    public synchronized boolean tryAcquire() { if (tokens > 0) { tokens--;  return true; }  return false; }
}
class AtomicBucket implements RateLimiter {               // lock-free: compare-and-swap in a loop
    private final AtomicLong tokens = new AtomicLong(10_000_000);
    public boolean tryAcquire() {
        for (long t = tokens.get(); t > 0; t = tokens.get())
            if (tokens.compareAndSet(t, t - 1)) return true;     // only wins if nobody changed it meanwhile
        return false; }
}
public class Main {
    static void hammer(String name, RateLimiter limiter) throws InterruptedException {
        AtomicInteger allowed = new AtomicInteger();  List<Thread> threads = new ArrayList<>();
        for (int t = 0; t < 4; t++) threads.add(Thread.ofPlatform().start(() -> {   // 4 threads at once
            for (int i = 0; i < 5_000_000; i++) if (limiter.tryAcquire()) allowed.incrementAndGet(); }));
        for (Thread t : threads) t.join();
        System.out.printf("%-13s 20,000,000 tries: %,d allowed (limit 10,000,000)%n", name, allowed.get());
    }
    public static void main(String[] args) throws InterruptedException {
        hammer("no lock:", new UnsafeBucket());  hammer("synchronized:", new SafeBucket());
        hammer("atomic CAS:", new AtomicBucket()); } }

Real output (the "no lock" number changes every run; we saw from 10,060,175 to 16,831,201):

no lock:      20,000,000 tries: 10,060,175 allowed (limit 10,000,000)
synchronized: 20,000,000 tries: 10,000,000 allowed (limit 10,000,000)
atomic CAS:   20,000,000 tries: 10,000,000 allowed (limit 10,000,000)

9. The class diagram

RateLimiter  (interface: boolean tryAcquire())        Strategy
 ├─ FixedWindow      one counter per window     cheap, boundary burst
 ├─ SlidingLog       a deque of timestamps      exact, O(limit) memory
 ├─ SlidingCounter   curr + prev × overlap      2 numbers, an estimate
 ├─ TokenBucket      tokens refill at a rate    allows short bursts
 └─ LeakyBucket      a queue drained at a rate  smooth output
RateLimiterRegistry: rules API → Supplier<RateLimiter>; limiters "user API" → its own
Clock (interface): SystemClock in production, FakeClock in tests
Thread-safe: synchronized tryAcquire, or AtomicLong + compareAndSet

10. Choosing an algorithm

Algorithm Memory per key Accuracy Bursts Good for
Fixed window counter 2 numbers Up to 2× at edges Yes, at edges Simple daily quotas
Sliding window log One timestamp per request Exact No Low limits that must be exact (OTP: 3 a minute)
Sliding window counter 3 numbers Close estimate Smoothed High-volume APIs
Token bucket 2 numbers Exact average Yes, up to capacity Most APIs: allow short bursts
Leaky bucket (queue) Up to capacity requests Exact output rate No: smooth Protecting a slow downstream service

11. Interview follow-ups

Follow-up Answer
Many servers, one limit Each server only sees its own requests; keep counters in one shared store all servers use, and update them atomically
What does the client see? 429 Too Many Requests and a Retry-After header (mini project computes it)
Millions of idle users Their limiters stay in memory: evict idle ones, e.g. with an LRU cache (episode 65) or a TTL
Bursts allowed or not? Bursts OK → token bucket; smooth flow → leaky bucket
Change limits without a deploy Read rules from configuration and rebuild limiters
10 a second AND 1,000 a day Several limiters per key; the request passes only if all allow (AllOf in the mini project)
Fail open or fail closed? If the limiter's store is down: allow everything (fail open, keeps the service up) or refuse everything (fail closed, protects it); choose per API

12. Common mistakes

Mistake What you see (real) Why Fix
System.currentTimeMillis() inside Tests must wait a real minute Time can't be controlled Inject a Clock
Fixed window only 10 allowed in 1 second (limit 5 a minute) Windows reset together A sliding window or token bucket
Sliding log for huge limits a billion timestamps One entry per request Sliding counter
long tokens with a fractional refill error: incompatible types: possible lossy conversion from double to long Tokens need fractions double tokens
Integer division in the refill tokens after 3 seconds: 0 (a request every 500 ms; 500 / 1000 = 0) Each small gap rounds to 0 Use double, or keep the remainder
long millis() without public in the class error: millis() in FakeClock cannot implement millis() in Clock ... attempting to assign weaker access privileges; was public Interface methods are public public long millis()
One counter for all users A bot uses up Asha's limit No per-user key Registry: user + API
if (tokens > 0) tokens-- with no lock more than 10,000,000 allowed Check-then-act race synchronized or CAS

The integer-division bug, run for real:

public class Main { public static void main(String[] a) {
    long tokens = 0, last = 0;                         // integer refill: 1 token per 1000 ms
    for (long now = 500; now <= 3000; now += 500) {    // a request every 500 ms
        tokens += (now - last) / 1000;  last = now;    // 500 / 1000 = 0 in integer maths
    }
    System.out.println("tokens after 3 seconds: " + tokens);
} }
tokens after 3 seconds: 0

Mini project: a small rate-limiting library

Thread-safe limiters that return a Decision with the Retry-After time, a registry with per-user, per-API rules, two limits combined with AllOf, a SystemClock for production and a FakeClock for tests.

import java.util.*;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.Supplier;

// Mini project: a small rate-limiting library. Every limiter is thread-safe, testable with a FakeClock,
// and answers with a Decision that says how long to wait (the Retry-After value) when it refuses.
interface Clock { long millis(); }
class SystemClock implements Clock { public long millis() { return System.currentTimeMillis(); } }
class FakeClock implements Clock {
    private long now;
    public synchronized long millis() { return now; }
    synchronized void advance(long ms) { now += ms; }
}

record Decision(boolean allowed, long retryAfterMs) {
    static Decision allow() { return new Decision(true, 0); }
    static Decision deny(long waitMs) { return new Decision(false, Math.max(1, waitMs)); }
}

interface RateLimiter { Decision tryAcquire(); }

class FixedWindow implements RateLimiter {
    private final int limit;  private final long win;  private final Clock clock;
    private long window = -1;  private int count;
    FixedWindow(int limit, long win, Clock clock) { this.limit = limit;  this.win = win;  this.clock = clock; }
    public synchronized Decision tryAcquire() {
        long now = clock.millis(), w = now / win;
        if (w != window) { window = w;  count = 0; }
        if (count < limit) { count++;  return Decision.allow(); }
        return Decision.deny((w + 1) * win - now);                 // wait until the next window starts
    }
}

class SlidingLog implements RateLimiter {
    private final int limit;  private final long win;  private final Clock clock;
    private final Deque<Long> times = new ArrayDeque<>();
    SlidingLog(int limit, long win, Clock clock) { this.limit = limit;  this.win = win;  this.clock = clock; }
    public synchronized Decision tryAcquire() {
        long now = clock.millis();
        while (!times.isEmpty() && times.peekFirst() <= now - win) times.pollFirst();
        if (times.size() < limit) { times.addLast(now);  return Decision.allow(); }
        return Decision.deny(times.peekFirst() + win - now);       // wait until the oldest one leaves
    }
}

class SlidingCounter implements RateLimiter {
    private final int limit;  private final long win;  private final Clock clock;
    private long window = 0;  private int curr, prev;
    SlidingCounter(int limit, long win, Clock clock) { this.limit = limit;  this.win = win;  this.clock = clock; }
    public synchronized Decision tryAcquire() {
        long now = clock.millis(), w = now / win;
        if (w != window) { prev = (w == window + 1) ? curr : 0;  curr = 0;  window = w; }
        double overlap = 1.0 - (double) (now % win) / win;
        if (prev * overlap + curr < limit) { curr++;  return Decision.allow(); }
        return Decision.deny(win / 10);                            // an estimate: try again a bit later
    }
}

class TokenBucket implements RateLimiter {
    private final double capacity, perMs;  private final Clock clock;
    private double tokens;  private long last;
    TokenBucket(double capacity, double perSecond, Clock clock) {
        this.capacity = tokens = capacity;  this.perMs = perSecond / 1000.0;  this.clock = clock;  last = clock.millis(); }
    public synchronized Decision tryAcquire() {
        long now = clock.millis();
        tokens = Math.min(capacity, tokens + (now - last) * perMs);  last = now;
        if (tokens >= 1) { tokens -= 1;  return Decision.allow(); }
        return Decision.deny((long) Math.ceil((1 - tokens) / perMs));   // until one whole token is back
    }
}

class AllOf implements RateLimiter {                               // several limits at once: all must pass
    private final List<RateLimiter> parts;
    AllOf(RateLimiter... parts) { this.parts = List.of(parts); }
    public synchronized Decision tryAcquire() {
        // simple version: a refusal by a later limiter still used up the earlier ones' quota
        long wait = 0;
        for (RateLimiter p : parts) { Decision d = p.tryAcquire();  if (!d.allowed()) wait = Math.max(wait, d.retryAfterMs()); }
        return wait == 0 ? Decision.allow() : Decision.deny(wait);
    }
}

class RateLimiterRegistry {
    private final Map<String, Supplier<RateLimiter>> rules = new ConcurrentHashMap<>();
    private final Map<String, RateLimiter> limiters = new ConcurrentHashMap<>();
    void rule(String api, Supplier<RateLimiter> make) { rules.put(api, make); }
    Decision check(String user, String api) {
        Supplier<RateLimiter> make = rules.get(api);
        if (make == null) return Decision.allow();                 // no rule: not limited
        return limiters.computeIfAbsent(user + " " + api, k -> make.get()).tryAcquire();
    }
    int size() { return limiters.size(); }
}

public class Main {
    static String http(Decision d) {                               // what an HTTP API would answer
        return d.allowed() ? "200 OK" : "429 Too Many Requests, Retry-After: " + (long) Math.ceil(d.retryAfterMs() / 1000.0) + " s";
    }
    public static void main(String[] args) {
        FakeClock clock = new FakeClock();
        RateLimiterRegistry api = new RateLimiterRegistry();
        api.rule("/otp", () -> new SlidingLog(3, 60_000, clock));
        api.rule("/search", () -> new AllOf(new TokenBucket(5, 1, clock), new FixedWindow(100, 86_400_000, clock)));

        for (int i = 1; i <= 4; i++) System.out.println("asha /otp try " + i + ": " + http(api.check("asha", "/otp")));
        clock.advance(20_000);
        System.out.println("20 s later, asha /otp: " + http(api.check("asha", "/otp")));
        System.out.println("ravi /otp: " + http(api.check("ravi", "/otp")));

        int ok = 0;  Decision last = null;
        for (int i = 0; i < 7; i++) { last = api.check("asha", "/search");  if (last.allowed()) ok++; }
        System.out.println("asha /search burst of 7: " + ok + " allowed, then " + http(last));
        clock.advance(2_000);
        System.out.println("2 s later, asha /search: " + http(api.check("asha", "/search")));
        System.out.println("limiters in memory: " + api.size());
        System.out.println("with the real clock: " + http(new TokenBucket(1, 1, new SystemClock()).tryAcquire()));
    }
}

Real output:

asha /otp try 1: 200 OK
asha /otp try 2: 200 OK
asha /otp try 3: 200 OK
asha /otp try 4: 429 Too Many Requests, Retry-After: 60 s
20 s later, asha /otp: 429 Too Many Requests, Retry-After: 40 s
ravi /otp: 200 OK
asha /search burst of 7: 5 allowed, then 429 Too Many Requests, Retry-After: 1 s
2 s later, asha /search: 200 OK
limiters in memory: 3
with the real clock: 200 OK

Asha's 4th OTP try is refused with Retry-After: 60 s; 20 s later she must wait 40 s more; Ravi is not affected. The /search burst of 7: 5 allowed by the token bucket, and 2 s later a token is back.

Practice

1. Add a SystemClock that uses the real time.

Answer

class SystemClock implements Clock { public long millis() { return System.currentTimeMillis(); } }. See the mini project: with the real clock: 200 OK.

2. Return the wait time (Retry-After) when a request is refused.

Answer

Return a Decision(allowed, retryAfterMs). Fixed window: until the next window starts, (w + 1) * win - now. Sliding log: until the oldest time leaves, oldest + win - now. Token bucket: until one whole token is back, (1 - tokens) / perMs. See the mini project.

3. Make SlidingCounter thread-safe.

Answer

Mark tryAcquire synchronized: it reads and writes window, curr and prev together, so they must change as one step. See the mini project.

4. Combine two limits: 10 a second and 100 a day.

Answer

new AllOf(new TokenBucket(10, 10, clock), new FixedWindow(100, 86_400_000, clock)): ask every part; refuse if any refuses, with the longest wait. Note the simple version still uses up the earlier parts' quota when a later one refuses; a stricter version checks all first, then commits.

5. Why is the leaky bucket called "smooth" and the token bucket "bursty"? Use the run in section 6.

Answer

The burst of 8 at 0 s: the token bucket served 5 immediately; the leaky bucket queued 5 and served them one per second at 1, 2, 3, 4 and 5 s.

Quick quiz

Token bucket: capacity 5, 1 new token per second, starts full. 7 requests at 0 s, 3 at 2 s. How many are allowed in total? (a) 5 (b) 7 (c) 8 (d) 10

Answer

(b) 7. 5 at 0 s (2 refused); by 2 s, 2 tokens have dripped back, so 2 of the 3 pass. Checked by running our TokenBucket:

7

Interview questions

  1. Name the classic rate-limiting algorithms and one trade-off of each. Fixed window (cheap, boundary burst), sliding log (exact, memory), sliding counter (cheap, estimate), token bucket (bursts allowed), leaky bucket (smooth, queues).
  2. What is the boundary burst? Up to 2 × limit requests around a fixed-window edge: 10 in 1 second with "5 a minute".
  3. Token bucket vs leaky bucket? Token bucket limits the average and allows bursts up to the capacity; leaky bucket forces a constant output rate.
  4. How do you test a limiter that depends on time? Inject a Clock; tests use a fake clock and move time by hand.
  5. How do you support different limits per user and per API? A key of user + API, a rule per API, and one limiter object per key, created on first use.
  6. How do you add a new algorithm? A new class implementing RateLimiter; nothing else changes (Strategy, Open-Closed).
  7. Is if (tokens > 0) tokens-- thread-safe? No: check-then-act and read-modify-write. Use synchronized or an AtomicLong with compareAndSet.
  8. What HTTP response does a refused request get? 429 Too Many Requests, optionally with Retry-After.
  9. How do you rate-limit across many servers? Shared counters in one store with atomic updates; or give each server a share of the limit.
  10. How much memory does each algorithm need per user? Fixed/counter/token: a few numbers; sliding log: one timestamp per request in the window; leaky bucket: up to its queue capacity.

Glossary

Term Meaning, with an example
Request One call from a client to a server: Asha asking for an OTP
API A door into a server that programs call: /login, /search
Rate Requests per unit of time: 5 a minute
Rate limiting Refusing requests above an allowed rate
Rate limiter The object that decides: tryAcquire() → true/false
tryAcquire Ask for permission for one request; false means refused
HTTP 429 Too Many Requests The web status code for a rate-limited request
Retry-After Optional header saying how long to wait: Retry-After: 60
OTP One-time password: a short code sent by SMS; limited to stop guessing
Clock An interface giving the current time: long millis()
Clock injection for tests Passing the clock in, so tests can use a fake one
FakeClock A test clock set by hand: clock.set(10, 0, 59)
Dependency injection Giving an object what it needs from outside, through its constructor
Window A block of time: the minute 10:00 to 10:01
Fixed window counter Count per fixed window, reset at each boundary
Boundary burst Up to 2 × limit around a window edge: 10 in 1 second
Sliding window Always the last N seconds counted back from now
Sliding window log Keep every allowed request's time; exact
Deque A double-ended queue: add at the back, remove from the front
Sliding window counter prev × overlap + curr; two numbers, an estimate
Overlap The part of the last window still inside the sliding window: 0.75
Token bucket A bucket of tokens refilled at a rate; each request spends one
Token Permission for one request
Capacity The most tokens (or queued requests) a bucket holds: 5
Refill rate How fast tokens come back: 1 a second
Lazy refill Compute the refill when a request arrives, no timer thread
Leaky bucket A queue served at a fixed rate; full means refuse
Burst Many requests in a very short time
Per-user and per-API limits A separate limiter for each user and API pair: "asha /login"
RateLimiter interface interface RateLimiter { boolean tryAcquire(); }
Strategy per algorithm Each algorithm is a class behind the same interface, swappable
Registry A map that creates and keeps one limiter per key
Supplier A function with no input that makes a value: () -> new FixedWindow(...)
computeIfAbsent Get the value for a key, creating it once if missing
Thread One path of work; servers run many at once
Race condition Threads interleave and the result is wrong: over 10,000,000 allowed
Check-then-act Check a condition, then act on it; unsafe if another thread acts in between
Thread-safe counters Counters that stay correct with many threads: synchronized or atomics
synchronized Only one thread at a time runs the method
AtomicLong A long with atomic operations like compareAndSet
Compare-and-swap (CAS) "Set to new only if still old"; retry if it changed
Lock-free Correct under threads without locks, using CAS
Fail open / fail closed When the limiter is broken: allow everything / refuse everything

Summary

  • Rate limiting refuses requests above a rate; on the web the answer is 429 with an optional Retry-After.
  • Clock injection made every algorithm testable in milliseconds with a FakeClock.
  • The fixed window counter is cheap but let 10 through in 1 second at the boundary.
  • The sliding window log is exact but stores every timestamp; the sliding window counter keeps 2 numbers and estimates.
  • The token bucket allows bursts up to its capacity; the leaky bucket gives a smooth, constant output.
  • A RateLimiter interface (Strategy) and a registry gave every user and API its own limiter.
  • synchronized or an AtomicLong compare-and-swap loop kept the limit exact under many threads.