令牌桶算法详解：从原理到工程实践

摘要

令牌桶（Token Bucket）是网络流量控制领域最经典、应用最广泛的算法之一。它通过一个简洁的数学模型，优雅地解决了”如何在允许突发流量的前提下保证长期平均速率”这一核心问题。本文将从算法原理、数学本质、工程实现到实际应用场景，全面剖析令牌桶算法，帮助读者不仅”会用”，更能”懂其所以然”。

关键词：令牌桶、流量控制、速率限制、拥塞控制、QoS

一、引言：为什么需要令牌桶

在计算机网络中，数据发送面临一个永恒的矛盾：

  • 发送太慢：浪费宝贵的带宽资源，传输效率低下
  • 发送太快：可能压垮接收端缓冲区，导致网络拥塞、丢包、重传，反而进一步恶化性能

理想的传输策略应该是：在绝大多数时间保持稳定的平均速率，但在网络空闲或数据积压时，允许短时间的”突发”传输以充分利用带宽。这个看似矛盾的需求，正是令牌桶算法的设计出发点。

令牌桶算法最早可以追溯到1986年，由Jonathan S. Turner在论文《New directions in communications（or which way to the information age?）》中提出，随后被广泛应用于各类网络设备和服务器的流量控制中，包括：

  • 路由器的流量整形（Traffic Shaping）：限制出口流量的速率
  • 网络接口的QoS（Quality of Service）：为不同业务分配带宽
  • API网关的限流（Rate Limiting）：防止服务被突发请求冲垮
  • CDN和云服务的带宽控制：按照套餐限制用户带宽
  • 多媒体流式传输：平滑视频码率，防止缓冲区溢出

二、算法核心原理

2.1 直观理解

令牌桶可以用一个生活中的比喻来理解：

想象你有一个特殊的”水桶”。一个”水龙头”以恒定的速率往桶里滴水（生成令牌），桶的容量有限，水满了就会溢出（令牌堆积上限）。每次你要发送数据时，必须先从这个桶里”舀走”一定量的水（消耗令牌）。如果桶里的水不够，你就得等待（阻塞策略），或者放弃这次发送（非阻塞策略）。

在这个比喻中，每一滴水就是一个”令牌”（Token），代表”发送一定量数据的许可”。你有多少令牌，就能发送多少数据。

2.2 数学模型

令牌桶算法可以用三个参数精确描述：

  • 平均速率（r）：令牌生成的速率，即长期平均发送速率，单位通常是”令牌/秒”
  • 桶容量（b）：桶最多能容纳的令牌数，即最大突发流量，单位是”令牌”
  • 当前令牌数（T(t)）：时刻 t 桶中实际拥有的令牌数

算法的核心状态更新方程如下：

T(t) = min(b, T(t₀) + r × (t – t₀) – C)

其中：

  • t₀ 是上次更新令牌的时刻
  • C 是从 t₀ 到 t 之间消耗的令牌总数
  • min 确保令牌数不超过桶容量 b

当 T(t) ≥ 需要消耗的令牌数 时，发送操作被允许；否则被拒绝或阻塞。

2.3 算法的行为特征

令牌桶算法在实际运行中呈现出规律的”充放电”动态特征：

在系统空闲或发送速率较低的时期，令牌持续积累，直到达到桶容量上限。当大量数据到达时，系统可以”突发”地消耗积攒的令牌，以高于平均速率的速度发送数据。突发结束后，令牌数降到低点，系统再次进入积累期，发送速率回落到平均水平。这一过程循环往复。

这种”积累-突发-恢复”的周期性行为，正是令牌桶能够在保证长期平均速率的同时，充分利用网络带宽的根本原因。

需要特别指出的是，令牌桶的”突发”能力由桶容量 b 决定：b 越大，允许的瞬时突发流量就越大，对带宽的利用率越高；但 b 过大也可能冲击接收端或网络链路，需要根据实际场景权衡。

2.4 令牌桶与漏桶的区别

很多人容易混淆”令牌桶”和”漏桶”（Leaky Bucket）。虽然名称相似，但行为有本质区别：

令牌桶（Token Bucket）：允许突发输出——只要有足够的令牌，数据可以以任意高速率发送。输出速率是”有上限的尽力而为”。

漏桶（Leaky Bucket）：强制平滑输出——无论输入速率多高，输出速率被强制固定在恒定值。输出速率是”硬性固定的”。

简单说：漏桶强制输出平滑，令牌桶允许突发但长期平均受限。在网络传输中，令牌桶更受欢迎，因为网络天然需要应对数据包的突发到达，完全平滑的输出反而可能浪费带宽。

三、令牌数变化曲线

为了直观理解令牌桶的动态行为，我们可以用 Python 绘制令牌数随时间变化的曲线图。运行下面的代码，会生成一张清晰的波形图，展示”积累→突发→恢复→再突发”的完整周期。

import matplotlib.pyplot as plt
import numpy as np

# 设置中文字体
plt.rcParams['font.sans-serif'] = ['SimHei', 'Arial Unicode MS', 'DejaVu Sans']
plt.rcParams['axes.unicode_minus'] = False

# 模拟参数
BURST_CAP = 10.0       # 桶容量
RATE = 0.8             # 令牌生成速率
DT = 0.1               # 时间步长
TOTAL_TIME = 100       # 总模拟时间

t = np.arange(0, TOTAL_TIME, DT)
tokens = np.zeros_like(t)
current = BURST_CAP * 0.5  # 初始令牌数（半满）

for i in range(len(t)):
    # 时间流逝，补充令牌（不能超过桶容量）
    current = min(BURST_CAP, current + RATE * DT)
    
    # 模拟突发消耗（在特定时间段内高速消耗令牌）
    if 20 < t[i] < 25:
        current -= 1.2 * DT
    elif 55 < t[i] < 60:
        current -= 1.5 * DT
    elif 80 < t[i] < 83:
        current -= 2.0 * DT
    
    # 确保不低于0
    current = max(0, current)
    tokens[i] = current

# 创建图形
fig, ax = plt.subplots(figsize=(13, 6))

# 绘制令牌数曲线
ax.plot(t, tokens, linewidth=2.5, color='#1f77b4', label='当前令牌数')

# 标注桶容量
ax.axhline(y=BURST_CAP, color='#ff7f0e', linestyle='--', linewidth=2, 
           label=f'桶容量 B = {BURST_CAP}')

# 标注平均速率线（示意长期平均水平）
avg_line = RATE * 10
ax.axhline(y=avg_line, color='#2ca02c', linestyle=':', linewidth=2, 
           label=f'长期平均速率 (示意)')

# 标注突发区域（红色背景）
ax.axvspan(20, 25, alpha=0.15, color='red', label='突发发送期')
ax.axvspan(55, 60, alpha=0.15, color='red')
ax.axvspan(80, 83, alpha=0.15, color='red')

# 标注积累区域（绿色背景）
ax.axvspan(0, 20, alpha=0.08, color='green', label='令牌积累期')
ax.axvspan(25, 55, alpha=0.08, color='green')
ax.axvspan(60, 80, alpha=0.08, color='green')

# 添加标注箭头
ax.annotate('突发消耗↓\n令牌急剧下降', xy=(22.5, 4), xytext=(22.5, 8.5),
            arrowprops=dict(arrowstyle='->', color='red', lw=2),
            ha='center', fontsize=11, color='red')

ax.annotate('令牌逐渐恢复↑', xy=(40, 2), xytext=(40, 7.5),
            arrowprops=dict(arrowstyle='->', color='green', lw=2),
            ha='center', fontsize=11, color='green')

ax.annotate('再次突发消耗', xy=(57.5, 3), xytext=(57.5, 8.5),
            arrowprops=dict(arrowstyle='->', color='red', lw=2),
            ha='center', fontsize=11, color='red')

ax.annotate('令牌重新积累', xy=(70, 2), xytext=(70, 7),
            arrowprops=dict(arrowstyle='->', color='green', lw=2),
            ha='center', fontsize=11, color='green')

# 图表装饰
ax.set_xlabel('时间', fontsize=13)
ax.set_ylabel('令牌数', fontsize=13)
ax.set_title('令牌桶算法：令牌数随时间变化曲线', fontsize=16, fontweight='bold')
ax.legend(loc='upper right', fontsize=11)
ax.grid(True, alpha=0.3, linestyle='--')
ax.set_xlim(0, TOTAL_TIME)
ax.set_ylim(0, BURST_CAP * 1.15)

plt.tight_layout()

# 保存为高清图片（同时输出PNG和SVG格式）
plt.savefig('token_bucket_waveform.png', dpi=300, bbox_inches='tight')
plt.savefig('token_bucket_waveform.svg', bbox_inches='tight')
plt.show()

运行这段代码后，会得到一张平滑的波形图。图中蓝色曲线代表令牌数的实时变化，红色区域对应突发发送期（令牌快速消耗），绿色区域对应令牌积累期，橙色虚线和绿色点线分别标示了桶容量和长期平均速率的参考位置。

四、工程实现

4.1 朴素实现（有锁版本）

最直接的实现方式是使用一个独立的线程定时生成令牌，并加锁保护共享状态：

#include <mutex>
#include <thread>
#include <chrono>

class SimpleTokenBucket {
public:
    SimpleTokenBucket(double rate, size_t burst)
        : rate_(rate), burst_(burst), tokens_(burst) {
        running_ = true;
        refill_thread_ = std::thread(&SimpleTokenBucket::refillLoop, this);
    }

    ~SimpleTokenBucket() {
        running_ = false;
        if (refill_thread_.joinable()) {
            refill_thread_.join();
        }
    }

    bool consume(size_t tokens) {
        std::lock_guard<std::mutex> lock(mtx_);
        if (tokens_ >= tokens) {
            tokens_ -= tokens;
            return true;
        }
        return false;
    }

private:
    void refillLoop() {
        while (running_) {
            std::this_thread::sleep_for(std::chrono::seconds(1));
            std::lock_guard<std::mutex> lock(mtx_);
            tokens_ = std::min(burst_, tokens_ + rate_);
        }
    }

    const double rate_;
    const size_t burst_;
    double tokens_;
    std::mutex mtx_;
    std::thread refill_thread_;
    bool running_ = true;
};

这种实现的问题：

首先，它需要一个独立的线程来定时补充令牌，这增加了系统开销和代码复杂度。其次，每秒只更新一次令牌数，精度有限，无法做到微秒级的平滑控制。最后，如果 consume 调用非常频繁，互斥锁会成为性能瓶颈。

4.2 惰性计算优化

更优雅的做法是不使用独立线程，而是在每次调用 consume 时根据时间差计算应该新增多少令牌。这就是”惰性计算”的核心思想：

class LazyTokenBucket {
public:
    LazyTokenBucket(double rate, size_t burst)
        : rate_(rate), burst_(burst), tokens_(burst) {
        last_update_ = std::chrono::steady_clock::now();
    }

    bool consume(size_t tokens) {
        std::lock_guard<std::mutex> lock(mtx_);
        updateTokens();
        if (tokens_ >= tokens) {
            tokens_ -= tokens;
            return true;
        }
        return false;
    }

private:
    void updateTokens() {
        auto now = std::chrono::steady_clock::now();
        double elapsed = std::chrono::duration<double>(now - last_update_).count();
        tokens_ = std::min(burst_, tokens_ + elapsed * rate_);
        last_update_ = now;
    }

    const double rate_;
    const size_t burst_;
    double tokens_;
    std::chrono::steady_clock::time_point last_update_;
    std::mutex mtx_;
};

优化效果：不需要独立线程；更新精度取决于时钟精度（通常微秒级）；令牌计算完全由调用驱动，空闲时零开销。

4.3 无锁实现：高性能方案

rigtorp/TokenBucket 是目前C++社区最知名的无锁令牌桶实现，在 GitHub 上可以找到。它的核心设计思路如下：

数据结构：所有共享状态（当前令牌数、上次更新时间）都使用 std::atomic 包装，保证读写操作的原子性。

CAS循环：核心操作采用 Compare-And-Swap 循环。线程先读取当前状态的快照，计算新的令牌数，然后尝试原子性地更新。如果更新过程中数据被其他线程修改了，就重新读取并重试，直到成功为止。

惰性时间计算：同样采用惰性策略，在每次 consume 调用时根据时间差计算应补充的令牌数。

内存序优化：使用精细的 std::memory_order 控制内存可见性，在保证正确性的前提下最大化性能。

这种无锁设计避免了线程挂起和上下文切换，在高并发场景下拥有显著更好的性能和扩展性。

4.4 不同实现的性能对比

实现方案吞吐量延迟适用场景
独立线程+互斥锁低（锁竞争严重）较高低并发场景
惰性计算+互斥锁中等中等一般并发场景
惰性计算+无锁CAS高低高并发、高性能场景

五、应用操作指南

5.1 基础配置：如何选择合适的参数

参数选择取决于具体场景，以下是一些通用准则：

rate（平均速率）的确定：

  • 网络带宽限制场景：设为可用带宽的 80%~90%，留出协议开销余量
  • API限流场景：根据服务器处理能力设定，通常为峰值QPS的70%
  • 视频流传输场景：设为视频平均码率的 1.1~1.2 倍
  • 文件传输场景：根据带宽和接收端处理能力综合设定

burst（突发容量）的确定：

一般经验公式：burst = rate × T，其中 T 是你允许的最大突发持续时间（秒）。

  • 对实时性要求高：T = 1~3 秒，允许短时间高速发送
  • 对平滑性要求高：T = 0.1~0.5 秒，限速更严格
  • 视频流中关键帧（I帧）很大：T 至少能容纳一个关键帧的大小

5.2 完整代码示例：集成到网络发送

以下是一个完整的网络发送器示例，展示了如何将令牌桶集成到实际的发送逻辑中：

#include "TokenBucket.h"
#include <asio.hpp>  // 或者使用你的网络库
#include <iostream>
#include <fstream>
#include <thread>
#include <chrono>
#include <vector>

class RateLimitedSender {
public:
    RateLimitedSender(const std::string& host, int port, 
                     double rate_byte_per_sec, size_t burst_bytes)
        : limiter_(rate_byte_per_sec, burst_bytes)
        , socket_(io_context_) {
        asio::ip::tcp::resolver resolver(io_context_);
        auto endpoints = resolver.resolve(host, std::to_string(port));
        asio::connect(socket_, endpoints);
    }

    // 非阻塞发送：令牌不足时直接返回 false
    bool send(const std::vector<char>& data) {
        size_t data_size = data.size();
        if (!limiter_.consume(data_size)) {
            return false;
        }
        auto bytes_sent = asio::write(socket_, asio::buffer(data));
        return bytes_sent == data_size;
    }

    // 阻塞发送：确保数据一定能发送出去
    void sendBlocking(const std::vector<char>& data) {
        size_t data_size = data.size();
        while (!limiter_.consume(data_size)) {
            std::this_thread::sleep_for(std::chrono::milliseconds(1));
        }
        asio::write(socket_, asio::buffer(data));
    }

private:
    rigtorp::TokenBucket limiter_;
    asio::io_context io_context_;
    asio::ip::tcp::socket socket_;
};

5.3 高级技巧：大包分块发送

当数据包超过 burst 容量时，应拆分成小块发送，避免单个大包永远无法通过限速器：

void sendLargeData(const std::vector<char>& data, 
                   RateLimitedSender& sender,
                   size_t chunk_size = 64 * 1024) {
    for (size_t offset = 0; offset < data.size(); offset += chunk_size) {
        size_t len = std::min(chunk_size, data.size() - offset);
        std::vector<char> chunk(data.begin() + offset, 
                                data.begin() + offset + len);
        while (!sender.send(chunk)) {
            std::this_thread::sleep_for(std::chrono::milliseconds(1));
        }
    }
}

5.4 常见陷阱与解决方案

时钟跳变问题：如果使用系统时间（如 system_clock），系统时间被修改会导致令牌计算错误。解决方案是使用 steady_clock，它提供单调递增的时钟，不受系统时间调整影响。

饥饿问题：非常大的数据包可能永远无法获得足够的令牌。解决方案是采用分块发送策略，将大包拆成多个小包分别过限速器。

精度损失：使用整数存储令牌数会导致小包累积误差。解决方案是使用浮点数存储令牌数，允许小数令牌的存在。

CPU空转：阻塞模式中使用 while 循环持续重试会占满 CPU。解决方案是在循环中添加 sleep_for 等待，或者使用条件变量。

突发过大：过大的 burst 参数可能冲击接收端缓冲区。解决方案是根据接收端的处理能力合理设置 burst，或者结合漏桶算法做二级平滑。

六、实际应用场景分析

6.1 场景一：视频流播发

视频流的特点是：I帧（关键帧）很大，P帧和B帧相对较小，码率波动剧烈。

配置建议：平均速率设为视频平均码率的 1.1 倍，突发容量至少能容纳一个最大 I 帧的大小，通常设为最大 I 帧的 2~3 倍。

这样配置的效果是：普通帧平滑发送，I帧来临时允许短时间突发，播放端缓冲区保持稳定。

6.2 场景二：API网关限流

API网关需要同时控制请求数量和总流量，保护后端服务不被冲垮。

配置建议：同时使用两个限速器——一个按请求数限流（如每秒1000个请求），一个按字节数限流（如每秒50MB）。每个请求必须同时通过两个限速器才能被处理。

6.3 场景三：TCP流量控制的补充

TCP自身有拥塞控制机制，但在应用层配合令牌桶可以做到更精细的速率控制。应用层限速作为”第一道防线”，保证即使TCP窗口允许高速发送，也不会过度占用网络带宽。

七、总结

令牌桶算法的核心价值在于：通过”以恒定速率生成令牌、消耗令牌才能发送”的机制，实现了对突发流量的容忍和对平均速率的精确控制。

从实现角度看，从简单的线程加锁方案，到高效的惰性计算加无锁CAS方案，性能不断提升。rigtorp/TokenBucket 代表了C++社区的最佳实践，推荐在生产环境中使用。

从应用角度看，参数选择要根据具体场景平衡”突发容忍度”和”速率平滑性”，没有放之四海皆准的配置。合理设置 rate 和 burst，配合分块发送、多级限流等高级技巧，可以应对绝大多数网络速率控制需求。

随着网络技术的演进，令牌桶算法也在不断发展，包括AI驱动的动态参数调整、多级令牌桶的精细化控制、以及硬件层面的加速实现。但无论技术如何演进，令牌桶这一经典算法的核心思想——”以许可机制平滑流量”——始终具有持久的生命力。

参考文献

  1. Turner, J. S. (1986). New directions in communications (or which way to the information age?). IEEE Communications Magazine, 24(10), 8-15.
  2. Tanenbaum, A. S., & Wetherall, D. J. (2011). Computer Networks (5th ed.). Pearson.
  3. Kurose, J. F., & Ross, K. W. (2017). Computer Networking: A Top-Down Approach (7th ed.). Pearson.
  4. ritorp/TokenBucket GitHub Repository: https://github.com/rigtorp/TokenBucket
作者

老丹

关注我
其他文章