Guava源码中很详尽的解释了RateLimiter的概念。
从概念上看,限流器以配置速率释放允许的请求(permit)。如有必要,调用acquire()将会阻塞知道一个允许可用。一旦被获取(acquired),允许(permits)将不必释放。
限流器在并发环境中是安全的:它限制所有线程总的调用速率。但是,值得注意的是,它难以保证公平。
限流器经常被用来限制一些物理或逻辑资源被访问的速率。经常和它对比的是j.u.c.Semaphore,它限制了访问资源总的并发数。(并发数和速率紧密相关,参见Little's Law)
限流器原始定义为许可被发布的速率。没有多余的配置,许可将被以固定速率(——字面意义被定义为 许可/sec) 分发。通过调节独立的许可之间的延迟,保证许可按照配置的速率平滑分发。
在限流器正式进入稳定速率前,通常允许限流器有一个短暂的预热阶段。在该阶段,许可分发速率稳步提升,直至预定到达速率为止。
举例,想象我们有一组任务要执行,但我们不想要每秒提交超过2个任务。
final RateLimiter rateLimiter = RateLimiter.create(2.0); // rate is 2 permits per second"
void submitTasks(List<Runnable> tasks, Executor executor) {
for (Runnable task : tasks) {
rateLimiter.acquire(); // may wait
executor.execute(task);
}
}
另一个例子是,想象我们生产一组数据流,但是我们想以5kb/sec速率恒定接收它。这个想法可以以限流器方式实现。即,每个许可对应一个字节,指定(限流器)恒定的速率为每秒5000次许可。
final RateLimiter rateLimiter = RateLimiter.create(5000.0); // rate = 5000 permits per second
void submitPacket(byte[] packet) {
rateLimiter.acquire(packet.length);
networkService.send(packet);
}
注意,请求的许可数量不会影响到对请求本身的压制。(acquire(1)会和acquire(1000)产生相同的效果),但是它会影响到对下一个请求的压制作用。如果成本较大的任务在空闲时到达限流器,将会被立即允许。但这之后的请求将会遭受额外的限制,为上次高昂代价的任务买单。
下面是一个SmoothRateLimiter的设计原理:
限流器的基本提点是一个“稳定的速率”,即在正常条件下的最大速率。未达到这个目的,限流器会根据需要压制到达的请求。通过计算,限流器会确保到达请求等待合理的时间,以此达到压制的目的。
维持一个速率(通常被指定为QPS)最简单的方法是记住上个被允许请求的最后时间戳,并保证在1/QPS时间内不执行请求。例如,QPS=5(每秒5个token),如果我们能够确保自从上个请求后,在200ms内没有请求被允许执行,那么我们将获得一个想要的速率。如果一个请求在上个请求被放行100ms后到达,那么我们需要等待额外的100ms。在这个速率下,15个新的许可耗时3秒钟(例如对于请求 acquire(15))。
很重要的一点,是能够意识到限流器对过去只有很浅的记忆。它只会记住上一个请求。那如果限流器很久没有被使用,然后一个请求突然到达并被立即允许怎么办?这可能会有两种情形,一种是资源利用不充分,另一种则是导致溢出,具体取决于没有遵循预定速率的真实原因。
之前的利用不足意味多余的资源可被获取。限流器应该加速一段时间,以利用这些资源。速率适应网络(带宽)很重要,过去的利用不足被解释为“几乎为空的缓冲”,可以被快速填补。
另一方面,过去的利用不足也可能意味着“服务器没有准备好处理将来的请求”,例如,缓存失效,请求更有可能会触发耗时的操作(一个更极端的例子是,当一个服务器刚刚被引导,它更可能忙于自身的唤醒)。
为应对以上场景,我们增添一种维度。即“过去的利用不足”被建模为变量“storedPermits”。这个变量在没有使用时为0,当有大量使用时,它可以增长到maxStoredPermits。所以,请求会被函数acquire(permits)触发许可,提供以下两种类型的许可:
-stored permits(可获取的已存许可)
-fresh permits(新的的许可)
工作原理如下:
对于一个限流器,每秒产生一个令牌。不使用限流器时,我们都会给storedPermits加1。如果说我们有10sec不使用限流器(例如预计请求在时刻X到来,但在请求到来之前,我们在X+10。这也是上段所描述的点。)。因此storedPermits变为10(假设maxStoredPermits>=10)。在这时,一个人acquire(3)的请求到了。我们从已有的storedPermits拿出许可服务这个请求,并将许可数降至7.(这如何被解释为压制时间,将会在之后被详细讨论。)这之后,假设马上有一个acquire(10)的请求到达,我们用剩下所有的7个许可数来应对这个请求,还有3个许可数,我们需要通过刷新限流器新提供。
我们也已经知道花费在3个新的许可上的时间:如果速率是1令牌/sec,那么我们将花费3秒。但是使用7个已存许可又是什么意思呢?正如上面所说,这里没有固定答案。如果我们主要兴趣在应对资源利用不足上,我们想要存储许可释放比刷新许可快。因为利用不足=尚有未被占用的资源。如果我们主要兴趣点在应对溢出,那么存储的许可数应该释放的比刷新的慢。因此,我们想要一个(在每种情形都不同的)方法来解释storePermits,以此压制时间。storedPermitsToWaitTime(double storedPermits, double permitsToTake) 在其中扮演重要角色。底层的模型是一个持续变化的函数映射storedPermits(从0到maxStoredPermits)到1/rate(时间间隔)。storedPermits在衡量未使用时间上是必不可少的。我们使用未利用时间换取许可数(permits)。速率是permits/time,因此1/rate=time/permits.因此"1/rate"(time/permits)乘以permits等于给定时间。对于指定数量的请求许可来说,这个积分函数(storedPermitsToWaitTime()计算)与持续请求的最小时间间隔相关。
这里有个storePermitsToWaitTime的例子。如果storedPermits=10,我们想要3个permits,我们从storedPermits中去获取,减少他们到7个,并且计算压制时间作为一个调用storedPermitsToWaitTime(storedPermits=10,permitsToTake=3),这将会评估这个函数积分从7到10.
使用积分保证acquire(3)效果等同于3次acquire(1),或一次acquire(2)+一次acquire(1)。因为积分在[7.0,10.0]等同于在[7.0,8.0],[8.0,9.0],[9.0,10.0]等等。无论这个函数是什么。这使得我们可以正确处理不同权重(permits)的请求时,不论真正的函数是什么。所以我们可以*调整。(唯一的条件显然是我们能够计算出他的间隔时间)。
注意,对于这个函数,我们选择水平线,高度为1/QPS,因此这个函数的影响是不存在的。对于storedPermits将会完全等同于刷新一个新的(1/QPS是他的代价)。我们将会在之后使用这个小诀窍。
如果我们采用一个低于这条水平线的函数,这意味着我们减少了这个函数的区域,也就是时间。因此限流器就会在一段时间的利用不足后变快。另一方面,如果我们使用一个高于此水平线的函数,这就意味着代表时间的区域增大,因此storedPermits将会比刷新一个新许可更耗时,相应地,限流器就会在一段时间的利用不足后变慢。
最后,考虑一个限流器以1permit/sec速率,当前未被使用,有一个acquire(100)的请求到来。等待100sec才开始执行任务将会是很愚蠢的行为。为什么不作任何事情只等待呢?一个更好的方法是立刻允许请求(正如它是acquire(1)的请求一样),并且按需要延缓此后的需求。在这个版本,我们允许立刻开始执行任务,并且延缓100秒之后的请求,因此我们允许工作执行而不是让它空闲等待。
这里有很重要的因果关系。这意味着限流器不会记住最后请求的时刻,但它会记住下一个请求(预计)时间。这也使我们能够立即知道(见tryAcquire(timeout))指定时间timeout是否足够将我们带到下一个调度的时间点,因为我们总维持那个。并且我们所指的“未被使用的限流器”也被这所定义:但我们观察“下一个请求的期待到达时间”在过去,那么(now-past)的时间差将被看作RateLimiter未被正式使用时间。这也是被我们解释为storedPermits的时间。(我们用空闲的时间产生的许可数来增加storedPermits)。所以,如果速率=1许可/sec,并且请求在之前那个请求后一秒后准时到达,那么storedPermits将永远不会增加。我们只会在当晚于预期一秒时间的到达,才会增加它。