Rate limit 限流技术

在高并发系统中经常使用三种技术保护系统：缓存，降级和限流。缓存的目的是提升系统访问速度和增大系统能处理的容量，降级是当服务出问题是暂时屏蔽掉，等高峰期后或问题解决后在重启，然而针对有些场景并不能用缓存和降级来解决，比如稀缺资源（秒杀，抢购），写服务（评论，下单），频繁的复杂查询（评论的最后几页），这时候需要限流这项技术来限制这些场景的并发/请求量。限流的目的是通过对并发访问/请求进行限速或者一个时间窗口内的的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务（定向到错误页或告知资源没有了）、排队或等待（比如秒杀、评论、下单）、降级（返回兜底数据或默认数据，如商品详情页库存默认有货）

常见限流算法（算法层面限流）

计数器，令牌桶，漏桶

计数器

主要用来限制总并发数，比如数据库连接池，线程池，秒杀的并发数；超过了瞬时请求数或者在一定时间段内的请求数设定的阈值，则进行简单粗暴的限流，主要针对的还是总体的请求数量，而不是考虑的平均速率的限流。

令牌桶 Token Bucket

随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了就不再加了.新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务.令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量 token_bucket

长期来看，符合流量的速率是受到令牌添加速率的影响，被稳定为：r 因为令牌桶有一定的存储量，可以抵挡一定的流量突发情况 M是以字节/秒为单位的最大可能传输速率。 M>r T max = b/(M-r) 承受最大传输速率的时间 B max = T max * M 承受最大传输速率的时间内传输的流量

Guava RateLimiter提供了令牌桶算法实现：平滑突发限流(SmoothBursty)和平滑预热限流(SmoothWarmingUp)实现。

漏桶 Leaky Bucket

漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法能强行限制数据的传输速率.

两桶对比

令牌桶是按照固定速率往桶中添加令牌，请求是否被处理需要看桶中令牌是否足够，当令牌数减为零时则拒绝新的请求；
漏桶则是按照常量固定速率流出请求，流入请求速率任意，当流入的请求数累积到漏桶容量时，则新流入的请求被拒绝；
令牌桶限制的是平均流入速率（允许突发请求，只要有令牌就可以处理，支持一次拿3个令牌，4个令牌），并允许一定程度突发流量；
漏桶限制的是常量流出速率（即流出速率是一个固定常量值，比如都是1的速率流出，而不能一次是1，下次又是2），从而平滑突发流入速率；
令牌桶允许一定程度的突发，而漏桶主要目的是平滑流入速率；
两个算法实现可以一样，但是方向是相反的，对于相同的参数得到的限流效果是一样的。

应用级限流

一般来说，对于一个应用系统都会有极限并发数和请求数，TPS和QPS。如果超过了阈值则系统会无法响应或者崩溃，所以一般在进行开发大规模系统的时候，要设置过载保护，以免大量请求使系统瘫痪。

限流总资源数。有的资源是稀缺资源（如数据库连接、线程），可以使用池化技术来限制总资源数：连接池、线程池。比如分配给每个应用的数据库连接是100，那么本应用最多可以使用100个资源，超出了可以等待或者抛异常。如果接口可能会有突发访问情况，但又担心访问量太大造成崩溃，如抢购业务；这个时候就需要限制这个接口的总并发/请求数总请求数了；因为粒度比较细，可以为每个接口都设置相应的阀值。可以使用Java中的AtomicLong进行限流：

try {
      if(atomic.incrementAndGet() > 限流数) {
          //拒绝请求  
      }    
      //处理请求
      } finally {    
        atomic.decrementAndGet();
      }

适合对业务无损的服务或者需要过载保护的服务进行限流，如抢购业务，超出了大小要么让用户排队，要么告诉用户没货了，对用户来说是可以接受的。而一些开放平台也会限制用户调用某个接口的试用请求量，也可以用这种计数器方式实现。这种方式也是简单粗暴的限流，没有平滑处理，需要根据实际情况选择使用； 2. 限流某个接口的时间窗请求数即一个时间窗口内的请求数，如想限制某个接口/服务每秒/每分钟/每天的请求数/调用量。如一些基础服务会被很多其他系统调用，比如商品详情页服务会调用基础商品服务调用，但是怕因为更新量比较大将基础服务打挂，这时我们要对每秒/每分钟的调用量进行限速；时间窗最大请求数，指定的时间范围内允许的最大请求数优点：这个算法能够满足绝大多数的流控需求，通过时间窗最大请求数可以直接换算出最大的QPS（QPS = 请求数/时间窗）缺点：这种方式可能会出现流量不平滑的情况，时间窗内一小段流量占比特别大

LoadingCache<Long, AtomicLong> counter =
        CacheBuilder.newBuilder()
                .expireAfterWrite(2, TimeUnit.SECONDS)
                .build(new CacheLoader<Long, AtomicLong>() {
                    @Override
                    public AtomicLong load(Long seconds) throws Exception {
                        return new AtomicLong(0);
                    }
                });
long limit = 1000;
while(true) {
    //得到当前秒
    long currentSeconds = System.currentTimeMillis() / 1000;
    if(counter.get(currentSeconds).incrementAndGet() > limit) {
        System.out.println("限流了:" + currentSeconds);
        continue;
    }
    //业务处理
}

我们使用Guava的Cache来存储计数器，过期时间设置为2秒（保证1秒内的计数器是有的），然后我们获取当前时间戳然后取秒数来作为KEY进行计数统计和限流，这种方式也是简单粗暴，刚才说的场景够用了。 3. 平滑限流某个接口的请求数之前的限流方式都不能很好地应对突发请求，即瞬间请求可能都被允许从而导致一些问题；因此在一些场景中需要对突发请求进行整形，整形为平均速率请求处理（比如5r/s，则每隔200毫秒处理一个请求，平滑了速率）。这个时候有两种算法满足我们的场景：令牌桶和漏桶算法。Guava框架提供了令牌桶算法实现，可直接拿来使用。 Guava RateLimiter提供了令牌桶算法实现：平滑突发限流(SmoothBursty)和平滑预热限流(SmoothWarmingUp)实现。

Ref

http://xiaobaoqiu.github.io/blog/2015/07/02/ratelimiter/ https://www.jianshu.com/p/a3d068f2586d https://mp.weixin.qq.com/s?__biz=MzI0MTk0NTY5MA==&mid=2247483711&idx=1&sn=28780c8b26f24ac6314ff5c599bb622c&chksm=e9029c0ade75151c353cd6b720ce438b4342afd8ef3a7d03c61712554c6a000ac3646bbc3124&scene=38#wechat_redirect 聊聊高并发系统之限流特技-1

Rate limit 限流技术#

常见限流算法 （算法层面限流）#

计数器#

令牌桶 Token Bucket#

漏桶 Leaky Bucket#

两桶对比#

应用级限流#

Ref#