上篇对阅读jaeger-core源码整理了一份思路，其中谈到jaeger定义了一个Sampler接口，jaeger为该接口写了几个实现，其中一个就是RateLimitingSampler。该采样类使用了限流策略中的“令牌桶算法”。下面通过参考网上的资料与结合自己的理解整理下限流的算法，以及jaeger中采用的限流算法。
限流算法
以下对算法的解释我们设定一个统一的情景：假设某应用设计为最大请求处理量为100/min，即每分钟处理100个请求，请为该应用设计一个请求控制类，使得应用处理的请求不超过100/min以避免发生系统故障。
计数器法
根据要求，我们很自然的想到将时间按照1分钟的间隔分段，每段的时长即为1分钟，我们只要控制每段的请求不超过100时正常处理，超过100时不予处理即可完成上述要求。如图：
我们再结合上图细化下上述描述：
首先有个初始时间作为第一个时间段的起点。
每次请求到达时，先判断当前时间减去初始时间是否小于1分钟，若小于一分钟，再判断计数器是否超过100，不超过即可将计数器加1，并处理请求，否则若超过100则不处理请求。
若判断当前时间减去初始时间大于1分钟，则说明该请求应该在第二个时间段内做判断，此时需要将初始时间重置为当前时间，开启第二个时间段，并将计数器重置为1，使得当前请求通过。
代码如下：
public class RateLimitCountDemo {
private long startTimeMillis = System.currentTimeMillis();//每个时间段的起始时间
private AtomicLong counter = new AtomicLong(0);//计数器 线程安全
private static final long REQ_PER_MIN = 100L;//每分钟请求数
public boolean isPaased(){
long currentTimeMillis = System.currentTimeMillis();//当前时间
//判断 当前时间 - 起始时间 是否小于 1分钟
if (currentTimeMillis - startTimeMillis < 1 * 60 * 1000){
//在时间段内
if (counter.get() >= REQ_PER_MIN) {
return false;//请求数已超过100/min 该请求不处理
}
counter.incrementAndGet();//计数器加1
return true;//该请求通过
}else {
//不在时间段内 将起始时间重置为当前时间
startTimeMillis = currentTimeMillis;
//将计数器 counter 重置为1 通过当前请求
counter.set(0);
return true;
}
}
}
计数器算法的缺陷：
上述算法貌似满足了我们一开始提到的情景，使得应用每分钟处理请求最大值为100条。但是在临界条件下会暴露出上述算法的问题，如下：
我们考虑上图这两个时间段。其中0:00--0:59属于第一个时间段，1:00--1:59属于第二个时间段，每个时间段允许的最大请求为100。
假设在第一个时间段里，只有0:59时刻瞬间有100个请求到达，根据上面的描述，这属于第一个时间段，可以通过。而1秒后1:00时刻又瞬间有100个请求到达，根据上面的算法，这次的100个请求属于第二个时间段，也是可以通过的。
但是我们从全局来看，这个应用设计每分钟最多处理100条请求，而现在从0:59到1:00这1秒内有了200条请求到达应用，且按照上面设计的算法，这200条请求都可以通过。这样就会造成该应用产生系统问题甚至崩溃。
我们现在知道上面的算法似乎在临界点处有漏洞。此处“临界”的定义并不局限于上诉所说的0:59 1:00这几秒内，而是指临界点往两端延伸所构成的任意一个长度为1分钟的时间段内请求数超过200，即可造成应用出现问题。如下：
所以上面的算法有可能会在临界处造成应用实际承受2倍于设计流量的压力。就如上面例子展示的设计流量为100/min，而实际上应用可能承受200/min请求的压力。
为什么会有这样的漏洞呢？因为在上面的算法中，我们人为的将自然界中平滑过渡的时间分为长度为1分钟的一个个时间段。下面会对上面的算法进行改进。
滑动窗口
我们将上面的一分钟时间段分为6个时间段，每个时间段10秒，且每个时间段拥有自己的计数器，当时间超过1分钟后不再往右移动1分钟的时间段，而是往右移动10秒的时间段，示图如下：
这样能一定程度上避免上面的问题，如上面提到的临界点的问题这里就能避免。当0:59突然有100个流量到达时，会落在第一行的灰色阴影的时间段内，此时6个时间段内的计数器之和为0，这100个流量可以通过。当时间进入1:00时，最左侧的时间段我们不再考虑，整体向右移动一个10秒的时间段，再次构成一个1分钟的时间段，此时1:00时突发的100个流量会落在第二行的红色阴影时间段内，此时6个时间段的计数器之和为100，根据规则，这100个流量不能通过。这样就避免了上面提到的问题。
当然这样做还会有漏洞，如下图：
上图中蓝色阴影代表80的流量，灰色阴影代表20的流量。假设在0:05时刻有80个流量到达，在灰色阴影内有20个流量，此时在第一个1分钟内没有问题，流量被限制为100/min。时间变为1:00后，如第二行所示，最左侧的10秒的时间段不再考虑，整体右移10秒的时间段，考虑新的1分钟时间段，假设在1:05时刻有80个流量到达，此时根据算法，这80个流量也可通过。
这时我们从全局考虑上图蓝色区域，该区域长度为1分钟，流量却为80+20+80=180/min。
可见滑动窗口也存在上面说的更广义的临界点问题。只是概率更低了。
但是很明显，如果我们将1分钟分的越细，上述临界点问题就越能得到缓解。形象点描述就是：将时间分的越细，越能代表时间的平滑过渡。（类似微分的思想）
从程序角度考虑，我们分的时间越细，就会造成时间段变多，而每个时间段需要维护自己时间段内的计数器，对内存占用有要求。所以也不能无限细分下去，要做一个平衡。
代码如下：
public class RateLimitRollingWindowDemo {
private long startTimeMillis = System.currentTimeMillis();//1分钟时间段的起始时间
private LinkedList<PerCell> list = new LinkedList();
private int divide = 6;//将1分钟分为几格
private static final long REQ_PER_MIN = 100L;//每分钟请求数
RateLimitRollingWindowDemo() {
long currentTimeMillis = System.currentTimeMillis();//当前时间
initList(currentTimeMillis);
}
void initList(long currentTimeMillis) {
//此for循环等同于下面注释的部分
for (int i = 0; i < divide; i++) {
list.addLast(new PerCell(currentTimeMillis + i * 10 * 1000));
}
/*if(list.size() == 0){
list.add(new PerCell(currentTimeMillis));
list.add(new PerCell(currentTimeMillis + 10 * 1000));
list.add(new PerCell(currentTimeMillis + 20 * 1000));
list.add(new PerCell(currentTimeMillis + 30 * 1000));
list.add(new PerCell(currentTimeMillis + 40 * 1000));
list.add(new PerCell(currentTimeMillis + 50 * 1000));
}*/
}
public boolean isPass() {
long currentTimeMillis = System.currentTimeMillis();//当前时间
if (currentTimeMillis < list.getFirst().startTimeMillis) {
//正常情况下不存在这种情况
return false;
} else if (currentTimeMillis - list.getFirst().startTimeMillis >= 0
&& currentTimeMillis - list.getLast().startTimeMillis <= 0) {
//时间落在在6个小格子内
//先判断所有小格子的计数器之和是否超过100
long sum = list.stream()
.mapToLong(perCell -> perCell.counter.get())
.summaryStatistics()
.getSum();
if (sum > REQ_PER_MIN) {
return false;//6个小格子所代表的1分钟内已经处理了100个请求，该请求不处理
}
//否则说明该请求可以通过
//首先找到该请求对应的小格子，然后计数器加1即可
int index = (int) (currentTimeMillis - list.getFirst().startTimeMillis) / (10 * 1000);
list.get(index).counter.incrementAndGet();
return true;
} else if (currentTimeMillis - list.getLast().startTimeMillis > 0
&& currentTimeMillis - list.getLast().startTimeMillis <= 60 * 1000) {
//当前时间不在6个小格子内 并且当前时间与最后一个小格子的时间差小于1分钟 需要小格子右移，且需要小格子中的计数器的数据
//判断需要右移几个小格子 右移index+1个格子 流量在时间尺度上均匀的话，每次右移1个格子，若不均匀则会右移多个格子
int index = (int) (currentTimeMillis - list.getLast().startTimeMillis) / (10 * 1000);
for (int i = 0; i <= index; i++) {
PerCell first = list.removeFirst();
list.addLast(new PerCell(first.startTimeMillis + 60 * 1000));
}
//小格子右移后，现在时间处于6个小格子内了
//先判断所有小格子的计数器之和是否超过100
long sum = list.stream()
.mapToLong(perCell -> perCell.counter.get())
.summaryStatistics()
.getSum();
if (sum > REQ_PER_MIN) {
return false;//6个小格子所代表的1分钟内已经处理了100个请求，该请求不处理
}
//否则该请求可以通过
//该请求必定落在最后一个格子
list.getLast().counter.incrementAndGet();
return true;
} else {
//最后剩下的情况就只能是 currentTimeMillis - list.getLast().startTimeMillis > 60 * 1000
//当前时间与最后一个小格子的时间差大于1分钟 我们就不需要小格子中的历史数据了。
//当流量不均匀时，如相隔很长时间才来一次流量，就会出现这样的情况
initList(currentTimeMillis);
list.getFirst().counter.incrementAndGet();
return true;//该请求通过
}
}
//PerCell 代表1分钟时间段内细分成的每个小格，有自己的起始时间与计数器
class PerCell {
long startTimeMillis = System.currentTimeMillis();//每个时间段的起始时间
AtomicLong counter = new AtomicLong(0);//计数器 线程安全
PerCell(long time) {
this.startTimeMillis = time;
}
}
}
漏桶算法
漏桶算法示意图如下：
漏桶算法基于生活中的常识。假设一个水桶的容量为C（capacity），水桶底部有一个小孔，能够使得水桶中的水以速率R（rate）均匀漏出。而往水桶中加水的行为我们无法预估，不知道什么时候加水，什么时候不加水，是均匀加水还是一下子加很多水，但是有一点，当加水超过水桶的容量C时，水会溢出。
这样就能保证水桶中有水时，出水总是均匀的。
上述代码描述如下：
public class RateLimitLeakyBucketDemo {
private long timeStamp = System.currentTimeMillis();
private long capacity;//水桶容量
private long rate;//出水速率
private long water;//当前水桶中的水
public boolean isPass(){
long currentTime = System.currentTimeMillis();
//计算自上一次加水后到现在桶内还剩多少水
water = Math.max(0,water-(currentTime - timeStamp)*rate);
timeStamp = currentTime;
if ((water + 1) < capacity){
//说明加水不会溢出，可以加水
water = water + 1;
return true;
}else {
return false;
}
}
}
我们切换到实际情形中，上述描述可以修改为：
我们有个应用，其单位时间内请求的最大容量为100，请求的通过速率为100/min。其代码描述为：
public class RateLimitLeakyBucketDemo {
private long timeStamp = System.currentTimeMillis();
private long requestCapacity = 100L;//单位时间内应用可处理的请求数
private long rate = requestCapacity/(1 * 60 * 1000);//请求通过的速率
private long sumRequest;//当前累计处理的请求 不含已经处理完的请求
public boolean isPass(){
long currentTime = System.currentTimeMillis();
//计算自上一次接收请求后到现在应用中还有多少请求
sumRequest = Math.max(0,sumRequest-(currentTime - timeStamp)*rate);
timeStamp = currentTime;
if ((sumRequest + 1) < requestCapacity){
//说明处理该请求不会超过应用的承受力，可以处理该请求
sumRequest = sumRequest + 1;
return true;
}else {
return false;
}
}
}
这里需要说明的是，我们不要被描述漏桶算法的示意图所迷惑，认为请求总是均匀的通过算法的校验。漏桶算法在真实世界中确实如示意图所示会按照速率R均匀出水。但是在我们上面的程序实现中，我们并不会将请求存储起来均匀的通过校验，而是只要判断还可以处理该请求就立刻返回true，使程序处理该请求。桶中的水代表的不是真正的请求，真实世界中的均匀出水也并非代表程序中放行请求。
正确的对应关系应该是这样：我们在程序中设置了一个变量sumRequest，这个变量不存储真正的请求，而是存储放行的请求的个数，因此桶中的水代表的是程序中放行的请求的个数，真实世界中的均匀出水可以看做程序对请求的处理进度，因此程序中sumRequest会有小数部分存在。
刚接触漏桶算法时，能够很好的理解漏桶算法在真实世界中的含义，而理解程序根据漏桶算法限制请求时就会有点绕不过弯，原因就在于此。
漏桶算法时如何避免之前讨论的问题的呢？
前面的算法面临临界点的问题是因为我们将平滑的时间人为的分段，而现在漏桶算法引入了请求处理的速率R，根据前后两次请求到达的间隔timeInterval乘以速率R计算程序对之前请求的处理进度，这样我们使用的是时间差，没有人为的将时间分段。且sumRequest显示的是当前程序正在处理的请求数，对应于前面所述算法中的counter计数器，不同于计数器从属与某个时间段，这个sumRequest是不属于任何时间段的，只是与应用对请求的处理进度有关，因此是从应用出发，杜绝任何一个时刻应用处理的请求数超过设计的100/min。
额外的思考，可能想的不对，可以跳过不看。上面的代码实现中我们是在什么时间尺度上判断应用对上次请求的处理进度的？是毫秒millis。如果有人能够在纳秒级别上瞬时发送超过100个请求给应用，且应用能同步响应的话，那么上述代码所实现的漏桶算法可能会有问题，如：
- 假设在纳秒级别上发送了100个请求，且应用能及时的响应
- 这100个请求的上次请求时间为timeStamp
- sumRequst为99.8
- (currentTime - timeStamp)*rate = 1.2
那么这100条请求的第一条请求被算法处理时，sumRequest = Math.max(0,sumRequest-(currentTime - timeStamp)*rate);得到sumRequest为99.8-1.2=98.6，根据算法98.6小于100，该请求通过，sumRequest加1变为99.6。
此时根据假设，请求能及时响应纳秒级别的并发请求，那么sumRequest = Math.max(0,sumRequest-(currentTime - timeStamp)*rate);这条语句中(currentTime - timeStamp)*rate的结果与第一个请求的计算结果同为1.2（纳秒级别反应在毫秒上导致两条请求的时间在毫秒上相同）。得到sumRequest为99.6-1.2 = 98.4，根据算法98.4小于100，该请求通过，sumRequest加1变为99.4。
一直这么算下去，可以发现，这100个请求都能通过算法的验证，放行给应用处理，但是一开始的sumRequest为99.8，减去第一个应用的1.2后为98.6，就说明应用最多只能处理一个请求，但是我们一下子塞给它100个请求，这样就会造成应用出现问题。
令牌桶算法
令牌桶算法示意图如下：
该算法的描述为：我们以一定的速率R往桶中放入令牌，桶的容量为C，当桶中令牌数达到C后，不再放入令牌。另一方面当请求到达时，从桶中取令牌，并将桶中的令牌数减1，该请求通过；若桶中无令牌，则该请求不处理。
