Design a Thread-Safe Rate Limiter (Token Bucket & Sliding Window)
In a 45-minute LLD interview, the key requirement is designing a thread-safe, low-latency rate limiter that guards downstream services without suffering race conditions or flaky test delays. Scope the solution to: in-process rate limiting with per-client quotas, interchangeable algorithms (Token Bucket with smooth replenishment and Sliding Window Log with rolling deques), multi-token consumption, and deterministic simulated time injection. Mention distributed Redis clusters as an operational follow-up.
Problem statement & clarifying requirements
Design a thread-safe rate limiter for an API gateway that protects downstream microservices from traffic surges. The system must support interchangeable algorithms (Token Bucket and Sliding Window Log) with per-client quotas, allow multiple tokens per request, and be 100% deterministically testable without flaky wall-clock sleeps.
Clients are identified by arbitrary string keys (such as an API key, bearer token, or caller IP address). Each identifier maintains isolated quota state.
We implement two core strategies: Token Bucket (allows controlled bursts up to a capacity and refills smoothly over time) and Sliding Window Log (enforces strict request counts across a rolling time window).
State mutations on client buckets and timestamp deques are synchronized using a mutex (std::mutex) and RAII locks (std::lock_guard).
We inject a Clock interface with a SimulatedClock implementation, allowing tests to advance simulated time instantaneously and deterministically.
First, sketch the design yourself
Spend 5 minutes listing the classes, who owns whom, and which interface hides the part that changes.
- 1.
Decouple algorithms from the gateway context: Using the Strategy pattern (
a1) lets callers swap or test rate limiting mechanisms at runtime without changing gateway routing logic. - 2.
Avoid wall-clock coupling in domain models: Direct calls to
std::chrono::steady_clock::now()make time-based unit tests slow and flaky. Abstracting time behind an injectableClockyields instant, reproducible tests. - 3.
Concurrency granularity: A coarse mutex per strategy protects internal maps during lookups and mutations. In high-scale production systems, this can be partitioned with sharded mutexes.
How to think through this problem (5-step walkthrough)
In a 45-minute LLD interview, the key requirement is designing a thread-safe, low-latency rate limiter that guards downstream services without suffering race conditions or flaky test delays. Scope the solution to: in-process rate limiting with per-client quotas, interchangeable algorithms (Token Bucket with smooth replenishment and Sliding Window Log with rolling deques), multi-token consumption, and deterministic simulated time injection. Mention distributed Redis clusters as an operational follow-up.
Not every noun in the prompt deserves its own class. Separate dumb data structs from stateful managers, and turn trivial nouns into fields or enums.
ClockAbstraction over time queries with a pure virtual now() method, enabling SimulatedClock to advance time deterministically in unit tests without wall-clock sleeps, alongside SystemClock for production.
RateLimitStrategyPolymorphic Strategy contract declaring allowRequest(clientId, tokens) so rate limiting algorithms (Token Bucket, Sliding Window Log, Leaky Bucket) can be swapped seamlessly.
TokenBucketLimiterConcrete Strategy holding per-client bucket state (double tokens and last refill timestamp), computing lazy token replenishment under a mutex.
SlidingWindowLimiterConcrete Strategy maintaining per-client timestamp deques (std::deque<time_point>) and purging expired entries upon request arrival under a mutex.
RateLimiterServiceContext facade holding a std::unique_ptr<RateLimitStrategy> and delegating incoming client requests to the active algorithm.
TokenTrap noun — beginner candidates often create a heap-allocated Token class; in high-throughput rate limiters, tokens are simply represented as an atomic or scalar numeric counter (double or int64_t), avoiding thousands of useless heap allocations per second.
A beginner attempts to write a monolithic RateLimiter class with hardcoded std::chrono::system_clock::now() and a single switch(algorithm) statement. Testing time-dependent replenishment forces calling std::this_thread::sleep_for(), making unit tests slow and flaky on CI runners. Furthermore, failing to synchronize concurrent client map mutations leads to immediate data races and undefined behavior under multi-threaded HTTP traffic.
A switch statement inside the gateway forces modifying core dispatch logic whenever a new algorithm or tier is introduced, violating the Open-Closed Principle.
Direct calls to std::chrono::steady_clock::now() couple the limiter to the physical system clock, making rate-limiting unit tests slow, sleep-dependent, and non-deterministic.
Unprotected reads and writes to shared std::unordered_map instances trigger memory corruption and data races when concurrent HTTP workers arrive simultaneously.
- ✓
Thread safety with fine-grained synchronization: Strategy mutations access per-client state maps under
std::scoped_lock/std::lock_guard<std::mutex>, ensuring concurrent requests for identical or distinct client IDs never corrupt internal token counters or timestamp queues. - ✓
Lazy replenishment invariant: In
TokenBucketLimiter, tokens are replenished on-demand upon each request arrival (min(capacity, current + elapsed * rate)) rather than running a background tick thread per client, preventing resource leaks and CPU spinning. - ✓
Multi-token atomicity: When consuming K tokens, the deduction is all-or-nothing: if
available < tokens, zero tokens are deducted and the method returnsfalseimmediately.
Entities & design patterns used
Unlock Full UML Diagram & C++23 Solution
The complete UML diagram, production-ready C++23 code, follow-up extensions, and design pitfall analysis are part of Brute2Best Pro. All 7 foundation chapters are 100% free.
First anchor question per pattern, Part 1 LLD & Module 1 C++ basics are 100% Free forever.