算法原理
六种限流器、一个接口。之所以有这么多种,是因为"限流"背后其实藏着好几个不同的问题:突发能不能过、速率要不要平滑、窗口边界怎么定义、下游是不是"冷"的、真正的约束是每秒次数还是同时在飞的数量。
| 限流器 | 速率模型 | 突发 | 状态 | 单次请求开销 |
|---|---|---|---|---|
TokenBucketLimiter | 平均速率,突发上限为容量 | 最多 capacity | 一个 long | 1 次读 + 1 次 CAS |
LeakyBucketLimiter | 严格匀速 | 1 | 一个 long | 1 次读 + 1 次 CAS |
SlidingWindowLimiter | 滚动窗口内 N 次 | 最多 N | slots 个 long | slots 次读 + 1 次 CAS(偶尔多一次读做回滚) |
FixedWindowLimiter | 对齐窗口内 N 次 | 边界处最多 2N | 一个 long | 1 次读 + 1 次 CAS |
WarmUpTokenBucketLimiter | 速率随运行时长爬升的令牌桶 | 冷态 capacity/3,预热后 capacity | 一个 long + 起始时刻 | 1 次读 + 1 次 CAS |
ConcurrencyLimiter | 同时在飞的许可数 | 不适用(没有时间轴) | 一个 int | 1 次读 + 1 次 CAS |
令牌桶(虚拟调度 / GCRA)
令牌桶有两个参数:每个间隔补多少令牌(速率),桶能装多少(容量,也就是最大突发)。空闲时令牌会累积,请求来了就消耗。
TokenBucketLimiter 没有"令牌计数器 + 补令牌线程",它只存一个数:下一个令牌可用的时刻,也就是理论到达时间。每个被放行的请求把这个时刻往后推一个发放间隔。于是"补充"这一动作被时间本身取代了,不需要任何定时任务。
发放间隔 T = window / permitsPerWindow
容忍度 τ = capacity * T
当 (max(arrival, now) - now) + permits * T <= τ 时放行
然后 arrival = max(arrival, now) + permits * T以每秒 100 次、容量 3 为例:每 10ms 发放一个,且最多一次性花掉 3 个。
时间 0ms 10ms 20ms 30ms 40ms
●───●──────●──────●──────●───▶ 令牌可用时刻(T = 10ms)
▓▓▓ 此刻可突发 3 个,之后每 10ms 一个桶永远不会溢出:空闲时调度时刻落在时钟之后,availablePermits() 报的是容量,不会更多。
漏桶
漏桶就像一条匀速排空的队列。空闲多久都不影响:放出第一个许可后,下一个许可恰好在一个发放间隔之后。
数学上这与令牌桶是同一套虚拟调度,只是容忍度为一个间隔。所以两个类共用 GCRA 内核、只在突发容忍度上不同——这不是"改个名字",而是两者做出真正不同的放行判断的原因:
TokenBucketLimiter bucket = RateLimiters.tokenBucket("t", 3, 100, Duration.ofSeconds(1));
Thread.sleep(50);
bucket.availablePermits(); // 3 —— 突发额度累积了
LeakyBucketLimiter leak = RateLimiters.leakyBucket("t", 100);
Thread.sleep(50);
leak.availablePermits(); // 1 —— 什么都没累积突发会打坏下游时(调用合作方接口、消费队列)用漏桶;空闲客户端确实该"追一追"时用令牌桶。
滑动窗口
固定窗口在时钟边界上重置计数器,于是客户端可以在边界前花掉全部额度、边界后再花掉全部额度。滑动窗口看的是"最近这段时间",这种玩法就不成立了。
窗口被切成 slots 个桶(默认 10 个)。每个桶里是"计数 + 它属于哪一代窗口",读取时只累加仍在窗口内的那几代,过期的直接忽略。内存固定为 slots 个 long,与流量无关。
│◀──────────── 滚动窗口(200ms)────────────▶│
slots [ 0 ][ 1 ][ 2 ][ 3 ][ 4 ][ 5 ][ 6 ][ 7 ][ 8 ][ 9 ]
过期 过期 有效 有效 有效 有效 有效 有效 有效 现在
└──忽略──┘└──────────── 计入 ────────────┘精度是一个槽(默认窗口的十分之一),想要更细就传更大的槽数。一个许可会被计到它所在的那个槽离开窗口为止,误差在一个槽之内。
并发下这个实现失败关闭(fail closed):线程先占位,再重读总数,若窗口已满就把自己的占位回滚。所以并发不会把计数顶过上限;代价是在极短的竞争窗口里可能误拒一次本来即将释放的许可。
固定窗口
FixedWindowLimiter 把全部状态塞进一个 AtomicLong:高 32 位是窗口编号,低 32 位是已用许可数。一次判断就是一次原子读、最多一次 CAS,因此它是运行开销最低的——流量极高、精度要求宽松时选它。
它的已知弱点是边界突发:11:59:59 用掉 100 个、12:00:01 又用掉 100 个,两秒内 200 个,等于配置速率的两倍。如果客户端会刻意利用这一点,请选滑动窗口。
并发数限流(Bulkhead)
ConcurrencyLimiter 是六者里的异类:它完全没有时间轴,回答的是"同一时刻允许多少个请求在处理",而不是"每秒多少次"。两者不能互相替代:
下游响应 3 秒,你限了每秒 10 次——限流器很满意;但同时有 30 个请求在飞,20 个连接的池子早就被打穿了。
既然是"槽位"而不是"令牌",就有三个推论:
- 槽位不会因为时间而归还,只有
release()才归还。所以默认应该用 try-with-resources(tryEnter()):出作用域自动还,任务抛异常也照样还。多还(归还数超过持有数)会抛IllegalStateException,把"重复释放"这种 bug 变成立即失败的测试,而不是悄悄把上限放大。 - 没有"补充"这回事。
availablePermits()就是maxConcurrency - inFlight,状态是一个AtomicInteger,tryAcquire(n)/release(n)都是一次 CAS,放不下的并发请求直接被拒,而不是把池子撑爆。 - 它与速率限流是叠加关系。两个一起用:令牌桶保护下游,并发限流保护本进程的线程与连接。谁也替代不了谁。
预热限流
WarmUpTokenBucketLimiter 是一个"发放间隔"会变的令牌桶:冷启动时间隔是稳态的 3 倍,之后随预热时长线性收缩到稳态。于是速率从配置值的 1/3 爬到 1;又因为突发预算是"若干个发放间隔",突发额度也同步从 capacity/3 涨到 capacity:
速率 ●
│ ╭──────────── 预热结束后维持满速
100% ┤ ╭─╯
│ ╭─╯
33% ┤╭───╯
└────┬────────────────────────▶ 时间
warmUpPeriod两个实践细节:
- 爬升依据是"限流器活多久",不是"来了多少请求"。空闲等待不会把它预热好:创建两分钟后它就是满速的,哪怕一个请求都没处理过。这正是"实例刚拉起就要接流量"场景需要的行为。
- 容量小于冷却系数的限流器也不会被饿死。突发预算被钳到至少一个发放间隔,所以"容量 1"(即不允许突发)的配置在冷态下仍然一次能放一个,而不是一个都放不出去。
冷却系数固定为 3,与 Alibaba Sentinel 取值一致。这是刻意的简化:可配置的冷却系数会改变曲线形状,每种组合都要单独回归,而 3 是"前几分钟别把下游打死"这个常见诉求上被生产验证过的值。
并发下的保证
| 保证 | 令牌桶/漏桶 | 滑动窗口 | 固定窗口 |
|---|---|---|---|
| 配置速率被突破 | 不会 | 不会 | 窗口边界处最多 2N |
| 因竞争丢失请求 | 不会 | 可能(失败关闭) | 不会 |
| 快路径上加锁/阻塞 | 无 | 无 | 无 |
| 每次调用分配对象 | 无 | 无 | 无 |
两种计数型限流器在并发争抢下会恰好放出上限那么多许可,这也是测试套件断言的内容:16 个线程争抢上限 20,恰好 20 次成功。
时钟与精度
时间取自 System.nanoTime(),它是单调的:改系统时间或 NTP 跳变都不会让限流器突然放出一波、也不会让它卡住一小时。分辨率是纳秒,实际精度受操作系统计时器限制——每秒几百次以上完全够用;对每小时几次这种极低速率,误差在一个调度刻度之内。
它不是分布式限流
这是单 JVM 限流器。三个实例各自持有一个桶,"每秒 100 次"是每个实例每秒 100 次。对于保护进程自身资源,这正是想要的行为,也是这个库不需要 Redis、不需要网络调用、不需要配置中心的原因。
需要集群级限流时,常规做法是前面留一层本地限流器(吸收突发、零延迟),后面再挂一个共享计数器——Redis 的原子 INCR + PEXPIRE,或者网关层限流。