Rate Limiter

Design an in-process rate limiter that allows each client a fixed number of requests per time window. The algorithm can be swapped, and it stays correct under many threads.

Design a rate limiter for our API. Each client may make at most 100 requests per minute, with short bursts allowed. Extra requests get HTTP 429. Make it easy to change the algorithm and the limits.

Questions to ask first

  • What is the key: user, API key or IP address? Assume the API key, but keep the key a plain string so any of them works.
  • Are bursts allowed? Yes. A client that was idle may send a short burst, up to the bucket size.
  • One server or many? Assume one server for the design. Limits across servers are a deep dive.
  • Do limits differ by plan? Yes, free and premium plans. Each plan has its own rule.
  • What happens to a rejected request? It is refused at once with 429. We do not queue it.
  • How exact must it be? Small errors are fine. The default algorithm must not let double the limit through at a window edge, so fixed window is only a cheap option.

Requirements

  • `tryAcquire(key)` returns true if the request may go ahead and false if it must be rejected.
  • Each key has its own limit state, so one noisy client cannot use another client's quota.
  • Support at least token bucket and fixed window, chosen by configuration.
  • Limits (capacity and refill rate) come from a rule per plan.
  • Stay correct when many threads call at once for the same key.
  • Read time from an injected clock so tests can move time without sleeping.

Out of scope

  • Limits shared across many servers (covered in a deep dive).
  • Queuing or delaying requests instead of rejecting them.
  • An admin screen to edit rules.

Entities

  • RateLimiter: tryAcquire(key), the contract
  • TokenBucketLimiter, FixedWindowLimiter, SlidingWindowLogLimiter: the algorithms
  • TokenBucket: capacity, tokens, refill rate, lastRefill; tryConsume(now)
  • LimitRule: algorithm, capacity, refillPerSecond
  • Algorithm: TOKEN_BUCKET, FIXED_WINDOW, SLIDING_WINDOW_LOG
  • RateLimiterFactory: create(rule)
  • Clock: nanoTime(); SystemClock in production, a fake clock in tests
  • RateLimitFilter: calls the limiter before each request

Classes in the model design

  • RateLimiter (interface)
  • TokenBucketLimiter (class)
  • FixedWindowLimiter (class)
  • SlidingWindowLogLimiter (class)
  • TokenBucket (class)
  • LimitRule (class)
  • Algorithm (enum)
  • RateLimiterFactory (class)
  • Clock (interface)
  • SystemClock (class)
  • RateLimitFilter (class)

The main use case, step by step

  1. A request with API key `k-42` reaches `RateLimitFilter`. The filter looks up the client's plan (free) and picks that plan's `RateLimiter`.
  2. The filter calls `limiter.tryAcquire("k-42")`. It knows only the interface, so the algorithm can change without touching the filter.
  3. `TokenBucketLimiter` reads the time once from the injected `Clock`. It then calls `buckets.computeIfAbsent("k-42", ...)`, which is atomic, so two first requests at the same moment still share one bucket.
  4. The limiter calls `bucket.tryConsume(now)`. Inside this synchronized method, the bucket first adds tokens for the time passed since the last call (elapsed time multiplied by the refill rate), up to its capacity.
  5. If at least one token is left, the bucket takes one and returns true. Otherwise it returns false and changes nothing.
  6. The filter passes the request on when the answer is true. When it is false, the filter returns HTTP 429 with a Retry-After header and never calls the business code.

Patterns used

  • Strategy: The RateLimiter interface with TokenBucketLimiter, FixedWindowLimiter and SlidingWindowLogLimiter.. The algorithm is a choice with real trade-offs. Callers depend on the interface, so the choice can change per plan or per endpoint without editing the filter.
  • Factory: RateLimiterFactory.create(rule) turns a LimitRule into the right limiter.. Configuration says TOKEN_BUCKET with 100 per minute. One place maps that to a class, so the filter never writes `new TokenBucketLimiter`.
  • Dependency inversion: The Clock interface with SystemClock, passed into every limiter.. Time is an input like any other. Tests pass a fake clock and move it forward, so they run in milliseconds and give the same result every time.

Key code

The interface, the rule and a thread-safe token bucket

public interface RateLimiter {
    /** True: let the request through. False: reply 429 Too Many Requests. */
    boolean tryAcquire(String key);
}

public interface Clock { long nanoTime(); }

public enum Algorithm { TOKEN_BUCKET, FIXED_WINDOW, SLIDING_WINDOW_LOG }

public record LimitRule(Algorithm algorithm, long capacity, double refillPerSecond) { }

/** One per key. Tokens are refilled lazily, when a request arrives: no timer threads. */
public final class TokenBucket {
    private final long capacity;
    private final double refillPerNano;
    private double tokens;
    private long lastRefill;

    public TokenBucket(long capacity, double refillPerSecond, long now) {
        this.capacity = capacity;
        this.refillPerNano = refillPerSecond / 1_000_000_000.0;
        this.tokens = capacity;                  // a new client may burst at once
        this.lastRefill = now;
    }

    /** synchronized: check and take must happen as one step for this key. */
    public synchronized boolean tryConsume(long now) {
        if (now > lastRefill) {                  // another thread may arrive with an older time
            tokens = Math.min(capacity, tokens + (now - lastRefill) * refillPerNano);
            lastRefill = now;
        }
        if (tokens < 1) return false;
        tokens -= 1;
        return true;
    }
}

TokenBucketLimiter and the factory

public final class TokenBucketLimiter implements RateLimiter {
    private final LimitRule rule;
    private final Clock clock;
    private final ConcurrentHashMap<String, TokenBucket> buckets = new ConcurrentHashMap<>();

    public TokenBucketLimiter(LimitRule rule, Clock clock) {
        this.rule = rule;
        this.clock = clock;
    }

    @Override
    public boolean tryAcquire(String key) {
        long now = clock.nanoTime();
        // computeIfAbsent is atomic: two first requests for one key get the same bucket.
        TokenBucket bucket = buckets.computeIfAbsent(key,
            k -> new TokenBucket(rule.capacity(), rule.refillPerSecond(), now));
        return bucket.tryConsume(now);
    }
}

public final class RateLimiterFactory {
    private final Clock clock;

    public RateLimiterFactory(Clock clock) { this.clock = clock; }

    // 100 per minute with bursts of 100: new LimitRule(TOKEN_BUCKET, 100, 100 / 60.0)
    public RateLimiter create(LimitRule rule) {
        return switch (rule.algorithm()) {
            case TOKEN_BUCKET -> new TokenBucketLimiter(rule, clock);
            case FIXED_WINDOW -> new FixedWindowLimiter(rule, clock);
            case SLIDING_WINDOW_LOG -> new SlidingWindowLogLimiter(rule, clock);
        };
    }
}

Deep dives

Which algorithm?

Weak: Fixed window: count requests per key per clock minute and reset at the start of each minute. It is simple. But a client can send 100 requests at 10:00:59 and 100 more at 10:01:00. That is 200 in two seconds, double the limit.

Good: Sliding window log: keep the time of each request in a queue per key, and drop entries older than one minute. It is exact. But it stores up to 100 timestamps per client, so memory grows with the limit.

Great: Token bucket: each key has a bucket of up to N tokens that refills at a steady rate, and each request takes one token. It allows short bursts up to N, enforces the average rate, and stores only two numbers per key. A sliding window counter (this window's count plus a weighted share of the last one) is a close second.

Trade-off: A token bucket allows a burst of N after idle time, which some APIs do not want. If traffic must be smooth, use a leaky bucket (a queue drained at a fixed rate) instead. Name the trade-off rather than claiming one algorithm is always best.

Thread safety for one key

Weak: A plain HashMap of buckets and an unsynchronized tryConsume. Two threads both see 1 token, both take it, and both requests pass. A HashMap changed by two threads at once can also lose entries.

Good: ConcurrentHashMap.computeIfAbsent to create buckets, and synchronized on each bucket's tryConsume. Different keys never block each other. For one key, the check and the take are atomic: no other thread can run between them.

Great: The same, plus two details. First, read the time once and ignore an older time that arrives late, so the bucket never moves backwards. Second, remove buckets that have been idle for a long time, or the map grows with every client ever seen. A lock-free version packs tokens and time into one AtomicLong and uses compare-and-set, but it is harder to read.

Trade-off: Per-bucket locks are simple and fast enough for most services. Lock-free code helps only for very busy keys and costs readability. In an interview, show the locked version and mention the other.

One limit across many servers

Weak: Each of 10 servers keeps its own buckets. A client whose requests are spread across servers gets up to 10 times the limit.

Good: Keep counters in Redis, a shared in-memory data store. A fixed window with INCR and EXPIRE per key per minute works across servers and is easy to build.

Great: Run the token bucket inside Redis as a Lua script. A Lua script is a small program that Redis runs as one step, so read, refill and take are atomic. Keep the RateLimiter interface: RedisTokenBucketLimiter is one more implementation. If Redis is down, fall back to a local limiter with a smaller share instead of rejecting everything.

Trade-off: A network call per request adds about a millisecond and a new dependency. Local limits with a share of the global limit (the limit divided by the number of servers) avoid that but are less exact.

Now add one more feature

  • Now give premium users a higher limit. Store a LimitRule per plan and let the filter pick the limiter by plan. No algorithm class changes.
  • Now limit by user and by IP address at the same time. Add `CompositeRateLimiter`, which implements RateLimiter and allows a request only if every inner limiter allows it. Take tokens only when all agree, or accept a small over-count.
  • Now tell clients when to retry. Change the result from boolean to a `Decision` record with `allowed` and `retryAfter`. The token bucket computes the wait as the missing tokens divided by the refill rate.
  • Now change limits without a restart. Keep rules in a `RuleStore` that the filter reads on each request. Build a new limiter when a rule changes, and keep the old buckets if the algorithm is the same.

What each level is expected to show

SDE-1: A RateLimiter interface, a working fixed window or token bucket per key, and a clear yes or no for each request. Knows that a plain HashMap is not safe under many threads.

SDE-2: Compares fixed window, sliding log and token bucket, and explains the burst at the window edge. Shows a thread-safe token bucket with lazy refill, an injected Clock, per-plan rules through a factory, and a plan for many servers with Redis.

Common mistakes

  • Refilling tokens with a background thread per key. Lazy refill on each request needs no threads.
  • Calling `System.currentTimeMillis()` inside the algorithm, which makes tests slow and flaky.
  • Using `containsKey` and then `put` to create buckets, so two threads create two buckets for one key.
  • Making the filter depend on TokenBucketLimiter directly, so changing the algorithm means editing the filter.
  • Never removing old keys, so memory grows with every client ever seen.
  • Claiming a fixed window enforces the limit exactly, and missing the burst at the window edge.

Lessons behind this answer