Rate Limiter Algorithm Design

A system-design round focused less on drawing a distributed architecture and more on rate-limit algorithms: token bucket, leaky bucket, fixed window, sliding window, state storage, and trade-offs. Requirements Design a rate limiter. The interviewer may keep the discussion narrow and focus on algorithms rather than a full distributed-system diagram. Functional requirements: Limit requests per user, API key, IP, or tenant. Return allow / reject decision on every request. Support configurable limits such as 100 requests / minute. Expose enough metadata for retry behavior, e.g. remaining quota and retry-after. Scale / constraints to clarify: QPS per limiter instance and globally. Number of tenants / keys. Required accuracy under concurrency. Burst tolerance. Whether fail-open or fail-closed is acceptable. Notes Algorithm trade-offs: Fixed window: simple counter per key and time bucket; cheap but allows boundary bursts. Sliding window log: exact but stores every timestamp; memory-heavy at high QPS. Sliding window counter: approximates by blending current and previous buckets; lower memory, small error. Token bucket: supports bursts up to bucket size while enforcing average refill rate. Leaky bucket: smooths output at a fixed drain rate; useful when downstream needs steady traffic. A practical design uses a local in-memory fast path for single-instance limits or a shared store such as Redis for distributed limits. For high scale, shard by key, batch updates where acceptable, and keep configuration in a separate control plane. Key interviewer traps: Drawing too much unrelated infrastructure when they want algorithm precision. Ignoring clock skew and atomicity in distributed counters. Not explaining burst behavior. Forgetting that per-key state size dominates memory. Preparation Memorize token bucket pseudocode: refill based on elapsed time, cap at capacity, consume one token if available. Prepare a table comparing fixed window, sliding log, sliding counter, token bucket, and leaky bucket. Walk through a boundary-burst example where fixed window permits nearly 2x intended traffic.