Token Bucket Rate Limiter

Algorithm System Design Rate Limiting

Implement a token bucket rate limiter as a class (or module) in your preferred programming language. The rate limiter should control the number of events allowed within a given interval by using tokens which are replenished at a fixed rate.

Requirements:

  1. The rate limiter should be initialized with two parameters:

    • The maximum burst size (i.e., maximum number of tokens that can accumulate).
    • The token refill rate (tokens per second).

  2. Provide a method (e.g., allow() or similar) that returns a boolean indicating if the event can proceed. An event is allowed if there is at least one token available at that moment; if allowed, consume a token.

  3. The token bucket should dynamically refill tokens as time passes, up to the maximum burst size. The refill mechanism must account for elapsed time between calls.

  4. Your implementation should be thread-safe if your chosen language supports concurrency.

  5. Include tests or a simple demonstration that simulates rapid incoming events to showcase that the rate limiter correctly enforces the rate limit.

Consider edge cases such as:

  • Requests arriving exactly at the refill boundaries.
  • A long pause between events, letting the bucket refill completely.
  • Concurrency issues if multiple threads/processes call the rate limiter simultaneously.

Write clean, idiomatic code with proper handling of time-based events.