限流算法：令牌桶、漏桶与 GCRA 的等价性和工程实现
内容提要
文章论证令牌桶、计量器漏桶与GCRA在参数T=1/r、τ=(b-1)T下判决完全等价，并以十万请求验证；NGINX、redis-cell、Envoy、Guava的实现均属同一约束，仅参数相差一。窗口计数属于另一类约束，最坏误差可达2L。文章还分析了分布式限流、并发与速率限制的区别及工程选型陷阱。
延伸解读
参数差一：跨系统迁移的常见陷阱
文章指出，NGINX 的 burst、redis-cell 的 max_burst 配置值加一才是实际突发容量，Envoy 的 max_tokens 直接对应容量，而 Guava 的 create(r) 从空闲起可放行 r+1 个。迁移限流配置时若直接照抄数值，会导致容量偏差。建议先统一换算为 GCRA 参数或“从空闲起连续放行数”再迁移。
窗口计数与到达曲线：误差来源不同
固定窗口和滑动计数约束的是窗口内计数，而非到达曲线，因此最坏情况下固定窗口可放行 2L 个请求，滑动计数也可能因均匀分布假设被构造出超限。文章用实验显示，在泊松流量下固定窗口与滑动日志判决不一致率超 40%。若要求任意窗口严格不超限，应使用滑动日志。
分布式限流：原子性与时钟选择
将 GCRA 状态放入 Redis 并用 Lua 脚本原子执行，可避免并发下的多放问题；实验显示非原子操作在 400 并发请求下放行数从 31 到 50 不等。时间源可选客户端或服务器，但客户端时钟偏差会直接转化为额度误差，服务器墙钟则受 NTP 回拨和主从切换影响。
速率限制与并发控制：互补而非替代
令牌桶等算法约束的是到达速率，无法限制在途请求数。根据 Little 定律，下游变慢时平均停留时间 W 增大，同样的速率会导致在途请求数 L 上升，可能压垮下游。文章建议单独设置并发限流或过载保护，以应对速率限制无法覆盖的场景。
Q&A
令牌桶、漏桶和GCRA在什么条件下判决完全等价？
当令牌桶参数为速率r、容量b，GCRA参数取T=1/r、τ=(b-1)T，且令牌桶初始为满、GCRA的TAT初始不晚于首个请求到达时刻时，两者对任意到达序列的每个请求给出相同判决。作为计量器的漏桶也与它们等价。
为什么NGINX的limit_req配置burst=9时，从空闲状态起能连续放行10个请求？
因为NGINX limit_req的判定部分等价于GCRA(1/r, B/r)，从空闲状态起可连续放行B+1个请求。配置burst=9时，B=9，所以能连续放行10个。文档中的“突发不超过5个”指的是超出速率的部分，不包括第一个请求。
滑动窗口计数器的误差真的只有0.003%吗？
0.003%是Cloudflare在特定流量分布下的统计结果，并非误差上界。攻击者可以构造最坏情况，使滑动计数在任意1秒区间内放行接近2L个请求。例如，让上一窗口的请求集中在末尾，下一窗口的请求集中在90%处，可放行19个（L=10）。
分布式限流中，为什么推荐使用Lua脚本或redis-cell而不是客户端先GET再SET？
因为客户端先GET再SET不是原子操作，并发下多个客户端可能读到相同的旧TAT，导致多放行。实验显示，8个线程各发50个请求，本应放行10个，实际放行31到50个。而Lua脚本在Redis中原子执行，能保证读-改-写的原子性，正确放行10个。
令牌桶限流能防止并发过载吗？
不能。令牌桶约束的是到达速率λ，而系统中的平均在途请求数L=λW（W为平均停留时间）。当下游变慢时W变大，同样的λ会导致更多在途请求，速率限流器无法察觉。因此需要单独设置并发请求限流器。
跨系统迁移限流配置时，关于burst参数最容易犯什么错误？
最容易忽略不同系统对burst的定义差异。NGINX和redis-cell的突发容量是配置值加1，Envoy的max_tokens就是突发容量，Guava的create(r)从空闲起可连续放行r+1个。迁移时应先换算成GCRA参数或“从空闲起连续放行数”再配置。
