一、写在最前
轰轰烈烈的双十二已经过去小半个月了，程序猿的我坐在办公桌上思考，双十二这么大的访问量，这群电商是怎么扛住的，接口分分钟会变得不可用，并引发连锁反应导致整个系统崩溃。好吃懒做的小编，被可怕的好奇心驱使着去调研流量控制算法。好奇心害死猫，才有了这篇文章。
二、流量控制算法简介
流量控制在计算机领域称为过载保护。何为过载保护？所谓“过载”，即需求超过了负载能力;而“保护”则是指当“过载”发生了，采取必要的措施保护自己不受“伤害”。在计算机领域，尤其是分布式系统领域，“过载保护”是一个重要的概念。一个不具备“过载保护”功能的系统，是非常危险和脆弱的，很可能由于瞬间的压力激增，引起“雪崩效应”，导致系统的各个部分都同时崩溃，停止服务。这就好像在没有保险丝的保护下，电压突然变高，导致所有的电器都会被损坏一样，“过载保护”功能是系统的“保险丝”。
如今互联网领域，也借鉴了这一思路扛住双十二， 控制网络数据传输的速率，使流量以比较均匀的速度向外发送。最终实现优化性能，减少延迟和提高带宽等。
三、常用的限流算法
常用的限流算法有两种：漏桶算法和令牌桶算法。本篇文章将介绍自己造轮子限流算法、漏桶算法和令牌桶算法。
3.1 自己造轮子限流算法
作为一名小白，我是不愿意自己造轮子的，但是真要早轮子，有一个简单粗暴的思路：
1）设置单位时间T（如10s）内的最大访问量，在单位时间T内维护计数器Count；
2）当请求到达时，判断时间是否进入下一个单位时间；
3）如果是，则重置计数器为0；
4）如果不是，计数器Count++,并判断计数器Count是否超过最大访问量，如超过，则拒绝访问。
long timeStamp = getNowTime();
int reqCount = 0;
const int maxReqCount = 10000;//时间周期内最大请求数
const long effectiveDuration = 10;//时间控制周期
public static bool control(){
long now = getNowTime();
if (now < timeStamp + effectiveDuration){//在时间控制范围内
reqCount++;
return reqCount > maxReqCount;//当前时间范围内超过最大请求控制数
}else{
timeStamp = now;//超时后重置
reqCount = 0;
return true;
}
}
public static int getNowTime(){
long time = System.currentTimeMillis();
return (int) (time/1000);
}
该算法实现看似确实完美的实现了“单位时间内最大访问量控制”，但它在两个单位时间的临界值上的处理是有缺陷的。如：设需要控制的最大请求数为1w, 在第一个单位时间（0-10s）的最后一秒（即第9s）里达到的请求数为1w,接下来第二个单位时间（10-20s）的第一秒（即第10s）里达到请求数也是1w,由于超时重置发生在两个单位时间之间，所以这2w个请求都将通过控制，也就是说在2s里处理2w个请求java 令牌桶算法 流量控制算法——漏桶算法和令牌桶算法，与我们设置的10s里1w个请求的设想是相违背。
学术一点的说法是该算法处理请求不够平滑，不能很好的满足限流需求。
3.2 漏桶算法
漏桶算法思路很简单，请求先进入到漏桶里，漏桶以固定的速度出水，也就是处理请求，当水加的过快，则会直接溢出，也就是拒绝请求，可以看出漏桶算法能强行限制数据的传输速率。
漏桶算法
long timeStamp = getNowTime();
int capacity = 10000;// 桶的容量
int rate = 1;//水漏出的速度
int water = 100;//当前水量
public static bool control() {
//先执行漏水，因为rate是固定的，所以可以认为“时间间隔*rate”即为漏出的水量
long now = getNowTime();
water = Math.max(0, water - (now - timeStamp) * rate);
timeStamp = now;
if (water < capacity) { // 水还未满，加水
water ++;
return true;
} else {
return false;//水满，拒绝加水
}
}
该算法很好的解决了时间边界处理不够平滑的问题，因为在每次请求进桶前都将执行“漏水”的操作，再无边界问题。
但是对于很多场景来说，除了要求能够限制数据的平均传输速率外，还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了，令牌桶算法更为适合。
3.3 令牌桶算法
令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。
令牌桶算法
3.3.1 原理
令牌桶是网络设备的内部存储池，而令牌则是以给定速率填充令牌桶的虚拟信息包。每个到达的令牌都会从数据队列领出相应的数据包进行发送，发送完数据后令牌被删除。
请求注解（RFC）中定义了两种令牌桶算法——单速率三色标记算法和双速率三色标记算法，其评估结果都是为报文打上红、黄、绿三色标记。QoS会根据报文的颜色，设置报文的丢弃优先级，其中单速率三色标记比较关心报文尺寸的突发，而双速率三色标记则关注速率上的突发，两种算法都可工作于色盲模式和非色盲模式。以下结合这两种工作模式介绍一下RFC中所描述的这两种算法。
1）单速率三色标记算法
网络工程师任务小组（IETF）的RFC文件定义了单速率三色标记算法，评估依据以下3个参数：承诺访问速率(CIR)，即向令牌桶中填充令牌的速率；承诺突发尺寸(CBS)，即令牌桶的容量，每次突发所允许的最大流量尺寸（注：设置的突发尺寸必须大于最大报文长度）；超额突发尺寸(EBS)。
一般采用双桶结构：C桶和E桶。Tc表示C桶中的令牌数，Te表示E桶中令牌数，两桶的总容量分别为CBS和EBS。初始状态时两桶是满的，即Tc和Te初始值分别等于CBS和EBS。令牌的产生速率是CIR，通常是先往C桶中添加令牌，等C桶满了，再往E桶中添加令牌，当两桶都被填满时，新产生的令牌将会被丢弃。
色盲模式下，假设到达的报文长度为B。若报文长度B小于C桶中的令牌数Tc，则报文被标记为绿色，且C桶中的令牌数减少B；若TcTe，标记为红色，两桶总令牌数都不减少。
在非色盲模式下，若报文已被标记为绿色或B Te，则标记为红色，Tc和Te都不减少。
2）双速率三色标记算法
IETF的RFC文件定义了双速率三色算法，主要是根据4种流量参数来评估：CIR、CBS、峰值信息速率(PIR)，峰值突发尺寸(PBS)。前两种参数与单速率三色算法中的含义相同，PIR这个参数只在交换机上才有，路由器没有这个参数。该值必须不小于CIR的设置值，如果大于CIR，则速率限制在CIR于PRI之间的一个值。
与单速率三色标记算法不同，双速率三色标记算法的两个令牌桶C桶和P桶填充令牌的速率不同，C桶填充速率为CIR，P桶为PIR；两桶的容量分别为CBS和PBS。用Tc和Tp表示两桶中的令牌数目，初始状态时两桶是满的，即Tc和Tp初始值分别等于CBS和PBS。
色盲模式下，如果到达的报文速率大于PIR，超过Tp+Tc部分无法得到令牌，报文被标记为红色，未超过Tp+Tc而从P桶中获取令牌的报文标记为黄色，从C桶中获取令牌的报文被标记为绿色；当报文速率小于PIR，大于CIR时，报文不会得不到令牌，但超过Tp部分报文将从P桶中获取令牌，被标记为黄色报文，从C桶中获取令牌的报文被标记为绿色；当报文速率小于CIR时，报文所需令牌数不会超过Tc，只从C桶中获取令牌，所以只会被标记为绿色报文。
在非色盲模式下，如果报文已被标记为红色或者超过Tp+Tc部分无法得到令牌的报文，被标记为红色；如果标记为黄色或者超过Tc未超过Tp部分报文记为黄色；如果报文被标记为绿或未超过Tc部分报文，被标记为绿色。
3.3.2 算法描述与实现
long timeStamp=getNowTime();
int capacity; // 桶的容量
int rate ;//令牌放入速度
int tokens;//当前水量
bool control() {
//先执行添加令牌的操作
long now = getNowTime();
tokens = max(capacity, tokens+ (now - timeStamp)*rate);
timeStamp = now; //令牌已用完，拒绝访问
if(tokens nextFreeTicketMicros) {
storedPermits = min(maxPermits,
storedPermits + (nowMicros - nextFreeTicketMicros) / stableIntervalMicros);
nextFreeTicketMicros = nowMicros;
}
}
另外，对于的使用，存在两种策略，二者区别主要体现在使用时候需要等待的时间。这个逻辑由ime函数实现：
/**
* Translates a specified portion of our currently stored permits which we want to
* spend/acquire, into a throttling time. Conceptually, this evaluates the integral
* of the underlying function we use, for the range of
* [(storedPermits - permitsToTake), storedPermits].
*
* <p>This always holds: {@code 0 0.0) {
double permitsAboveHalfToTake = min(availablePermitsAboveHalf, permitsToTake);
micros = (long) (permitsAboveHalfToTake * (permitsToTime(availablePermitsAboveHalf)
+ permitsToTime(availablePermitsAboveHalf - permitsAboveHalfToTake)) / 2.0);
permitsToTake -= permitsAboveHalfToTake;
}
// measuring the integral on the left part of the function (the horizontal line)
micros += (stableIntervalMicros * permitsToTake);
return micros;
}
private double permitsToTime(double permits) {
return stableIntervalMicros + permits * slope;
}
}
等于热身()期间能产生的令牌数，比如QPS=4，为2秒，则=8。为的一半。
参考注释中的神图：
<p><pre>* ^ throttling
- |
- 3*stable + /
- interval | /.
- (cold) | / .
- | / .