源码令牌桶算法实现逻辑？

访客源码剖析 2026-06-08 01:27:34 1

令牌桶算法实现逻辑与核心机制

目录导读

令牌桶算法概述
什么是令牌桶？为什么需要它？
算法核心逻辑拆解
令牌生成、存储与消费机制
源码级实现详解（Java/Python）
关键代码片段与逻辑注释
常见问题解析（Q&A）
如何应对突发流量？令牌桶与漏桶有何区别？
性能优化与工程落地建议
基于Google Guava RateLimiter的实战分析
何时选用令牌桶？

令牌桶算法概述

令牌桶（Token Bucket）是流量整形与限流领域的经典算法，广泛应用于API网关、消息队列、网络带宽控制等场景，其核心理念是：系统以恒定速率向一个“桶”中放入令牌，每个请求需要消耗一个令牌才能被处理，若桶中无令牌，请求将被阻塞或拒绝。

与漏桶算法不同,令牌桶允许一定程度的突发流量——只要桶中还有积累的令牌，瞬间可消耗多个令牌处理积压请求，这一特性使其成为平衡“平滑性”与“吞吐量”的理想选择。

算法核心逻辑拆解

1 四个关键参数

容量（capacity）：桶最多能存储的令牌数。
填充速率（fillRate）：每秒放入令牌的数量（单位为 tokens/s）。
当前令牌数（currentTokens）：实时动态更新的可用令牌。
最后填充时间（lastFillTime）：记录上次令牌更新的时间戳。

2 执行流程

请求到达时：计算距离上次填充的时间间隔，按速率补充令牌（但不超过容量）。
判断可用性：若currentTokens >= 1，允许请求并消耗1个令牌；否则拒绝或等待。
周期性重置：时间驱动填充，确保长期平均速率稳定。

关键公式：
tokensToAdd = (now - lastFillTime) * fillRate
currentTokens = min(capacity, currentTokens + tokensToAdd)

源码级实现详解（Java/Python）

1 Java 简易实现（基于时间戳）

public class TokenBucket {
    private final long capacity;     // 桶容量
    private final double fillRate;   // 令牌填充速率（每秒）
    private double currentTokens;    // 当前令牌数
    private long lastFillTime;       // 上次补充时间戳
    public TokenBucket(long capacity, double fillRate) {
        this.capacity = capacity;
        this.fillRate = fillRate;
        this.currentTokens = capacity; // 初始满桶
        this.lastFillTime = System.nanoTime();
    }
    public synchronized boolean tryAcquire(int tokens) {
        refillTokens(); // 补充令牌
        if (currentTokens >= tokens) {
            currentTokens -= tokens;
            return true;
        }
        return false;
    }
    private void refillTokens() {
        long now = System.nanoTime();
        double timeDelta = (now - lastFillTime) / 1_000_000_000.0;
        currentTokens = Math.min(capacity, currentTokens + timeDelta * fillRate);
        lastFillTime = now;
    }
}

逻辑解析：

synchronized保证线程安全。
refillTokens() 只在实际请求时执行“按需补充”，避免后台定时器开销。
时间单位采用纳秒,精度高但需注意long溢出问题（工程中用AtomicLong优化）。

2 Python 简洁版（无锁实现）

import time
class TokenBucket:
    def __init__(self, capacity, fill_rate):
        self.capacity = capacity
        self.fill_rate = fill_rate
        self.tokens = capacity
        self.last_time = time.monotonic()
    def consume(self, tokens=1):
        now = time.monotonic()
        delta = now - self.last_time
        self.tokens = min(self.capacity, self.tokens + delta * self.fill_rate)
        self.last_time = now
        if self.tokens >= tokens:
            self.tokens -= tokens
            return True
        return False

差异点：