Skip to content

算法原理 ​

六种限流器、一个接口。之所以有这么多种,是因为"限流"背后其实藏着好几个不同的问题:突发能不能过、速率要不要平滑、窗口边界怎么定义、下游是不是"冷"的、真正的约束是每秒次数还是同时在飞的数量。

限流器速率模型突发状态单次请求开销
TokenBucketLimiter平均速率,突发上限为容量最多 capacity一个 long1 次读 + 1 次 CAS
LeakyBucketLimiter严格匀速1一个 long1 次读 + 1 次 CAS
SlidingWindowLimiter滚动窗口内 N 次最多 Nslots 个 longslots 次读 + 1 次 CAS(偶尔多一次读做回滚)
FixedWindowLimiter对齐窗口内 N 次边界处最多 2N一个 long1 次读 + 1 次 CAS
WarmUpTokenBucketLimiter速率随运行时长爬升的令牌桶冷态 capacity/3,预热后 capacity一个 long + 起始时刻1 次读 + 1 次 CAS
ConcurrencyLimiter同时在飞的许可数不适用(没有时间轴)一个 int1 次读 + 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 内核、只在突发容忍度上不同——这不是"改个名字",而是两者做出真正不同的放行判断的原因:

java
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 个连接的池子早就被打穿了。

既然是"槽位"而不是"令牌",就有三个推论:

  1. 槽位不会因为时间而归还,只有 release() 才归还。所以默认应该用 try-with-resources(tryEnter()):出作用域自动还,任务抛异常也照样还。多还(归还数超过持有数)会抛 IllegalStateException,把"重复释放"这种 bug 变成立即失败的测试,而不是悄悄把上限放大。
  2. 没有"补充"这回事。availablePermits() 就是 maxConcurrency - inFlight,状态是一个 AtomicInteger,tryAcquire(n)/release(n) 都是一次 CAS,放不下的并发请求直接被拒,而不是把池子撑爆。
  3. 它与速率限流是叠加关系。两个一起用:令牌桶保护下游,并发限流保护本进程的线程与连接。谁也替代不了谁。

预热限流 ​

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,或者网关层限流。