限流算法

令牌桶（Token Bucket）

令牌以速率 r 个/秒积累，最多存储 B 个。每个请求消耗一个令牌。允许瞬间爆发最多 B 个请求；持续速率上限为 r。

更新公式：tokens = min(B, tokens + (now - last_refill) × r)

算法

1. 每次请求到来（时间 t）：补充令牌 = min(B, tokens + (t - last) × r)；更新 last = t
2. 若 tokens >= 1：消耗 1 个令牌，返回 ALLOW
3. 否则：返回 DENY（或将请求排队）

// Token Bucket rate limiter
// r = tokens per second, B = bucket capacity
struct TokenBucket {
    double tokens, rate, capacity;
    double lastTime;
    TokenBucket(double r, double B) : tokens(B), rate(r), capacity(B), lastTime(0) {}
    bool allow(double now) {
        tokens = min(capacity, tokens + (now - lastTime) * rate);
        lastTime = now;
        if (tokens >= 1.0) { tokens -= 1.0; return true; }
        return false;
    }
};

应用场景

• AWS API Gateway——可配置突发上限（桶容量）+ 速率限制
• Google Cloud——基于令牌桶语义的项目配额
• Linux tc——令牌桶过滤器（TBF）用于网络 QoS
• 基于 Redis 的惰性补充限流

突发行为：令牌桶允许桶满时一次性爆发 B 个请求，之后恢复到持续速率 r。适合突发型 API 客户端。漏桶强制完全均匀的输出速率。

漏桶（Leaky Bucket）

请求填入容量为 C 的桶，桶以固定速率 r 排水（每 1/r 秒处理一个请求）。桶满时新请求被丢弃。输出完全平滑。

算法

1. 维护：待处理请求队列、当前水量、上次排水时间
2. 每次请求到来（时间 t）：drain = (t - last_drain) × r；water = max(0, water - drain)；更新 last_drain = t
3. 若 water + 1 <= C：water += 1，ALLOW（入队）；否则 DENY（丢弃）

// Leaky Bucket: constant drain rate r, capacity C
struct LeakyBucket {
    double water, rate, capacity, lastDrain;
    LeakyBucket(double r, double C) : water(0), rate(r), capacity(C), lastDrain(0) {}
    bool allow(double now) {
        double drained = (now - lastDrain) * rate;
        water = max(0.0, water - drained);
        lastDrain = now;
        if (water + 1.0 <= capacity) { water += 1.0; return true; }
        return false;
    }
};

应用场景

• 网络流量整形——VoIP / 视频流平滑输出
• ISP 带宽限速——无论输入突发如何，输出速率恒定
• Linux tc HTB（分层令牌桶）结合了令牌桶与漏桶概念

对比令牌桶：漏桶保证恒定输出速率（适合流量整形）。令牌桶允许突发但限制平均速率（适合 API 限流）。绝大多数生产系统选择令牌桶。

滑动窗口计数

融合当前窗口与上一窗口的计数，按当前时间在窗口中的位置加权。消除了固定窗口边界处的突发问题。

计数公式：count = prev_count × (1 - elapsed/window) + cur_count

算法

1. 维护：prev_count（上窗口计数）、cur_count（当前窗口计数）、window_start
2. 每次请求到来（时间 t）：若 t >= window_start + window，推进：prev_count = cur_count，cur_count = 0，window_start += window
3. elapsed = (t - window_start) / window
4. approx_count = prev_count × (1 - elapsed) + cur_count
5. 若 approx_count < limit：cur_count += 1，ALLOW；否则 DENY

// Sliding Window Counter (two-window approximation)
// Uses integer millisecond timestamps
struct SlidingWindow {
    long long limit, windowMs;
    long long prevCount, curCount, windowStart;
    SlidingWindow(long long limit, long long windowMs)
        : limit(limit), windowMs(windowMs), prevCount(0), curCount(0), windowStart(0) {}
    bool allow(long long now) {
        // Advance window if needed
        while (now >= windowStart + windowMs) {
            prevCount = curCount;
            curCount = 0;
            windowStart += windowMs;
        }
        long long elapsed = now - windowStart;
        // Approximate count over the sliding window
        double approx = prevCount * (1.0 - (double)elapsed / windowMs) + curCount;
        if (approx < limit) { curCount++; return true; }
        return false;
    }
};

应用场景

• Cloudflare 限流——Redis 中的滑动窗口计数器
• NGINX limit_req 模块——漏桶变体，效果类似
• Stripe / Braintree API——每用户滑动窗口

固定窗口突发问题：固定窗口在边界处可允许 2× 限额（第 N 期末 + 第 N+1 期初）。滑动窗口消除此问题，在均匀流量下近似误差 < 0.003%。