常见限流算法(常见限流算法包括)

  本篇文章为你整理了常见限流算法(常见限流算法包括)的详细内容,包含有常见限流算法有哪几种 常见限流算法包括 常见的限流算法 限流算法包括哪些 常见限流算法,希望能帮助你了解 常见限流算法。

  限流顾名思义是对流量大小进行限制,防止请求数量超过系统的负载能力,导致系统崩溃,起到保护作用。
 

  现实生活中限流也随处可见,节假日出门旅行的人数会剧增,对于旅游景点来说往往会不堪重负,如果不进行人数控制,对整个景点的压力会非常大,游客的体验也会非常差,还容易出现安全事故等危险。
 

  同样的在一线城市地铁限流也非常常见,早高峰为了控制乘车人数和有序进站,地铁往往会在地铁口进行拦截,一定时间内才放行一部分人进站乘车。
 

  
 

  具体到程序,限流可以有以下几种场景

  限制某个接口每秒最多访问多少次

  限制某个ip每秒最多访问多少次

  限制某个用户或某个来源每秒最多访问多少次

  限制某些用户下载速度每秒最多多少kb

  禁止某些用户或ip的访问

  限流起到了保护作用,那么如何限呢?如果限制得太严,保护是保护到了,但是系统的处理能力下降了,体验会很差;如果限制得太松,就会被一些突增流量冲击到,或者被黑客利用进行安全攻击。如何限流需要根据系统的负载来评估,系统的负载和处理能力是动态的,例如平时的qps是1000,双11一般会进行扩容,也就是加服务节点,qps可能就是5000,这个时候系统处理能力变强的,限流策略也应该相应的调整。还有一种是出于安全的限流,例如同一个客户端ip 1s内对系统发出上万次请求,这种可以确定就是安全攻击,很可能是有人恶意破坏,或者是一些爬虫,这种可以限制请求数,超出的就直接拒绝。
 

  如何限流是限流算法要实现的,常见的限流算法有“两桶两窗”,固定窗口、滑动窗口、漏桶与令牌桶,接下来介绍这四种算法及应用。

  固定窗口的思想和实现非常简单,就是统计每个固定每个时间窗口的请求数,超过则拒绝。
 

  
 

  如图我们定义了窗口大小为1s,最大请求数100,窗口内超过100的请求数将被拒绝。实现上也非常简单,利用redis的incr自增计数,当前时间秒作为缓存key,每次自增后判断是否超过指定大小即可。
 

  固定窗口的问题是容易出现“突刺现象”,例如在1s内,100个请求都是在前100ms过来的,那么后面的900ms的请求都会被拒绝,而系统此时是空闲的。另外还有“临界问题”,如果100个请求是在后100ms过来的,而下一个1s的100个请求在前100ms过来,此时系统在这200ms内就需要处理200个请求,跟我们想要的不符合。到这里我们很容易想到,1s这个范围太大了,缩小一些就更好了,这种把固定窗口拆成更多个小窗口的做法就是滑动窗口算法了。
 

  滑动窗口的思想是将固定窗口拆成更多个小窗口,随着时间的推移,窗口不断的滑动,统计也在不断的变化。窗口拆分的越多,滑动就会越平滑,统计就会越精确,所消耗的资源就会越多。滑动窗口如果只拆为1个窗口,就退化为固定窗口。
 

  滑动窗口算法可以解决上面固定窗口的问题,像hystrix和sentinel中都使用该算法进行数据统计,用于限流熔断等策略处理。如hystrix中图所示,在一个窗口内拆分了10个桶(bucket),随着时间的推移,会创建新的桶也会丢弃过期的桶,当然窗口的大小和拆分桶的数量都是可配置的。
 

  漏桶算法的思想是将请求先放到一个桶中,然后像滴水一样不断的从中取出请求执行,桶满则溢,后面的请求会被拒绝。
 

  漏桶算法的特点是流入速度不确定,但是流出速度是确定的,漏桶可以很平滑,均衡的处理请求,但是无法应对短暂的突发流量。

  令牌桶算法的思想是不断的生成令牌放到一个桶中,请求到来时到桶中申请令牌,申请得到就执行,申请不到就拒绝。如果桶中的令牌满了,新生成的令牌也会丢弃。
 

  与漏桶不同的是,令牌桶是流入速度确定(生成令牌的速度),流出速度不确定,所以它不想漏桶一样可以均衡的处理请求,但是由于有令牌桶这个缓冲,一旦有突增的流量,令牌桶里已有的令牌可以短暂的应对突发流量,由于流出速度是不限制的,此时桶中已有的令牌都可以被申请到,请求一下子就会到我们的服务,给系统带来一定的压力,所以桶的大小需要合适,不宜过大。举个栗子:令牌桶的大小是1000,每秒放100个令牌,经过一段时间后,请求有空闲时,桶里的令牌就会积压,最终保存了满1000个令牌,由于某刻流量突增,有1000个请求到来,此时能申请到1000个令牌,所有请求都会放行,最终达到我们的系统,如果令牌桶过大,系统可能会承受不了这波请求。

  guava RateLimiter

  guava限流实现的是桶算法,通过RateLimiter.create创建,可以创建两种类型的限流器,SmoothBursty和SmoothWarmingUp,前者定时生成令牌,后者有一个预热的过程。
 

  我们如下示例代码,每秒会创建2个令牌,并且初始化的时候就是2。定时器每200ms会申请一次令牌,每秒申请5次,只有2次成功,所有运行程序每秒有3次success和2次fail。

  

 RateLimiter rateLimiter = RateLimiter.create(2);

 

   new Timer().schedule(new TimerTask() {

   @Override

   public void run() {

   if (rateLimiter.tryAcquire()) {

   System.out.println("success");

   } else {

   System.out.println("fail");

   }, 0, 200);

  

 

  既然是桶,那么桶的大小是多少呢?SmoothBursty里最大令牌数由maxPermits字段表示,该字段等于maxBurstSeconds * permitsPerSecond,permitsPerSecond是每秒要生成的令牌数,maxBurstSeconds默认是1。
 

  另外还可以创建SmoothWarmingUp带有预热功能的限流器,预热的作用是通过一个过程才达到permitsPerSecond,相当于让系统有个热身的时间。

  

 RateLimiter rateLimiter = RateLimiter.create(5, 10, TimeUnit.MILLISECONDS);

 

   new Timer().schedule(new TimerTask() {

   @Override

   public void run() {

   log.info("" + rateLimiter.acquire());

   }, 0, 200);

  

 

  rateLimiter.acquire()返回的是获取打令牌的时间,运行程序可以看到开始并不是每秒都能产生5个令牌,也就是不是能立刻获取到令牌,获取令牌需要的时间会越来越小,直到预热期过后就能立马获取到令牌了。
 

  guava的限流只能提供单机版的实现,对于集群就无能为力了,并且它通常作为一个工具存在,使用还需要自己封装,集成到服务,并不能开箱即用。

  bucket4j

  bucket4j是一个java实现,基于令牌桶算法的限流组件。它支持分布式限流,支持多种存储,可以方便与各种框架和监控集成。github上start 1.2K,但是issues数量少,国内估计使用的人也不多,并且官方的实现存储不支持最常用的redis,它专注于限流,如果是自研或者二次开发,是一个很好的参考。

  Resilience4j

  之前我们介绍过它的熔断功能,Resilience4j也提供了限流的实现,可以参考这里。相比guava,Resilience4j是框架级别的,可以很方便的使用。但Resilience4j也是单机版的实现,无法支持集群功能。
 

  Resilience4j限流实现的是令牌桶,如下配置,每1s会生成10个令牌。

  

resilience4j.ratelimiter:

 

   instances:

   backendA:

   limitForPeriod: 10

   limitRefreshPeriod: 1s

   timeoutDuration: 0

   registerHealthIndicator: true

   eventConsumerBufferSize: 100

  

 

  sentinel

  流量控制是sentinel最重要的一个功能,sentinel属于后起之秀,文档齐全,支持的场景更加丰富。sentinel支持集群限流,也可以像guava一样预热,还可以基于调用链路进行限流。
 

  sentinel还提供了控制台功能,支持多种数据源的持久化,使用spring cloud的话可以通过spring cloud alibaba引入sentinel。
 

  开源版的sentinel有一些限制,并且使用起来并不是那么方便,例如Resilience4j可以配置一个default针对所有的请求生效,但sentinel需要单个单个url去配置,显得非常麻烦,包括熔断feign接口的配置也是,这个给spring cloud alibaba提了feature,也许在下一个版本就会提供支持。

  nginx

  上面讲到的都是应用级别的限流,nginx通常作为网络请求的入口,从运维的角度来说,在这里做限流再合适不过,nginx本身也提供了限流的支持。
 

  nginx比较适合对外的限流,但是我们内部不同系统间的调用一遍不经过nginx,会直接访问到对方的网关,所以两者并不矛盾。
 

  nginx限流通过limit_req和limit_conn两个模块支持,分别对应请求限制和链接限制(一个链接可以有多个请求)。

  

http { 

 

   limit_req_zone zone=name:10m rate=100r/s;

   server {

   location /app/ {

   limit_req zone=name burst=500 nodelay;

  

 

  如上,定义了一个name zone,访问速率最高是100个每秒,/app路径应用了这个规则。busrt表示爆发的意思,是一个缓冲队列,用于存储突增的请求,这些请求会被缓存不会拒绝,如果超过了burst,nodelay表示不等待直接拒绝。
 

  前面我们说到有些恶意攻击可能每秒发送上万个请求,导致服务崩溃,如果多个应用系统共用一个nginx,那么可以统一在nginx配置处理,不需要每个系统自己去实现。

  

limit_conn_zone $binary_remote_addr zone=name:10m;

 

  server {

   limit_conn name 50;

  

 

  如上,定义了一个name zone,$binary_remote_addr表示远端地址,也就是ip,10m表示存储空间,10m大概可以存储16w的ip地址,我们在server节点应用这个规则,50表示最多50个,超过就会拒绝。

  欢迎关注我的github:https://github.com/jmilktea/jtea

  以上就是常见限流算法(常见限流算法包括)的详细内容,想要了解更多 常见限流算法的内容,请持续关注盛行IT软件开发工作室。

郑重声明:本文由网友发布,不代表盛行IT的观点,版权归原作者所有,仅为传播更多信息之目的,如有侵权请联系,我们将第一时间修改或删除,多谢。

留言与评论(共有 条评论)
   
验证码: