信号量与令牌桶_限流算法之漏桶算法、令牌桶算法

RateLimiter是Guava的concurrent包下的一个用于限制访问频率的类.

1.限流

每个API接口都是有访问上限的,当访问频率或者并发量超过其承受范围时候,我们就必须考虑限流来保证接口的可用性或者降级可用性.即接口也需要安装上保险丝,以防止非预期的请求对系统压力过大而引起的系统瘫痪.

通常的策略就是拒绝多余的访问,或者让多余的访问排队等待服务,或者引流.

如果要准确的控制QPS,简单的做法是维护一个单位时间内的Counter,如判断单位时间已经过去,则将Counter重置零.此做法被认为没有很好的处理单位时间的边界,比如在前一秒的最后一毫秒里和下一秒的第一毫秒都触发了最大的请求数,将目光移动一下,就看到在两毫秒内发生了两倍的QPS.

2.限流算法

常用的更平滑的限流算法有两种:漏桶算法和令牌桶算法.

两种限流的祖师级算法确有其独到之处，其他实现比如滑动时间窗或者三色速率标记法，其实是“漏桶”与“令牌桶”的变种。要么将“漏桶”容积换成了单位时间，要么是按规则将请求标记颜色进行处理，底层还是“令牌”的思想。

2.1计数器

计数器法是限流算法里最简单也是最容易实现的一种算法。比如我们规定，对于A接口来说，我们1分钟的访问次数不能超过100个。那么我们我们可以设置一个计数器counter，其有效时间为1分钟(即每分钟计数器会被重置为0)，每当一个请求过来的时候，counter就加1，如果counter的值大于100，就说明请求数过多；

这个算法虽然简单，但是有一个十分致命的问题，那就是临界问题。

如上图所示，在1:00前一刻到达100个请求，1:00计数器被重置，1:00后一刻又到达100个请求，显然计数器不会超过100，所有请求都不会被拦截；然而这一时间段内请求数已经达到200，远超100。

2.2 漏桶算法

漏桶(Leaky Bucket)算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水(接口有响应速率),当水流入速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,而当入小于出的情况下，漏桶不起任何作用。可以看出漏桶算法能强行限制数据的传输速率.示意图如下:

      

注意：在我们的应用中，漏桶算法强制限定流量速率后，多出的(溢出的)流量可以被利用起来，并非完全丢弃，我们可以把它收集到一个队列里面，做流量队列，尽量做到合理利用所有资源。

漏桶算法：水(请求)先进入到漏桶里，漏桶以一定的速度出水，当水流入速度过大会直接溢出(拒绝服务)，可以看出漏桶算法能强行限制数据的传输速率

流入：以任意速率往桶中放入水滴。

流出：以固定速率从桶中流出水滴。

用白话具体说明：假设漏斗总支持并发100个最大请求，如果超过100个请求，那么会提示系统繁忙，请稍后再试，数据输出那可以设置1个线程池，处理线程数5个，每秒处理20个请求。

缺点：因为当流出速度固定，大规模持续突发量，无法多余处理，浪费网络带宽

优点：无法击垮服务

示例：

可见这里有两个变量,一个是桶的大小,支持流量突发增多时可以存多少的水(burst),另一个是水桶漏洞的大小(rate)，伪代码如下：

double rate; //leak rate in calls/s

double burst; //bucket size in calls

long refreshTime; //time for last water refresh

double water; //water count at refreshTime

refreshWater() {long now =getTimeOfDay();//水随着时间流逝,不断流走,最多就流干到0.

water = max(0, water- (now - refreshTime)*rate);

refreshTime=now;

}

bool permissionGranted() {

refreshWater();if (water < burst) { //水桶还没满,继续加1

water ++;return true;

}else{return false;

}

}

因为漏桶的漏出速率是固定的参数,所以,即使网络中不存在资源冲突(没有发生拥塞),漏桶算法也不能使流突发(burst)到端口速率.因此,漏桶算法对于存在突发特性的流量来说缺乏效率.

2.3 令牌桶算法

令牌桶算法(Token Bucket)和 Leaky Bucket 效果一样但方向相反的算法,更加容易理解.随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token(想象和漏洞漏水相反,有个水龙头在不断的加水),如果桶已经满了，令牌就溢出了。如果桶未满，令牌可以积累。新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务.

令牌桶的另外一个好处是可以方便的改变速度. 一旦需要提高速率,则按需提高放入桶中的令牌的速率. 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量.

令牌桶算法：一个存放固定容量令牌的桶，按照固定速率(每秒/或者可以自定义时间)往桶里添加令牌，然后每次获取一个令牌，当桶里没有令牌可取时，则拒绝服务

令牌桶分为2个动作，动作1(固定速率往桶中存入令牌)、动作2(客户端如果想访问请求，先从桶中获取token)

流入：以固定速率从桶中流入水滴

流出：按照任意速率从桶中流出水滴

技术上使用Google开源工具包Guava提供了限流工具类RateLimiter，该类基于令牌桶算法来完成限流，非常易于使用

优点：支持大的并发，有效利用网络带宽

漏桶和令牌桶的区别：

并不能说明令牌桶一定比漏洞好，她们使用场景不一样。

令牌桶算法，放在服务端，用来保护服务端(自己)，主要用来对调用者频率进行限流，为的是不让自己被压垮。所以如果自己本身有处理能力的时候，如果流量突发(实际消费能力强于配置的流量限制=桶大小)，那么实际处理速率可以超过配置的限制(桶大小)。

而漏桶算法，放在调用方，这是用来保护他人，也就是保护他所调用的系统。主要场景是，当调用的第三方系统本身没有保护机制，或者有流量限制的时候，我们的调用速度不能超过他的限制，由于我们不能更改第三方系统，所以只有在主调方控制。这个时候，即使流量突发，也必须舍弃。因为消费能力是第三方决定的。

2.4、滑动时间窗

滑动窗口，又称rolling window。为了解决这个问题，我们引入了滑动窗口算法。如果学过TCP网络协议的话，那么一定对滑动窗口这个名词不会陌生。下面这张图，很好地解释了滑动