文档章节

限流分析(Guava RateLimter)

robin-yao
 robin-yao
发布于 2016/11/19 22:18
字数 2234
阅读 2155
收藏 93

一般系统为了防止服务被调用的QPS超出其承载能力,防止大流量压垮服务器造成雪崩后果,设计时往往会加入限流的逻辑。通过限流,当请求超出系统的服务能力时,系统可以采取拒绝服务/排队等待/降级等策略保护自身。

常见的限流算法

计数器法

原理:单位时间内计数,对请求计数,当超过设定的限流值,系统对请求采取限流策略;当单位时间结束时,计数器清零,重新开始计数;

优点:实现简单,容易理解;

缺点:不能实现均衡的限流,比如在单位时间快结束时发起大量请求,并在下一次单位时间刚开始发起大量请求,这样就会对系统请求造成连续两个峰值,有可能压垮系统,不能有效的把请求均摊;

如果单位时间越小,限流的精度就会越高。

草图

漏桶算法

原理:请求像一个水管里的水流一样注入到一个漏桶里,漏桶以恒定的速度往外漏水(无论进入的桶里的水流速度是多少);当桶满了,水流则会溢出;这样当流量再大也会以恒定的速度调用后台服务,或者低于设定的速度(当请求流量不足时);

优点:漏桶可以起到削峰,平滑请求的作用,

缺点:不能有效的利用系统资源,即时在系统可乘受住的峰值进入时,也不能加快处理请求,整体上会放缓系统对请求的处理速度。

输入图片说明

令牌桶

原理:令牌桶是一个桶可以容纳有限的令牌,令牌是以固定的速度往令牌桶里不停的放,如果令牌桶满了,令牌着放不进去溢出;当有请求时,根据请求量去取相应的令牌数;

优点:相比漏桶,令牌桶允许一定的突发流量,请求空闲时预热一部分令牌,新请求进来时无需等待。

缺点:代码实现相对复杂一些。

输入图片说明

RateLimiter 分析

RateLimiter简介

RateLimiter是Guava工具包提供的限流工具,采用令牌桶算法实现。 RateLimiter通过配置固定的rate参数,来以恒定的速度分发许可。同时RateLimiter提供了预热模式来分发许可,逐步达到配置的rate速度(比如在系统缓存还没有预热好时,过多的请求会给系统带来过大压力,预热模式可以很好的解决这个问题)。如果RateLimiter在预热阶段内,不被调用了,它会逐渐的回到冷却状态,再次调用时,在像刚开始一样重新预热。RateLimiter提供了acquire(阻塞)和tryAcquire(非阻塞)两种模式获取许可。

相关接口

  • 创建实例接口

    • create(double permitsPerSecond)
    • create(double permitsPerSecond, long warmupPeriod, TimeUnit unit) 预热模式创建
  • 获取permits

    • acquire(int permits) 阻塞模式获取,直到等到permits数量满足要求。
    • tryAcquire(long timeout, TimeUnit unit) 指定超时时间获取
    • tryAcquire(int permits) 非阻塞模式获取

请求令牌数量不影响请求本身限流的效果(如果acquire(1)和acquire(1000)触发了限流,对该请求限流结果是一样的),它只会影响接下来请求的限流效果,比如如果上一次请求开销很大,拿去了很多的permits,那接下来的高开销请求可能会被限制。

使用示例

  • 有一些任务要执行,假设每秒最多不能执行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/s 的速度进行发送,可以采用下面的方式实现。
final RateLimiter rateLimiter = RateLimiter.create(5000.0); // rate = 5000 permits per second

void submitPacket(byte[] packet) {
      rateLimiter.acquire(packet.length);
      networkService.send(packet);
}

### RateLimiter实现原理

这里通过对RateLimiter扩展实现类的SmoothRateLimiter注解进行翻译加上个人理解,逐步讲述RateLimiter设计实现。

假定对于实现固定QPS的访问速度限定,可以通过记录上一次请求授权的timestamp,然后当1/QPS时间度过后分发一个permit。例如,固定速率 QPS=5,如果当上一个请求过去不到200ms,确保新请求不被授权,我们就可以达到想要的限定rate。

RateLimiter对过去的记录很少,假设它只记录了上一次请求。如果RateLimiter长时间没有被使用,新的请求到达时,能否立即被授权?RateLimiter将忘掉过去的未使用的授权。依照现实世界,当使用没有达到设定的rate时,perimits将会利用率不足,或者溢出。过去的利用不足(past underutilization)意味着过量的资源是可用的,那么RateLimiter可以通过加速一会来充分利用这些资源。例如当限定bandwidth时,过去资源利用不足意味着几乎为空的buffers可以通过加速瞬速被填满。过去利用不足意味着服务器可能对处理未来新的请求准备不充分,比如服务器的缓存失效,或者新请求可能触发开销比较大的操作。

为了应对这些场景,RateLimiter添加了一个额外的维度,把过去的利用不足(past underutilization)设为 storedPermits变量。当没有利用不足时,storedPermits为0,如果有充分的利用不足发生时,storedPermits逐渐增加到maxStoredPermits,当有新新请求调用acquire(permits)时,如果storedPermits>permits,则直接返还回对应的permits(这里在预热模式实现会不同,预热模式同样会让请求等待),如果不足,则不足部分等到新的permits。


通过下边的例子解释这种工作机制:

例如RateLimiter每秒产生一个token,如果接下来RateLimiter没有被利用,那么我们把storedPermits加1,假设我们10s没有用RateLimiter,那么storedPermits将为10(设定maxStoredPermits >= 10.0)。这时一个acquire(3)的请求到达,我们直接从storedPermits中取出3个来服务,瞬间这时有个acquire(10)的请求到达,我们可以通过storedPermits中取出剩余的7个,然后剩下的3个通过RateLimiter新的生产出3个permits来服务。

我们已经知道分发3个新permits将会花费3秒,那么如何分发7个stored permits?这个没有统一的答案。如果我们希望处理利用不足问题,那么我们可能会把更快的或者不让请求等待直接从storedPermits中取出,如果我们担心资源使用过度或者预热不足,我们可以放慢分发storedPermits,因此我们需要一个function把storedPermits转换为限流时间。

这个function 在RateLimiter的扩展类SmoothRateLimiter中是storedPermitsToWaitTime(double storedPermits, double permitsToTake),这个function把storedPermits转换为等待时间。这个在SmoothBursty和SmoothWarmingUp是不同的实现,SmoothBursty直接返回无需等待,SmoothWarmingUp则要计数出等待时间。

最后一点是,如果RateLimiter 采用QPS=1的限定速度,那么开销较大的acquire(100)请求到达时,它是没必要等到100s 才开始实际任务。我们可以先开始任务执行,并把未来的请求推后100s,这样我们就可以同时工作,同时生产需要的permits,而不是空等待permits生产够才开始工作。这样的话那么RateLimiter不需要记住time of the _last_ request,它只需要记住
   the (expected) time of the _next_ request。我们通过 (now -  the expected time of the _next_ request )计算出为利用的时间段t,通过t*QPS计算出storedPermits。这个方法就是 SmoothRateLimiter 中的reserveEarliestAvailable方法。


### 关键方法分析
*  SmoothRateLimiter中的 reserveEarliestAvailable

//该方法计算满足当前requiredPermits数量的“时刻” final long reserveEarliestAvailable(int requiredPermits, long nowMicros) { //最重要的逻辑 resync(nowMicros); long returnValue = nextFreeTicketMicros; double storedPermitsToSpend = min(requiredPermits, this.storedPermits); double freshPermits = requiredPermits - storedPermitsToSpend; long waitMicros = storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend) + (long) (freshPermits * stableIntervalMicros); //设定本次请求会消耗到的时刻 this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros); this.storedPermits -= storedPermitsToSpend; return returnValue; }

void resync(long nowMicros) {
// if nextFreeTicket is in the past, resync to now
//nextFreeTicketMicros 是上文中我们讲的the expected time of the _next_ request
if (nowMicros > nextFreeTicketMicros) {
  double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
  storedPermits = min(maxPermits, storedPermits + newPermits);
  nextFreeTicketMicros = nowMicros;
}

}

//非预热模式 SmoothBursty double coolDownIntervalMicros() { // 等价于 1/QPS return stableIntervalMicros; }


* SmoothWarmingUp中的storedPermitsToWaitTime

long storedPermitsToWaitTime(double storedPermits, double permitsToTake) { double availablePermitsAboveThreshold = storedPermits - thresholdPermits; long micros = 0; // measuring the integral on the right part of the function (the climbing line) if (availablePermitsAboveThreshold > 0.0) { double permitsAboveThresholdToTake = min(availablePermitsAboveThreshold, permitsToTake); // TODO(cpovirk): Figure out a good name for this variable. double length = permitsToTime(availablePermitsAboveThreshold) + permitsToTime(availablePermitsAboveThreshold - permitsAboveThresholdToTake); micros = (long) (permitsAboveThresholdToTake * length / 2.0); permitsToTake -= permitsAboveThresholdToTake; } // measuring the integral on the left part of the function (the horizontal line) micros += (stableIntervalMicros * permitsToTake); return micros; }

![输入图片说明](https://static.oschina.net/uploads/img/201611/19221636_NrQQ.png "在这里输入图片标题")

方法中设计到的参数计算方式这里不细讲了。

[https://my.oschina.net/robinyao/blog/790890](https://my.oschina.net/robinyao/blog/790890)

© 著作权归作者所有

上一篇: 常用的shell
下一篇: Ansible
robin-yao
粉丝 167
博文 54
码字总数 61436
作品 0
杭州
私信 提问
加载中

评论(1)

pczhangtl
pczhangtl
很不错
Guava RateLimiter限流源码解析和实例应用

在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流 缓存的目的是提升系统访问速度和增大系统处理容量 降级是当服务出现问题或者影响到核心流程时,需要暂时屏蔽掉,待高峰或者问题...

算法之名
05/26
272
0
SpringMVC 限流

在使用做接口访问如何做接口的限流,这里我们可以使用google的Guava包来实现,当然我们也可以自己实现限流,Guava中的限流是久经考验的我们没必需重新再去写一个,如果想了解限流原理的同学可...

dounine
2017/11/30
0
0
高并发系统限流设计

欢迎访问我的博客查看原文:http://wangnan.tech 概述 高并发系统时有三把利器用来保护系统:缓存、降级和限流,缓存的目的是提升系统访问速度和增大系统能处理的容量,降级是当服务出问题或...

wanna
2017/10/25
0
0
接口限流算法:漏桶算法和令牌桶算法

漏桶算法 漏桶可以看作是一个带有常量服务时间的单服务器队列,如果漏桶(包缓存)溢出,那么数据包会被丢弃。这一点和线程池原理是很相似的。 把请求比作是水,水来了都先放进桶里,并以限定...

铁骨铮铮
05/23
242
0
基于分布式环境下限流系统的设计

前提 业务背景 就拿前些天的双十一的 “抢券活动” 来说,一般是设置整点开始抢的,你想想,淘宝的用户群体非常大,可以达到亿级别,而服务接口每秒能处理的量是有限的,那么这个时候问题就会...

t4i2b10X4c22nF6A
2017/11/18
0
0

没有更多内容

加载失败,请刷新页面

加载更多

最简单的获取相机拍照的图片

  import android.content.Intent;import android.graphics.Bitmap;import android.os.Bundle;import android.os.Environment;import android.provider.MediaStore;import andr......

MrLins
今天
6
0
说好不哭!数据可视化深度干货,前端开发下一个涨薪点在这里~

随着互联网在各行各业的影响不断深入,数据规模越来越大,各企业也越来越重视数据的价值。作为一家专业的数据智能公司,个推从消息推送服务起家,经过多年的持续耕耘,积累沉淀了海量数据,在...

个推
今天
9
0
第三方支付-返回与回调注意事项

不管是支付宝,微信,还是其它第三方支付,第四方支付,支付机构服务商只要涉及到钱的交易都要进行如下校验,全部成功了才视为成功订单 1.http请求是否成功 2.校验商户号 3.校验订单号及状态...

Shingfi
今天
5
0
简述Java内存分配和回收策略以及Minor GC 和 Major GC(Full GC)

内存分配: 1. 栈区:栈可分为Java虚拟机和本地方法栈 2. 堆区:堆被所有线程共享,在虚拟机启动时创建,是唯一的目的是存放对象实例,是gc的主要区域。通常可分为两个区块年轻代和年老代。更...

DustinChan
今天
7
0
Excel插入批注:可在批注插入文字、形状、图片

1.批注一直显示:审阅选项卡-------->勾选显示批注选项: 2.插入批注快捷键:Shift+F2 组合键 3.在批注中插入图片:鼠标右键点击批注框的小圆点【重点不可以在批注文本框内点击】----->调出批...

东方墨天
今天
7
1

没有更多内容

加载失败,请刷新页面

加载更多

返回顶部
顶部