Token Bucket vs. Leaky Bucket: Which is the "Optimal Solution" for Flow Control?

2025.08.27

When asked about current limiting algorithms in interviews, many interviewers ask you to write a handwritten implementation of a token bucket or leaky bucket. Although I've used existing current limiting tools like Redis and Guava, I still find writing them by hand a bit daunting. Today, we'll discuss the differences between these two classic current limiting algorithms and implement them in Java.

Many current limiting tools use them at the bottom layer.

1. Token Bucket vs. Leaky Bucket: Core Differences

Token Bucket

The core idea of the token bucket is: a bucket with fixed capacity, tokens are put into the bucket at a fixed rate, and tokens are taken from the bucket when a request comes, and rejected if there is no token.

It’s a bit like buying a ticket to enter the station. If you want to take a train, you go to the ticket window to buy a ticket first. Once you have bought a ticket, you can enter with the ticket. If you can’t buy a ticket, you have to wait, because the window will release tickets at a fixed time, and then you can grab them.

The following picture is generated by Ai, which roughly reflects this meaning.

Token bucket features:

1. It can handle burst traffic (it can be used as long as there are tokens in the bucket), because there are not always a lot of requests, but tokens will be added to the bucket at a fixed rate. When there are few requests, the bucket is full of tokens. When there is a surge in requests, the bucket can be filled with tokens for a while.

2. Relatively simple in principle and implementation

3. Small memory footprint

Leaky bucket applicable scenarios:

Interface current limiting: protecting business systems or sensitive interfaces
Prevent malicious attacks: defend against Dos or DDos attacks
……

Its advantage is that it can limit the average rate while allowing a certain amount of burst traffic

leaky bucket

The core idea of the leaky bucket is earlier and simpler than the token bucket: requests flow into the bucket like water, and the bucket "leaks" to process requests at a fixed rate. Requests that exceed the bucket capacity are discarded or queued.

Features of leaky bucket:

1. The output is very smooth and stable

2. Can effectively protect downstream systems (flow smoothing)

3. ❌ Unable to handle burst traffic

4. ❌ May cause request delays

Leaky bucket applicable scenarios:

Database connection pool: protect the database from being overloaded
Message queue consumption: controlling consumption rate
Payment system: ensuring payment processing stability

2. Handwriting Implementation

Token Bucket Implementation

public class TokenBucket {
    // 桶容量（最大令牌数）
    privatefinallong capacity;
    // 令牌填充速率（令牌/秒）
    privatefinallong refillRate;
    // 当前令牌数量
    private AtomicLong tokens;
    // 上次填充时间戳（纳秒）
    privatelong lastRefillTime;

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

    // 示例使用
    public static void main(String[] args) throws InterruptedException {
        // 创建桶：容量10令牌，每秒填充5令牌
        TokenBucket bucket = new TokenBucket(10, 2);

        // 模拟请求
        for (int i = 1; i <= 50; i++) {
            if (bucket.tryAcquire()) {
                System.out.println("请求" + i + ": 通过");
            } else {
                System.out.println("请求" + i + ": 限流");
            }
            Thread.sleep(100); // 100ms请求一次
        }
    }

    /**
     * 尝试获取令牌
     *
     * @return true-获取成功，false-被限流
     */
    public synchronized boolean tryAcquire() {
        refillTokens();
        if (tokens.get() > 0) {
            tokens.decrementAndGet();
            returntrue;
        }
        returnfalse;
    }

    /**
     * 尝试获取多个令牌
     *
     * @param numTokens 请求令牌数
     */
    public synchronized boolean tryAcquire(int numTokens) {
        refillTokens();
        if (tokens.get() >= numTokens) {
            tokens.addAndGet(-numTokens);
            returntrue;
        }
        returnfalse;
    }

    // 根据时间差补充令牌
    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;
        }
    }
}1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.
65.
66.
67.
68.
69.
70.
71.
72.
73.
74.
75.

Use AtomicLong to ensure thread safety.
The number of tokens replenished is dynamically calculated based on the time difference.
Bucket capacity limits the maximum value of burst traffic.

picture

Leaky Bucket Implementation

import java.util.concurrent.atomic.AtomicLong;

publicclass LeakyBucket {
    // 桶容量（最大请求数）
    privatefinallong capacity;
    // 漏水速率（请求/秒）
    privatefinallong leakRate;
    // 当前水量（待处理请求数）
    private AtomicLong water;
    // 上次漏水时间戳（毫秒）
    privatelong lastLeakTime;

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

    // 示例使用
    public static void main(String[] args) throws InterruptedException {
        // 创建桶：容量5请求，每秒处理2请求
        LeakyBucket bucket = new LeakyBucket(5, 1);

        // 模拟请求
        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请求一次
        }
    }

    /**
     * 尝试通过漏桶
     *
     * @return true-允许通过，false-被限流
     */
    public synchronized boolean tryPass() {
        leakWater();
        if (water.get() < capacity) {
            water.incrementAndGet();
            returntrue;
        }
        returnfalse;
    }

    // 根据时间差漏水
    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;
            }
        }
    }
}1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.
36.
37.
38.
39.
40.
41.
42.
43.
44.
45.
46.
47.
48.
49.
50.
51.
52.
53.
54.
55.
56.
57.
58.
59.
60.
61.
62.
63.
64.

The leakage rate is fixed to ensure smooth request processing.
If the water volume exceeds the capacity, the request will be rejected directly.

picture

3. Test comparison

public class RateLimiterTest {
    public static void main(String[] args) throws InterruptedException {
        // 测试令牌桶：容量10，每秒填充5个令牌
        TokenBucket tokenBucket = new TokenBucket(10, 5);

        // 测试漏桶：容量10，每秒漏出5个请求
        LeakyBucket leakyBucket = new LeakyBucket(10, 5);

        System.out.println("=== 令牌桶测试（支持突发） ===");
        testTokenBucket(tokenBucket);

        Thread.sleep(1000);

        System.out.println("\n=== 漏桶测试（平滑输出） ===");
        testLeakyBucket(leakyBucket);
    }

    private static void testTokenBucket(TokenBucket bucket) {
        // 模拟突发请求
        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) {
        // 模拟突发请求
        for (int i = 0; i < 15; i++) {
            boolean success = bucket.tryConsume();
            System.out.printf("请求%d: %s (当前水量: %.1f)%n", 
                i + 1, success ? "通过" : "拒绝", bucket.getCurrentWater());
        }
    }
}1.
2.
3.
4.
5.
6.
7.
8.
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
19.
20.
21.
22.
23.
24.
25.
26.
27.
28.
29.
30.
31.
32.
33.
34.
35.

4. Summary of interview points

Questions the interviewer may ask:

Q: What is the core difference between the two algorithms?

A: Token bucket allows bursts, while leaky bucket forces smooth output

Q: In what scenarios is a token bucket used and in what scenarios is a leaky bucket used?

A: Use a token bucket to handle bursts, and use a leaky bucket to protect downstream traffic.

Q: How do I choose the capacity and rate of the bucket?

A: Comprehensive consideration based on business peak, system carrying capacity, and user experience

Q: How to implement it in a distributed environment?

A: It can be implemented with Redis, or with consistent hashing.

Let me tell you later

Handwritten current limiting algorithms are generally not often seen in high-level interviews, but their basic concepts must be mastered, and they are good solutions when answering scenario questions.

Simply remember: the token bucket is like an ATM machine, you can withdraw money as long as you have money; the leaky bucket is like a faucet, which discharges water at a fixed flow rate.

Done!

新聞

Token Bucket vs. Leaky Bucket: Which is the "Optimal Solution" for Flow Control?

1. Token Bucket vs. Leaky Bucket: Core Differences

Token Bucket

Leaky bucket applicable scenarios:

leaky bucket

Leaky bucket applicable scenarios:

2. Handwriting Implementation

Token Bucket Implementation

Leaky Bucket Implementation

3. Test comparison

4. Summary of interview points

Let me tell you later

Detailed Explanation of the MSTP Mechanism Principle (Selected Illustrations and Text)

Stanford CS144 Computer Networks Podcast: Key Concepts and Methods of Network Security TLS/HTTPS