Rate limiter design

Overview

A rate limiter component decides whether a request from a client is allowed right now, based on a policy such as 100 requests per minute. The common algorithms are token bucket (tokens refill at a steady rate, allowing bursts up to capacity), leaky bucket (constant outflow), fixed window counters, and sliding window log or counter.

An LLD answer should define a clean interface (tryAcquire(clientId)), make algorithms pluggable (Strategy), support per-client and per-endpoint rules, use an injectable clock for tests, and be thread-safe. For distributed use, the state moves to Redis with atomic scripts, but the in-process design is the same.

When to use it

• Interview prompt: 'Design a rate limiter class'.
• Protecting APIs, logins, and expensive operations.
• Client-side throttling of calls to third-party APIs.

Where it shows up in interviews

Where it is used in real software

Key terms

Token bucket

Capacity plus refill rate; allows bursts.

Sliding window log

Timestamps of recent requests; exact but memory heavy.

Fixed window

Counter per time window; bursts at edges.

Key

What is limited: user, API key, IP, endpoint.

Retry-After

When the client may try again.

How it works, step by step

1. 1
   Define the interface

   tryAcquire(key): boolean, plus retryAfter.

2. 2
   Pick the algorithm

   Token bucket is a common default.

3. 3
   Store state per key

   ConcurrentHashMap of buckets.

4. 4
   Refill lazily on access

   tokens += elapsed x rate, capped.

5. 5
   Make it thread-safe and testable

   Synchronize per bucket, inject a clock.

Token bucket trace

Capacity 3, refill 1 token/second

Bursts up to capacity are allowed; sustained rate is bounded by the refill rate.

Implementation

1import java.time.Clock;2import java.util.concurrent.ConcurrentHashMap;3 4public interface RateLimiter { boolean tryAcquire(String key); }5 6public final class TokenBucketLimiter implements RateLimiter {7    private static final class Bucket {8        double tokens;9        long lastRefillNanos;10        Bucket(double tokens, long now) { this.tokens = tokens; this.lastRefillNanos = now; }11    }12 13    private final int capacity;14    private final double refillPerSecond;15    private final Clock clock;16    private final ConcurrentHashMap<String, Bucket> buckets = new ConcurrentHashMap<>();17 18    public TokenBucketLimiter(int capacity, double refillPerSecond, Clock clock) {19        this.capacity = capacity;20        this.refillPerSecond = refillPerSecond;21        this.clock = clock;22    }23 24    @Override25    public boolean tryAcquire(String key) {26        long now = clock.millis() * 1_000_000L;27        Bucket b = buckets.computeIfAbsent(key, k -> new Bucket(capacity, now));28        synchronized (b) {                                    // per-key lock29            double elapsed = (now - b.lastRefillNanos) / 1e9;30            b.tokens = Math.min(capacity, b.tokens + elapsed * refillPerSecond);31            b.lastRefillNanos = now;32            if (b.tokens >= 1) { b.tokens -= 1; return true; }33            return false;34        }35    }36}

Complexity and performance

Trade-offs

Variants and related techniques

Common mistakes

• Fixed windows allowing 2x bursts at boundaries.

  Fix: Use sliding windows or token buckets.

• Unbounded map of keys.

  Fix: Expire idle buckets.

• Using System.currentTimeMillis directly.

  Fix: Inject a clock for deterministic tests.

Interview questions

Practice problems