Implement a thread-safe rate limiter

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.