Design a Rate Limiter Component in Java (Code-Level)
Fast recall
Quick revision
Core answer
tryAcquire(key) returning (allowed, remaining, retryAfter). Implement two strategies: token bucket (atomic counter with timestamp; refill on each call based on elapsed) and sliding window log (deque of recent timestamps; trim outside window). Index by per-client key (`MapAlgorithm choice (token bucket vs sliding window), atomic update, per-client state, distributed extension, and operational concerns (memory bounds, eviction).
Using `synchronized` blocks on the whole map (contention), no idle-bucket eviction (memory leak), or sliding window log without size cap (memory blow-up under attack).
Compare token bucket / sliding window log / sliding window counter trade-offs, discuss in-process vs distributed enforcement, and walk through atomic update via `compareAndSet` or Lua.
Interview-ready guide
Interview answer
Algorithms
Three to know:
Token bucket — default. Bucket has capacity and refillRate. Each call costs a token. Refill on each call by elapsed * refillRate (capped at capacity). Allows bursts up to capacity, smooth long-term rate, O(1) memory per key.
Sliding window log — strict. Deque of recent timestamps; allow if size < limit; trim entries outside window. Exact accuracy. O(limit) memory per key — prohibitive at scale (limit=10K → 80KB per key).
Sliding window counter — approximate. Two counters: previous + current fixed window; effective rate = previous × (1 - progressInCurrentWindow) + current. O(1) memory. Slight inaccuracy at window boundaries; Cloudflare uses this for 10M+ keys per node.
Default: token bucket for general throttling, sliding-window counter for very-large-scale, sliding-window log for small strict limits.
Token bucket atomic implementation
AtomicReference<State> state; // (tokens, lastRefillNanos)
while (true) {
State cur = state.get();
double refilled = min(capacity, cur.tokens + (now - cur.lastRefill) * refillPerNano);
if (refilled < 1) return false;
if (state.compareAndSet(cur, new State((long)(refilled - 1), now))) return true;
}CAS-based, lock-free. Bounded retry loop — hot keys spin briefly under contention but it's microseconds.
Per-key state
ConcurrentHashMap<String, TokenBucket> buckets.
Memory bound is critical — a million one-shot clients OOM the JVM. Use Caffeine with maximumSize + expireAfterAccess; LRU eviction at cap; TTL for idle keys; lock-free reads; background eviction off the hot path.
Key normalization: sanitize input ('api_key:abc' vs 'apikey-abc') so accidentally different keys don't share state.
Distributed enforcement — Redis + Lua
In-process limiter only enforces per-instance. 10 instances + 100/sec limit → user gets 1000/sec aggregate. Wrong.
Redis Lua script: HMGET tokens + lastMs, compute refill, deduct if allowed, HMSET back, PEXPIRE. The whole sequence is atomic in Redis — multiple instances hitting the same key can't race.
Pre-load script via EVALSHA so we send hash not full body each call.
Fail-open on Redis error: log, trip a circuit breaker, allow the request. Cost of false negatives at the limit is far less than DDoS-style outage from blocking everything.
Tiers and composability
TierResolver maps key → tier (free/pro/enterprise) with (capacity, refillRate). Cache resolution TTL ~30s to avoid per-call DB lookup.
Daily quota = layer a long-window limiter on top of short-window. CompositeRateLimiter ANDs both.
Per-operation cost: tryAcquire(key, cost) overload; expensive ops consume more tokens.
Wait vs reject: tryAcquire non-blocking; acquire(key, timeout) blocks up to timeout for tokens to refill (batch jobs).
LLD
- RateLimiter interface — tryAcquire(key) -> Result(allowed, remaining, retryAfter)
- Implementations: TokenBucketLimiter, SlidingWindowLogLimiter, SlidingWindowCounterLimiter, RedisLimiter
- TierResolver interface for per-plan limits
- BucketStore interface (CaffeineBucketStore, RedisBucketStore) — swappable storage
App code depends on the interface; tests use in-memory with mocked clock; production swaps to Redis-backed for distributed enforcement.
Failure modes
- Hot key contention — CAS retry loop bounded; LongAdder + periodic reconcile if extreme; for distributed, single Redis key serializes (acceptable)
- Map blow-up on attack — Caffeine maxSize evicts oldest
- Clock skew — Redis Lua uses Redis clock (single source); in-process nanoTime is monotonic per instance
- Redis outage — fail-open + circuit breaker for throttling; fail-closed only for security/anti-abuse
- Bucket TTL pitfall — too short = free refill via inactivity; size TTL above expected idle
- Time-based attacks — never trust client timestamp; always server time; sliding window defends against window-boundary 2x burst
Production picks
- Resilience4j RateLimiter — in-process with metrics integration
- Bucket4j — in-process or Hazelcast/Redis backend, multiple algorithms, hierarchical limits
- Both production-grade; prefer either to hand-rolled
Recommendation
RateLimiter interface returning (allowed, remaining, retryAfter). Token bucket as default algorithm with AtomicReference + CAS for atomic in-process update. ConcurrentHashMap or Caffeine for per-key state with bounded size and idle eviction. TierResolver for per-plan limits, cached locally. For multi-instance deployments, swap the in-memory bucket for a Redis + Lua implementation — same interface, atomic check-update via Lua script. Fail-open on Redis errors with a circuit breaker for throttling use cases. Use Resilience4j or Bucket4j in production rather than rolling your own. The interview value is showing you understand the algorithm trade-offs and can layer the same component for both single-process and distributed enforcement.
Design a Rate Limiter Component in Java (Code-Level)
Direct Answer
Define a RateLimiter interface with tryAcquire(key) returning (allowed, remaining, retryAfter). Implement two strategies: token bucket (atomic counter with timestamp; refill on each call based on elapsed) and sliding window log (deque of recent timestamps; trim outside window). Index by per-client key (Map<String, Bucket>) with idle eviction. For distributed enforcement, swap the in-memory state with Redis + Lua script (atomic check-and-update). Compose with TierResolver for per-tier limits. Reach for Resilience4j RateLimiter, Bucket4j, or Guava RateLimiter in production.
Common Mistakes & Pitfalls
Using synchronized blocks on the whole map (contention), no idle-bucket eviction (memory leak), or sliding window log without size cap (memory blow-up under attack).
Check your understanding
Answer these without looking back at the article.
- Walk through the difference in behavior between token bucket and sliding window counter when a client sends 100 requests right at the boundary of a window.
- How do you handle a distributed rate limiter when Redis is in a degraded state?
- Compare your implementation with Resilience4j's RateLimiter API — what does theirs do differently?
- Design a hierarchical rate limit (e.g., per-IP AND per-API-key) where both must allow.
Related interview prep categories
2Want a guided curriculum order?
These modules are also sequenced in our flagship backend interview track — open it when you prefer an ordered path instead of browsing by topic.