Token Bucket Algorithm

1. One-Liner

The Token Bucket algorithm limits how many requests a client can send by giving them a fixed number of "tokens" that refill over time.

2. The Problem It Solves

Imagine you run an API. Without any protection:

A single user could send 10,000 requests per second and crash your server.

Bots could scrape your data endlessly.

Your paying customers would get slow responses because resources are hogged.

Rate limiting solves this. It sets a rule: "You can only make X requests per Y seconds." The Token Bucket algorithm is one of the best ways to enforce this rule.

3. The Core Idea

Picture a real bucket sitting on a table:

Someone drops coins (tokens) into the bucket at a steady rate — say, 2 coins per second.

The bucket can hold a maximum of 10 coins (its capacity). Extra coins fall off.

Every time you want to make a request, you must take a coin from the bucket.

Coin available? Your request goes through.

Bucket empty? Sorry, wait for more coins.

This is the entire algorithm. That’s it.

4. How It Works (Step-by-Step)

Step	What Happens
1. Initialize	Create a bucket with `capacity` tokens, all filled up
2. Request arrives	Before checking, calculate how much time has passed since last check
3. Refill tokens	Add `elapsed_time × refill_rate` tokens, but never exceed capacity
4. Check tokens	Is `current_tokens ≥ cost`?
5a. YES → Allow	Subtract cost from tokens. Request goes through.
5b. NO → Deny	Not enough tokens. Return error (HTTP 429).
6. Save timestamp	Remember the current time for the next refill calculation

Key insight: We don’t run a background timer. We only calculate tokens when a request actually arrives. This is called lazy evaluation and makes it very efficient.

5. Dry Run Example

Setup: capacity = 5, refill rate = 1/sec, cost = 1

Time	Action	Tokens Before	Result	Tokens After
0.0s	Start	5	—	5
0.2s	Request	5	✅ Allow	4
0.4s	Request	4	✅ Allow	3
0.6s	Request	3	✅ Allow	2
0.8s	Request	2	✅ Allow	1
1.0s	Request	1 + 1 refill = 2	✅ Allow	1
1.1s	Request	1.1	✅ Allow	0.1
1.2s	Request	0.2	❌ Deny	0.2
3.0s	Request	0.2 + 1.8 = 2.0	✅ Allow	1.0

Notice how at t=3.0s, the bucket has refilled over time and can accept requests again.

6. Key Properties

Property	Value
Allows burst traffic?	Yes — a full bucket permits a burst up to capacity
Smooth rate over time?	Yes — limited by refill rate in the long run
Memory per user	O(1) — just 3 values: tokens, capacity, last_timestamp
Background timer needed?	No — uses lazy evaluation
Configurable?	Yes — capacity, rate, and cost can be set per endpoint or user

7. Where It Is Used

Company / System	How They Use It
AWS API Gateway	Default rate limiting algorithm
Nginx	`limit_req` module uses a variant of token bucket
Stripe	API rate limits for payment endpoints
Google Cloud	Quota management for API calls
Linux Kernel	Network traffic shaping (`tc` command)
Kong Gateway	Rate limiting plugin

8. Interview Tips

What interviewers want to hear:

1. You understand why rate limiting is needed (protect servers, fairness, cost control)

2. You can explain token bucket with a simple analogy (bucket + coins)

3. You know it uses lazy evaluation (no background thread)

4. You can compare it with alternatives (see section below)

5. You can discuss distributed rate limiting — what happens when you have multiple servers?

Common follow-up questions:

"How would you implement this across multiple servers?" → Use Redis to store token counts centrally. Use atomic operations (MULTI/EXEC or Lua scripts).

"What happens during a race condition?" → Use atomic compare-and-swap or Redis Lua scripts for thread safety.

"How is this different from a fixed window counter?" → Fixed window can have a burst at window boundaries (2x burst). Token bucket smooths this out.

"What HTTP status code should you return?" → 429 Too Many Requests with a Retry-After header.

9. Comparison with Other Algorithms

Algorithm	Burst Handling	Memory	Complexity	Best For
Token Bucket	✅ Allows bursts	O(1)	O(1)	APIs needing burst tolerance
Leaky Bucket	❌ No bursts	O(1)	O(1)	Smooth, constant output rate
Fixed Window	⚠️ Edge burst	O(1)	O(1)	Simple use cases
Sliding Window Log	✅ Precise	O(n)	O(n)	High accuracy needed
Sliding Window Counter	✅ Good	O(1)	O(1)	Balance of accuracy & efficiency

10. Complexity

Metric	Value
Time Complexity	O(1) per request
Space Complexity	O(1) per user/client
Refill Calculation	O(1) — simple multiplication

Implementation Example (PYTHON)

import time

class TokenBucket:
    def __init__(self, capacity, rate):
        self.capacity = capacity
        self.rate = rate
        self.tokens = capacity
        self.last_refill = time.monotonic()

    def _refill(self):
        now = time.monotonic()
        elapsed = now - self.last_refill
        self.tokens += elapsed * self.rate
        self.tokens = min(self.tokens, self.capacity)
        self.last_refill = now

    def try_consume(self, cost=1):
        self._refill()
        if self.tokens >= cost:
            self.tokens -= cost
            return True   # ALLOW
        return False       # DENY