3. 常见限流算法：原理与数学推导

在金融压力测试场景中，限流算法的选择直接决定系统在高并发下的行为特征。本节从数学原理出发，深入剖析四种经典限流算法：计数器算法、滑动窗口算法、漏桶算法与令牌桶算法，并给出各自的适用边界与数学推导。

3.1 计数器算法（Counter Algorithm）

原理：将时间划分为固定大小的窗口（如 1 秒），每个窗口内维护一个计数器。请求到达时计数器加 1，若计数器超过阈值则拒绝；窗口结束时计数器归零。

数学推导：

• 设窗口大小为 \( T \)（单位：秒），阈值上限为 \( N \)（单位：请求数）。
• 在任意窗口 \( [k \cdot T, (k+1) \cdot T) \) 内，累计请求数 \( C(t) \) 满足：

C(t) = Σ_{i=1}^{m} 1_{t_i ∈ [kT, (k+1)T)}

• 限流条件：\( C(t) \leq N \)，否则拒绝后续请求。
• 临界突变问题：若在窗口末尾（如 0.99s）突发 N 个请求，紧接着下一窗口开头（1.00s）又突发 N 个请求，则瞬时 QPS 可达 \( 2N \)，远超阈值。

3.2 滑动窗口算法（Sliding Window Algorithm）

原理：将固定窗口细分为多个子窗口（如 1 秒分为 10 个 100ms 子窗口），每个子窗口独立计数。滑动窗口以当前时间为终点，向前取一个完整窗口长度，统计所有子窗口的累计请求数。

数学推导：

• 设窗口总长度 \( T \)，子窗口数量 \( n \)，每个子窗口长度 \( \Delta t = T / n \)。
• 当前时间 \( t \) 对应的滑动窗口区间为 \( [t - T, t) \)。
• 累计请求数：

C_slide(t) = Σ_{j=0}^{n-1} count(子窗口_{t - (j+1)Δt}^{t - jΔt})

• 限流条件：\( C_slide(t) \leq N \)。
• 精度与粒度：子窗口数 \( n \) 越大，滑动窗口越平滑，但内存开销线性增长。当 \( n \to \infty \) 时，滑动窗口趋近于精确的令牌桶。

3.3 漏桶算法（Leaky Bucket Algorithm）

原理：将请求视为水滴，漏桶以恒定速率漏水（处理请求）。桶有最大容量，超出容量的请求被丢弃。漏桶强制输出速率恒定，适合保护下游系统。

数学推导：

• 设桶容量 \( C \)（单位：请求数），漏水速率 \( r \)（单位：请求/秒）。
• 当前桶内水量 \( W(t) \) 满足微分方程：

dW(t)/dt = λ(t) - r

• 其中 \( λ(t) \) 为到达速率。限流条件：\( W(t) \leq C \)。
• 稳态解：当 \( λ(t) > r \) 持续时，桶满后丢弃率为 \( (λ - r) / λ \)。
• 关键特性：输出速率恒为 \( r \)，与输入突发无关。但无法应对“瞬时高吞吐”需求（如缓存预热）。

3.4 令牌桶算法（Token Bucket Algorithm）

原理：系统以恒定速率向桶中放入令牌，每个请求消耗一个令牌。桶有最大令牌数上限。若桶中有令牌则放行，否则拒绝。令牌桶允许一定程度的突发流量。

数学推导：

• 设桶容量 \( B \)（最大令牌数），令牌生成速率 \( r \)（令牌/秒）。
• 当前令牌数 \( T(t) \) 满足：

dT(t)/dt = r - μ(t)

• 其中 \( μ(t) \) 为消耗速率。限流条件：\( T(t) \geq 1 \) 时放行。
• 突发能力：若桶初始满（\( T(0) = B \)），则允许瞬时突发 \( B \) 个请求，之后输出速率被限制为 \( r \)。
• 稳态吞吐：长期平均速率不超过 \( r \)，但短时峰值可达 \( B + r \cdot \Delta t \)。

3.5 算法选型对比总结