拾荒的小海螺

1、简述

令牌桶算法（Token Bucket Algorithm）是一种流控算法，用于控制数据流的传输速率，同时允许一定程度的突发流量。这种算法广泛应用于网络流量整形、限流等场景。

代码样例：https://gitee.com/lhdxhl/algorithm-example.git

2、工作原理

令牌桶算法基于以下机制：

🔹 令牌桶：有一个容量为 C 的桶，最多存储 C 个令牌。
🔹 令牌生成速率：按照固定速率 r 向桶中添加令牌。
🔹 数据请求消耗令牌：每个数据请求会消耗一定数量的令牌。只有当桶中有足够的令牌时，请求才被允许通过，否则请求会被拒绝或延迟。
🔹 突发处理：允许桶中提前积累令牌，用于处理短时间内的突发流量。

算法步骤：

🔹 每隔固定时间间隔向桶中添加令牌，直到桶满。
🔹 当请求到达时，检查桶中令牌数量：
如果令牌足够，消耗相应数量的令牌并通过请求。
如果令牌不足，请求被拒绝或延迟。

3、实现样例

以下是用 Java 实现令牌桶算法的简单示例：

import java.util.concurrent.atomic.AtomicLong;

public class TokenBucket {
    private final long capacity; // 桶的容量
    private final long refillRate; // 令牌生成速率，单位：令牌/秒
    private AtomicLong tokens; // 当前令牌数量
    private long lastRefillTimestamp; // 上次填充令牌的时间戳

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

    private synchronized void refill() {
        long now = System.nanoTime();
        long elapsedTime = now - lastRefillTimestamp;
        long tokensToAdd = (elapsedTime * refillRate) / 1_000_000_000L;
        if (tokensToAdd > 0) {
            tokens.set(Math.min(capacity, tokens.get() + tokensToAdd));
            lastRefillTimestamp = now;
        }
    }

    public synchronized boolean tryConsume(long numTokens) {
        refill();
        if (tokens.get() >= numTokens) {
            tokens.addAndGet(-numTokens);
            return true;
        }
        return false;
    }

    public static void main(String[] args) {
        TokenBucket tokenBucket = new TokenBucket(10, 5); // 容量为10，速率为5令牌/秒

        for (int i = 0; i < 20; i++) {
            if (tokenBucket.tryConsume(1)) {
                System.out.println("请求成功通过: " + i);
            } else {
                System.out.println("请求被拒绝: " + i);
            }

            try {
                Thread.sleep(200); // 模拟每200ms发送一个请求
            } catch (InterruptedException e) {
                Thread.currentThread().interrupt();
            }
        }
    }
}

4、应用场景

令牌桶算法适用于以下场景：

🔹 网络流量整形：限制数据包发送速率，避免网络拥塞。
🔹 API 限流：在微服务中限制用户请求速率，保护后端服务不被过载。
🔹 分布式系统限流：协调多个节点的流量，防止单点过载。
🔹 带宽管理：在视频流媒体、文件下载等场景中限制带宽使用。

令牌桶的优缺点

🔹 优点：
支持突发流量，灵活性高。
实现简单，适合多种场景。

🔹 缺点：
在请求积压严重时可能导致延迟。
需要根据具体场景调整参数（桶容量、令牌速率）。

5、小结

令牌桶算法是一种高效的流控算法，广泛应用于流量控制和服务保护场景。通过合理配置算法参数，可以满足各种业务需求。在实际开发中，结合业务场景调整算法实现，可以有效提升系统的稳定性和可靠性。

JAVA：令牌桶流控算法的技术指南