Design a Rate Limiter (LLD)
Token bucket, leaky bucket, and sliding window as interchangeable strategies behind one thread-safe interface.
Problem Statement
Design the object model for an in-memory rate limiter that decides whether a request from a client should be allowed or rejected.
The design must keep the public API small, keep mutable state isolated per client, and make the limiting algorithm pluggable. The target algorithm family includes fixed window, sliding window log, sliding window counter, token bucket, and leaky bucket. The provided reference implementation demonstrates the core Strategy seam with TokenBucketRateLimiter and SlidingWindowRateLimiter.
This is the object-design view of rate limiting. Stay inside one service process: no Redis, no distributed counters, no gateway routing, and no cross-region consistency problem.
Business context
Rate limiting appears in API gateways, SaaS tenant throttling, login protection, webhooks, and internal platform quotas. Interviewers use it as an advanced LLD problem because it combines algorithm tradeoffs with object boundaries: Strategy for algorithms, a factory for construction, a shared configured limiter instance, and careful thread-safety around per-client mutable state.
A strong answer does not jump straight to a distributed cache. It first shows that the candidate can model RateLimiter, RateLimitConfig, per-client state, and a construction seam cleanly enough that new algorithms can be added without changing callers.
Functional Requirements
Expose a single decision API: allow or reject a request for a given client id.
Maintain independent rate-limit state for each client key.
Support algorithms behind a common strategy interface: fixed window, sliding window log, sliding window counter, token bucket, and leaky bucket.
Provide a factory that builds the correct limiter from an algorithm choice and configuration.
Support configurable capacity, refill rate, request window, and maximum requests.
Make request decisions thread safe when multiple threads call the same limiter.
Create per-client state lazily when the first request from that client arrives.
Keep callers unaware of algorithm-specific state such as token counts or timestamp logs.
Non-Functional Requirements
Thread-safety
Two concurrent requests for the same client must not both pass by racing on the same bucket or timestamp deque. Different clients should still proceed in parallel.
Extensibility
A new algorithm should be a new RateLimiter implementation plus a factory case, not a rewrite of application code.
Per-client isolation
Client A exhausting its quota must not affect Client B because their mutable state lives in different map entries.
Low latency
The hot path should do only a map lookup, a small synchronized state update, and a constant or window-bounded calculation.
Memory discipline
Timestamp-based strategies can grow with recent traffic; the design should make state ownership clear so cleanup and eviction can be added.
Requirement Clarification
QIs this an in-process limiter or a distributed limiter?
Assume one service instance and in-memory state. Distributed counters, Redis, sharding, and replication are HLD extensions, not part of this LLD scope.
QWhat identifies a client?
A String clientId is enough for the base design. In production it might be an API key, tenant id, user id, IP address, or a composite key.
QShould rejection include retry metadata?
The reference API returns a boolean to keep the core object model focused. A richer result object with retry-after and remaining-quota fields is an easy extension.
QDo all algorithms need exact fairness?
No. Sliding window log is exact but can store many timestamps. Token bucket allows bursts. Fixed window is simple but has boundary spikes. Sliding counter smooths boundaries approximately. Leaky bucket smooths output rate.
QCan limits change while the process is running?
The reference RateLimitConfig is immutable. Dynamic config can be layered later with a config provider or by swapping the shared limiter instance at the composition root.
UML Class Diagram
Sequence Diagram
Entity Identification
RateLimiter
Strategy interface. It defines the only operation the application needs: allowRequest(clientId).
RateLimitConfig
Immutable configuration object carrying all tuning knobs used by the concrete algorithms. It validates that capacity, refill rate, window, and request limit are positive.
TokenBucket
Per-client mutable state for token bucket limiting. It refills from elapsed nanoseconds, caps tokens at capacity, and atomically consumes one token when available.
TokenBucketRateLimiter
Concrete RateLimiter strategy for burst-friendly limits. It stores a concurrent map from client id to TokenBucket and delegates the critical update to the bucket.
SlidingWindowRateLimiter
Concrete RateLimiter strategy for exact sliding windows. It stores a recent timestamp deque per client, prunes expired entries, and appends the current request only when under limit.
RateLimiterFactory
Creation boundary. It maps Algorithm values to concrete RateLimiter implementations so callers never directly choose constructors.
Design Patterns Used
RateLimiter is the strategy interface. TokenBucketRateLimiter and SlidingWindowRateLimiter implement different algorithms behind the same method, and fixed window, sliding counter, or leaky bucket can be added the same way.
RateLimiterFactory.create centralizes algorithm selection. Application code asks for an algorithm by enum and receives a RateLimiter, keeping constructors and switch logic out of callers.
A service should share one configured limiter instance per quota policy so per-client maps are not fragmented. The reference factory is stateless with a private constructor; in a larger app the composition root or provider exposes the selected limiter as a singleton.
Step-by-Step Design
1Define the stable strategy interface
The caller should not know if the active algorithm is token bucket, sliding log, fixed window, sliding counter, or leaky bucket. One boolean method keeps integration narrow.
public interface RateLimiter { boolean allowRequest(String clientId); }2Capture algorithm knobs in an immutable config
RateLimitConfig holds capacity, refill rate, window length, and max requests. Validating once at construction keeps every strategy from repeating defensive checks.
public RateLimitConfig(int capacity, double refillPerSecond, long windowMillis, int maxRequests) { if (capacity <= 0 || refillPerSecond <= 0 || windowMillis <= 0 || maxRequests <= 0) { throw new IllegalArgumentException("Rate limit values must be positive"); } this.capacity = capacity; this.refillPerSecond = refillPerSecond; this.windowMillis = windowMillis; this.maxRequests = maxRequests; }3Model token bucket state per client
TokenBucket owns the mutable token count for one client. tryConsume is synchronized, so refill and decrement happen as one critical section.
public synchronized boolean tryConsume() { refill(); if (tokens < 1.0) { return false; } tokens -= 1.0; return true; }4Use a concurrent map for lazy client state
TokenBucketRateLimiter uses ConcurrentHashMap.computeIfAbsent so client buckets are created only when needed and different clients can be looked up concurrently.
public boolean allowRequest(String clientId) { TokenBucket bucket = buckets.computeIfAbsent( clientId, key -> new TokenBucket(config.getCapacity(), config.getRefillPerSecond()) ); return bucket.tryConsume(); }5Implement exact sliding window with a per-client deque
SlidingWindowRateLimiter removes timestamps outside the current window, checks the deque size, and appends the current timestamp only when the client is still under quota.
synchronized (clientLog) { long cutoff = now - config.getWindowMillis(); while (!clientLog.isEmpty() && clientLog.peekFirst() <= cutoff) { clientLog.removeFirst(); } if (clientLog.size() >= config.getMaxRequests()) { return false; } clientLog.addLast(now); return true; }6Keep algorithm selection in the factory
RateLimiterFactory maps an enum to a concrete strategy. Adding fixed window, sliding window counter, or leaky bucket means adding a new implementation and a new enum case.
public static RateLimiter create(Algorithm algorithm, RateLimitConfig config) { switch (algorithm) { case TOKEN_BUCKET: return new TokenBucketRateLimiter(config); case SLIDING_WINDOW_LOG: return new SlidingWindowRateLimiter(config); default: throw new IllegalArgumentException("Unknown algorithm: " + algorithm); } }
Complete Java Implementation
Explanation of Every Class
RateLimiter
The strategy interface. It keeps every caller dependent on allowRequest(String) rather than on a specific algorithm, which is the core seam for plugging in more limiters.
RateLimitConfig
Immutable value object for algorithm tuning. It validates that all numeric limits are positive and exposes read-only getters for capacity, refill rate, window size, and max requests.
TokenBucket
Per-client token state. It starts full, computes refill from elapsed nanoseconds, caps tokens at capacity, and synchronizes tryConsume so no two threads overspend the same token.
TokenBucketRateLimiter
Concrete burst-friendly strategy. It stores ConcurrentMap<String, TokenBucket> conceptually as client id to bucket, creates buckets lazily, and delegates the critical decision to the bucket.
SlidingWindowRateLimiter
Concrete exact-window strategy. It stores a timestamp deque per client, synchronizes on that deque, prunes expired timestamps, checks maxRequests, and records the allowed request.
RateLimiterFactory
Static construction boundary with a private constructor and nested Algorithm enum. It returns TokenBucketRateLimiter or SlidingWindowRateLimiter based on the selected algorithm.
Dry Run
Sample input
Token bucket config: capacity 3, refill 1 token/sec. Client A sends four immediate requests, Client B sends one request, then Client A retries after two seconds.
| Step | Time | Client | State before | Decision | State after |
|---|---|---|---|---|---|
| 1 | t=0 | A | 3.0 tokens | Allow | 2.0 tokens |
| 2 | t=0 | A | 2.0 tokens | Allow | 1.0 tokens |
| 3 | t=0 | A | 1.0 tokens | Allow | 0.0 tokens |
| 4 | t=0 | A | 0.0 tokens | Reject | 0.0 tokens |
| 5 | t=0 | B | new bucket with 3.0 tokens | Allow | B has 2.0 tokens |
| 6 | t=2s | A | refills to 2.0 tokens | Allow | 1.0 token |
Client A and Client B do not share quota. A is rejected only after its own bucket is empty, while B receives a fresh bucket. The retry after two seconds shows elapsed-time refill before consumption.
Complexity Analysis
| Operation | Time | Space | Note |
|---|---|---|---|
| TokenBucketRateLimiter.allowRequest | O(1) | O(C) | C is number of active clients; each client stores one TokenBucket. |
| SlidingWindowRateLimiter.allowRequest | O(E) | O(C × R) | E expired timestamps may be pruned; R is max requests retained per active client window. |
| RateLimiterFactory.create | O(1) | O(1) | Switches on the enum and returns one concrete strategy instance. |
| Adding a new strategy | O(1) caller impact | Strategy-specific | Callers stay unchanged because they depend on RateLimiter. |
Token bucket is constant-time per request and memory-light. Sliding window log is exact but can spend time pruning and stores recent timestamps. Fixed window and sliding counter reduce storage, while leaky bucket smooths throughput with queue-like state.
Extensibility
Fixed window strategy
Add a FixedWindowRateLimiter with per-client window start and count. It is simple and memory-light but allows bursts at window boundaries.
Sliding window counter strategy
Add current and previous window counters per client, then weight the previous count by overlap. This lowers memory versus a full timestamp log.
Leaky bucket strategy
Add a per-client queue or next-allowed-time state that drains at a constant rate. This smooths output rather than allowing token-bucket bursts.
Richer decision response
Replace boolean with RateLimitResult containing allowed, remaining, reset time, and retry-after. Existing strategies can compute those fields from their state.
Client state cleanup
Introduce last-access timestamps and a background eviction policy so maps do not retain inactive clients forever.
Alternative Designs
Fixed window counter
Store windowStart and count for each client. Reset the count when the current time crosses the window boundary.
Tradeoffs
Very fast and tiny memory footprint, but a client can send nearly two windows worth of requests around a boundary.
Sliding window counter
Store counts for current and previous windows, then estimate usage as current count plus previous count weighted by overlap.
Tradeoffs
Smoother than fixed window and much smaller than sliding log, but it is approximate rather than exact.
Leaky bucket queue
Model each client as a queue drained at a fixed rate or as a next-allowed timestamp. Requests are accepted only if the queue is not full.
Tradeoffs
Excellent for smoothing traffic, but less natural when the product explicitly wants burst capacity.
Global synchronized limiter
Synchronize the entire allowRequest method and keep one map for all client state.
Tradeoffs
Easiest to reason about, but all clients contend on one monitor, so unrelated tenants block one another.
Common Mistakes
- ×
Putting every algorithm in one giant if or switch inside a single limiter class instead of using Strategy.
- ×
Using a plain HashMap for client state while multiple threads call allowRequest.
- ×
Synchronizing the entire limiter and accidentally serializing all clients.
- ×
Sharing one TokenBucket across all clients, turning a per-client limit into a global limit.
- ×
Forgetting to prune old timestamps in the sliding window log before checking size.
- ×
Letting the factory return different limiter instances for the same policy on every request, fragmenting state.
- ×
Claiming token bucket and leaky bucket are identical; one permits bursts up to capacity, the other smooths output.
Follow-up Interview Questions
QHow would you add fixed window without changing callers?
Create FixedWindowRateLimiter implements RateLimiter, keep per-client count and window start, add a FIXED_WINDOW enum value, and add one factory case.
QWhy synchronize on the bucket or deque instead of the whole limiter?
Only requests for the same client compete for the same mutable state. Per-client locking preserves correctness while allowing different clients to proceed concurrently.
QHow do you prevent client maps from growing forever?
Track last-access time in each client state and periodically evict entries that are idle beyond a retention window. The state owner makes this extension straightforward.
QWhen would you choose sliding window log over token bucket?
Choose sliding window log when exact count within the last N milliseconds matters more than memory. Choose token bucket when burst tolerance and constant-time decisions matter more.
QWhere does Singleton fit without hiding dependencies?
Keep construction explicit at startup, then share one configured RateLimiter instance per policy through dependency injection or a provider. Avoid a hard global that tests cannot replace.
Production Considerations
Clock control
Inject a clock for deterministic tests and consistent time calculations. The reference uses system time directly to keep the practice code compact.
State lifecycle
Add idle-client eviction, maximum map size, and metrics around active client count so abusive or forgotten client ids do not leak memory.
Observability
Emit allow count, reject count, decision latency, active clients, and per-policy saturation. These metrics reveal whether limits are too strict or too loose.
Configuration rollout
Treat config as a versioned policy. If limits change, decide whether existing client state is migrated, reset, or allowed to drain naturally.
Boundary behavior
Document each algorithm's fairness tradeoff. Fixed windows have boundary spikes; token bucket has bursts; sliding log is exact but memory-heavy.
What Interviewers Look For
Did the candidate separate the stable RateLimiter API from algorithm-specific state?
Can they explain why per-client state needs synchronization even when the map is concurrent?
Do they know the tradeoffs among fixed window, sliding log, sliding counter, token bucket, and leaky bucket?
Is the factory used as a construction boundary rather than scattered constructor calls?
Do they understand why one shared configured limiter instance matters for consistent quota state?
Can they keep the discussion at LLD scope and avoid jumping to distributed storage too early?
Quiz
0/5 answered
1.Why does the design make **RateLimiter** an interface?
2.What does **ConcurrentHashMap** protect in the reference design?
3.Why is **TokenBucket.tryConsume** synchronized?
4.Which algorithm is exact but can store many timestamps per active client?
5.What is the main risk of creating a new limiter instance for every request?
Practice Variants
Add **FixedWindowRateLimiter**
BeginnerImplement per-client window start and count, add FIXED_WINDOW to the factory enum, and document the boundary-burst tradeoff.
Return rich limit results
IntermediateReplace boolean with a result object that includes allowed, remaining quota, retry-after millis, and reset time without breaking strategy boundaries.
Inject a test clock
IntermediateRefactor both token bucket and sliding window strategies to use an injected clock so tests can advance time deterministically.
Add idle-client eviction
AdvancedTrack last access on each client state and evict idle entries safely without blocking the hot path for all clients.
Flashcards
Cheat Sheet
Core API: RateLimiter.allowRequest(clientId) returns allow or reject.
Reference classes: RateLimiter, RateLimitConfig, TokenBucket, TokenBucketRateLimiter, SlidingWindowRateLimiter, RateLimiterFactory.
Patterns: Strategy for algorithms; Factory Method for construction; Singleton at composition root for one shared configured limiter per policy.
Thread-safety: ConcurrentHashMap for per-client state lookup; synchronize the bucket or deque for same-client mutation.
Algorithm tradeoffs: fixed window is simple but spiky; sliding log is exact but memory-heavy; sliding counter is approximate; token bucket allows bursts; leaky bucket smooths output.
Complexity: token bucket O(1) per request; sliding log O(E) prune work; memory grows with active clients and retained per-client state.
Extensions: add new strategies behind RateLimiter, expand Algorithm enum, enrich decision result, inject clock, evict idle clients.
References
- BookDesign Patterns: Elements of Reusable Object-Oriented Software — Gamma, Helm, Johnson, Vlissides
- BookEffective Java — Item 34 Enums and Item 78 Synchronize Access to Shared Mutable Data — Joshua Bloch
- DocsRefactoring Guru — Strategy Pattern
- DocsJava Platform Docs — ConcurrentHashMap — Oracle