Problem statement
Design a thread-safe token-bucket rate limiter: a reusable primitive that admits or delays calls so a caller stays under a configured rate, refilling tokens over time. Focus on the concurrency and object model of the bucket itself, plus a registry that vends one bucket per name.
Operating context. One process, many threads calling tryAcquire(n). A bucket has a capacity (the burst ceiling) and a refill rate in tokens per second. Refill is lazy: on each call the bucket computes how many tokens accrued since the last refill from the elapsed time, capped at capacity, with no background timer thread. A blocking acquire(n) waits until enough tokens exist. A registry hands out named buckets (for example one per API key) so the same limit is shared by name.
Out of scope. Distributed or cluster-wide rate limiting, leaky-bucket or sliding-window variants (name them as alternatives but do not build them), persistence of counters, HTTP middleware wiring, and the accuracy of the underlying clock hardware.
What to produce. The class model (the bucket with its token count and refill computation, a clock abstraction, and a bucket registry), the public API, and the state transitions of the token count over time under lazy refill. Be explicit about the token invariant, why refill and consume must be one atomic step, how a blocking acquire computes its wait without a background thread, and how the registry's get-or-create per name is atomic.
Functional requirements
- tryAcquire(n) succeeds and removes n tokens if at least n are available after a lazy refill, otherwise fails immediately.
- Refill tokens from the time elapsed since the last refill, capped at the bucket capacity.
- acquire(n) blocks until n tokens are available, computing the earliest time it can succeed.
- The registry vends a named bucket with its rate and capacity, returning that same instance thereafter.
- Report the currently available tokens after a refill without consuming any.
Non-functional requirements
- Token invariant: the token count stays within 0 and capacity, and refill never pushes it above capacity.
- tryAcquire is O(1) and guarded (lock or CAS) so concurrent callers never double-spend the same token.
- No background thread: refill is computed lazily from an injected clock on each call.
- The clock is an injected, pluggable abstraction so the bucket is testable against virtual time.
- The registry's get-or-create per name is atomic, so concurrent first-callers share one bucket.
- Deterministically testable by advancing a fake clock, with no real waiting for tokens to refill.
Topics
- System Design LLD
- Concurrency Rate-Limiting
- Concurrency Atomics
- Patterns Registry
- Oop Interface-Design