0%

GuavaRateLimiter的理解

一. 介绍

项目中一直在使用RateLimiter进行单机的限流,但是没有去了解他的运作原理,这里就简单记录下,为以后学习Sentinal做铺垫。

这里强烈推荐酷家乐的文章《RateLimiter解析(一) ——设计哲学与快速使用》

把定积分写入技术文档我也是第一次见,实打实的说,核心部分我也没看懂。

本文仅仅讨论SmoothBursty的情况,SmoothWarmingUp先放着,因为不是很理解。

二. 个人困惑点

2.1 放令牌的时间窗口

其实在阅读源码前,自己对单机限流的工具进行了脑补,想单机限流工具的实现方案。

之前了解的方法,基本就两种,一种是漏桶,一种是令牌桶。

我比较疑惑的是令牌桶方式的放令牌的时间窗口,比如说,我设置的QPS是1分钟6000。

放令牌的时候,是每隔一分钟,丢6000个进去吗?

还是把6000个平均的分布在这一分钟的跨度内,每秒放100个进去呢?

个人理解比较合适的方式是每秒放100个进去。

因为如果你每分钟就立即放6000个进去,如果在1S内立马被消耗完了,那就剩余的59S就在那儿干等。

对于服务器而言,比如说Mysql,显然是不太合理的。

这种场景下,Mysql的QPS可能达到6000/S,如果抗过去了这1S,剩余的59S一个请求也就没有。

但是如果设置的QPS是1S6000。

那么这种放令牌的方式是怎么放呢?

每隔1S就放6000个令牌,还是再下降一个计时单位到毫秒进行发放?

如果每次的放置时间窗口都下降一个单位,再小的时间单位对于计算机而言也没有意义。

2.2 放令牌的方式

往令牌桶中放令牌的方式,是单独起一个线程,每隔一段时间醒一次,往令牌桶中放令牌吗?

这种方式看起来有点太消耗内存和CPU了。

不知道RateLimiter是怎么实现的

三. 具体实现

先来看看创建方法:RateLimiter create(double permitsPerSecond)

RateLimiter的创建方法,是个double类型的值,表示1s可以产生的令牌数。

进入doSetRate方法,注意两行代码:

1
2
double stableIntervalMicros = (double)TimeUnit.SECONDS.toMicros(1L) / permitsPerSecond;
this.stableIntervalMicros = stableIntervalMicros;

这里的stableIntervalMicros的值,就是以微秒为时间单位,计算多少微秒可以产生一个令牌。

所以这里基本上可以解答我的第一个疑惑,RateLimiter的时间窗口是微秒。

1s = 1,000millis = 1,000,000micros。

这里为什么是微秒,能不能是毫秒的单位?我其实还不是很懂。

有时间看看其他的限流器的实现

令牌桶与漏桶算法的区别就是在空闲时可以保存一部分的令牌,那么是多少个呢?

这个变量保存在SmoothRateLimiter::maxPermits中,如果看调用的话,根据是SmoothBursty还是SmoothWarmingUp是不同的,

这里我们仅仅讨论SmoothBursty的情况,因为SmoothWarmingUp实在是看不懂。

SmoothBursty.doSetRate方法中,进行了这个值的设置,maxBurstSeconds的默认值是1s。

1
maxPermits = maxBurstSeconds * permitsPerSecond;

所以这个空闲时最多保留的令牌数就是我们构造参数传入的值。

最后来看看最后一个问题,何时放置令牌以及取令牌的过程。

说到这儿其实已经知道了,RateLimiter并没有单独启一个线程去放令牌,而是使用了取时计算的方式。

而使用这种方式也是有弊端的,就是acquire方法需要加锁:

1
2
3
4
5
6
7
8
9
10
11
12
RateLimter##acquire()
public double acquire(int permits) {
long microsToWait = reserve(permits);
...
}

final long reserve(int permits) {
checkPermits(permits);
synchronized (mutex()) { //加锁
return reserveAndGetWaitLength(permits, stopwatch.readMicros());
}
}

取令牌时,我们要知道目前令牌桶中存有几个令牌。计算方式也比较简单,记录下上一次获取令牌的时间t,

公式:(now - t) / windowTime

就能计算出,空闲的这段时间内,产生了多少空闲的令牌。

同时记得要和maxPermits取个最小值。

这个方法在方法resync中:

方法coolDownIntervalMicros()SmoothBursty就是上文提到的固定的时间窗口stableIntervalMicros

1
2
3
4
5
6
7
8
9
void resync(long nowMicros) {
// if nextFreeTicket is in the past, resync to now
if (nowMicros > nextFreeTicketMicros) {
storedPermits = min(maxPermits,
storedPermits
+ (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros());
nextFreeTicketMicros = nowMicros;
}
}

得到了获取时,当前令牌桶中有多少令牌,最后看整体的获取逻辑:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
resync(nowMicros);
long returnValue = nextFreeTicketMicros;
double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
double freshPermits = requiredPermits - storedPermitsToSpend; // 1
long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
+ (long) (freshPermits * stableIntervalMicros); // 2

try {
this.nextFreeTicketMicros = LongMath.checkedAdd(nextFreeTicketMicros, waitMicros); // 3
} catch (ArithmeticException e) {
this.nextFreeTicketMicros = Long.MAX_VALUE;
}
this.storedPermits -= storedPermitsToSpend; // 4
return returnValue;
}
  1. 比较想要获取的令牌数和目前令牌桶中的令牌数量,得到除去令牌桶中的令牌数,有多少令牌还未产生,需要慢慢等待。

    比如令牌桶中只有3个令牌,而需要获取10个令牌,则需要额外的等待7个令牌的获取时间

  2. storedPermitsToWaitTimeSmoothBursty是返回的0。

    所以这里的waitMicors就是freshPermits * timeWindow

  3. 由于下面的freshPermits个令牌都被这个请求拿走了,所以下一次产生令牌的时间需要加上waitMicros

这里假设的是令牌不够的情况,那么如果空闲时间的令牌数足够的情况是呢?

比如令牌桶中有10个令牌,请求3个。

  1. freshPermits = 0
  2. waitMicros = 0
  3. nextFreeTicketMicros 不变
  4. 需要减去使用完的令牌数

四. 总结

看到这儿对RateLimiter有了大概的了解

  1. 对于存放令牌的时间窗口是微秒。
  2. 是完全公平的限流器,来请求的线程按照顺序等待。

并没有可扩展的其他复杂逻辑。比如排队多了,丢弃后续的请求,而不是一直卡在那儿等。

Welcome to my other publishing channels