What you’re building
01In-memory
Single process
02Per endpoint
Own algorithm
03Per client
Quota key
04Result
allow · remaining · retry
A rate limiter decides whether a client may call an API within a window. Under quota → proceed; over → reject. This LLD is an in-memory gateway component that enforces rules loaded from config — not a distributed Redis limiter (see distributed design for that).
Analogy: nightclub bouncer
A rate limiter is the bouncer with a clicker (token bucket) or a guest list for the last minute (sliding window). Two requests for the same guest id must not both sneak past because they checked the clicker at the same instant — lock the clicker.
Clarifying questions → locked requirements
- algoConfig shape? → Heterogeneous — params differ by algorithm.
- Request shape? →
(clientId, endpoint)strings. - Return? → Structured: allowed, remaining, retryAfterMs (null if allowed).
- Unknown endpoint? → Fall back to a default limiter — don’t reject bare.
- Concurrency? → “Start without it; we’ll return if time” → plan for per-key locks.
- Distributed? → No — single process, in-memory.
- Config lifecycle? → Loaded once at startup (hot-reload is an extension).
Entities
- RateLimiter — facade: endpoint → Limiter map + defaultLimiter.
- Limiter (interface) —
allow(key) → RateLimitResult; TokenBucket / SlidingWindowLog implement it. - LimiterFactory — config discriminator → concrete Limiter.
- RateLimitResult — allowed, remaining, retryAfterMs (nullable).
- Not classes: Request, Client, Endpoint — strings / params.
Class design
class RateLimiter:
- limiters: dict[str, Limiter] # endpoint → algorithm instance
- default_limiter: Limiter
+ RateLimiter(configs, default_config)
+ allow(client_id, endpoint) -> RateLimitResult
class LimiterFactory:
+ create(config) -> Limiter # switch on algorithm
class Limiter(Protocol):
+ allow(key: str) -> RateLimitResult
class RateLimitResult:
- allowed: bool
- remaining: int
- retry_after_ms: int | None # None when allowedclass RateLimiter {
// Map<String, Limiter> limiters; // endpoint → algorithm instance
// Limiter defaultLimiter;
// RateLimiter(List<Config> configs, Config defaultConfig)
// RateLimitResult allow(String clientId, String endpoint)
}
interface LimiterFactory {
Limiter create(Config config); // switch on algorithm
}
interface Limiter {
RateLimitResult allow(String key);
}
class RateLimitResult {
final boolean allowed;
final int remaining;
final Integer retryAfterMs; // null when allowed
RateLimitResult(boolean allowed, int remaining, Integer retryAfterMs) {
this.allowed = allowed; this.remaining = remaining; this.retryAfterMs = retryAfterMs;
}
}Factory + Strategy: heterogeneous startup config picks an algorithm; RateLimiter only looks up and delegates. Don’t add
getConfig / updateConfig unless asked (YAGNI).Factory and RateLimiter
def create(self, external_config: dict) -> Limiter:
algorithm = external_config["algorithm"]
cfg = external_config["algoConfig"]
if algorithm == "TokenBucket":
return TokenBucketLimiter(cfg["capacity"], cfg["refillRatePerSecond"])
if algorithm == "SlidingWindowLog":
return SlidingWindowLogLimiter(cfg["maxRequests"], cfg["windowMs"])
raise ValueError(f"unknown algorithm: {algorithm}")
class RateLimiter:
def __init__(self, configs: list[dict], default_config: dict):
factory = LimiterFactory()
self._limiters = {
c["endpoint"]: factory.create(c) for c in configs if c.get("endpoint")
}
self._default = factory.create(default_config) # eager at startup
def allow(self, client_id: str, endpoint: str) -> RateLimitResult:
limiter = self._limiters.get(endpoint, self._default)
return limiter.allow(client_id)Limiter create(Map<String, Object> externalConfig) {
String algorithm = (String) externalConfig.get("algorithm");
@SuppressWarnings("unchecked")
Map<String, Object> cfg = (Map<String, Object>) externalConfig.get("algoConfig");
if ("TokenBucket".equals(algorithm)) {
return new TokenBucketLimiter(
((Number) cfg.get("capacity")).intValue(),
((Number) cfg.get("refillRatePerSecond")).doubleValue());
}
if ("SlidingWindowLog".equals(algorithm)) {
return new SlidingWindowLogLimiter(
((Number) cfg.get("maxRequests")).intValue(),
((Number) cfg.get("windowMs")).intValue());
}
throw new IllegalArgumentException("unknown algorithm: " + algorithm);
}
class RateLimiter {
private final Map<String, Limiter> limiters = new HashMap<>();
private final Limiter defaultLimiter;
RateLimiter(List<Map<String, Object>> configs, Map<String, Object> defaultConfig) {
LimiterFactory factory = this::create;
for (Map<String, Object> c : configs) {
if (c.get("endpoint") != null) {
limiters.put((String) c.get("endpoint"), factory.create(c));
}
}
this.defaultLimiter = factory.create(defaultConfig); // eager at startup
}
RateLimitResult allow(String clientId, String endpoint) {
Limiter limiter = limiters.getOrDefault(endpoint, defaultLimiter);
return limiter.allow(clientId);
}
}TokenBucketLimiter
Each client has a bucket (capacity tokens) that refills at
refillRatePerSecond. One request costs one token. Bursts up to capacity; average rate = refill. Refill on demand from elapsed time — no background timer.class TokenBucket:
def __init__(self, tokens: float, last_refill_ms: int):
self.tokens = tokens
self.last_refill_ms = last_refill_ms
class TokenBucketLimiter:
def __init__(self, capacity: int, refill_rate_per_second: float):
self.capacity = capacity
self.refill_rate = refill_rate_per_second
self.buckets: dict[str, TokenBucket] = {}
def allow(self, key: str) -> RateLimitResult:
bucket = self._get_or_create(key)
now = now_ms()
elapsed = now - bucket.last_refill_ms
bucket.tokens = min(
self.capacity,
bucket.tokens + (elapsed * self.refill_rate) / 1000.0,
)
bucket.last_refill_ms = now
if bucket.tokens >= 1:
bucket.tokens -= 1
return RateLimitResult(True, int(bucket.tokens), None)
needed = 1 - bucket.tokens
retry_ms = math.ceil((needed * 1000) / self.refill_rate)
return RateLimitResult(False, 0, retry_ms)
def _get_or_create(self, key: str) -> TokenBucket:
if key not in self.buckets:
self.buckets[key] = TokenBucket(float(self.capacity), now_ms())
return self.buckets[key]class TokenBucket {
double tokens;
long lastRefillMs;
TokenBucket(double tokens, long lastRefillMs) {
this.tokens = tokens; this.lastRefillMs = lastRefillMs;
}
}
class TokenBucketLimiter implements Limiter {
private final int capacity;
private final double refillRate;
private final Map<String, TokenBucket> buckets = new HashMap<>();
TokenBucketLimiter(int capacity, double refillRatePerSecond) {
this.capacity = capacity; this.refillRate = refillRatePerSecond;
}
public RateLimitResult allow(String key) {
TokenBucket bucket = getOrCreate(key);
long now = nowMs();
long elapsed = now - bucket.lastRefillMs;
bucket.tokens = Math.min(capacity, bucket.tokens + (elapsed * refillRate) / 1000.0);
bucket.lastRefillMs = now;
if (bucket.tokens >= 1) {
bucket.tokens -= 1;
return new RateLimitResult(true, (int) bucket.tokens, null);
}
double needed = 1 - bucket.tokens;
int retryMs = (int) Math.ceil((needed * 1000) / refillRate);
return new RateLimitResult(false, 0, retryMs);
}
private TokenBucket getOrCreate(String key) {
return buckets.computeIfAbsent(key, k -> new TokenBucket(capacity, nowMs()));
}
}SlidingWindowLogLimiter
Per client: queue of request timestamps. On allow: drop stamps older than
now - windowMs, then if size < maxRequests append now; else deny with retry when the oldest stamp ages out. Perfect accuracy, higher memory.from collections import deque
class SlidingWindowLogLimiter:
def __init__(self, max_requests: int, window_ms: int):
self.max_requests = max_requests
self.window_ms = window_ms
self.logs: dict[str, deque[int]] = {}
def allow(self, key: str) -> RateLimitResult:
log = self.logs.setdefault(key, deque())
now = now_ms()
cutoff = now - self.window_ms
while log and log[0] < cutoff:
log.popleft()
if len(log) < self.max_requests:
log.append(now)
return RateLimitResult(True, self.max_requests - len(log), None)
retry_ms = (log[0] + self.window_ms) - now
return RateLimitResult(False, 0, retry_ms)class SlidingWindowLogLimiter implements Limiter {
private final int maxRequests;
private final int windowMs;
private final Map<String, Deque<Long>> logs = new HashMap<>();
SlidingWindowLogLimiter(int maxRequests, int windowMs) {
this.maxRequests = maxRequests; this.windowMs = windowMs;
}
public RateLimitResult allow(String key) {
Deque<Long> log = logs.computeIfAbsent(key, k -> new ArrayDeque<>());
long now = nowMs();
long cutoff = now - windowMs;
while (!log.isEmpty() && log.peekFirst() < cutoff) log.pollFirst();
if (log.size() < maxRequests) {
log.addLast(now);
return new RateLimitResult(true, maxRequests - log.size(), null);
}
int retryMs = (int) ((log.peekFirst() + windowMs) - now);
return new RateLimitResult(false, 0, retryMs);
}
}Verification (Token Bucket)
- t=0, capacity 10, refill 1/s — first allow → remaining 9.
- t=500ms — +0.5 token, allow → ~8 remaining.
- After depleting — deny with retryAfterMs ≈ time to accumulate 1 token.
- Happy: capacity 10, refill 1/s — ten allows succeed; eleventh waits or denies depending on policy.
- Failure: Unknown algorithm in config → factory raises; empty bucket → allow false.
- Concurrency: Two threads allow(same_key) — per-key lock serializes consume so capacity never goes negative.
Extensibility
- New algorithm — implement Limiter + one factory case; orchestrator untouched.
- Hot config — rebuild map (lose per-key state) vs
updateConfigon Limiter (preserve buckets/logs). Trade off. - Thread safety — ConcurrentHashMap / dict +
computeIfAbsent; synchronize on the bucket/log (per-key), not the whole limiter. Build RateLimitResult outside the lock. - Memory growth — last-access TTL eviction or LRU capacity; inactive clients return with a full burst (acceptable).
Common interview pitfalls
These mistakes show up constantly on this prompt. Name the trap, then show the fix in your design — don’t wait for the interviewer to catch you.
- Jumping to Redis/distributed limiting when the prompt is an in-memory single-process design.
- One global lock for all keys when per-key locks (with careful map creation) are the interesting part.
- Confusing Token Bucket (burst + refill rate) with Sliding Window Log (precise, memory-heavy).
- Forgetting clock injection — using time.time() everywhere makes tests and traces mushy.
- Allowing strategy objects to know about HTTP / user identity instead of a pure key + config.
- Hot config reload that silently drops per-key state without calling out the trade-off.
Interview script (say this)
Read this once out loud before a mock. It’s the spine of a strong answer — not a script to recite robotically.
- I’d lock scope: in-memory, per-key limits, which algorithms matter for v1, and whether we need multi-algorithm support.
- v1: RateLimiter orchestrator + Limiter interface; Token Bucket and Sliding Window Log behind a factory.
- Caller asks allow(key) → bool (or decision with remaining).
- Factory builds limiter from config; orchestrator maps key → limiter instance.
- Token Bucket: capacity, refill tokens/sec, on allow consume 1 if available after refill.
- Sliding Log: keep timestamps in window; allow if count < limit; prune old stamps.
- Concurrency: lock per key around allow; careful when creating new key entries.
- Trace: burst to capacity, wait for refill, deny when empty; compare memory vs precision trade-off.
- Extension: new algorithm = new Limiter + factory case; orchestrator untouched.
Extra verification traces
Walk these three traces on the board. If you can narrate them cleanly, your implementation section usually follows.
def allow(self, key: str) -> bool:
limiter = self._limiter_for(key) # may create under map lock
with limiter.lock:
limiter.refill(now=self.clock())
if limiter.tokens < 1:
return False
limiter.tokens -= 1
return Trueboolean allow(String key) {
Limiter limiter = limiterFor(key); // may create under map lock
synchronized (limiter.lock) {
limiter.refill(clock());
if (limiter.tokens < 1) return false;
limiter.tokens -= 1;
return true;
}
}Staff-level follow-ups
At staff+, they twist the prompt. Answer in one sentence that names the seam — don’t redesign the whole board.
- Distributed limit? — Move Limiter state to Redis with Lua for atomic refill+consume; keep interface.
- Fairness across users? — Separate keys per user/tenant; optional global semaphore as scarcity layer.
- Change limits live? — updateConfig on Limiter vs rebuild map — call out state loss.
- Sliding window counter approx? — Mention as cheaper alternative when log memory hurts.
Complete solution: locked Token Bucket
Refill + consume must be atomic per client key. Without a lock, two threads read the same token count and both subtract — over-admit.
from dataclasses import dataclass
from threading import Lock
from typing import Optional
import math, time
def now_ms() -> int:
return int(time.time() * 1000)
@dataclass
class RateLimitResult:
allowed: bool
remaining: int
retry_after_ms: Optional[int]
@dataclass
class Bucket:
tokens: float
last_refill_ms: int
class TokenBucketLimiter:
def __init__(self, capacity: int, refill_per_sec: float):
self.capacity = capacity
self.refill = refill_per_sec
self.buckets: dict[str, Bucket] = {}
self._lock = Lock() # coarse; or dict[key, Lock] if hot
def allow(self, key: str) -> RateLimitResult:
with self._lock:
b = self.buckets.get(key)
now = now_ms()
if b is None:
b = Bucket(float(self.capacity), now)
self.buckets[key] = b
elapsed = now - b.last_refill_ms
b.tokens = min(
self.capacity,
b.tokens + elapsed * self.refill / 1000.0,
)
b.last_refill_ms = now
if b.tokens >= 1:
b.tokens -= 1
return RateLimitResult(True, int(b.tokens), None)
needed = 1 - b.tokens
retry = math.ceil(needed * 1000 / self.refill)
return RateLimitResult(False, 0, retry)import java.util.*;
import java.util.concurrent.locks.ReentrantLock;
class RateLimitResult {
final boolean allowed; final int remaining; final Integer retryAfterMs;
RateLimitResult(boolean allowed, int remaining, Integer retryAfterMs) {
this.allowed = allowed; this.remaining = remaining; this.retryAfterMs = retryAfterMs;
}
}
class Bucket {
double tokens; long lastRefillMs;
Bucket(double tokens, long lastRefillMs) { this.tokens = tokens; this.lastRefillMs = lastRefillMs; }
}
class TokenBucketLimiter {
private final int capacity;
private final double refill;
private final Map<String, Bucket> buckets = new HashMap<>();
private final ReentrantLock lock = new ReentrantLock(); // coarse; or per-key locks if hot
TokenBucketLimiter(int capacity, double refillPerSec) {
this.capacity = capacity; this.refill = refillPerSec;
}
static long nowMs() { return System.currentTimeMillis(); }
RateLimitResult allow(String key) {
lock.lock();
try {
long now = nowMs();
Bucket b = buckets.get(key);
if (b == null) {
b = new Bucket(capacity, now);
buckets.put(key, b);
}
long elapsed = now - b.lastRefillMs;
b.tokens = Math.min(capacity, b.tokens + elapsed * refill / 1000.0);
b.lastRefillMs = now;
if (b.tokens >= 1) {
b.tokens -= 1;
return new RateLimitResult(true, (int) b.tokens, null);
}
double needed = 1 - b.tokens;
int retry = (int) Math.ceil(needed * 1000 / refill);
return new RateLimitResult(false, 0, retry);
} finally { lock.unlock(); }
}
}Concurrency cases
- Same key, two allows — classic RMW race on tokens; lock (or per-key lock) required.
- Different keys — coarse lock makes them wait each other (usually fine). Per-key locks:
self._key_locks.setdefault(key, Lock())— watch map growth. - Refill vs consume split — never refill under lock then consume outside; that’s the broken check-then-act again.