随机化与近似结构

限流器

四种算法，先看它们错在哪

限流的目标是「每秒最多 N 次」。四种常见实现，差别不在复杂度，在边界行为：

算法	每个 key 的状态	主要问题
固定窗口	2 个数	🚨 边界处能放行 2 倍
滑动日志	limit 个时间戳	精确，但空间随限额线性增长
令牌桶	2 个数	允许突发（有时正是想要的）
漏桶	2 个数	计量器版就是令牌桶

下面每一条都有实测。

🚨 固定窗口：边界处放行 2 倍

最直白的写法：记一个窗口起点和一个计数器，过了窗口就清零。

function fixedWindow(limit, windowMs) {
  let start = 0, count = 0;
  return (now) => {
    if (now - start >= windowMs) { start = now - (now - start) % windowMs; count = 0; }
    return count < limit ? (count++, true) : false;
  };
}

限额 100 次/秒。在第 999 毫秒打满 100 次，再在第 1000 毫秒打满 100 次：

t = 999ms   放行 100
t = 1000ms  放行 100
--------------------------
相邻 2 毫秒内共放行 200 —— 而限额是 100/秒

⚠️ 两次都「没超过窗口限额」，但它们跨了窗口边界，于是在任意 1 秒的滑动区间里实际放行了 2 倍。同样场景下滑动日志只放行 100 次。

🚨 这个缺陷在压测里很难发现：均匀打流量时它完全正常，只有请求恰好聚在边界两侧才暴露 —— 而真实流量（整点任务、秒杀开始）恰恰爱聚在整秒。

滑动日志：精确，但空间是代价

存下每次放行的时刻，查询时把窗口外的丢掉：

function slidingLog(limit, windowMs) {
  const q = [];
  return (now) => {
    while (q.length && q[0] <= now - windowMs) q.shift();
    return q.length < limit ? (q.push(now), true) : false;
  };
}

⭐ 它没有边界问题，因为窗口是跟着当前时刻滑动的，不存在「跨窗口」。

⚠️ 代价是每个 key 要存 limit 个时间戳。限额 1000/秒就是 1000 个数，而限流通常是「每个用户一个 key」——用户量一上来，这个空间不可接受。

📌 折中做法是滑动窗口计数：把窗口切成若干小格，只存每格的计数，按当前时刻在格内的比例加权。空间降到格数，精度介于两者之间。

令牌桶：`cap` 就是允许的突发量

按固定速率往桶里放令牌，桶满则弃；每个请求取走一个，没有就拒绝。

function tokenBucket(rate, cap) {
  let tokens = cap, last = 0;
  return (now) => {
    tokens = Math.min(cap, tokens + (now - last) / 1000 * rate);
    last = now;
    return tokens >= 1 ? (tokens -= 1, true) : false;
  };
}

⭐ 桶容量直接等于允许的瞬时突发量。驱动方式：t=0 一次性打 200 个请求，之后每毫秒发一个，直到 t=3000（这个口径要写出来，换一种驱动数字就变）：

rate= 10/s  cap=10   瞬时放行 10   3 秒共放行  40   期望 rate×3+cap =  40  ✅
rate= 10/s  cap= 1   瞬时放行  1   3 秒共放行  31   期望             =  31  ✅
rate= 10/s  cap=50   瞬时放行 50   3 秒共放行  80   期望             =  80  ✅
rate=100/s  cap=20   瞬时放行 20   3 秒共放行 319   期望             = 320  ❌ 差 1

⭐ 三行严丝合缝，放行总量 = rate×秒数 + cap，这是个能直接拿去算容量的式子。

🚨 最后一行差的那 1 次不是算法的性质，是浮点误差 —— 把令牌数改成整数刻度（放大 1000 倍）重跑，这一格就是 320。下面「漏桶」一节会说清这个坑，它在这一篇里一共冒头三次。

📌 cap 和 rate 是两个独立旋钮：rate 管长期平均，cap 管能容忍多大的瞬时尖峰。想完全禁止突发就把 cap 设成 1。

⚠️ 注意长期速率会比 rate 略高：每毫秒发一个跑 10 秒，实测放行 110 次而不是 100 —— 多出来的正好是初始的一桶 cap=10。算容量时要把它算进去。

⭐ 漏桶：计量器版就是令牌桶

很多文章把漏桶和令牌桶讲成两种不同的算法。「计量器版」漏桶不是。

计量器版漏桶：水位随时间匀速下降，每个请求加一滴水，超过容量就拒绝。把它和令牌桶并排写：

// 令牌桶：令牌随时间增加，请求消耗
tokens = Math.min(cap, tokens + Δ);   if (tokens >= 1) tokens -= 1;

// 漏桶（计量器版）：水位随时间减少，请求增加
water  = Math.max(0,  water  - Δ);    if (water + 1 <= cap) water += 1;

⭐ 令 水位 = 容量 − 令牌，两式逐项相等 —— 它们是同一个算法的两种说法。

实测印证。6 种驱动 × 6 组 (rate, cap) 参数（10/10、10/1、10/50、 100/20、7/3、1000/100）逐次比对。「随机到达」是这样生成的：

function mulberry32(a) {                    // 每组实验各起各的种子
  return () => { a = (a + 0x6d2b79f5) | 0; let t = a;
    t = Math.imul(t ^ (t >>> 15), t | 1); t ^= t + Math.imul(t ^ (t >>> 7), t | 61);
    return ((t ^ (t >>> 14)) >>> 0) / 4294967296; };
}
function arrivals(seed, endMs, maxGap) {    // 间隔取 [0, maxGap) 的随机整数毫秒
  const r = mulberry32(seed), out = [];
  for (let t = 0; t < endMs; ) { t += Math.floor(r() * maxGap); out.push(t); }
  return out;                               // 种子 1/2：endMs=10000 maxGap=5
}                                           // 种子 3：endMs=60000 maxGap=20

驱动                        决策数    浮点分歧        整数刻度分歧
每 1ms 一次，10 秒           60006    0.59%  (354)      0.00%  (0)
每 1ms 一次，60 秒          360006    0.65% (2354)      0.00%  (0)
每 3ms 一次，60 秒          120006    0.36%  (438)      0.00%  (0)
随机到达（种子1），10 秒      30090    1.13%  (340)      0.00%  (0)
随机到达（种子2），10 秒      30402    1.86%  (566)      0.00%  (0)
随机到达（种子3），60 秒      37926    2.70% (1025)      0.00%  (0)

⭐ 整数刻度那一列六种驱动全是 0.00% —— 这一列才是结论：它们确实是同一个算法。而浮点那一列 0.36% ~ 2.70% 全随驱动变，报单独一个百分比没有意义。

📌 分歧不是算法差异，是浮点累积误差在 tokens >= 1 这条边界上来回翻。 ⭐ 而且翻得很有规律：rate=10 cap=10 每 1ms 那组 195 次分歧里， 97 对是相邻两拍、方向相反、互相抵消的（t=300 令牌桶放行/漏桶拒， t=301 反过来），净差只有 1 次。 👉 「分歧率 2%」听着吓人，落到长期放行总量上只差 1 次 —— 看指标要看净效应，别看翻转次数。

⚠️ 顺带一个实用结论：限流器这类「反复累加小增量再比阈值」的代码， 用整数刻度比用浮点稳 —— 否则同样的输入在不同机器、不同调用顺序下可能给出不同结果。

真正与令牌桶不同的是队列版漏桶：请求先入队，出口严格按固定速率放行。它的特点是出口绝对匀速（保护下游），代价是请求要排队等待，而令牌桶是「要么立刻放行、要么立刻拒绝」。

长期速率对不对

每毫秒都发一个请求（t=0 到 t=10000，共 10001 个），跑 10 秒，目标 10/s：

                     浮点实现        整数刻度
固定窗口   101 次      → 10.1/s        101 次     （不涉及浮点）
滑动日志   101 次      → 10.1/s        101 次     （不涉及浮点）
令牌桶     110 次      → 11.0/s        110 次     （多的 10 次是初始那一桶）
漏桶       109 次      → 10.9/s        110 次  ←  浮点下比令牌桶少 1

🚨 漏桶那个 109 别当成算法差异。 上一节刚证明它和令牌桶是同一个算法，这里却少放行 1 次 —— 差的正是那 195 次成对分歧没抵消干净的最后一次。整数刻度下两者都是 110，严丝合缝。

⭐ 这是这一篇里同一个浮点误差第三次冒头（前两次：3 秒表的 319、分歧率 2%）。 📌 判据：当两个你已经证明等价的实现给出不同的数，先怀疑数值实现，别怀疑等价性。

⭐ 四种的长期平均都对得上。它们的区别从来不在长期速率，而在短期形状 —— 选哪个取决于你能不能接受突发，以及能为每个 key 花多少内存。

怎么选

场景	选
单机、限额小、要精确	滑动日志
单机、限额大	滑动窗口计数（分格）
API 网关，允许合理突发	⭐ 令牌桶
保护下游（数据库、第三方）	队列版漏桶 —— 出口匀速才是目的
只要能扛住、实现越简单越好	固定窗口，但必须知道它边界会放 2 倍

🚨 最后一行是重点：固定窗口不是不能用，是用之前要知道它的实际上限是 2N 而不是 N。按 2N 去规划下游容量，它就是个够用的选择。

⚠️ 这一篇没有配套题

力扣上的限流题（日志速率限制器 359、敲击计数器 362）都是会员题，本站不收录。而且限流在面试里几乎总是以问答出现，不是让你在判题器上写。

📌 想练的话，最有效的方式是把上面四种各实现一遍，然后复现那几个数字：固定窗口在边界处放行 2 倍、令牌桶的瞬时突发恰好等于 cap、放行总量 = rate×秒数 + cap、计量器版漏桶与令牌桶在整数运算下分歧为 0。自己量出来一次，比背四种算法的定义有用得多。

⭐ 量的时候记住两条 —— 把驱动方式写下来（每毫秒一个？还是一次打 200 个？数字完全不同）， 同时跑浮点版和整数版（对不上的那几处，多半是浮点不是算法）。

本章小结

四篇讲完了。回看这一章的主线 —— 每一个结构都放弃了一点确定性：

	放弃	换来	代价可量化吗
跳表	结构确定	免掉旋转	✅ 层高分布 = `(1-p)p^(k-1)`
布隆过滤器	答案精确	空间 1/42	✅ 误判率 = `(1-e^(-kn/m))^k`
一致性哈希	分布均匀	迁移 0 冗余	✅ 非必要迁移恒为 0
限流器	计数精确	O(1) 状态	✅ 突发上限 = `cap`

⭐ 最后一列才是关键。这些结构之所以能用在生产上，不是因为「差不多够」，而是因为代价有公式、公式与实测对得上。 面试里被问到任何一个，能把这个公式和它的实测偏差说出来，比背定义有说服力得多。

限流器