Problem
Design and implement a thread-safe rate limiter that many threads call concurrently to decide whether a request is allowed.
Requirements
boolean allow(key) returns whether the caller may proceed now.- Configurable limit and time window; support per-key limits (per user / API key).
- Correct under high concurrency; minimal contention.
Core design
- Choose an algorithm: token bucket (smooth, allows bursts up to capacity), fixed-window counter (simple, boundary bursts), or sliding-window log/counter (accurate, more memory).
- State: a concurrent map from key → bucket/counter; refill based on elapsed time using a monotonic clock.
- Make the check-and-update atomic per key (e.g. per-key lock,
compareAndSet, or an atomic token count).
Discussion points
- Lock granularity vs throughput: global lock (simple, contended) vs per-key locks / lock-free CAS.
- Handling clock skew and time source; eviction of idle keys to bound memory.
- Extending to a distributed limiter (Redis with Lua / token bucket) and the consistency trade-offs.