System Design 101: The token-bucket algorithm

The token bucket algorithm is a technique for managing the frequency of system events. It keeps track of a bucket of tokens continuously added to at a set rate. These tokens can be viewed as units of capacity or permission that can be used to regulate the frequency at which events take place.

  • The token bucket algorithm limits the number of tokens that can be in the bucket at any given time, representing the maximum capacity or permission available to the system.
  • Tokens are added to the bucket at a fixed rate over time, starting with an empty bucket.
  • When an event occurs, it requests a token from the bucket.
  • If a token is available, it is removed from the bucket, allowing the event to occur.
  • If no tokens are available, the event is blocked or delayed until a token becomes available.
  • After each event, the algorithm checks whether the bucket has exceeded its capacity, and if so, additional tokens are discarded.
  • This ensures that the bucket is not too full and the system remains controlled.

Leave a Reply

This site uses Akismet to reduce spam. Learn how your comment data is processed.