📚 课程目录第2章限流算法基础

2、限流算法基础：令牌桶算法原理、漏桶算法原理、计数器算法与滑动窗口算法对比

在金融API网关中，限流算法的选择直接决定了系统的防护效果与用户体验。本章深入剖析四种核心限流算法的数学原理、实现要点与适用场景，为后续框架搭建奠定理论基础。

2.1 令牌桶算法（Token Bucket）

令牌桶算法是业界应用最广泛的限流算法之一，其核心思想是：系统以恒定速率向桶中放入令牌，每个请求必须获取一个令牌才能被处理；当桶中令牌耗尽时，请求被拒绝或排队等待。

  核心参数：
  桶容量（capacity）：令牌桶的最大容量，决定突发流量可消耗的令牌上限。
令牌生成速率（rate）：每秒向桶中放入的令牌数量，决定长期平均处理速率。
当前令牌数（tokens）：桶中实时剩余的令牌数量，受上次请求时间和生成速率影响。

金融场景最佳实践：令牌桶算法天然支持突发流量——当系统空闲时桶会积累令牌，瞬间高峰请求可消耗这些令牌，避免误杀正常交易。在证券行情推送、支付回调等场景中，建议将桶容量设置为平均速率的2~3倍。

2.2 漏桶算法（Leaky Bucket）

漏桶算法与令牌桶形成对称结构：请求以任意速率进入漏桶，桶以固定速率向下漏水（处理请求）；当桶满时，新进入的请求被丢弃。其核心特征是强制平滑流量，不允许任何突发。

关键区别：漏桶算法不允许任何突发流量，即使系统空闲也会强制以固定速率处理请求。在金融API中，漏桶适用于对延迟不敏感但必须严格限制速率的场景，如批量对账文件上传、报表导出等后台任务。

2.3 计数器算法（Counter / Fixed Window）

计数器算法是最直观的限流实现：将时间划分为固定窗口（如1秒），每个窗口内维护一个计数器，请求到达时计数器加1；当计数器超过阈值时拒绝请求，窗口结束时计数器归零。

实现伪代码：

class FixedWindowCounter:
    def __init__(self, limit, window_size_ms):
        self.limit = limit          # 窗口内最大请求数
        self.window_size = window_size_ms  # 窗口大小（毫秒）
        self.counter = 0
        self.window_start = now()
    
    def allow_request(self):
        current = now()
        if current - self.window_start >= self.window_size:
            self.window_start = current
            self.counter = 0
        self.counter += 1
        return self.counter <= self.limit

2.4 滑动窗口算法（Sliding Window）

滑动窗口算法是计数器算法的改进版本，它将窗口进一步细分为多个小格（如1秒窗口分为10个100ms小格），每次判断时统计当前时间点往前一个完整窗口内的总请求数，从而消除固定窗口的边界突刺问题。

边界突刺问题：固定窗口算法在窗口切换瞬间可能出现两倍阈值的请求通过——例如窗口1最后100ms通过100个请求，窗口2开始100ms又通过100个请求，实际200ms内通过了200个请求。滑动窗口通过细粒度统计有效抑制此类突刺。

2.5 四种算法对比总结

对比维度	令牌桶	漏桶	计数器（固定窗口）	滑动窗口
突发处理能力	支持突发（桶内积攒令牌）	不支持突发（强制平滑）	窗口内支持突发	窗口内支持突发
边界突刺风险	无（连续时间模型）	无（连续时间模型）	严重（窗口切换瞬间）	轻微（取决于小格粒度）
实现复杂度	中等（需维护时间戳）	中等（需维护队列或时间戳）	低（仅需计数器和时间）	较高（需维护小格数组）
内存开销	O(1)	O(1) 或 O(队列长度)	O(1)	O(小格数)
适用金融场景	交易接口、行情推送	批量任务、对账导出	简单限流、非关键路径	核心交易、精确限流
精度	高（连续时间）	高（连续时间）	低（窗口边界误差）	中~高（取决于小格数）

2.6 算法选型决策树

在实际金融系统架构中，可按照以下决策路径选择限流算法：

是否需要支持突发流量？
- 是 → 令牌桶算法（首选）或滑动窗口（次选）
- 否 → 漏桶算法或计数器算法
是否对边界突刺敏感？
- 是（如支付、下单接口）→ 令牌桶或滑动窗口
- 否（如日志上报、非核心查询）→ 计数器算法
实现与运维成本要求？
- 低 → 计数器算法
- 中 → 令牌桶算法（推荐）
- 高 → 滑动窗口算法（需调优小格数）

  框架选型建议：在《金融API限流熔断Python框架》中，我们将以令牌桶算法作为核心限流器，同时提供滑动窗口算法作为高精度备选方案。令牌桶在突发处理、实现复杂度、内存开销三个维度上取得了最佳平衡，且天然支持分布式场景下的令牌同步。