Design a distributed rate limiter using token buckets. Each user or API key has a bucket with a fixed capacity. Tokens refill at a configured rate, and a request is allowed only if it can consume the required tokens. The limiter runs across many application servers and should add low latency while preserving a clear behavior during storage failures or regional partitions. ### Constraints & Assumptions - Bucket configuration can change and must be versioned. - Concurrent requests for the same key must not independently spend the same token. - Define whether a small amount of oversubscription is acceptable. ### Clarifying Questions to Ask - Is the limit global or regional? - Do requests always cost one token? - Should failure of the limiter fail open or fail closed for each endpoint class? ```hint Refill lazily Store a token balance and last-refill time; compute accrued tokens when the next request arrives rather than scheduling refill jobs. ``` ### What a Strong Answer Covers - Atomic token calculation and consumption, time semantics, keying, TTL, and configuration rollout. - Local caching or quota leasing with quantified oversubscription. - Hot keys, failure policy, observability, and abuse resistance. ### Follow-up Questions - How would you enforce both per-user and global limits? - How would clock skew affect refill calculations? - When is a sliding-window limiter preferable?