avatar
概述
在分布式的系统中，限流是指限制请求的速率，从而保护系统不被过载的流量打垮。
实列
avatar
生活中，限流是你再熟悉不过的东西了，当流量超过对象能承载的阀值时，为了保护对象，通常会采用限流措施控制流速。
avatar
例如，为了防止长江水域发生洪灾，我国修建了三峡大坝，它也不负众望，一次次的经受住了洪峰考验。比如，2012年7月24日，三峡大坝经受住了建库以来最大的洪峰考验，当时入库的峰值流量达7.12万立方米/秒，出库流量为4万多立方米/秒，为下游削峰3万立方米／秒。7万立方米是什么概念？当天的流量比平均流量1万5千立方米/秒足足高出了5倍之多，而且当地百年一遇的洪水流量也就8.37万立方米/秒。如果没有大坝对洪流进行消峰，后果可想而知。
再如，地铁站在早晚高峰会对人流的流速进行限制，高速公路在节假日车流高峰会对车流的流速进行限制等等不甚枚举。
同样，我们的系统无论它是单体架构还是分布式的架构，为了保护它不被流量打垮，也需要为它修建"大坝"即限流。为什么？假设我们有一个系统A，它每秒能处理的请求数（QPS）是200；如果此时请求的速率是400每秒，并持续1个小时，那会发生什么呢？假设所有的请求都会进入队列，那么理论上队列中每秒会多出200个处理不掉的请求，1个小时便会多出12000个；但实际上，会比这个数多，因为多出的12000个请求不仅处理不掉而且还会占用系统的CPU、内存、网络等资源，进而导致请求处理速度下降，可能从原来的200个每秒下降到150个每秒。可见，当请求速率超过系统的处理阀值后，请求速率越大系统处理请求的速率就越慢，请求速率大一定值后处理请求的速率将变为0。
总之，无论是生活中还是软件中，限流的目的都是为了保护对象。
问题
综上，限流面临的问题便是：如何将请求限制在阀值之下。
方案
限制请求的策略通常有限速、限量两种，或者是两种策略的组合策略。限速指的是限制单位时间内允许的请求的数量，如将请求限制在每秒5个，或3秒15个，典型的例子便是大坝限制水流流出的速度；限量指的是限制请求数量，不对请求的速率进行限制，典型的例子如：餐厅、车库，不限制对象进入的速率，但限制数量。
限量的实现比较简单，我们就不重点介绍，我们简单介绍一下限速的实现思路。假如，系统每秒处理请求的阀值是5，那么我们可以用计算器来统计该时段内的请求数量，每当有请求进入的时候计数器加一，当计数器中请求的数量超过了允许的阀值5时，那么就拒绝该请求或者缓存当系统空闲时在处理，否则允许该请求被执行。这便是限速的基本思路，下面是几种常见的限流算法，它们都能限流但效率有所差异。
Fixed Window 固定窗口
avatar
在固定窗口算法中，以一个固定的时间长度为单位即窗口，统计进入该窗口的请求数量——每进入一个新的请求，请求数量便加一；当请求数量大于预设的阀值时，请求将不被允许执行，反之，当请求数量小于预设阀值时，请求会被允许执行；上一个窗口结束时，便会开启下一个窗口，相邻的两个窗口不相交，上一个窗口的结束时间是下一个窗口的开始时间。
伪代码如下：
public class FixedWindow {
//窗口大小
protected int window;
//请求数量阀值
protected int threshold;
//当前窗口请求数量
protected int count;
//当前窗口开始时间
protected Long windowStartTime;
public FixedWindow(){
//......
}
public boolean tryAcquire(){
long currentTime = System.currentTimeMillis(); //当前时间
if (currentTime - windowStartTime > window) { //检查是否在时间窗口内
count = 0; // 请求数清零
windowStartTime = currentTime; //开启新窗口
}
if (count < threshold) { // 小于阀值
count++; //计数器加1
return true;
}
return false;
}
}
avatar
该算法的优势是简单、易懂、实现复杂度低；劣势是存在临界问题——两个窗口边界中的请求数量在一个单位的窗口时间内有超过阀值的可能。比如说，我们有两个窗口A、B，窗口的时间长度为1分钟，阀值为5，A窗口占据11：00：00-11：00：59这个时间段，B窗口占据11：01：00-11：01：59这个时间段；A窗口在前40秒内都没有收到任何请求，但后20秒内接受了5个请求；B窗口在前20秒接受了5个请求，但在后40秒没有接到任何请求；那么，可以看出A,B窗口的请求数量都没有超过阀值，但位于两边界的那一分钟时段，其总数10超过了阀值5。
Sliding Window 滑动窗口
在滑动窗口算法中，同样是通过一个具有固定时长的窗口，统计进入该窗口的请求数量；但是，不同的是它将这个窗口划分成n个同等大小的小窗口，将限流阀值也均摊到小窗口上，每个小窗口占据的时间是总时间t和小窗口数量n的比值，即：t/n；当请求落到某个小窗口上时，如果该小窗口的请求数量大于小窗口阀值时，请求将不被允许，反之小于时就允许；当请求的时间不在窗口内时，窗口会向前滑动，以满足当前时间可以落在小窗口上。
下面是简单的实现：
public class SlidingWindow {
//窗口时长
protected int windowLength;
//请求数量阀值
protected int threshold;
//小窗口数量
protected int slots;
//小窗口阀值
protected int smallWindowThreshold;
//小窗口请求数量列表
protected List<Integer> count;
//上一次滑动时间
protected Long windowStartTime;
public SlidingWindow(int slots, int threshold, int windowLength){
this.slots = slots;
this.threshold = threshold;
this.windowLength = windowLength;
smallWindowThreshold=threshold/slots;
count = new LinkedList<>();
for (int i = 0; i < slots; i++) {
count.add(0,0);
}
windowStartTime=System.currentTimeMillis();
}
public static void main(String[] args) {
SlidingWindow window = new SlidingWindow(3,15,3000);
for (int i = 0; i < 5; i++) {
try {
Thread.sleep(2000);
} catch (InterruptedException e) {
e.printStackTrace();
}
for (int j = 0; j < 30; j++) {
window.tryAcquire();
}
}
}
protected int getSlotIndex(long currentTime){
int index = Long.valueOf(currentTime - windowStartTime).intValue() % slots;
return index;
}
private void trySlippingWindow(long currentTime) {
//当前时间不再窗口内
if(windowStartTime+windowLength<currentTime){
//第一步：计算滑动的步数
long duration = currentTime-(windowStartTime+windowLength);
int smallWindowTime = windowLength/slots;
int steps = (int)Math.ceil(new BigDecimal(duration).divide(new BigDecimal(smallWindowTime)).doubleValue());
if(steps>=slots){
System.out.println("窗口距离当前时间较远，滑动到当前时间");
//重置小窗口请求数
count.forEach(item->item=0);
windowStartTime=currentTime;
}else{
System.out.println("滑动步数："+steps);
for (int i = 0; i < steps; i++) {
//第一步：移除最早的小窗口
count.remove(slots-1);
//第二步：添加新窗口
count.add(0,0);
}
windowStartTime+=windowLength/slots*steps;
}
}
}
protected boolean tryAcquire(){
long currentTime = System.currentTimeMillis(); //当前时间
trySlippingWindow(currentTime);
int index = getSlotIndex(currentTime);
if(count.get(index)>=smallWindowThreshold){
System.out.println("当前第"+index+"窗口，请求被拒绝");
return false;
}else{
count.set(index,count.get(index)+1);
System.out.println("当前第"+index+"窗口请求被允许，请求数量："+count.get(index));
return true;
}
}
}
该算法解决了边界的问题，能将流量准确的限制在规定的阀值之下；但也存在不足之处，我们的目标除了限流外，其实还要最大化处理请求的数量。例如，当系统每秒的处理能力是5个请求，请求会持续3秒钟，每秒的请求数量分别为：4、8、4时；如果，窗口的时间长度为3秒，阀值是15，小窗口个数为3；那么，3秒后的结果便是：13个请求被允许，3个请求被拒绝。
Leaky Bucket 漏桶算法
avatar
在漏桶算法中，没有窗口的概念，它只控制请求流出的速率，不控制请求进入的速率但超过容量的请求会被拒绝。它类似于一个漏斗，请求以不定的速度灌入漏斗中，但以固定的速率流出，这样即能将请求的处理速率控制在阀值之下，又能解决固定时间窗口和滑动时间窗口不能延迟处理请求的问题。在上面例子的条件下：系统每秒的处理能力是5个请求......，如果漏斗的容量是15，请求流出的速率是每秒5个，那么3秒后的结果是：14个请求被允许，2个请求被拒绝，比滑动窗口算法要多处理一个。但漏桶算法和固定窗口以及滑动窗口一样因为其控制的是流出的速率，所以在面对突发流量时处理请求的效率不高。比如，某一时刻突然来了15个请求，漏斗算法只能按5个每秒的速度流出请求，即使此刻系统每秒能处理7个。
Token Bucket 令牌桶算法
avatar
在漏桶算法中，令牌会以固定的速率放入桶中，桶有固定的容量，令牌的数量不能超过该容量。每当有请求进入系统时，每个请求都需要从桶中取出一个令牌，拿不到令牌的请求会被拒绝，每秒取出令牌的数量是不限的只要有令牌都可以取走。还是上面的条件下，如果桶的容量是15，桶初始化后便有15个令牌，此后每隔3秒向桶中放入15个令牌；那么3秒后的结果便是：14个请求被允许，2个请求被拒绝。虽然在这个同样的例子中，令牌桶不比漏桶处理的请求数多，但是如果某一时刻突然来了15个请求，令牌桶里面刚好有15个令牌，那么它不会限制令牌被取走的速率，只要系统能处理一秒钟全拿着也是可以的。
总结
限流的两个关键点，一个是设置阀值，另一个是选择合适的算法，通常阀值的设置会比算法来得重要些。阀值的好坏，阀值设置得比系统实际负载能力低，那么就不能最大限度的处理更多的请求，存在资源浪费的现象；反之，过高会使算法发挥不了限流的作用。设置阀值最理想的方式是：根据服务实时的负载情况来动态调整。
网友评论