Course contentsShow
← System Design
Lesson 964 of 1,91925. Rate Limiting and ThrottlingFree lesson

Token Bucket Algorithm

How token bucket controls request rates by refilling tokens at a fixed rate and allowing bursts up to bucket capacity.

Token Bucket Algorithm

What you'll learn: How the token bucket algorithm smoothly controls request rates while allowing controlled bursts of traffic.


The Core Idea

Imagine a physical bucket that holds tokens. Tokens are added to the bucket at a fixed, steady rate (e.g., 100 tokens per second). Each incoming request must "spend" one token to proceed. If the bucket is empty, the request is rejected or delayed. The bucket has a maximum capacity, so excess tokens overflow and are lost.

This simple mechanism provides two crucial features: sustained rate limiting and burst tolerance.

How It Works

The algorithm maintains:

  • A bucket capacity (e.g., 500 tokens max)
  • A refill rate (e.g., 100 tokens/second)
  • A current token count

When a request arrives:

  1. Calculate how many tokens should have been added since the last check
  2. Add those tokens to the bucket (up to capacity)
  3. If at least one token exists, consume it and allow the request
  4. If no tokens exist, reject or throttle the request

Burst Handling

The bucket capacity allows bursts up to its size. A client could make 500 requests instantly if the bucket is full, then be rate-limited to the refill rate (100 req/s). This flexibility is crucial for handling legitimate traffic spikes while preventing sustained abuse.

Real-World Analogy

Think of a coffee shop giving customers punch cards. Cards are handed out at a steady rate (one per minute), and you can save up to 10 cards. If you arrive with 10 cards, you can buy 10 coffees immediately, then you're limited to one per minute thereafter.

Key Takeaway: The token bucket algorithm controls sustained request rates through steady token refills while permitting short bursts up to the bucket's capacity, making it ideal for practical rate limiting that accommodates natural traffic patterns.