2. 常见限流算法详解：计数器算法、滑动窗口算法、漏桶算法、令牌桶算法的原理与数学推导
在金融API网关与微服务架构中，限流算法的选择直接决定了系统的抗冲击能力与资源利用率。本章从数学原理出发，逐一剖析四种经典限流算法的数学模型、实现要点与适用场景。
2.1 计数器算法（Counter Algorithm）
计数器算法是最直观的限流实现，在固定时间窗口内维护一个计数器，当请求到达时计数器加1，若计数器超过阈值则拒绝请求，窗口结束后计数器重置。
数学推导
设时间窗口长度为 T（单位：秒），窗口内最大允许请求数为 N。在任意时刻 t，当前窗口内的请求计数为 C(t)。限流判定条件为：
C(t) < N → 允许请求，C(t) = C(t) + 1
C(t) ≥ N → 拒绝请求窗口重置逻辑：当 t mod T = 0 时，C(t) = 0。
临界突变问题
计数器算法存在明显的“窗口边界突变”缺陷：在窗口切换的瞬间，流量可能瞬间翻倍。例如 T=1s, N=100，若第0.9s~1.0s内通过100个请求，第1.0s~1.1s内又通过100个请求，则实际0.2s内通过了200个请求，远超平均速率。
2.2 滑动窗口算法（Sliding Window Algorithm）
滑动窗口算法将固定窗口细分为多个子窗口，通过滑动子窗口的统计来平滑流量，消除计数器算法的边界突变问题。
数学推导
将时间窗口 T 划分为 m 个等长子窗口，每个子窗口长度为 T/m。维护一个长度为 m 的环形数组 counts[]，记录每个子窗口内的请求数。当前时间 t 对应的子窗口索引为：
index = floor(t / (T/m)) % m当前窗口总请求数 S(t) 为所有子窗口计数之和：
S(t) = Σ counts[i] (i = 0, 1, ..., m-1)限流判定：S(t) < N 则允许，否则拒绝。
精度与开销权衡
| 子窗口数 m | 精度提升 | 内存开销 | 推荐场景 |
|---|---|---|---|
| 2~5 | 低 | 极低 | 非核心监控、日志限流 |
| 10~20 | 中 | 低 | 普通API限流 |
| 50~100 | 高 | 中 | 金融核心交易、高频交易 |
2.3 漏桶算法（Leaky Bucket Algorithm）
漏桶算法将请求视为水滴，以恒定速率从桶底漏出，桶容量有限，超出容量的请求被丢弃。该算法强制输出流量完全平滑，适用于需要严格整形流量的场景。
数学推导
定义漏桶参数：
- 容量 C：桶的最大存储请求数
- 漏出速率 r：单位时间漏出的请求数（请求/秒）
- 当前水量 W(t)：t 时刻桶内的请求数
漏桶的微分方程：
dW(t)/dt = λ(t) - r其中 λ(t) 为 t 时刻的请求到达速率。离散化实现：
// 每次请求到达时执行
current_time = now()
elapsed = current_time - last_leak_time
water = max(0, water - elapsed * r) // 先漏水
if water < C:
water += 1 // 允许请求
last_leak_time = current_time
return true
else:
return false // 桶满，拒绝关键特性
| 特性 | 描述 | 金融场景影响 |
|---|---|---|
| 输出速率恒定 | 无论输入流量多大，输出始终 ≤ r | 保护下游系统不被突发流量冲垮 |
| 允许突发输入 | 桶容量 C 可吸收瞬时突发 | 适合处理短时脉冲，但延迟会增加 |
| 无法应对空载 | 桶空时无法加速输出 | 空闲时段资源无法被利用 |
2.4 令牌桶算法（Token Bucket Algorithm）
令牌桶算法以恒定速率向桶中添加令牌，请求到达时需消耗一个令牌才能通过。与漏桶不同，令牌桶允许一定程度的突发流量，是业界最广泛使用的限流算法。
数学推导
定义令牌桶参数：
- 桶容量 B：桶中最多存放的令牌数
- 令牌生成速率 r：每秒生成的令牌数
- 当前令牌数 T(t)：t 时刻桶内的令牌数
令牌生成过程：
T(t) = min(B, T(t₀) + r × (t - t₀))请求消耗令牌：
if T(t) ≥ 1:
T(t) = T(t) - 1
return true // 允许请求
else:
return false // 令牌不足，拒绝突发能力分析
令牌桶允许的最大突发请求数等于桶容量 B。当桶满时，可一次性处理 B 个请求，之后输出速率被限制为 r。长期平均速率同样为 r。
2.5 四种算法对比与选型
| 算法 | 输出平滑度 | 突发能力 | 实现复杂度 | 内存开销 | 金融推荐度 |
|---|---|---|---|---|---|
| 计数器 | 差（边界突变） | 高（窗口边界） | 极低 | 极低 | ★☆☆☆☆ |
| 滑动窗口 | 中（取决于m） | 中 | 低 | 低 | ★★★☆☆ |
| 漏桶 | 极高（严格整形） | 低（受限于容量） | 中 | 低 | ★★★★☆ |
| 令牌桶 | 高 | 高（可配置B） | 中 | 低 | ★★★★★ |
2.6 分布式环境下的算法演进
在分布式金融系统中，单机限流需要扩展为集群限流。核心挑战在于：如何在高并发下维持全局计数的一致性？
分布式令牌桶实现方案
- Redis + Lua 脚本：利用 Redis 单线程模型和 Lua 原子性，实现分布式令牌桶。每次请求执行一次 Lua 脚本，保证令牌获取的原子性。
- 本地令牌桶 + 定期同步：每个节点维护本地令牌桶，通过配置中心（如 etcd/Consul）定期同步全局配额。牺牲一定精度换取性能。
- Sentinel 集群流控：阿里开源的 Sentinel 提供 Token Server/Client 模式，由 Token Server 统一分配令牌，Client 本地缓存。
// Redis + Lua 分布式令牌桶核心逻辑
local key = KEYS[1] -- 令牌桶key
local rate = tonumber(ARGV[1]) -- 令牌生成速率
local capacity = tonumber(ARGV[2]) -- 桶容量
local now = tonumber(ARGV[3]) -- 当前时间戳（毫秒）
local requested = tonumber(ARGV[4])-- 请求消耗令牌数
local last_time = redis.call('hget', key, 'last_time') or now
local tokens = redis.call('hget', key, 'tokens') or capacity
-- 计算时间差，生成新令牌
local elapsed = math.max(0, now - last_time)
tokens = math.min(capacity, tokens + elapsed * rate / 1000)
-- 判断是否允许
if tokens >= requested then
tokens = tokens - requested
redis.call('hmset', key, 'tokens', tokens, 'last_time', now)
return 1 -- 允许
else
redis.call('hmset', key, 'tokens', tokens, 'last_time', now)
return 0 -- 拒绝
end