乐趣区

关于后端:一文搞懂高频面试题之限流算法从算法原理到实现再到对比分析

jiezi

限流是指在零碎面临高并发、大流量申请的状况下，限度新的流量对系统的拜访，从而保证系统服务的安全性。罕用的限流算法有计数器固定窗口算法、滑动窗口算法、漏斗算法和令牌桶算法，上面将对这几种算法进行别离介绍，并给出具体的实现。本文目录如下，略长，读者能够全文浏览，同样也能够只看感兴趣的局部。

计数器固定窗口算法原理代码实现及测试特点剖析计数器滑动窗口算法原理代码实现及测试特点剖析漏斗算法原理代码实现及测试特点剖析令牌桶算法原理代码实现及测试特点剖析小结

计数器固定窗口算法

原理

计数器固定窗口算法是最根底也是最简略的一种限流算法。原理就是对一段固定工夫窗口内的申请进行计数，如果申请数超过了阈值，则舍弃该申请；如果没有达到设定的阈值，则承受该申请，且计数加 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: exzlc@139.com
* @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 个被限流，达到了预期的限流成果。

特点剖析

长处：实现简略，容易了解。

毛病：流量曲线可能不够平滑，有“突刺景象”，如下图所示。这样会有两个问题：

  1. 一段时间内（不超过工夫窗口）零碎服务不可用。比方窗口大小为 1s，限流大小为 100，而后恰好在某个窗口的第 1ms 来了 100 个申请，而后第 2ms-999ms 的申请就都会被回绝，这段时间用户会感觉零碎服务不可用。
  2. 窗口切换时可能会产生两倍于阈值流量的申请。比方窗口大小为 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: exzlc@139.com
* @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 次申请，计数器滑动窗口算法与计数器固定窗口算法进行对别，能够看到如下后果：

固定窗口算法在窗口切换时产生了两倍于阈值流量申请的问题，而滑动窗口算法防止了这个问题。

特点剖析

  1. 防止了计数器固定窗口算法固定窗口切换时可能会产生两倍于阈值流量申请的问题；
  2. 和漏斗算法相比，新来的申请也可能被解决到，防止了漏斗算法的饥饿问题。

漏斗算法

原理

漏斗算法的原理也很容易了解。申请来了之后会首先进到漏斗里，而后漏斗以恒定的速率将申请流出进行解决，从而起到平滑流量的作用。当申请的流量过大时，漏斗达到最大容量时会溢出，此时申请被抛弃。从零碎的角度来看，咱们不晓得什么时候会有申请来，也不晓得申请会以多大的速率来，这就给零碎的安全性埋下了隐患。然而如果加了一层漏斗算法限流之后，就可能保障申请以恒定的速率流出。在零碎看来，申请永远是以平滑的传输速率过去，从而起到了爱护零碎的作用。

代码实现及测试

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: exzlc@139.com
* @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 漏斗会漏出一个申请而后进行解决。

特点剖析

  1. 漏桶的漏出速率是固定的，能够起到整流的作用。即尽管申请的流量可能具备随机性, 忽大忽小，然而通过漏斗算法之后，变成了有固定速率的稳固流量，从而对上游的零碎起到爱护作用。
  2. 不能解决流量突发的问题。还是拿刚刚测试的例子，咱们设定的漏斗速率是 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: exzlc@139.com
* @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 个 / 秒的速率，即 容许肯定水平的流量突发。这一点也是和漏斗算法的次要区别，能够认真领会一下。

特点剖析

令牌桶算法是对漏桶算法的一种改良，除了可能在限度调用的均匀速率的同时还容许肯定水平的流量突发。

小结

咱们对上述四种限流算法进行一下简略的总结。

计数器固定窗口算法 实现简略，容易了解。和漏斗算法相比，新来的申请也可能被马上解决到。然而流量曲线可能不够平滑，有“突刺景象”，在窗口切换时可能会产生两倍于阈值流量的申请。而 计数器滑动窗口算法 作为计数器固定窗口算法的一种改良，无效解决了窗口切换时可能会产生两倍于阈值流量申请的问题。

漏斗算法 可能对流量起到整流的作用，让随机不稳固的流量以固定的速率流出，然而不能解决 流量突发 的问题。令牌桶算法 作为漏斗算法的一种改良，除了可能起到平滑流量的作用，还容许肯定水平的流量突发。

以上四种限流算法都有本身的特点，具体应用时还是要联合本身的场景进行选取，没有最好的算法，只有最合适的算法。比方令牌桶算法个别用于爱护本身的零碎，对调用者进行限流，爱护本身的零碎不被突发的流量打垮。如果本身的零碎理论的解决能力强于配置的流量限度时，能够容许肯定水平的流量突发，使得理论的解决速率高于配置的速率，充分利用系统资源。而漏斗算法个别用于爱护第三方的零碎，比方本身的零碎须要调用第三方的接口，为了爱护第三方的零碎不被本身的调用打垮，便能够通过漏斗算法进行限流，保障本身的流量安稳的打到第三方的接口上。

算法是死的，而算法中的 思维精华 才是值得咱们学习的。理论的场景中齐全能够灵活运用，还是那句话，没有最好的算法，只有最合适的算法。

感觉文章有用的话，点赞 + 关注 呗，好让更多的人看到这篇文章，也激励博主写出更多的好文章。更多对于 校招面试、算法、数据结构和计算机基础知识 的内容，欢送扫码关注我的原创公众号「超悦编程」。

更多举荐浏览
为什么有红黑树？什么是红黑树？看完这篇你就明确了
《深入浅出话数据结构》系列之什么是 B 树、B+ 树？为什么二叉查找树不行？
都 2020 年了，据说你还不会归并排序？手把手教你手写归并排序算法
为什么会有多线程？什么是线程平安？如何保障线程平安？
《一文说透数据结构》系列之什么是堆？看这一篇就够了

退出移动版