Design scalable rate limiter with token bucket

You are asked to design and implement a rate limiter for an HTTP API.

Requirements

• Limit each client (e.g., user ID or API key) to at most N requests per T seconds.
• The rate limiter should run in memory (assume a single application instance to start).
• It must be:
  • Low latency (per-request check must be fast).
  • Memory efficient even when there are many distinct clients and very high traffic.
  • Easy to extend later to a distributed setting.

The interviewer guides you through the following steps:

1. Baseline design (sliding window):
   • Describe how you would implement a basic sliding-window rate limiter.
   • Be explicit about what data you store per client, how you decide whether to allow or reject a request given its timestamp, and the time and space complexity.
2. Scalability concern:
   • Explain what happens when traffic becomes extremely large (e.g., millions of clients, each sending many requests per second).
   • Why might the naive sliding-window implementation run into memory and performance issues?
3. **Improved design (token bucket with lazy refill):
   • Redesign the rate limiter using a token bucket algorithm so that memory usage stays small and per-request operations remain O(1).
   • You should:
     • Describe the conceptual model of a token bucket (capacity, refill rate, token consumption on each request).
     • Specify exactly what you store per client (e.g., current token count, last refill timestamp, etc.).
     • Explain how to perform a lazy refill : instead of refilling tokens every second via a background job or timer, you only recalculate and refill tokens when a request for that client arrives, using the request's timestamp.
     • Show how the lazy refill calculation works for a request arriving at time now , given last_refill_time , current_tokens , bucket capacity , and refill_rate (tokens per second).
   • Discuss how this design solves the large-data, low-memory problem compared to the sliding-window implementation.
4. Additional considerations:
   • How would you handle concurrency (multiple threads) accessing the same client's rate-limit state?
   • How would you clean up or evict inactive clients so the in-memory data structure does not grow without bound?
   • Briefly mention how you might extend this design to multiple application servers (e.g., by storing state in a shared store like Redis), but focus on the core token-bucket-with-lazy-refill design.

Provide a detailed, system-design level answer: data structures, algorithms, complexity, trade-offs between sliding window and token bucket, and how lazy refill works in practice.