Home/Learn/Low Level Design/Design a Rate Limiter

Design a Rate Limiter

Advanced

LLD Interview Problems

Implement multiple rate-limiting algorithms — Token Bucket, Sliding Window, Fixed Window — behind a common interface with thread-safe implementations.

Overview

A Rate Limiter controls request throughput to protect downstream services. Four algorithms are commonly asked: Token Bucket (smooth bursting — tokens refill continuously, extra tokens spill), Fixed Window Counter (simple, but suffers boundary burst), Sliding Window Log (accurate, memory heavy), and Leaky Bucket (strict constant rate, no bursting). Each algorithm is a concrete implementation of the RateLimiter interface with a tryAcquire() method. Strategy pattern selects the algorithm at construction. Decorator chains multiple limiters (e.g., per-user and global). AtomicLong and ConcurrentHashMap ensure thread safety without heavy synchronization.

Requirements Analysis

Functional: allow or deny requests based on rate limit, support per-user and global limits, configurable algorithm, RateLimitResult communicates whether request was allowed and remaining quota. Non-functional: thread-safe under high concurrency, O(1) tryAcquire() for Token Bucket and Fixed Window, composable via Decorator.

Requirements

// Algorithms : TokenBucket, SlidingWindow, FixedWindow, LeakyBucket
// Patterns : Strategy (algorithm selection), Decorator (chaining limiters)

Core Classes & Relationships

RateLimiter interface has tryAcquire(String key). RateLimitResult record holds allowed and remainingTokens. RateLimitConfig holds maxTokens, refillRate, and windowSeconds. TokenBucketRateLimiter uses AtomicLong for thread-safe token tracking per key. SlidingWindowRateLimiter uses ConcurrentHashMap of deques. CompositeRateLimiter chains multiple limiters (Decorator).

Java — enums & interfaces

public interface RateLimiter {
    RateLimitResult tryAcquire(String key);
}

public record RateLimitResult(boolean allowed, long remaining, String algorithm) {}

public class RateLimitConfig {
    public final long maxTokens;
    public final long refillRatePerSecond;
    public final long windowSeconds;

    public RateLimitConfig(long maxTokens, long refillRatePerSecond, long windowSeconds) {
        this.maxTokens = maxTokens;
        this.refillRatePerSecond = refillRatePerSecond;
        this.windowSeconds = windowSeconds;
    }
}

Java Implementation

TokenBucketRateLimiter stores per-key token counts and last-refill timestamp in a ConcurrentHashMap. tryAcquire() computes elapsed seconds, adds new tokens (capped at max), and atomically decrements. SlidingWindowRateLimiter stores a deque of request timestamps per key and evicts entries outside the window. CompositeRateLimiter chains two limiters — both must allow the request.

Java — core classes

import java.util.concurrent.ConcurrentHashMap;
import java.util.concurrent.atomic.AtomicLong;

// ── Token Bucket ─────────────────────────────────────────────────────
public class TokenBucketRateLimiter implements RateLimiter {
    private final RateLimitConfig config;
    private final ConcurrentHashMap<String, long[]> buckets = new ConcurrentHashMap<>();
    // long[0] = current tokens, long[1] = last refill timestamp (ms)

    public TokenBucketRateLimiter(RateLimitConfig config) { this.config = config; }

    @Override
    public synchronized RateLimitResult tryAcquire(String key) {
        long[] bucket = buckets.computeIfAbsent(key,
            k -> new long[]{config.maxTokens, System.currentTimeMillis()});

        long now     = System.currentTimeMillis();
        long elapsed = (now - bucket[1]) / 1000;           // seconds since last refill
        bucket[0]    = Math.min(config.maxTokens, bucket[0] + elapsed * config.refillRatePerSecond);
        bucket[1]    = now;

        if (bucket[0] > 0) {
            bucket[0]--;
            return new RateLimitResult(true, bucket[0], "TOKEN_BUCKET");
        }
        return new RateLimitResult(false, 0, "TOKEN_BUCKET");
    }
}

// ── Sliding Window Log ────────────────────────────────────────────────
public class SlidingWindowRateLimiter implements RateLimiter {
    private final RateLimitConfig config;
    private final ConcurrentHashMap<String, java.util.Deque<Long>> windowLog =
        new ConcurrentHashMap<>();

    public SlidingWindowRateLimiter(RateLimitConfig config) { this.config = config; }

    @Override
    public synchronized RateLimitResult tryAcquire(String key) {
        long now        = System.currentTimeMillis();
        long windowMs   = config.windowSeconds * 1000;
        long cutoff     = now - windowMs;

        java.util.Deque<Long> timestamps = windowLog.computeIfAbsent(
            key, k -> new java.util.ArrayDeque<>());
        while (!timestamps.isEmpty() && timestamps.peekFirst() < cutoff) {
            timestamps.pollFirst();
        }

        if (timestamps.size() < config.maxTokens) {
            timestamps.addLast(now);
            return new RateLimitResult(true, config.maxTokens - timestamps.size(), "SLIDING_WINDOW");
        }
        return new RateLimitResult(false, 0, "SLIDING_WINDOW");
    }
}

// ── Fixed Window Counter ──────────────────────────────────────────────
public class FixedWindowRateLimiter implements RateLimiter {
    private final RateLimitConfig config;
    private final ConcurrentHashMap<String, long[]> windows = new ConcurrentHashMap<>();
    // long[0] = count, long[1] = window start (ms)

    public FixedWindowRateLimiter(RateLimitConfig config) { this.config = config; }

    @Override
    public synchronized RateLimitResult tryAcquire(String key) {
        long now       = System.currentTimeMillis();
        long windowMs  = config.windowSeconds * 1000;
        long[] window  = windows.computeIfAbsent(key, k -> new long[]{0, now});

        if (now - window[1] >= windowMs) { window[0] = 0; window[1] = now; } // new window

        if (window[0] < config.maxTokens) {
            window[0]++;
            return new RateLimitResult(true, config.maxTokens - window[0], "FIXED_WINDOW");
        }
        return new RateLimitResult(false, 0, "FIXED_WINDOW");
    }
}

// ── Composite (Decorator chaining) ────────────────────────────────────
public class CompositeRateLimiter implements RateLimiter {
    private final RateLimiter primary;
    private final RateLimiter secondary;

    public CompositeRateLimiter(RateLimiter primary, RateLimiter secondary) {
        this.primary = primary; this.secondary = secondary;
    }

    @Override
    public RateLimitResult tryAcquire(String key) {
        RateLimitResult r1 = primary.tryAcquire(key);
        if (!r1.allowed()) return r1;
        return secondary.tryAcquire(key);
    }
}

Key Points to Remember

1Token Bucket allows controlled bursting — tokens accumulate up to max capacity, smoothing bursty traffic better than Fixed Window.
2Sliding Window Log is the most accurate algorithm but stores O(requests) timestamps per key — use Fixed Window for memory efficiency at scale.
3Fixed Window suffers the boundary burst problem: a user can make 2× the limit in two seconds straddling a window boundary.
4synchronized on tryAcquire() is simple but limits throughput; production systems use Redis atomic scripts (EVAL) for distributed rate limiting.

Interview Questions

Explain the boundary burst problem with Fixed Window and how Sliding Window solves it.

MediumUber

How would you implement a distributed rate limiter across multiple application servers?

HardGoogle

What are the memory and CPU trade-offs between Token Bucket and Sliding Window Log?

MediumAmazon

Ask Aria about Design a Rate Limiter

Your personal AI tutor — ask anything about this concept

Revision Status

Personal Notes

Discussion

Loading discussion…

Design a Notification System

Design an LRU Cache