一、固定窗口算法（计数器）
1. 简介
固定窗口算法（Fixed Window Algorithm），又称计数器算法，是最简单、最直观的一种限流方式：把时间切成一个个连续的固定窗口，并对每个窗口内能够通过的请求数设定上限。
Fixed Window
2. 工作原理
可以把时间想象成一条被均匀切分的时间轴，例如：
- 按秒限流：每 1 秒是一个窗口；
- 按分钟限流：每 1 分钟是一个窗口。
在固定窗口算法中，一般会维护三个核心信息：
- 当前窗口的起始时间；
- 当前窗口内已经通过的请求数量（计数器）；
- 每个窗口允许通过的最大请求数（阈值）。
具体处理过程如下：
- 确定时间窗口：请求到达时，根据当前时间计算出它属于哪个窗口（例如：
now / interval）。 - 窗口切换与重置：如果发现当前时间已经跨过了上一个窗口：
- 更新“当前窗口起始时间”；
- 将计数器重置为 0。
- 计数与判断：
- 若当前窗口的计数器
< 阈值：将计数器+1，并放行请求； - 若计数器已经
>= 阈值：直接拒绝请求。
- 若当前窗口的计数器
这样，就能保证：在每个时间窗口内，最多只会有 threshold 个请求被通过。
3. 算法特点
- 实现简单：只需要一个计数器和一个时间标记即可完成限流逻辑，几乎所有语言都可以几行代码实现。
- 行为“硬性”：在单个时间窗口内，可以非常清楚地知道“已经通过了多少个请求，还能再放行多少个”，易于理解和调试。
- 容易出现“临界突刺”：这是固定窗口算法最大的缺点。
所谓“临界突刺”，指的是窗口交界附近的瞬时流量，可能远大于设定的限流阈值。例如：
- 设定：每秒最多 100 个请求通过；
- 在
第 0.9 秒 ~ 1.0 秒这 100ms 内，突然来了 100 个请求，全部落在“第 0 秒这个窗口”里，被放行； - 紧接着，在
第 1.0 秒 ~ 1.1 秒这 100ms 内，又来了 100 个请求，此时已经进入“第 1 秒这个窗口”，计数器被重置，又可以全部放行。
从限流规则上看，是第 0 秒窗口 100 个 + 第 1 秒窗口 100 个，规则并没有被破坏；
但从“真实时间”看，在大约 200ms 的极短时间内通过了 200 个请求，瞬时 QPS 实际上达到了 2 倍阈值，这对某些对瞬时流量非常敏感的系统来说，可能依然是不可接受的。
二、滑动窗口算法
1. 简介
滑动窗口算法是在固定窗口算法基础上的改进，目标是解决“窗口边界瞬间放过两倍流量”的问题，让任意连续时间段内的请求数都更加接近设定阈值。
核心思路是：不再只看“自然时间段”（比如 10:00–10:01），而是以请求的时间点为起点，向前回溯一个固定长度的窗口（例如最近 1 秒或最近 1 分钟），统计这段时间内的请求数。
常见有两种实现方式：
- 滑动窗口计数器算法；
- 滑动窗口日志（或时间戳）算法。
rolling window
2. 工作原理
1）滑动窗口计数器算法
滑动窗口计数器可以理解为“对固定窗口计数器做更细粒度的拆分和加权”：
- 将整个时间轴再细分成多个小格子，例如：1 秒的窗口拆成 10 个 100ms 子窗口；
- 每个子窗口都有自己的计数器；
- 当前请求到来时：
- 先淘汰“已经完全滑出统计窗口之外”的旧子窗口；
- 把还在窗口内的子窗口计数加总，得到“最近 1 秒”的请求数近似值；
- 若加总结果 < 阈值，则当前子窗口计数 +1，放行请求，否则拒绝。
这种方式属于“分段近似滑动”，实现比较简单，但仍然是近似值，窗口越细粒度，统计越精确，开销越大。
2）滑动窗口日志算法
滑动窗口日志算法会记录每一次请求的时间戳：
- 为每个限流对象维护一个有序列表（或队列），存储最近一段时间内所有请求的时间戳；
- 每个请求到来时：
- 从队头开始删除“时间戳 < 当前时间 - 窗口大小”的过期记录；
- 剩余的记录条数就是“当前滑动窗口内的真实请求数”；
- 若条数 < 阈值，则在尾部追加一条当前时间的记录，放行请求；
- 否则拒绝。
这种方式统计精度最高，是真正意义上的“任意连续窗口”限流，但需要在内存或存储中保存更多历史记录。
3. 使用场景与优劣分析
使用场景
- 对“瞬时流量”敏感、不能接受固定窗口临界突刺的接口；
- 需要按“最近 N 秒 / N 分钟”做严格配额控制的场景，例如：
- 按用户、IP、API Key 做调用频率限制；
- 计费型接口、风控策略中的频次规则。
优点
- 相比固定窗口，能有效平滑窗口边界处的突刺流量；
- 滑动窗口日志算法在统计上更接近“真实连续时间窗口”，限流行为更严格可控。
缺点
- 实现和存储开销明显高于固定窗口；
- 滑动窗口计数器是近似算法，精度与拆分粒度有关；
- 滑动窗口日志需要维护大量时间戳记录，在高并发、长窗口场景下要注意内存与清理策略。
在 Go 生态中，滑动窗口更常见于自研实现或者基于 Redis 的服务端限流逻辑中，而通用开源库多采用令牌桶或漏桶算法作为默认实现。
三、令牌桶算法
1. 简介
令牌桶算法（Token Bucket）是最常用、最通用的限流算法之一。它通过向“桶”中按固定速率放入令牌，请求只有在获取到令牌时才被允许通过，从而控制平均处理速率，同时允许一定程度的突发流量。
在很多网关、API 网关、客户端 SDK 中，令牌桶都是默认或推荐的限流策略。
Tokenbucket
2. 工作原理
- 维护一个容量为
capacity的“令牌桶”； - 以固定速率
rate往桶中放入令牌，如果桶已满则新的令牌会被丢弃； - 每次请求到来时：
- 尝试从桶中取出 1 个令牌；
- 如果取到令牌，则请求通过；
- 如果桶中没有令牌，则拒绝或排队等待（取决于实现）。
令牌桶的关键特性是：
- 平均速率受令牌生成速率约束；
- 突发能力由桶容量决定：桶中积累的令牌可以允许短时间内的请求高峰。
Traffic spike
3. 使用场景与优劣分析
使用场景
- 公共 API、开放平台接口的频率控制；
- 支持短时间突发流量，但整体需要控制在平均速率以内的业务；
- 单机限流、中间件限流（HTTP 中间件、gRPC 拦截器等）。
优点
- 能平衡“稳定速率控制”和“一定程度的突发”；
- 参数含义清晰：
rate控制平均速率，capacity控制可承受的突发程度； - 实现简单，容易分布式扩展（结合 Redis、滑动窗口等）。
缺点
- 令牌生成速率与桶容量需要根据业务仔细调优；
- 如果桶容量设置过大，仍可能在短时间内形成较高瞬时流量；
- 对于要求“流量绝对平滑”的场景，可能不如漏桶算法适配。
4. Go 三方库示例：golang.org/x/time/rate
Go 官方扩展库 golang.org/x/time/rate 提供了一个高质量的令牌桶限流实现，使用方式非常简单：
CodeBlock Loading...
NewLimiter(10, 20) 表示：
- 平均每秒允许 10 个请求；
- 在令牌充足时，最多可以瞬间放行 20 个请求（桶容量）。
该库还支持按上下文阻塞等待（Wait / WaitN），常用于需要限速但不希望直接拒绝请求的场景，例如客户端对下游服务的调用。
四、漏桶算法
1. 简介
漏桶算法（Leaky Bucket）和令牌桶一样，也是非常经典的限流与整形（shaping）算法。可以把它想象成一个“底部有孔的桶”：
请求先进入桶中排队，桶会以一个固定速率向外“漏水”，即以恒定速度处理请求。
当短时间内请求大量涌入时：
- 超过桶容量的请求要么被丢弃，要么被阻塞等待；
- 对外表现为平滑、稳定的输出速率。
LeakyBucket
2. 工作原理
- 为每个限流对象维护一个容量为
capacity的队列（漏桶）； - 到达的请求先进入桶中排队；
- 后台有一个“出水速率”为
rate的消费者，以固定间隔从桶中取出请求并处理； - 当桶满时，再有新请求到来：
- 要么直接丢弃（拒绝）；
- 要么阻塞等待空间腾出（取决于实现）。
与令牌桶“先发令牌、后消费”不同，漏桶更像是“先收请求、再匀速放出”。
3. 使用场景与优劣分析
使用场景
- 对下游服务、数据库等资源敏感，要求“请求处理速率尽量平滑、不能有大的抖动”的场景；
- 需要做“流量整形”的系统，比如：
- 对第三方较脆弱接口的访问；
- 对批量任务、消息消费做限速处理。
优点
- 输出速率稳定，可很好地保护下游服务不被突发流量压垮；
- 行为容易预期：基本不出现突发性的高 QPS 峰值。
缺点
- 对于需要“允许一定突发”的业务不够友好，可能会过度平滑；
- 队列占用资源，需要考虑桶容量、丢弃策略等；
- 与令牌桶相比，整体吞吐调优略显复杂。
4. Go 三方库示例
1）go.uber.org/ratelimit：阻塞式漏桶限速
Uber 开源的 go.uber.org/ratelimit 提供了一个阻塞式漏桶限流器：
CodeBlock Loading...
Take 会在必要时阻塞，使两次调用之间的间隔尽量稳定，从而实现“平滑限速”。这种方式适合：
- 客户端对外部依赖（例如第三方 API）的访问限速；
- 服务内部对某些昂贵操作（例如批量写数据库）的节流。
2）与令牌桶库配合使用
在很多工程实践中，会组合使用：
- 入口处用令牌桶控制整体速率与突发能力；
- 下游调用前用漏桶（或基于时间间隔的节流）进一步平滑流量。
两种算法各有侧重：令牌桶更适合控制“平均速率 + 突发”，漏桶更适合“稳定输出 + 保护下游”。
五、算法对比与选型建议
1. 关键维度对比
可以从几个常见维度来横向比较前面几种算法：
实现复杂度
- 固定窗口：最简单，计数器 + 窗口时间。
- 滑动窗口：需要更细粒度窗口或维护时间戳队列，实现和存储更复杂。
- 令牌桶：中等复杂度，实现和调参都比较成熟。
- 漏桶：实现上需要队列或时间调度，对整体吞吐和延迟影响更大，需要结合业务仔细设计。
是否允许突发流量
- 固定窗口：在窗口边界处会出现“临界突刺”，相当于允许某些“不可控”的突发。
- 滑动窗口：对突发更敏感，任意连续时间窗口统计更接近阈值，突发空间有限。
- 令牌桶：可以显式通过桶容量控制“可接受的突发量”。
- 漏桶：几乎不允许突发，对外表现为较为稳定的输出速率。
流量平滑程度
- 固定窗口：窗口内可能出现抖动，边界处更明显。
- 滑动窗口：比固定窗口更平滑。
- 令牌桶：总体比较平滑，但允许短时间集中消耗令牌。
- 漏桶：最平滑，输出速率接近常数。
状态和存储开销
- 固定窗口：一个计数器 + 一个时间标记，开销最小。
- 滑动窗口计数器：多个子窗口计数器，仍在可控范围内。
- 滑动窗口日志：需要存储请求时间戳，开销和请求量、窗口长度成正比。
- 令牌桶：少量状态（当前令牌数 + 上次填充时间）。
- 漏桶：需要队列或调度器，开销与排队请求数相关。
2. 典型选型建议
可以按“需求场景”来做一个粗略决策：
只是想快速给接口加一个“每秒 N 次”的粗粒度保护
- 优先考虑：固定窗口算法。
- 若对边界突刺有所担心，可以稍微放宽阈值，或者配合网关级别的总限流。
需要严格意义上的“最近 N 秒/分钟”的调用频次控制
- 优先考虑：滑动窗口算法（尤其是滑动窗口日志）。
- 常见于：计费、风控、按用户/API Key 控制配额等。
需要既控制平均速率，又希望允许业务可感知的突发
- 优先考虑：令牌桶算法。
- 典型参数选择思路：
rate贴近系统整体可承受的稳定 QPS；capacity决定可以接住多大短暂流量峰值。
极度关注下游稳定性，需要“匀速出水”保护某个资源
- 优先考虑：漏桶算法或基于时间间隔的节流。
- 常见于：第三方脆弱接口、数据库慢查询保护、批量任务调度等。
3. 与 Go 生态结合的实践建议
单机或中间件层限流：
- 可以优先使用
golang.org/x/time/rate等成熟的令牌桶实现； - 对下游敏感调用可以在内部再加一层
go.uber.org/ratelimit做平滑节流。
- 可以优先使用
分布式、多实例部署的限流：
- 可结合 Redis 或其他集中存储，实现滑动窗口/令牌桶的分布式版本；
- 核心是把“计数/令牌”状态放在共享存储中，避免单机限流导致整体失控。
总体来说，没有一种算法在所有场景下都是“最优解”。更现实的做法是：
- 选定一两种作为团队的“默认方案”（通常是令牌桶 + 固定窗口）；
- 在特定敏感路径上，根据业务特点补充滑动窗口或漏桶；
- 通过监控与日志观察限流命中情况，持续调整参数。