Design a Rate Limiter

Design a pluggable API rate limiter — fixed window, sliding window, token bucket, and leaky bucket — with the math and edge cases behind each algorithm.

August 11, 2026

lldrate-limitertoken-bucketsliding-windowalgorithmsdistributed

Design a Rate Limiter

A rate limiter is asked in both LLD and system-design rounds because it has both a clean object-oriented shape (a RateLimiter interface, several interchangeable algorithms) and real distributed-systems depth (what happens when the limiter itself runs on N stateless API servers instead of one process). This guide covers the single-process LLD fully, then extends into the distributed case since it's the natural, expected follow-up question.

1. Requirements

Functional requirements

Limit the number of requests a client can make within a time window (per-second, per-minute, per-hour — window size configurable).
Support multiple limiting algorithms: fixed window, sliding window (log or counter), token bucket, leaky bucket — selectable per client or endpoint.
Configurable limits per client, per endpoint, or per (client, endpoint) pair.
Return whether a request is allowed, plus remaining quota and reset time, so the caller can populate rate-limit response headers.
Support burst allowance for some algorithms (token bucket) vs. strictly smooth output (leaky bucket).

Non-functional requirements

The limiter check itself must be fast (sub-millisecond) — it sits on the hot path of every request.
Memory bounded per client — must not grow unboundedly with request volume (rules out a naive unbounded timestamp log).
Thread-safe for concurrent requests from the same client hitting the same server.
Must work correctly (or degrade predictably) when the limiter's state needs to be shared across multiple API server instances, not just one JVM.

Out of scope: the HTTP/API gateway integration layer itself, IP-based abuse/DDoS detection heuristics (a rate limiter is one building block of that, not the whole system).

2. Actors & Use Cases

Actors

API client — identified by API key, user ID, or IP address; the entity being rate-limited.
API gateway / middleware — calls the rate limiter on every incoming request, before the request reaches business logic.
Configuration source — sets per-client or per-endpoint limits (static config or a dynamic admin API).
Redis / shared store — in the distributed case, the coordination point across API server instances.

Primary use cases

A request arrives for clientId="acct_123" on endpoint /search → gateway calls rateLimiter.allow("acct_123", "/search") → limiter returns allowed=true, remaining=17, resetAt=... → gateway forwards the request and sets response headers.
Client exceeds its configured limit → limiter returns allowed=false → gateway responds 429 Too Many Requests with a Retry-After header derived from resetAt.
Operator changes acct_123's limit from 100/min to 500/min → next request picks up the new RateLimitConfig without a restart.
A burst of 20 requests arrives in one second, then nothing for 10 seconds, under a token-bucket config allowing bursts up to bucket capacity → all 20 are allowed if within capacity, since token bucket explicitly tolerates bursts.
The same burst under a leaky-bucket config → only the configured steady rate is allowed through per unit time; the rest are queued or rejected — leaky bucket smooths, it does not tolerate bursts.

3. Class Diagram

4. Core Class Design

Common interface and result type

java

public interface RateLimiter {
    RateLimitResult allow(String clientId);
}
 
public final class RateLimitResult {
    private final boolean allowed;
    private final int remaining;
    private final Instant resetAt;
 
    public RateLimitResult(boolean allowed, int remaining, Instant resetAt) {
        this.allowed = allowed;
        this.remaining = remaining;
        this.resetAt = resetAt;
    }
    public boolean allowed() { return allowed; }
    public int remaining() { return remaining; }
    public Instant resetAt() { return resetAt; }
}
 
public enum AlgorithmType { FIXED_WINDOW, SLIDING_WINDOW, TOKEN_BUCKET, LEAKY_BUCKET }
 
public final class RateLimitConfig {
    private final String clientId;
    private final String endpoint;
    private final int limit;
    private final Duration window;
    private final AlgorithmType algorithm;
    // constructor / getters omitted for brevity
}

Fixed window — simplest, has the boundary-burst problem

java

public final class FixedWindowLimiter implements RateLimiter {
    private final int limit;
    private final long windowMillis;
    private final Map<String, WindowCounter> counters = new ConcurrentHashMap<>();
 
    public FixedWindowLimiter(int limit, Duration windowSize) {
        this.limit = limit;
        this.windowMillis = windowSize.toMillis();
    }
 
    public RateLimitResult allow(String clientId) {
        long now = System.currentTimeMillis();
        long windowStart = (now / windowMillis) * windowMillis; // bucket the timeline into fixed slots
 
        WindowCounter counter = counters.compute(clientId, (id, existing) -> {
            if (existing == null || existing.windowStart != windowStart) {
                return new WindowCounter(windowStart, new AtomicInteger(0));
            }
            return existing;
        });
 
        int count = counter.count.incrementAndGet();
        boolean allowed = count <= limit;
        Instant resetAt = Instant.ofEpochMilli(windowStart + windowMillis);
        return new RateLimitResult(allowed, Math.max(0, limit - count), resetAt);
    }
 
    private static final class WindowCounter {
        final long windowStart;
        final AtomicInteger count;
        WindowCounter(long windowStart, AtomicInteger count) { this.windowStart = windowStart; this.count = count; }
    }
}

Sliding window counter — smooths the boundary problem cheaply

java

public final class SlidingWindowCounterLimiter implements RateLimiter {
    private final int limit;
    private final long windowMillis;
    private final Map<String, int[]> currentAndPrevious = new ConcurrentHashMap<>(); // [prevCount, currCount]
    private final Map<String, Long> currentWindowStart = new ConcurrentHashMap<>();
 
    public SlidingWindowCounterLimiter(int limit, Duration windowSize) {
        this.limit = limit;
        this.windowMillis = windowSize.toMillis();
    }
 
    public synchronized RateLimitResult allow(String clientId) {
        long now = System.currentTimeMillis();
        long windowStart = (now / windowMillis) * windowMillis;
        long prevStart = currentWindowStart.getOrDefault(clientId, windowStart);
        int[] counts = currentAndPrevious.computeIfAbsent(clientId, k -> new int[]{0, 0});
 
        if (windowStart != prevStart) {
            counts[0] = (windowStart - prevStart == windowMillis) ? counts[1] : 0; // roll forward
            counts[1] = 0;
            currentWindowStart.put(clientId, windowStart);
        }
 
        double elapsedFraction = (now - windowStart) / (double) windowMillis;
        double weightedCount = counts[0] * (1 - elapsedFraction) + counts[1];
 
        if (weightedCount >= limit) {
            return new RateLimitResult(false, 0, Instant.ofEpochMilli(windowStart + windowMillis));
        }
        counts[1]++;
        int remaining = (int) Math.max(0, limit - weightedCount - 1);
        return new RateLimitResult(true, remaining, Instant.ofEpochMilli(windowStart + windowMillis));
    }
}

5. Design Patterns Applied

Pattern	Where used	Why
Strategy	`RateLimiter` interface, four algorithm implementations	Algorithm choice is a config value, not a code branch; a new algorithm (e.g. GCRA) is a new class.
Factory Method	`RateLimiterFactory.create(algorithm, config)`	Callers request a limiter by config, never instantiate `TokenBucketLimiter` directly.
Decorator	Wrapping a `RateLimiter` with a `MetricsRateLimiter` that records allow/deny counts	Adds observability without touching the algorithm implementations.
Composite	A `PerEndpointRateLimiter` that holds one `RateLimiter` per endpoint and delegates by request path	Lets different endpoints have different limits/algorithms while exposing one `RateLimiter`-shaped entry point to the gateway.
Template Method	Shared "compute window key → check → update → build result" shape across the window-based limiters	The window bucketing logic is nearly identical between fixed and sliding window; a shared abstract skeleton reduces duplication (elided above for clarity of the concrete classes).

6. Key Algorithms, Concurrency & Edge Cases

Fixed window — the boundary-burst problem

Fixed window is simple but allows up to 2 × limit requests in a short span straddling a window boundary: a client can send limit requests in the last millisecond of one window and limit more in the first millisecond of the next. This is the concrete failure mode interviewers expect you to name unprompted.

Sliding window log — exact, but memory-proportional-to-traffic

java

public final class SlidingWindowLogLimiter implements RateLimiter {
    private final int limit;
    private final long windowMillis;
    private final Map<String, Deque<Long>> requestLog = new ConcurrentHashMap<>();
 
    public SlidingWindowLogLimiter(int limit, Duration windowSize) {
        this.limit = limit;
        this.windowMillis = windowSize.toMillis();
    }
 
    public RateLimitResult allow(String clientId) {
        long now = System.currentTimeMillis();
        Deque<Long> log = requestLog.computeIfAbsent(clientId, k -> new ArrayDeque<>());
 
        synchronized (log) {
            long cutoff = now - windowMillis;
            while (!log.isEmpty() && log.peekFirst() < cutoff) {
                log.pollFirst(); // evict timestamps that have aged out of the window
            }
            if (log.size() >= limit) {
                long resetAt = log.peekFirst() + windowMillis;
                return new RateLimitResult(false, 0, Instant.ofEpochMilli(resetAt));
            }
            log.addLast(now);
            return new RateLimitResult(true, limit - log.size(), Instant.ofEpochMilli(now + windowMillis));
        }
    }
}

Exact — no boundary burst — but memory is O(requests in the window) per client, which is unbounded relative to limit for a client sending far more than limit requests per window (each rejected request still needs a check, though only accepted ones are logged here, bounding it to limit entries — worth stating explicitly since it's a common point of confusion).

Token bucket — the interview's favorite, worth knowing the refill math cold

java

public final class TokenBucketLimiter implements RateLimiter {
    private final int capacity;
    private final double refillTokensPerNano;
    private final Map<String, TokenBucket> buckets = new ConcurrentHashMap<>();
 
    public TokenBucketLimiter(int capacity, double refillRatePerSecond) {
        this.capacity = capacity;
        this.refillTokensPerNano = refillRatePerSecond / 1_000_000_000.0;
    }
 
    public RateLimitResult allow(String clientId) {
        TokenBucket bucket = buckets.computeIfAbsent(clientId,
            k -> new TokenBucket(capacity, System.nanoTime()));
 
        synchronized (bucket) {
            refill(bucket);
            if (bucket.tokens >= 1.0) {
                bucket.tokens -= 1.0;
                return new RateLimitResult(true, (int) bucket.tokens, estimateResetAt(bucket));
            }
            return new RateLimitResult(false, 0, estimateResetAt(bucket));
        }
    }
 
    private void refill(TokenBucket bucket) {
        long now = System.nanoTime();
        long elapsedNanos = now - bucket.lastRefillNanos;
        double tokensToAdd = elapsedNanos * refillTokensPerNano;
        if (tokensToAdd > 0) {
            bucket.tokens = Math.min(capacity, bucket.tokens + tokensToAdd);
            bucket.lastRefillNanos = now;
        }
    }
 
    private Instant estimateResetAt(TokenBucket bucket) {
        double tokensNeeded = 1.0 - bucket.tokens;
        long nanosUntilNextToken = (long) (tokensNeeded / refillTokensPerNano);
        return Instant.now().plusNanos(Math.max(0, nanosUntilNextToken));
    }
 
    private static final class TokenBucket {
        double tokens;
        long lastRefillNanos;
        TokenBucket(double tokens, long lastRefillNanos) { this.tokens = tokens; this.lastRefillNanos = lastRefillNanos; }
    }
}

The key trick: no background thread refills the bucket on a timer. Refill is computed lazily, on demand, as elapsedTime × refillRate at the moment of each allow() call — this is what makes the algorithm O(1) per request with zero idle CPU cost, and it's the detail that most distinguishes a correct token-bucket implementation from a naive one.

Leaky bucket — smooths output, never bursts

Leaky bucket is the mirror image: instead of accumulating capacity to permit bursts, it accumulates a "water level" that leaks (drains) at a fixed rate, and a request is rejected if adding it would overflow capacity.

java

public final class LeakyBucketLimiter implements RateLimiter {
    private final double capacity;
    private final double leakPerNano;
    private final Map<String, LeakyBucket> buckets = new ConcurrentHashMap<>();
 
    public LeakyBucketLimiter(double capacity, double leakRatePerSecond) {
        this.capacity = capacity;
        this.leakPerNano = leakRatePerSecond / 1_000_000_000.0;
    }
 
    public RateLimitResult allow(String clientId) {
        LeakyBucket bucket = buckets.computeIfAbsent(clientId, k -> new LeakyBucket(0, System.nanoTime()));
        synchronized (bucket) {
            leak(bucket);
            if (bucket.level + 1.0 <= capacity) {
                bucket.level += 1.0;
                return new RateLimitResult(true, (int) (capacity - bucket.level), Instant.now());
            }
            return new RateLimitResult(false, 0, Instant.now());
        }
    }
 
    private void leak(LeakyBucket bucket) {
        long now = System.nanoTime();
        double leaked = (now - bucket.lastLeakNanos) * leakPerNano;
        bucket.level = Math.max(0, bucket.level - leaked);
        bucket.lastLeakNanos = now;
    }
 
    private static final class LeakyBucket {
        double level;
        long lastLeakNanos;
        LeakyBucket(double level, long lastLeakNanos) { this.level = level; this.lastLeakNanos = lastLeakNanos; }
    }
}

Token bucket vs. leaky bucket, precisely: token bucket controls the rate of admission and explicitly allows saved-up capacity to be spent as a burst. Leaky bucket controls the rate of output and never allows a burst through, regardless of how idle the client was beforehand — it's the right choice when downstream capacity (not just fairness) is the constraint, e.g. queueing requests to a fixed-throughput worker pool.

Distributed rate limiting

A single-process ConcurrentHashMap of buckets works only if all requests for a client land on the same server. Behind a load balancer with N stateless API servers, the limiter state must be centralized:

java

// Redis + Lua for atomicity: read-modify-write must be a single atomic operation,
// since a plain GET-then-SET from the app process is a race across concurrent requests.
public final class RedisTokenBucketLimiter implements RateLimiter {
    private static final String LUA_SCRIPT = """
        local key = KEYS[1]
        local capacity = tonumber(ARGV[1])
        local refillRate = tonumber(ARGV[2])
        local now = tonumber(ARGV[3])
 
        local bucket = redis.call('HMGET', key, 'tokens', 'ts')
        local tokens = tonumber(bucket[1]) or capacity
        local lastTs = tonumber(bucket[2]) or now
 
        tokens = math.min(capacity, tokens + (now - lastTs) * refillRate)
        local allowed = 0
        if tokens >= 1 then
            tokens = tokens - 1
            allowed = 1
        end
 
        redis.call('HMSET', key, 'tokens', tokens, 'ts', now)
        redis.call('EXPIRE', key, 3600)
        return {allowed, tokens}
        """;
 
    private final RedisClient redis;
 
    public RateLimitResult allow(String clientId) {
        // eval() executes the script atomically on the Redis server — no read/write race possible.
        List<Long> result = redis.eval(LUA_SCRIPT, List.of("ratelimit:" + clientId),
            List.of(String.valueOf(100), String.valueOf(10.0), String.valueOf(System.currentTimeMillis() / 1000.0)));
        return new RateLimitResult(result.get(0) == 1, result.get(1).intValue(), Instant.now().plusSeconds(60));
    }
}

The Lua script runs atomically inside Redis's single-threaded event loop, eliminating the check-then-act race that a naive GET + application-side compute + SET would have across concurrent requests from different API server processes.

Edge cases

Clock skew across distributed API servers using local-time-based windows can cause inconsistent enforcement; centralizing on Redis's own TIME command (used inside the Lua script) avoids trusting each server's local clock.
New client with no prior state must default to a full bucket/quota, not zero — otherwise the first request from every new client is incorrectly rejected.
Per-endpoint vs. global limits: a client might have both a global 1000/min limit and a stricter 10/min limit on an expensive endpoint — the gateway should check both and reject on the first that fails.
Negative remaining: display as 0 in headers, never a negative number, even though internal state might momentarily compute it during the window-rollover transition in the sliding-window-counter approach.

7. Trade-offs & Extensions

Algorithm	Memory	Burst handling	Precision
Fixed window	O(1) per client	Allows up to 2x limit at boundaries	Low
Sliding window log	O(limit) per client	Exact, no burst beyond limit	Exact
Sliding window counter	O(1) per client	Small approximation error, smooths boundary issue	Approximate
Token bucket	O(1) per client	Explicitly allows bursts up to bucket capacity	Exact for the model it implements
Leaky bucket	O(1) per client	No bursts ever — strictly smooths output rate	Exact for the model it implements

Natural extensions:

GCRA (Generic Cell Rate Algorithm): a mathematically equivalent, more storage-efficient variant of token bucket used by systems like Cloudflare and Envoy — worth naming for extra credit.
Tiered limits: per-second burst limit and per-day quota simultaneously, both enforced.
Adaptive limits: reduce a client's limit automatically after repeated violations (progressive penalty), or raise it for consistently well-behaved clients.
Response headers: standardize on X-RateLimit-Limit, X-RateLimit-Remaining, X-RateLimit-Reset (or the IETF RateLimit-* draft headers) so client SDKs can back off predictably.

Interview Questions

Walk through the boundary-burst problem in fixed window rate limiting with concrete numbers. How does the sliding window counter approximation fix it without the memory cost of a full log?
Explain the token bucket refill math: why is refilling computed lazily per-request instead of via a background timer thread?
What's the precise difference between token bucket and leaky bucket — not just "one allows bursts," but why, in terms of what each algorithm is modeling?
How would you make a rate limiter behind a load-balanced fleet of API servers give consistent results, given that in-memory per-process state won't be shared?
Why does the Redis-based implementation need a Lua script instead of separate GET/SET calls from the application?
How would you rate-limit both a per-second burst and a per-day quota for the same client, and in what order would you check them?
A new client makes its very first request ever — walk through what the token bucket state should default to, and why getting this wrong would break onboarding.

Design a Cache (LRU/LFU)

Design a Pub-Sub System