LLD Series: Rate Limiter (Low-Level Design)

Overview

1. Problem statement and how it is asked
2. Requirements clarification
3. Entities and class diagram
4. Design patterns and why
5. Code
6. Key flow
7. Extensibility
8. Concurrency and edge cases
9. Follow-ups and model answers
10. Common mistakes and rubric

Part of the Interview Prep series. Dotted-underline words are glossary terms: hover for the meaning or open the Glossary. Track your progress on the Interview Prep tracker. Series index: Start here.

1. Problem statement and how it is asked

"Design a rate limiter that decides whether an incoming request from a user/API key should be allowed. Support multiple algorithms, different limits per user and per API, and make it thread-safe."

Typical phrasing: "Design an API throttler", "Limit 100 req/min per user", "Implement token bucket". Asked at Visa/Mastercard (API gateway protection, card-network throttling), NPCI (UPI PSP throttling per bank/VPA, e.g. balance-check limits), PayU/Amex (merchant API quotas, OTP/login brute-force limits). Expect a 45-60 min machine-coding round with a working demo, followed by "how would you distribute it?".

2. Requirements clarification

Functional

allow(user, api) returns true/false.
Pluggable algorithms: Token Bucket, Fixed Window, Sliding Window Log (Sliding Window Counter discussed as an extension).
Config per user, per API, per (user, API), and a default. Most specific wins.
Independent state for each (user, api) pair.

Non-functional

Thread-safe, low contention (different keys must not block each other); O(1) per check (log variant O(limit) memory).
Deterministic testability: injectable clock.
No background threads required (lazy refill / lazy window reset).

Assumptions / out of scope

Single JVM, in-memory. Distributed (Redis) is a follow-up.
Returns boolean only (no Retry-After, headers, or queueing); easy to extend to a Decision object.
Config is set at startup; hot reload is mentioned but not built. Stale keys are never evicted (mention TTL cleanup).

3. Entities and class diagram

 +-------------------+ uses  +--------------------+ creates +-------------------+
 | RateLimiterService|------>| RateLimiterFactory |-------->| <<interface>>     |
 |-------------------| 1   1 |--------------------|         | RateLimiter       |
 | allow(user, api)  |       | create(config)     |         | +allow(key):bool  |
 | configureUser()   |       +--------------------+         +---------^---------+
 | configureApi()    |                                         |      |       |
 | configureUserApi()|                          +--------------+  +---+----+  +----------------+
 +---------+---------+                          |TokenBucket   |  |FixedWin|  |SlidingWindowLog|
           | resolves                           |Limiter       |  |Limiter |  |Limiter         |
           v                                    +--------------+  +--------+  +----------------+
 +-------------------+  has   +-----------+
 | RateLimitConfig   |------->| Algorithm | (enum)
 | limit, windowMs   |        +-----------+
 +-------------------+
 Per-key state: Bucket{tokens,lastRefill} | Window{start,count} | Deque<timestamp>

4. Design patterns and why

Pattern	Where	Why / rejected alternative
Strategy	`RateLimiter` with 3 impls	Algorithms are interchangeable at runtime per config. Rejected: `if/else` on algorithm inside one class (violates OCP, untestable).
Factory	`RateLimiterFactory`	Service should not know constructors. Could be a `Map<Algorithm, Function<Config,RateLimiter>>` for pure OCP.
Facade	`RateLimiterService`	One entry point hiding config resolution + limiter lookup.
Immutable value object	`RateLimitConfig`	Safe as a `ConcurrentHashMap` key (limiters are shared per config).
Dependency injection of clock	`LongSupplier`	Deterministic tests/demo; avoids `Thread.sleep`.

Algorithm comparison (be ready to state this):

Algorithm	Memory/key	Accuracy	Burst	Note
Token bucket	O(1)	good	allows burst up to capacity, then steady rate	Stripe/AWS style, default choice
Fixed window	O(1)	poor at boundary (2x burst)	yes	simplest
Sliding window log	O(limit)	exact	no	memory heavy for large limits
Sliding window counter	O(1)	approx (weighted prev+curr window)	smoothed	best tradeoff at scale
Leaky bucket	O(1)/queue	smooth output	none	shapes traffic, queue-based

5. Code

Compiled with javac and run on JDK; all files in the default package for easy copy-paste.

RateLimiter.java

/** Strategy: one instance holds state for ALL keys under ONE policy. */
public interface RateLimiter {
    boolean allow(String key);
}

Algorithm.java

public enum Algorithm { TOKEN_BUCKET, FIXED_WINDOW, SLIDING_WINDOW_LOG }

RateLimitConfig.java

import java.util.Objects;

/** Immutable policy: 'limit' requests per 'windowMillis' (bucket capacity = limit, refill = limit/window). */
public final class RateLimitConfig {
    private final Algorithm algorithm;
    private final int limit;
    private final long windowMillis;

    public RateLimitConfig(Algorithm algorithm, int limit, long windowMillis) {
        if (limit <= 0 || windowMillis <= 0) throw new IllegalArgumentException("limit/window must be > 0");
        this.algorithm = Objects.requireNonNull(algorithm);
        this.limit = limit;
        this.windowMillis = windowMillis;
    }
    public Algorithm algorithm() { return algorithm; }
    public int limit() { return limit; }
    public long windowMillis() { return windowMillis; }
    @Override public boolean equals(Object o) {
        if (!(o instanceof RateLimitConfig)) return false;
        RateLimitConfig c = (RateLimitConfig) o;
        return algorithm == c.algorithm && limit == c.limit && windowMillis == c.windowMillis;
    }
    @Override public int hashCode() { return Objects.hash(algorithm, limit, windowMillis); }
    @Override public String toString() { return algorithm + "(" + limit + "/" + windowMillis + "ms)"; }
}

TokenBucketLimiter.java

import java.util.concurrent.ConcurrentHashMap;
import java.util.function.LongSupplier;

/** Lazy refill: no timer threads. Lock per bucket (per key) -> keys never contend with each other. */
public class TokenBucketLimiter implements RateLimiter {
    private static final class Bucket {
        double tokens;
        long lastRefillMs;
        Bucket(double t, long ts) { tokens = t; lastRefillMs = ts; }
    }
    private final int capacity;
    private final double refillPerMs;
    private final LongSupplier clock;
    private final ConcurrentHashMap<String, Bucket> buckets = new ConcurrentHashMap<>();

    public TokenBucketLimiter(int capacity, long windowMillis, LongSupplier clock) {
        this.capacity = capacity;
        this.refillPerMs = (double) capacity / windowMillis;
        this.clock = clock;
    }

    @Override public boolean allow(String key) {
        long now = clock.getAsLong();
        Bucket b = buckets.computeIfAbsent(key, k -> new Bucket(capacity, now));
        synchronized (b) {
            long elapsed = Math.max(0, now - b.lastRefillMs);
            b.tokens = Math.min(capacity, b.tokens + elapsed * refillPerMs);
            b.lastRefillMs = now;
            if (b.tokens >= 1.0) { b.tokens -= 1.0; return true; }
            return false;
        }
    }
}

FixedWindowLimiter.java

import java.util.concurrent.ConcurrentHashMap;
import java.util.function.LongSupplier;

/** Counter per aligned window. Cheap (O(1) memory/key) but allows 2x burst at window boundary. */
public class FixedWindowLimiter implements RateLimiter {
    private static final class Window { long start; int count; }
    private final int limit;
    private final long windowMs;
    private final LongSupplier clock;
    private final ConcurrentHashMap<String, Window> windows = new ConcurrentHashMap<>();

    public FixedWindowLimiter(int limit, long windowMs, LongSupplier clock) {
        this.limit = limit; this.windowMs = windowMs; this.clock = clock;
    }

    @Override public boolean allow(String key) {
        long now = clock.getAsLong();
        long start = now - (now % windowMs);
        Window w = windows.computeIfAbsent(key, k -> new Window());
        synchronized (w) {
            if (w.start != start) { w.start = start; w.count = 0; }
            if (w.count < limit) { w.count++; return true; }
            return false;
        }
    }
}

SlidingWindowLogLimiter.java

import java.util.ArrayDeque;
import java.util.Deque;
import java.util.concurrent.ConcurrentHashMap;
import java.util.function.LongSupplier;

/** Exact: stores timestamps of accepted requests. O(limit) memory/key. */
public class SlidingWindowLogLimiter implements RateLimiter {
    private final int limit;
    private final long windowMs;
    private final LongSupplier clock;
    private final ConcurrentHashMap<String, Deque<Long>> logs = new ConcurrentHashMap<>();

    public SlidingWindowLogLimiter(int limit, long windowMs, LongSupplier clock) {
        this.limit = limit; this.windowMs = windowMs; this.clock = clock;
    }

    @Override public boolean allow(String key) {
        long now = clock.getAsLong();
        Deque<Long> log = logs.computeIfAbsent(key, k -> new ArrayDeque<>());
        synchronized (log) {
            while (!log.isEmpty() && log.peekFirst() <= now - windowMs) log.pollFirst();
            if (log.size() < limit) { log.addLast(now); return true; }
            return false;
        }
    }
}

RateLimiterFactory.java

import java.util.function.LongSupplier;

/** Factory: maps config -> strategy. Add an algorithm = add enum value + case (or register in a Map for pure OCP). */
public final class RateLimiterFactory {
    private final LongSupplier clock;
    public RateLimiterFactory(LongSupplier clock) { this.clock = clock; }

    public RateLimiter create(RateLimitConfig c) {
        switch (c.algorithm()) {
            case TOKEN_BUCKET:       return new TokenBucketLimiter(c.limit(), c.windowMillis(), clock);
            case FIXED_WINDOW:       return new FixedWindowLimiter(c.limit(), c.windowMillis(), clock);
            case SLIDING_WINDOW_LOG: return new SlidingWindowLogLimiter(c.limit(), c.windowMillis(), clock);
            default: throw new IllegalArgumentException("Unknown " + c.algorithm());
        }
    }
}

RateLimiterService.java

import java.util.concurrent.ConcurrentHashMap;

/**
 * Facade. Config resolution order: (user,api) > api > user > default.
 * One RateLimiter instance per distinct config is shared by all keys that use it;
 * the counter key is "<user>|<api>" so every (user, api) pair has independent state.
 */
public class RateLimiterService {
    private final RateLimiterFactory factory;
    private final RateLimitConfig defaultConfig;
    private final ConcurrentHashMap<String, RateLimitConfig> overrides = new ConcurrentHashMap<>();
    private final ConcurrentHashMap<RateLimitConfig, RateLimiter> limiters = new ConcurrentHashMap<>();

    public RateLimiterService(RateLimiterFactory factory, RateLimitConfig defaultConfig) {
        this.factory = factory; this.defaultConfig = defaultConfig;
    }
    public void configureUser(String user, RateLimitConfig c)            { overrides.put("U:" + user, c); }
    public void configureApi(String api, RateLimitConfig c)              { overrides.put("A:" + api, c); }
    public void configureUserApi(String user, String api, RateLimitConfig c) { overrides.put("UA:" + user + "|" + api, c); }

    public boolean allow(String user, String api) {
        RateLimitConfig c = resolve(user, api);
        RateLimiter l = limiters.computeIfAbsent(c, factory::create);
        return l.allow(user + "|" + api);
    }

    RateLimitConfig resolve(String user, String api) {
        RateLimitConfig c = overrides.get("UA:" + user + "|" + api);
        if (c == null) c = overrides.get("A:" + api);
        if (c == null) c = overrides.get("U:" + user);
        return c != null ? c : defaultConfig;
    }
}

Main.java

import java.util.concurrent.*;
import java.util.concurrent.atomic.*;

public class Main {
    static final AtomicLong now = new AtomicLong(0);   // fake clock => deterministic demo

    static String run(RateLimiterService s, String u, String api, int n) {
        StringBuilder sb = new StringBuilder();
        for (int i = 0; i < n; i++) sb.append(s.allow(u, api) ? 'Y' : 'N');
        return sb.toString();
    }

    public static void main(String[] args) throws Exception {
        RateLimiterFactory f = new RateLimiterFactory(now::get);
        RateLimiterService svc = new RateLimiterService(f, new RateLimitConfig(Algorithm.FIXED_WINDOW, 3, 1000));
        svc.configureApi("search", new RateLimitConfig(Algorithm.TOKEN_BUCKET, 5, 1000));       // 5 tokens, 5/s refill
        svc.configureUser("premium", new RateLimitConfig(Algorithm.SLIDING_WINDOW_LOG, 4, 1000));
        svc.configureUserApi("premium", "pay", new RateLimitConfig(Algorithm.TOKEN_BUCKET, 2, 1000));

        System.out.println("-- default fixed window 3/s, alice@/home: " + run(svc, "alice", "home", 5));
        System.out.println("-- bob is independent of alice:            " + run(svc, "bob", "home", 4));

        System.out.println("-- token bucket search 5 cap, burst of 7:  " + run(svc, "alice", "search", 7));
        now.addAndGet(400);  // refill 2 tokens
        System.out.println("   +400ms (2 tokens refilled), 3 calls:    " + run(svc, "alice", "search", 3));

        System.out.println("-- fixed window boundary burst (3/s):");
        now.set(10_900); System.out.println("   t=10900: " + run(svc, "carl", "home", 3));
        now.set(11_050); System.out.println("   t=11050: " + run(svc, "carl", "home", 3) + "  (6 allowed within 150ms: known flaw)");

        System.out.println("-- sliding log premium 4/s:");
        now.set(20_000); System.out.println("   t=20000: " + run(svc, "premium", "feed", 5));
        now.set(20_900); System.out.println("   t=20900: " + run(svc, "premium", "feed", 1));
        now.set(21_001); System.out.println("   t=21001: " + run(svc, "premium", "feed", 5) + "  (first 4 expired)");

        System.out.println("-- user+api override premium/pay (token bucket 2): " + run(svc, "premium", "pay", 3));

        // concurrency: 1000 threads-calls on one key, limit 100 => exactly 100 allowed
        now.set(100_000);
        RateLimiterService cs = new RateLimiterService(f, new RateLimitConfig(Algorithm.SLIDING_WINDOW_LOG, 100, 60_000));
        ExecutorService ex = Executors.newFixedThreadPool(16);
        AtomicInteger ok = new AtomicInteger();
        CountDownLatch done = new CountDownLatch(1000);
        for (int i = 0; i < 1000; i++) ex.submit(() -> { if (cs.allow("u", "api")) ok.incrementAndGet(); done.countDown(); });
        done.await(); ex.shutdown();
        System.out.println("-- concurrent: 1000 requests, limit 100 -> allowed = " + ok.get());
    }
}

Real output (javac -d out *.java && java -cp out Main)

-- default fixed window 3/s, alice@/home: YYYNN
-- bob is independent of alice:            YYYN
-- token bucket search 5 cap, burst of 7:  YYYYYNN
   +400ms (2 tokens refilled), 3 calls:    YYN
-- fixed window boundary burst (3/s):
   t=10900: YYY
   t=11050: YYY  (6 allowed within 150ms: known flaw)
-- sliding log premium 4/s:
   t=20000: YYYYN
   t=20900: N
   t=21001: YYYYN  (first 4 expired)
-- user+api override premium/pay (token bucket 2): YYN
-- concurrent: 1000 requests, limit 100 -> allowed = 100

Locking granularity. ConcurrentHashMap.computeIfAbsent creates per-key state atomically; then synchronized(state) guards the read-modify-write on that single key. Locks are per key, so users never contend with each other; a global lock would serialize every request. Rejected: AtomicInteger alone (check-then-act race between window reset and increment); AtomicLong CAS loops are possible for token bucket (pack tokens+timestamp) but harder to explain in an interview.

6. Key flow

Client -> Service.allow("alice","search")
  Service: resolve(user,api): (alice|search)? -> api:search? -> user:alice? -> default
           => TOKEN_BUCKET(5/1000ms)
  Service: limiters.computeIfAbsent(config, factory::create)   // one limiter per policy
  Limiter: key="alice|search"; bucket = computeIfAbsent(...)
           synchronized(bucket):
              tokens = min(cap, tokens + elapsed*rate); lastRefill = now
              tokens>=1 ? tokens-- , return true : return false
  <- true/false  (caller maps false to HTTP 429)

7. Extensibility

New algorithm (Sliding Window Counter, Leaky Bucket): new class implementing RateLimiter, add an enum value and one factory case. Service untouched.
New dimension (per IP, per tenant): the key is just a string; add configureXxx or generalize to a KeyResolver/Rule list (first matching rule wins).
Rich result: change boolean to Decision{allowed, remaining, retryAfterMs} for response headers (X-RateLimit-Remaining).
Composite limits (10/s AND 1000/day): CompositeRateLimiter implements RateLimiter (Composite pattern) that ANDs children; roll back tokens on partial failure.

8. Concurrency and edge cases

Check-then-act race: solved by per-key monitor. Demo proves exactly 100/1000 allowed under 16 threads.
Clock going backwards: Math.max(0, elapsed) in token bucket. Use System.nanoTime() (monotonic) in production, not wall clock.
Floating-point tokens: fine for refill; alternative is integer micro-tokens to avoid drift.
Fixed-window boundary burst: demonstrated in output (6 allowed in 150 ms).
Memory leak: idle keys stay forever. Fix with Caffeine/expiring map or periodic sweep of buckets idle > window (a full bucket is equivalent to no bucket).
Config change at runtime: existing limiters keyed by config keep their state; new config gets a fresh limiter (state reset). Mention as a trade-off.
Invalid config (limit <= 0) rejected in constructor. null user: treat as anonymous/IP key.
Fail-open vs fail-closed when the limiter store (Redis) is down: payments usually fail-closed on security limits (OTP), fail-open on availability limits.

9. Follow-ups and model answers

Q: Make it distributed. Centralize state in Redis, keyed per (user,api). Token bucket in a Lua script (atomic: read tokens+ts, refill, decrement, write with EXPIRE) so one round trip and no race. Sliding window via sorted set (ZREMRANGEBYSCORE, ZCARD, ZADD) in Lua, or the counter approximation with two INCR keys. To cut latency: local token cache that leases N tokens from Redis in batches (accepts slight over-admission), or shard by key via consistent hashing to a limiter service. Discuss Redis failure mode and clock skew (use Redis TIME).

Q: Persist it? Rate state is ephemeral; persist only the config (DB + pub/sub or polling to refresh). Losing counters on restart is acceptable (briefly permissive).

Q: Why token bucket over sliding window? O(1) memory, supports controlled bursts, easy to reason about refill rate. Sliding log is exact but O(limit) memory per user.

Q: Hot key / one user with a huge limit? Per-key lock is still short (O(1)); for sliding log use a ring buffer of longs. For extreme rates, use striped counters or the approximate counter.

Q: How do you test time-based logic? Injected clock (as demoed), never sleep.

Q: Where to place it? API gateway/filter/interceptor (before business logic), plus sidecar (Envoy) for service mesh.

Complexity: token bucket / fixed window allow O(1) time, O(1) space per key; sliding log amortized O(1) time (each timestamp added/removed once), O(limit) space per key. Config resolve: 3 hash lookups.

10. Common mistakes and rubric

Red flags

Single synchronized method / global lock for all users.
AtomicInteger incremented separately from window reset (race).
Thread.sleep/scheduler thread refilling every bucket (does not scale; use lazy refill).
if (algo == ...) ladders instead of Strategy; new Date() hard-wired (untestable).
Not explaining fixed-window 2x burst; ignoring memory growth.
Using HashMap and containsKey then put (non-atomic).

Mini rubric (10 pts): requirements/clarify (1), clean Strategy+Factory (2), correct token bucket (2), thread-safety with right granularity (2), per-user/API config resolution (1), tests/demo with injected clock (1), distributed discussion (1).

Previous Blog← What to Prepare Before Hiring a Developer for a SaaS MVP

Next BlogLLD Series: LRU / LFU Cache (Low-Level Design) →