📚 课程目录第3章常见限流算法详解（上）

3. 常见限流算法详解（上）：计数器算法与滑动窗口算法

在金融低延迟API网关中，限流算法直接决定了系统的吞吐能力、资源消耗以及面对突发流量时的行为。本章深入剖析两种基础但广泛应用的限流算法：计数器算法与滑动窗口算法，并结合金融场景分析其优缺点。

3.1 计数器算法（固定窗口算法）

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

3.1.1 核心原理与实现

  核心逻辑： 固定时间窗口 + 原子计数器。窗口边界清晰，实现复杂度极低。

// 伪代码：计数器算法核心逻辑
public class FixedWindowRateLimiter {
    private final long windowSizeMs;      // 窗口大小，如 1000ms
    private final int maxRequests;        // 窗口内最大请求数
    private final AtomicLong counter;     // 原子计数器
    private volatile long windowStart;    // 当前窗口起始时间

    public boolean tryAcquire() {
        long now = System.currentTimeMillis();
        long currentWindowStart = now - (now % windowSizeMs);

        // 窗口切换时重置
        if (currentWindowStart != windowStart) {
            synchronized (this) {
                if (currentWindowStart != windowStart) {
                    windowStart = currentWindowStart;
                    counter.set(0);
                }
            }
        }
        return counter.incrementAndGet() <= maxRequests;
    }
}

3.1.2 金融场景下的优缺点

维度	评价	金融场景影响
实现复杂度	极低，仅需一个原子变量	适合极简场景，如单机API Key限流
内存占用	极低，O(1) 空间	可支持百万级并发连接
边界突变问题	严重，窗口切换瞬间允许2倍流量	可能导致瞬时洪峰击穿下游交易系统
时间精度	依赖系统时钟，窗口边界硬切	时钟回拨可能导致限流失效
公平性	差，窗口后半段可能完全无服务	不适合对延迟敏感的行情推送

金融风险警示： 计数器算法的边界突变问题在金融交易场景中尤为危险。假设每秒限流1000笔，攻击者可在第999ms和第1000ms各发送1000笔请求，实际瞬时流量达到2000笔/秒，可能直接导致核心交易系统过载。

3.2 滑动窗口算法

滑动窗口算法将固定窗口细分为多个小格子（如1秒窗口分为10个100ms的格子），每个格子独立计数。窗口随着时间推移向前滑动，统计当前时间点前一个完整窗口内的总请求数。这有效缓解了计数器算法的边界突变问题。

3.2.1 核心原理与实现

  核心逻辑： 时间分片 + 滑动统计。通过增加内存粒度换取流量平滑度。

// 伪代码：滑动窗口算法核心逻辑（基于环形数组）
public class SlidingWindowRateLimiter {
    private final long windowSizeMs;      // 窗口大小，如 1000ms
    private final int slotCount;          // 格子数量，如 10
    private final long slotSizeMs;        // 格子大小，如 100ms
    private final int[] slots;            // 每个格子的计数
    private final int maxRequests;        // 窗口内最大请求数
    private volatile long lastUpdateTime; // 上次更新时间

    public boolean tryAcquire() {
        long now = System.currentTimeMillis();
        int currentSlot = (int)((now % windowSizeMs) / slotSizeMs);
        
        // 清理过期格子
        synchronized (this) {
            long elapsedSlots = (now - lastUpdateTime) / slotSizeMs;
            if (elapsedSlots > 0) {
                // 将过期格子清零
                for (int i = 0; i < Math.min(elapsedSlots, slotCount); i++) {
                    slots[(currentSlot - i + slotCount) % slotCount] = 0;
                }
                lastUpdateTime = now;
            }
        }

        // 统计当前窗口总请求数
        int total = 0;
        for (int count : slots) {
            total += count;
        }
        if (total >= maxRequests) {
            return false;
        }
        slots[currentSlot]++;
        return true;
    }
}

3.2.2 金融场景下的优缺点

维度	评价	金融场景影响
边界突变	显著改善，流量平滑度与格子数正相关	有效抑制瞬时洪峰，保护交易链路
内存占用	O(N)，N为格子数，通常10~100	单机可接受，但分布式场景需权衡
实现复杂度	中等，需处理格子过期与并发	需注意锁粒度，避免影响延迟
时间精度	格子粒度决定精度，通常ms级	满足大部分金融API限流需求
内存与性能权衡	格子越多越平滑，但CPU开销增加	建议格子数不超过100，避免GC压力

3.3 两种算法对比与金融场景选择

对比维度	计数器算法	滑动窗口算法
流量平滑度	差，存在边界突变	良好，格子越多越平滑
内存占用	O(1)，极低	O(N)，N通常10~100
单次判断延迟	纳秒级，无循环	微秒级，需遍历格子
适用场景	非关键路径、粗粒度限流	核心交易、行情推送、风控校验
分布式扩展	容易，仅需共享计数器	较复杂，需同步格子状态

金融实践建议： 对于行情推送、订单录入等低延迟核心链路，推荐使用滑动窗口算法，格子数设为20~50（即20~50ms粒度）。对于非关键路径（如日志上传、报表查询），计数器算法足以胜任。

3.4 边界突变问题可视化

下图直观展示了计数器算法与滑动窗口算法在面对突发流量时的行为差异。红色区域代表被拒绝的请求，绿色区域代表通过的请求。

3.5 内存占用与性能权衡

在金融低延迟场景中，内存占用和GC压力是选择算法时必须考虑的因素。以下对比展示了不同配置下的资源消耗：

算法	单实例内存	10万连接内存	单次判断CPU	GC压力
计数器	~40 bytes	~4 MB	~10 ns	极低
滑动窗口（10格）	~120 bytes	~12 MB	~100 ns	低
滑动窗口（100格）	~800 bytes	~80 MB	~500 ns	中等

低延迟优化建议： 滑动窗口算法中，格子数建议不超过50。超过50后，内存占用线性增长，而流量平滑度提升趋于饱和。对于单机10万连接场景，推荐使用20格滑动窗口，总内存约20MB，单次判断延迟控制在200ns以内。

3.6 金融场景选型决策树

根据金融业务的不同特性，可参考以下决策路径选择限流算法：

3.7 本章小结

计数器算法实现简单、内存极低，但存在严重的边界突变问题，不适合金融核心交易链路。
滑动窗口算法通过时间分片有效平滑流量，内存占用可控，是金融低延迟场景的推荐基础算法。
格子数的选择需要在流量平滑度与内存/CPU开销之间权衡，建议范围10~50。
两种算法均存在时间精度依赖问题，在分布式环境中需额外处理时钟同步。