Skip to content
Back to all concepts
System DesignAlgorithmsRate Limiting

Token Bucket vs Leaky Bucket

A comprehensive comparison of two fundamental rate limiting algorithms: Token Bucket allows controlled bursts while Leaky Bucket enforces constant output rates.

By ScaleWikiUpdated 4 min readIntermediate

Token Bucket vs Leaky Bucket

Token Bucket and Leaky Bucket are two fundamental algorithms for rate limiting and traffic shaping. Despite their similar names, they serve different purposes and behave very differently.

Quick comparison:

  • Token Bucket: Allows bursts, limits average rate
  • Leaky Bucket: Smooths traffic, enforces constant rate

Token Bucket Algorithm

How It Works

Imagine a bucket that holds tokens (permissions to make requests):

Mechanics:

  1. Bucket has capacity C tokens (initially full)
  2. Tokens added at rate R per second
  3. Each request consumes 1 token
  4. If bucket empty → reject request
  5. If tokens available → process immediately

Visual Example

Capacity: 10 tokens
Refill: 1 token/second

Time | Tokens | Event              | Result
-----|--------|--------------------|-----------
0s   | 10     | User idle (10 sec) | Bucket full
0s   | 10     | 5 requests arrive  | ✓ All accepted (5 left)
1s   | 6      | +1 refill          | 6 tokens
1s   | 6      | 8 requests arrive  | ✓ First 6, ✗ Last 2 rejected
2s   | 1      | +1 refill          | 1 token
2s   | 1      | 1 request arrives  | ✓ Accepted

Key insight: Bursts allowed up to capacity, then limited to refill rate.

Implementation (Python)

python
import time

class TokenBucket:
    def __init__(self, capacity, refill_rate):
        if capacity <= 0 or refill_rate <= 0:
            raise ValueError("Capacity and refill rate must be positive")
        self.capacity = capacity
        self.tokens = capacity
        self.refill_rate = refill_rate
        self.last_refill = time.monotonic()
    
    def consume(self, tokens=1):
        if tokens <= 0:
            raise ValueError("Requested tokens must be positive")
        self._refill()
        if self.tokens >= tokens:
            self.tokens -= tokens
            return True
        return False
    
    def _refill(self):
        now = time.monotonic()
        elapsed = now - self.last_refill
        tokens_to_add = elapsed * self.refill_rate
        self.tokens = min(self.capacity, self.tokens + tokens_to_add)
        self.last_refill = now

# Usage
bucket = TokenBucket(capacity=10, refill_rate=1)
if bucket.consume():
    process_request()
else:
    return_429_error()

Use Cases

✅ API Rate Limiting

Free tier: 100 req/min average, burst of 20
bucket = TokenBucket(capacity=20, refill_rate=100/60)

✅ User-Facing Services

  • Allows natural user behavior (refresh button = 3 quick requests)
  • Good UX: occasional bursts don't get penalized

✅ AWS API Gateway Throttling

yaml
throttling:
  burstLimit: 5000    # Token bucket capacity
  rateLimit: 10000    # Refill rate (requests/sec)

Leaky Bucket Algorithm

How It Works

Imagine a bucket with a hole in the bottom:

Mechanics:

  1. Requests enter a queue (bucket)
  2. Requests processed (leak) at constant rate R
  3. If queue full → drop incoming requests
  4. While queued work is available, dispatch is paced at the chosen maximum rate; an empty queue produces no work

Visual Example

Queue Capacity: 5 requests
Leak Rate: 1 request/second

Time | Queue | Event              | Result
-----|-------|--------------------|-------------
0s   | []    | 3 requests arrive  | Queue: [R1, R2, R3]
1s   | [R2,R3] | Process R1       | R1 processed
1s   | [R2,R3,R4,R5,R6] | 3 more arrive | All three accepted (queue now full)
2s   | [R3,R4,R5] | Process R2    | R2 processed
3s   | [R4,R5] | Process R3       | R3 processed

Key insight: Output is smooth and constant, bursts are queued or dropped.

Implementation (Python)

text
producer: append to a bounded queue or reject when full
scheduler: wait until the next permitted dispatch time
           take at most one ready item
           dispatch it, then schedule the next slot

This is a shaper: it delays actual dispatch. A counter that models queue drain can decide admission, but it does not execute a background scheduler. Timer delays should not cause an unlimited catch-up burst.

Use Cases

✅ Network Traffic Shaping

  • ISPs use leaky bucket to smooth bursty traffic
  • Prevents network congestion

✅ Video Streaming

  • Output frames at constant 30 FPS
  • Buffer handles temporary encoding delays

✅ Background Job Processing

  • Process tasks at sustainable rate
  • Prevents worker overload

Side-by-Side Comparison

AspectToken BucketLeaky Bucket
Burst Handling✅ Allows controlled bursts❌ Smooths bursts, no acceleration
Output RateVariable (instant if tokens available)Paced up to the configured rate when work exists
QueueingNo queue, immediate decisionQueue requests for processing
MemoryO(1) — just track tokensO(n) — store queued requests
LatencyLow (immediate response)Higher (queuing delay)
User ExperienceBetter (responsive to bursts)Worse (artificial delays)
Server ProtectionModerateExcellent (guaranteed max rate)
ImplementationSimpleModerate (need queue management)

Traffic Pattern Comparison

Input:  ▂▂▂███████▂▂▂▂▂▂▂ (burst in middle)

Token Bucket Output:
        ▂▂▂██████▂▂▂▂▂▂▂▂  (burst passed through, some rejected)
        
Leaky Bucket Output:
        ▂▂▂▃▃▃▃▃▃▃▃▃▃▃▃▂  (smoothed to constant rate)

When to Use Each

Choose Token Bucket When:

✅ User-facing APIs

  • Users expect quick responses to bursts (page refresh)
  • Good UX is priority

✅ Variable workload patterns

  • Traffic naturally bursty
  • Average rate matters more than instantaneous rate

✅ Multi-tier rate limiting

python
free_user = TokenBucket(capacity=10, refill_rate=1)      # 1 req/sec, burst 10
paid_user = TokenBucket(capacity=1000, refill_rate=100)  # 100 req/sec, burst 1000

Choose Leaky Bucket When:

✅ Protecting downstream services

  • Database can only handle 100 QPS consistently
  • Bursts would cause crashes

✅ Regulatory compliance

  • Must guarantee max rate (e.g., rate-limited APIs)

✅ Fair scheduling

  • Process items in order received
  • No priority to bursty users

Hybrid Approaches

Leaky Bucket with Token Bucket

Combine both for flexibility:

python
class HybridRateLimiter:
    def __init__(self):
        # Token bucket for burst allowance
        self.token_bucket = TokenBucket(capacity=100, refill_rate=10)
        # Leaky bucket for smoothing output
        self.leaky_bucket = LeakyBucket(capacity=50, leak_rate=10)
    
    def handle_request(self, request):
        # First check: Can accept burst?
        if not self.token_bucket.consume():
            return False, "Rate limit exceeded (burst)"
        
        # Second check: Queue for processing
        if not self.leaky_bucket.add_request(request):
            return False, "Server busy (queue full)"
        
        return True, "Request queued"

Benefits:

  • Token bucket prevents abuse
  • Leaky bucket protects server

Real-World Examples

Nginx Rate Limiting (Leaky Bucket)

nginx
http {
    # Define rate limiting zone (leaky bucket)
    limit_req_zone $binary_remote_addr zone=api:10m rate=10r/s;
    
    server {
        location /api/ {
            limit_req zone=api burst=20 nodelay;
            # Leak rate: 10/sec
            # Burst capacity: 20 requests
        }
    }
}

AWS API Gateway (Token Bucket)

python
# CloudFormation configuration
UsagePlan:
  Type: AWS::ApiGateway::UsagePlan
  Properties:
    Throttle:
      BurstLimit: 5000   # Token bucket capacity
      RateLimit: 10000   # Refill rate (req/sec)

Service-specific policies

A managed service may enforce per-client rates and temporary bans without exposing its internal algorithm. Do not interpret a ban threshold as a leaky-bucket queue size. Read the product's contract and test observed behavior within the allowed usage policy.

Distributed Implementation Challenges

The Python example is single-threaded teaching code. Concurrent calls need synchronization around refill-and-consume. A distributed decision requires shared atomic state or an explicitly approximate allocation scheme.

Problem: Multiple Servers

Server A: User uses 50 tokens
Server B: User uses 50 tokens
Total: 100 tokens consumed (2x the limit!)

Solution: Centralized Redis

lua
-- token_bucket.lua (Redis Lua script)
local key = KEYS[1]
local capacity = tonumber(ARGV[1])
local refill_rate = tonumber(ARGV[2])
local clock = redis.call('TIME')
local now = tonumber(clock[1]) + tonumber(clock[2]) / 1000000
if not capacity or not refill_rate or capacity <= 0 or refill_rate <= 0 then
    return redis.error_reply('capacity and refill rate must be positive')
end

local bucket = redis.call('HMGET', key, 'tokens', 'last_refill')
local tokens = tonumber(bucket[1]) or capacity
local last_refill = tonumber(bucket[2]) or now

-- Refill tokens
local elapsed = math.max(0, now - last_refill)
tokens = math.min(capacity, tokens + (elapsed * refill_rate))

-- Consume token
local allowed = 0
if tokens >= 1 then
    tokens = tokens - 1
    allowed = 1
end

redis.call('HMSET', key, 'tokens', tokens, 'last_refill', now)
-- Do not expire before an empty bucket would have fully refilled.
redis.call('EXPIRE', key, math.max(1, math.ceil(capacity / refill_rate)))

return {allowed, tokens}

Interview Tips 💡

When discussing rate limiting in system design interviews:

  1. Clarify requirements: "Do we need to allow bursts for better UX, or enforce strict constant rates?"
  2. Compare algorithms: "Token bucket allows occasional bursts, while leaky bucket smooths traffic..."
  3. Justify choice: "For this user-facing API, token bucket is better because users might refresh pages..."
  4. Discuss distribution: "We'd use Redis with Lua scripts to share rate limit state across servers..."
  5. Mention alternatives: "We could also use fixed window counters for simpler cases..."
  6. Real examples: "AWS API Gateway uses token bucket with separate burst and rate limits..."

Related Concepts

Sources and a burst calculation

AWS API Gateway throttling documents token-bucket rate/burst behavior as best-effort targets. NGINX request limiting documents delay and burst settings. An ideal full bucket of capacity C and refill R permits at most approximately C + R × T token units over an interval T; downstream capacity must tolerate the initial burst as well as the sustained rate.

Keep reading

Intermediate

Geohashing (Location Encoding)

A geocoding system that encodes latitude/longitude coordinates into short alphanumeric strings for efficient proximity searches and spatial indexing.

System DesignGeospatialAlgorithms
Advanced

Raft Consensus Algorithm

A comprehensive guide to Raft, the consensus algorithm powering Etcd, Consul, and Kubernetes. Leader election, log replication, safety guarantees, and production deployment patterns.

Distributed SystemsAlgorithmsConsensus
Advanced

Top-K Heavy Hitters (Streaming)

How to find 'Trending Topics' in massive real-time streams. MapReduce, Count-Min Sketches, and Sliding Windows.

AlgorithmsBig DataStreaming
Advanced

Cache Eviction Policies

When the cache is full, something has to go. A comprehensive guide to LRU, LFU, ARC, and other replacement algorithms with implementation details.

CachingAlgorithmsPerformance
Advanced

Chat Delivery: Durable Acknowledgments and Device Sync

Design a chat workflow with retry-safe message IDs, per-device receipts, offline queues and explicit encryption boundaries.

System DesignReal-timeSocial
Advanced

File Synchronization: Versions, Conflicts and Recovery

A worked file-sync design: immutable blocks, version checks, offline conflicts, and safe cleanup. Includes a clearly scoped Dropbox engineering reference.

System DesignStorageDistributed Systems