Token Bucket vs Leaky Bucket: Which Is the Optimal Rate‑Limiting Solution?

1. Core Differences Between Token Bucket and Leaky Bucket

Token Bucket

The token bucket algorithm uses a fixed‑capacity bucket that is refilled at a constant rate. Requests consume a token; if no token is available the request is rejected. This is analogous to buying a ticket before boarding a train: tickets are released periodically, and only those who hold a ticket may proceed.

Key characteristics:

Handles burst traffic because tokens can accumulate when request rate is low.

Simple principle and implementation.

Low memory footprint.

Leaky Bucket

The leaky bucket algorithm treats incoming requests as water flowing into a bucket that leaks at a fixed rate. Excess requests that would overflow the bucket are discarded or queued. This ensures a smooth, steady output.

Key characteristics:

Produces very smooth and stable output.

Effectively protects downstream systems by smoothing traffic.

Cannot handle burst traffic (requests are limited to the leak rate).

May introduce request latency when the bucket is full.

2. Hand‑Written Implementations (Java)

Token Bucket Implementation

public class TokenBucket {
    // Bucket capacity (max tokens)
    private final long capacity;
    // Token refill rate (tokens/second)
    private final long refillRate;
    // Current token count
    private AtomicLong tokens;
    // Last refill timestamp (nanoseconds)
    private long lastRefillTime;

    public TokenBucket(long capacity, long refillRate) {
        this.capacity = capacity;
        this.refillRate = refillRate;
        this.tokens = new AtomicLong(capacity);
        this.lastRefillTime = System.nanoTime();
    }

    // Example usage
    public static void main(String[] args) throws InterruptedException {
        TokenBucket bucket = new TokenBucket(10, 2); // capacity 10, 2 tokens/sec
        for (int i = 1; i <= 50; i++) {
            if (bucket.tryAcquire()) {
                System.out.println("请求" + i + ": 通过");
            } else {
                System.out.println("请求" + i + ": 限流");
            }
            Thread.sleep(100); // 100ms per request
        }
    }

    /**
     * Try to acquire a single token.
     * @return true if successful, false if rate‑limited
     */
    public synchronized boolean tryAcquire() {
        refillTokens();
        if (tokens.get() > 0) {
            tokens.decrementAndGet();
            return true;
        }
        return false;
    }

    /**
     * Try to acquire multiple tokens.
     * @param numTokens number of tokens requested
     */
    public synchronized boolean tryAcquire(int numTokens) {
        refillTokens();
        if (tokens.get() >= numTokens) {
            tokens.addAndGet(-numTokens);
            return true;
        }
        return false;
    }

    // Refill tokens based on elapsed time
    private void refillTokens() {
        long now = System.nanoTime();
        double elapsedSec = (now - lastRefillTime) * 1e-9;
        long tokensToAdd = (long) (elapsedSec * refillRate);
        if (tokensToAdd > 0) {
            tokens.set(Math.min(capacity, tokens.get() + tokensToAdd));
            lastRefillTime = now;
        }
    }
}

Leaky Bucket Implementation

import java.util.concurrent.atomic.AtomicLong;

public class LeakyBucket {
    // Bucket capacity (max pending requests)
    private final long capacity;
    // Leak rate (requests/second)
    private final long leakRate;
    // Current water level (pending requests)
    private AtomicLong water;
    // Last leak timestamp (milliseconds)
    private long lastLeakTime;

    public LeakyBucket(long capacity, long leakRate) {
        this.capacity = capacity;
        this.leakRate = leakRate;
        this.water = new AtomicLong(0);
        this.lastLeakTime = System.currentTimeMillis();
    }

    // Example usage
    public static void main(String[] args) throws InterruptedException {
        LeakyBucket bucket = new LeakyBucket(5, 1); // capacity 5, 1 request/sec
        for (int i = 1; i <= 15; i++) {
            if (bucket.tryPass()) {
                System.out.println("请求" + i + ": 通过 (当前水位: " + bucket.water.get() + ")");
            } else {
                System.out.println("请求" + i + ": 限流 (水位溢出)");
            }
            Thread.sleep(200); // 200ms per request
        }
    }

    /**
     * Try to let a request pass.
     * @return true if allowed, false if rate‑limited
     */
    public synchronized boolean tryPass() {
        leakWater();
        if (water.get() < capacity) {
            water.incrementAndGet();
            return true;
        }
        return false;
    }

    // Leak water based on elapsed time
    private void leakWater() {
        long now = System.currentTimeMillis();
        long elapsedMs = now - lastLeakTime;
        if (elapsedMs > 0) {
            long leaked = (long) (elapsedMs * leakRate / 1000.0);
            if (leaked > 0) {
                water.updateAndGet(cur -> Math.max(0, cur - leaked));
                lastLeakTime = now;
            }
        }
    }
}

3. Test Comparison

public class RateLimiterTest {
    public static void main(String[] args) throws InterruptedException {
        // Test token bucket: capacity 10, refill 5 tokens/sec
        TokenBucket tokenBucket = new TokenBucket(10, 5);
        // Test leaky bucket: capacity 10, leak 5 requests/sec
        LeakyBucket leakyBucket = new LeakyBucket(10, 5);

        System.out.println("=== 令牌桶测试（支持突发） ===");
        testTokenBucket(tokenBucket);
        Thread.sleep(1000);
        System.out.println("
=== 漏桶测试（平滑输出） ===");
        testLeakyBucket(leakyBucket);
    }

    private static void testTokenBucket(TokenBucket bucket) {
        // Simulate burst requests
        for (int i = 0; i < 15; i++) {
            boolean success = bucket.tryConsume(1);
            System.out.printf("请求%d: %s (当前令牌: %.1f)%n", i + 1, success ? "通过" : "拒绝", bucket.getCurrentTokens());
        }
    }

    private static void testLeakyBucket(LeakyBucket bucket) {
        // Simulate burst requests
        for (int i = 0; i < 15; i++) {
            boolean success = bucket.tryConsume();
            System.out.printf("请求%d: %s (当前水量: %.1f)%n", i + 1, success ? "通过" : "拒绝", bucket.getCurrentWater());
        }
    }
}

4. Interview Takeaways

Typical interview questions include:

What is the core difference between the two algorithms? – Token bucket allows bursts; leaky bucket enforces smooth output.

When should each be used? – Use token bucket for burst‑tolerant scenarios; use leaky bucket to protect downstream services.

How to choose bucket capacity and refill/leak rate? – Base the decision on business peak load, system capacity, and desired user experience.

How to implement in a distributed environment? – Common approaches are Redis‑based counters or consistent‑hash sharding.

Understanding these concepts is valuable for senior‑level interview discussions on rate limiting and traffic control.