3、令牌桶算法原理

令牌桶算法（Token Bucket）是限流领域最常用的算法之一，它通过一个“桶”来平滑突发流量，同时允许一定程度的突发请求，比漏桶算法更具灵活性。本节将深入剖析令牌桶的工作机制、核心参数、适用场景，并与漏桶算法进行对比。

3.1 工作机制

令牌桶算法的核心思想是：系统以恒定速率向一个桶中放入令牌，每个请求在到达时必须从桶中获取一个令牌才能被处理。如果桶中没有令牌，请求将被拒绝或等待。

• 令牌生成：系统以固定的速率（如每秒 100 个）向桶中添加令牌。
• 桶容量：桶有一个最大容量（如 200 个），超过容量的令牌会被丢弃。
• 请求消费：每个请求到达时，尝试从桶中取出一个令牌。如果成功，请求被放行；如果失败，请求被限流。
• 突发处理：当桶中积累了大量令牌（如空闲期），可以一次性处理多个突发请求，直到桶空。

3.2 参数配置

令牌桶算法有两个核心参数，它们共同决定了限流的效果：

3.3 适用场景

令牌桶算法特别适合以下场景：

• API 网关限流：允许用户在短时间内发起突发请求（如刷新页面），但长期速率受控。
• 微服务间调用：保护下游服务不被突发流量冲垮，同时允许正常的业务峰值。
• 消息队列消费：控制消费者从队列中拉取消息的速率，同时允许积压消息的快速消费。
• 数据库连接池：限制每秒的数据库查询次数，但允许短时间内的查询爆发。

3.4 与漏桶算法的对比

漏桶算法（Leaky Bucket）是另一种经典的限流算法，它与令牌桶算法在机制和效果上有显著差异。下表从多个维度进行对比：

3.5 Go 语言实现示例

以下是一个基于时间戳计算的令牌桶实现，不依赖外部定时器，适合在 Go 服务中直接使用：

package tokenbucket

import (
    "sync"
    "time"
)

type TokenBucket struct {
    rate       float64 // 每秒生成的令牌数
    burst      float64 // 桶的最大容量
    tokens     float64 // 当前令牌数
    lastTime   time.Time // 上次更新时间
    mu         sync.Mutex
}

func NewTokenBucket(rate, burst float64) *TokenBucket {
    return &TokenBucket{
        rate:     rate,
        burst:    burst,
        tokens:   burst, // 初始时桶是满的
        lastTime: time.Now(),
    }
}

func (tb *TokenBucket) Allow() bool {
    tb.mu.Lock()
    defer tb.mu.Unlock()

    now := time.Now()
    // 计算时间差，补充令牌
    elapsed := now.Sub(tb.lastTime).Seconds()
    tb.tokens += elapsed * tb.rate
    if tb.tokens > tb.burst {
        tb.tokens = tb.burst
    }
    tb.lastTime = now

    // 判断是否有令牌可用
    if tb.tokens >= 1 {
        tb.tokens--
        return true
    }
    return false
}