一文搞懂高频面试题之限流算法，从算法原理到实现，再到对比分析
source link: http://www.cnblogs.com/exzlc/p/13639452.html
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
限流是指在系统面临高并发、大流量请求的情况下，限制新的流量对系统的访问，从而保证系统服务的安全性。常用的限流算法有计数器固定窗口算法、滑动窗口算法、漏斗算法和令牌桶算法，下面将对这几种算法进行分别介绍，并给出具体的实现。本文目录如下，略长，读者可以全文阅读，同样也可以只看感兴趣的部分。
目录
计数器固定窗口算法
原理
计数器固定窗口算法是最基础也是最简单的一种限流算法。原理就是对一段固定时间窗口内的请求进行计数，如果请求数超过了阈值，则舍弃该请求；如果没有达到设定的阈值，则接受该请求，且计数加1。当时间窗口结束时，重置计数器为0。
代码实现及测试
实现起来也比较简单，如下：
package project.limiter; import java.util.concurrent.atomic.AtomicInteger; /** * Project: AllForJava * Title: * Description: * Date: 2020-09-07 15:56 * Copyright: Copyright (c) 2020 * * @公众号: 超悦编程 * @微信号：exzlco * @author: 超悦人生 * @email: [email protected] * @version 1.0 **/ public class CounterLimiter { private int windowSize; //窗口大小，毫秒为单位 private int limit;//窗口内限流大小 private AtomicInteger count;//当前窗口的计数器 private CounterLimiter(){} public CounterLimiter(int windowSize,int limit){ this.limit = limit; this.windowSize = windowSize; count = new AtomicInteger(0); //开启一个线程，达到窗口结束时清空count new Thread(new Runnable() { @Override public void run() { while(true){ count.set(0); try { Thread.sleep(windowSize); } catch (InterruptedException e) { e.printStackTrace(); } } } }).start(); } //请求到达后先调用本方法，若返回true，则请求通过，否则限流 public boolean tryAcquire(){ int newCount = count.addAndGet(1); if(newCount > limit){ return false; }else{ return true; } } //测试 public static void main(String[] args) throws InterruptedException { //每秒20个请求 CounterLimiter counterLimiter = new CounterLimiter(1000,20); int count = 0; //模拟50次请求，看多少能通过 for(int i = 0;i < 50;i ++){ if(counterLimiter.tryAcquire()){ count ++; } } System.out.println("第一拨50次请求中通过：" + count + ",限流：" + (50 - count)); //过一秒再请求 Thread.sleep(1000); //模拟50次请求，看多少能通过 count = 0; for(int i = 0;i < 50;i ++){ if(counterLimiter.tryAcquire()){ count ++; } } System.out.println("第二拨50次请求中通过：" + count + ",限流：" + (50 - count)); } }
测试结果如下：
可以看到50个请求只有20个通过了，30个被限流，达到了预期的限流效果。
特点分析
优点：实现简单，容易理解。
缺点：流量曲线可能不够平滑，有“突刺现象”，如下图所示。这样会有两个问题：
-
一段时间内（不超过时间窗口）系统服务不可用。比如窗口大小为1s，限流大小为100，然后恰好在某个窗口的第1ms来了100个请求，然后第2ms-999ms的请求就都会被拒绝，这段时间用户会感觉系统服务不可用。
-
窗口切换时可能会产生两倍于阈值流量的请求。比如窗口大小为1s，限流大小为100，然后恰好在某个窗口的第999ms来了100个请求，窗口前期没有请求，所以这100个请求都会通过。再恰好，下一个窗口的第1ms有来了100个请求，也全部通过了，那也就是在2ms之内通过了200个请求，而我们设定的阈值是100，通过的请求达到了阈值的两倍。
计数器滑动窗口算法
原理
计数器滑动窗口算法是计数器固定窗口算法的改进，解决了固定窗口切换时可能会产生两倍于阈值流量请求的缺点。
滑动窗口算法在固定窗口的基础上，将一个计时窗口分成了若干个小窗口，然后每个小窗口维护一个独立的计数器。当请求的时间大于当前窗口的最大时间时，则将计时窗口向前平移一个小窗口。平移时，将第一个小窗口的数据丢弃，然后将第二个小窗口设置为第一个小窗口，同时在最后面新增一个小窗口，将新的请求放在新增的小窗口中。同时要保证整个窗口中所有小窗口的请求数目之后不能超过设定的阈值。
从图中不难看出，滑动窗口算法就是固定窗口的升级版。将计时窗口划分成一个小窗口，滑动窗口算法就退化成了固定窗口算法。而滑动窗口算法其实就是对请求数进行了更细粒度的限流，窗口划分的越多，则限流越精准。
代码实现及测试
package project.limiter; /** * Project: AllForJava * Title: * Description: * Date: 2020-09-07 18:38 * Copyright: Copyright (c) 2020 * * @公众号: 超悦编程 * @微信号：exzlco * @author: 超悦人生 * @email: [email protected] * @version 1.0 **/ public class CounterSildeWindowLimiter { private int windowSize; //窗口大小，毫秒为单位 private int limit;//窗口内限流大小 private int splitNum;//切分小窗口的数目大小 private int[] counters;//每个小窗口的计数数组 private int index;//当前小窗口计数器的索引 private long startTime;//窗口开始时间 private CounterSildeWindowLimiter(){} public CounterSildeWindowLimiter(int windowSize, int limit, int splitNum){ this.limit = limit; this.windowSize = windowSize; this.splitNum = splitNum; counters = new int[splitNum]; index = 0; startTime = System.currentTimeMillis(); } //请求到达后先调用本方法，若返回true，则请求通过，否则限流 public synchronized boolean tryAcquire(){ long curTime = System.currentTimeMillis(); long windowsNum = Math.max(curTime - windowSize - startTime,0) / (windowSize / splitNum);//计算滑动小窗口的数量 slideWindow(windowsNum);//滑动窗口 int count = 0; for(int i = 0;i < splitNum;i ++){ count += counters[i]; } if(count >= limit){ return false; }else{ counters[index] ++; return true; } } private synchronized void slideWindow(long windowsNum){ if(windowsNum == 0) return; long slideNum = Math.min(windowsNum,splitNum); for(int i = 0;i < slideNum;i ++){ index = (index + 1) % splitNum; counters[index] = 0; } startTime = startTime + windowsNum * (windowSize / splitNum);//更新滑动窗口时间 } //测试 public static void main(String[] args) throws InterruptedException { //每秒20个请求 int limit = 20; CounterSildeWindowLimiter counterSildeWindowLimiter = new CounterSildeWindowLimiter(1000,limit,10); int count = 0; Thread.sleep(3000); //计数器滑动窗口算法模拟100组间隔30ms的50次请求 System.out.println("计数器滑动窗口算法测试开始"); System.out.println("开始模拟100组间隔150ms的50次请求"); int faliCount = 0; for(int j = 0;j < 100;j ++){ count = 0; for(int i = 0;i < 50;i ++){ if(counterSildeWindowLimiter.tryAcquire()){ count ++; } } Thread.sleep(150); //模拟50次请求，看多少能通过 for(int i = 0;i < 50;i ++){ if(counterSildeWindowLimiter.tryAcquire()){ count ++; } } if(count > limit){ System.out.println("时间窗口内放过的请求超过阈值，放过的请求数" + count + ",限流：" + limit); faliCount ++; } Thread.sleep((int)(Math.random() * 100)); } System.out.println("计数器滑动窗口算法测试结束，100组间隔150ms的50次请求模拟完成，限流失败组数：" + faliCount); System.out.println("==========================================================================================="); //计数器固定窗口算法模拟100组间隔30ms的50次请求 System.out.println("计数器固定窗口算法测试开始"); //模拟100组间隔30ms的50次请求 CounterLimiter counterLimiter = new CounterLimiter(1000,limit); System.out.println("开始模拟100组间隔150ms的50次请求"); faliCount = 0; for(int j = 0;j < 100;j ++){ count = 0; for(int i = 0;i < 50;i ++){ if(counterLimiter.tryAcquire()){ count ++; } } Thread.sleep(150); //模拟50次请求，看多少能通过 for(int i = 0;i < 50;i ++){ if(counterLimiter.tryAcquire()){ count ++; } } if(count > limit){ System.out.println("时间窗口内放过的请求超过阈值，放过的请求数" + count + ",限流：" + limit); faliCount ++; } Thread.sleep((int)(Math.random() * 100)); } System.out.println("计数器滑动窗口算法测试结束，100组间隔150ms的50次请求模拟完成，限流失败组数：" + faliCount); } }
测试时，取滑动窗口大小为1000/10=100ms，然后模拟100组间隔150ms的50次请求，计数器滑动窗口算法与计数器固定窗口算法进行对别，可以看到如下结果：
固定窗口算法在窗口切换时产生了两倍于阈值流量请求的问题，而滑动窗口算法避免了这个问题。
特点分析
- 避免了计数器固定窗口算法固定窗口切换时可能会产生两倍于阈值流量请求的问题；
- 和漏斗算法相比，新来的请求也能够被处理到，避免了漏斗算法的饥饿问题。
漏斗算法
原理
漏斗算法的原理也很容易理解。请求来了之后会首先进到漏斗里，然后漏斗以恒定的速率将请求流出进行处理，从而起到平滑流量的作用。当请求的流量过大时，漏斗达到最大容量时会溢出，此时请求被丢弃。从系统的角度来看，我们不知道什么时候会有请求来，也不知道请求会以多大的速率来，这就给系统的安全性埋下了隐患。但是如果加了一层漏斗算法限流之后，就能够保证请求以恒定的速率流出。在系统看来，请求永远是以平滑的传输速率过来，从而起到了保护系统的作用。
代码实现及测试
package project.limiter; import java.util.Date; import java.util.LinkedList; /** * Project: AllForJava * Title: * Description: * Date: 2020-09-08 16:45 * Copyright: Copyright (c) 2020 * * @公众号: 超悦编程 * @微信号：exzlco * @author: 超悦人生 * @email: [email protected] * @version 1.0 **/ public class LeakyBucketLimiter { private int capaticy;//漏斗容量 private int rate;//漏斗速率 private int left;//剩余容量 private LinkedList<Request> requestList; private LeakyBucketLimiter() {} public LeakyBucketLimiter(int capaticy, int rate) { this.capaticy = capaticy; this.rate = rate; this.left = capaticy; requestList = new LinkedList<>(); //开启一个定时线程，以固定的速率将漏斗中的请求流出，进行处理 new Thread(new Runnable() { @Override public void run() { while(true){ if(!requestList.isEmpty()){ Request request = requestList.removeFirst(); handleRequest(request); } try { Thread.sleep(1000 / rate); //睡眠 } catch (InterruptedException e) { e.printStackTrace(); } } } }).start(); } /** * 处理请求 * @param request */ private void handleRequest(Request request){ request.setHandleTime(new Date()); System.out.println(request.getCode() + "号请求被处理，请求发起时间：" + request.getLaunchTime() + ",请求处理时间：" + request.getHandleTime() + ",处理耗时：" + (request.getHandleTime().getTime() - request.getLaunchTime().getTime()) + "ms"); } public synchronized boolean tryAcquire(Request request){ if(left <= 0){ return false; }else{ left --; requestList.addLast(request); return true; } } /** * 请求类，属性包含编号字符串、请求达到时间和请求处理时间 */ static class Request{ private int code; private Date launchTime; private Date handleTime; private Request() { } public Request(int code,Date launchTime) { this.launchTime = launchTime; this.code = code; } public int getCode() { return code; } public void setCode(int code) { this.code = code; } public Date getLaunchTime() { return launchTime; } public void setLaunchTime(Date launchTime) { this.launchTime = launchTime; } public Date getHandleTime() { return handleTime; } public void setHandleTime(Date handleTime) { this.handleTime = handleTime; } } public static void main(String[] args) { LeakyBucketLimiter leakyBucketLimiter = new LeakyBucketLimiter(5,2); for(int i = 1;i <= 10;i ++){ Request request = new Request(i,new Date()); if(leakyBucketLimiter.tryAcquire(request)){ System.out.println(i + "号请求被接受"); }else{ System.out.println(i + "号请求被拒绝"); } } } }
测试时，取漏斗限流算法的容量是5，漏斗速率为2个/秒，然后模拟了连续的10个请求，编号从1-10，结果如下：
可以看到1-5号请求被接受，而6-10号请求被拒绝，说明此时漏斗已经溢出了，符合我们的预期。
我们再关注下被接受的这5个请求的处理情况，可以看到这5个请求虽然被接受了，但是处理是一个一个被处理的（不一定是顺序的，取决于具体实现），大约每500ms处理一个。这就体现了漏斗算法的特点了，即虽然请求流量是瞬时产生的，但是请求以固定速率流出被处理。因为我们设定的漏斗速率为2个/秒，所以每500ms漏斗会漏出一个请求然后进行处理。
特点分析
- 漏桶的漏出速率是固定的，可以起到整流的作用 。即虽然请求的流量可能具有随机性,忽大忽小，但是经过漏斗算法之后，变成了有固定速率的稳定流量，从而对下游的系统起到保护作用。
- 不能解决流量突发的问题 。还是拿刚刚测试的例子，我们设定的漏斗速率是2个/秒，然后突然来了10个请求，受限于漏斗的容量，只有5个请求被接受，另外5个被拒绝。你可能会说，漏斗速率是2个/秒，然后瞬间接受了5个请求，这不就解决了流量突发的问题吗？不，这5个请求只是被接受了，但是没有马上被处理，处理的速度仍然是我们设定的2个/秒，所以没有解决流量突发的问题。而接下来我们要谈的令牌桶算法能够在一定程度上解决流量突发的问题，读者可以对比一下。
令牌桶算法
原理
令牌桶算法是对漏斗算法的一种改进，除了能够起到限流的作用外，还允许一定程度的流量突发。在令牌桶算法中，存在一个令牌桶，算法中存在一种机制以恒定的速率向令牌桶中放入令牌。令牌桶也有一定的容量，如果满了令牌就无法放进去了。当请求来时，会首先到令牌桶中去拿令牌，如果拿到了令牌，则该请求会被处理，并消耗掉拿到的令牌；如果令牌桶为空，则该请求会被丢弃。
代码实现及测试
package project.limiter; import java.util.Date; /** * Project: AllForJava * Title: * Description: * Date: 2020-09-08 19:22 * Copyright: Copyright (c) 2020 * * @公众号: 超悦编程 * @微信号：exzlco * @author: 超悦人生 * @email: [email protected] * @version 1.0 **/ public class TokenBucketLimiter { private int capaticy;//令牌桶容量 private int rate;//令牌产生速率 private int tokenAmount;//令牌数量 public TokenBucketLimiter(int capaticy, int rate) { this.capaticy = capaticy; this.rate = rate; tokenAmount = capaticy; new Thread(new Runnable() { @Override public void run() { //以恒定速率放令牌 while (true){ synchronized (this){ tokenAmount ++; if(tokenAmount > capaticy){ tokenAmount = capaticy; } } try { Thread.sleep(1000 / rate); } catch (InterruptedException e) { e.printStackTrace(); } } } }).start(); } public synchronized boolean tryAcquire(Request request){ if(tokenAmount > 0){ tokenAmount --; handleRequest(request); return true; }else{ return false; } } /** * 处理请求 * @param request */ private void handleRequest(Request request){ request.setHandleTime(new Date()); System.out.println(request.getCode() + "号请求被处理，请求发起时间：" + request.getLaunchTime() + ",请求处理时间：" + request.getHandleTime() + ",处理耗时：" + (request.getHandleTime().getTime() - request.getLaunchTime().getTime()) + "ms"); } /** * 请求类，属性只包含一个名字字符串 */ static class Request{ private int code; private Date launchTime; private Date handleTime; private Request() { } public Request(int code,Date launchTime) { this.launchTime = launchTime; this.code = code; } public int getCode() { return code; } public void setCode(int code) { this.code = code; } public Date getLaunchTime() { return launchTime; } public void setLaunchTime(Date launchTime) { this.launchTime = launchTime; } public Date getHandleTime() { return handleTime; } public void setHandleTime(Date handleTime) { this.handleTime = handleTime; } } public static void main(String[] args) throws InterruptedException { TokenBucketLimiter tokenBucketLimiter = new TokenBucketLimiter(5,2); for(int i = 1;i <= 10;i ++){ Request request = new Request(i,new Date()); if(tokenBucketLimiter.tryAcquire(request)){ System.out.println(i + "号请求被接受"); }else{ System.out.println(i + "号请求被拒绝"); } } } }
测试时，为了与漏斗限流算法进行对别，同样取令牌桶算法的容量是5，产生令牌的速度为2个/秒，然后模拟了连续的10个请求，编号从1-10，结果如下：
可以看到，对于10个请求，令牌桶算法和漏斗算法一样，都是接受了5个请求，拒绝了5个请求。与漏斗算法不同的是，令牌桶算法马上处理了这5个请求，处理速度可以认为是5个/秒，超过了我们设定的2个/秒的速率，即 允许一定程度的流量突发 。这一点也是和漏斗算法的主要区别，可以认真体会一下。
特点分析
令牌桶算法是对漏桶算法的一种改进，除了能够在限制调用的平均速率的同时还允许一定程度的流量突发。
小结
我们对上述四种限流算法进行一下简单的总结。
计数器固定窗口算法实现简单，容易理解。和漏斗算法相比，新来的请求也能够被马上处理到。但是流量曲线可能不够平滑，有“突刺现象”，在窗口切换时可能会产生两倍于阈值流量的请求。而 计数器滑动窗口算法 作为计数器固定窗口算法的一种改进，有效解决了窗口切换时可能会产生两倍于阈值流量请求的问题。
漏斗算法能够对流量起到整流的作用，让随机不稳定的流量以固定的速率流出，但是不能解决 流量突发 的问题。 令牌桶算法 作为漏斗算法的一种改进，除了能够起到平滑流量的作用，还允许一定程度的流量突发。
以上四种限流算法都有自身的特点，具体使用时还是要结合自身的场景进行选取， 没有最好的算法，只有最合适的算法 。比如令牌桶算法一般用于保护自身的系统，对调用者进行限流，保护自身的系统不被突发的流量打垮。如果自身的系统实际的处理能力强于配置的流量限制时，可以允许一定程度的流量突发，使得实际的处理速率高于配置的速率，充分利用系统资源。而漏斗算法一般用于保护第三方的系统，比如自身的系统需要调用第三方的接口，为了保护第三方的系统不被自身的调用打垮，便可以通过漏斗算法进行限流，保证自身的流量平稳的打到第三方的接口上。
算法是死的，而算法中的 思想精髓 才是值得我们学习的。实际的场景中完全可以灵活运用，还是那句话， 没有最好的算法，只有最合适的算法 。
觉得文章有用的话， 点赞 + 关注 呗，好让更多的人看到这篇文章，也激励博主写出更多的好文章。
更多关于 校招面试、算法、数据结构和计算机基础知识 的内容，欢迎扫码关注我的原创公众号「 超悦编程 」。
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK