面试官：限流算法有哪些？

曾经终败给现在 2023-09-24 19:23 66阅读 0赞

![b07a3e0fc8e5d6bd54940908d17b0142.jpeg][]

作者 | 磊哥

来源 | Java中文社群（ID：javacn666）

转载请联系授权（微信ID：GG\_Stone）

> 磊哥《Java 面试提高课(2023版)》（戳我加入）正式上线了，里面包含了 **20 万字的最新 Java 面试题（问答形式），并配有 Spring Cloud、MQ、设计模式等内容**，以及简历辅导、面试辅导、复习规划、一对一答疑等服务，期待你的加入~

限流的实现算法有很多，但常见的限流算法有三种：计数器算法、漏桶算法和令牌桶算法。

### 1.计数器算法 ###

计数器算法是在一定的时间间隔里，记录请求次数，当请求次数超过该时间限制时，就把计数器清零，然后重新计算。当请求次数超过间隔内的最大次数时，拒绝访问。

计数器算法的实现比较简单，但存在“突刺现象”。

突刺现象是指，比如限流 QPS（每秒查询率）为 100，算法的实现思路就是从第一个请求进来开始计时，在接下来的 1 秒内，每来一个请求，就把计数加 1，如果累加的数字达到了 100，后续的请求就会被全部拒绝。等到 1 秒结束后，把计数恢复成 0，重新开始计数。如果在单位时间 1 秒内的前 10 毫秒处理了 100 个请求，那么后面的 990 毫秒会请求拒绝所有的请求，我们把这种现象称为“突刺现象”。

计数器算法的简单实现代码如下：

import java.util.Calendar;
    import java.util.Date;
    import java.util.Random;
    
    public class CounterLimit {
        // 记录上次统计时间
        static Date lastDate = new Date();
        // 初始化值
        static int counter = 0;
        // 限流方法
        static boolean countLimit() {
            // 获取当前时间
            Date now = new Date();
            Calendar calendar = Calendar.getInstance();
            calendar.setTime(now);
            // 当前分
            int minute = calendar.get(Calendar.MINUTE);
            calendar.setTime(lastDate);
            int lastMinute = calendar.get(Calendar.MINUTE);
            if (minute != lastMinute) {
                lastDate = now;
                counter = 0;
            }
            ++counter;
            return counter >= 100; // 判断计数器是否大于每分钟限定的值。
        }
    
        // 测试方法
        public static void main(String[] args) {
            for (; ; ) {
                // 模拟一秒
                try {
                    Thread.sleep(1000);
                } catch (InterruptedException e) {
                    e.printStackTrace();
                }
                Random random = new Random();
                int i = random.nextInt(3);
                // 模拟1秒内请求1次
                if (i == 1) {
                    if (countLimit()) {
                        System.out.println("限流了" + counter);
    
                    } else {
                        System.out.println("没限流" + counter);
                    }
                } else if (i == 2) { // 模拟1秒内请求2次
                    for (int j = 0; j < 2; j++) {
                        if (countLimit()) {
                            System.out.println("限流了" + counter);
                        } else {
                            System.out.println("没限流" + counter);
                        }
                    }
                } else { // 模拟1秒内请求10次
                    for (int j = 0; j < 10; j++) {
                        if (countLimit()) {
                            System.out.println("限流了" + counter);
                        } else {
                            System.out.println("没限流" + counter);
                        }
                    }
                }
            }
        }
    }

### 2.漏桶算法 ###

漏桶算法的实现思路是，有一个固定容量的漏桶，水流（请求）可以按照任意速率先进入到漏桶里，但漏桶总是以固定的速率匀速流出，当流入量过大的时候（超过桶的容量），则多余水流（请求）直接溢出。如下图所示：

![cabeb3040947bbe362507400abe539d5.png][]

漏桶算法提供了一种机制，通过它可以让突发流量被整形，以便为系统提供稳定的请求，比如 Sentinel 中流量整形（匀速排队功能）就是此算法实现的，如下图所示：

![d592feb2d6ccc5ec9898f472ddf8495a.png][] 更多 Sentinel 内容详见： https://mp.weixin.qq.com/s/nF5f18BP8hscqIEmIFRN8Q

### 3.令牌桶算法 ###

令牌按固定的速率被放入令牌桶中，桶中最多存放 N 个令牌（Token），当桶装满时，新添加的令牌被丢弃或拒绝。当请求到达时，将从桶中删除 1 个令牌。令牌桶中的令牌不仅可以被移除，还可以往里添加，所以为了保证接口随时有数据通过，必须不停地往桶里加令牌。由此可见，往桶里加令牌的速度就决定了数据通过接口的速度。我们通过控制往令牌桶里加令牌的速度从而控制接口的流量。令牌桶的实现原理如下图所示：

![957e89f7dabf0326e6c6be4840cbef25.png][]

### 4.漏桶算法 VS 令牌桶算法 ###

漏桶算法是按照常量固定速率流出请求的，流入请求速率任意，当流入的请求数累积到漏桶容量时，新流入的请求被拒绝。令牌桶算法是按照固定速率往桶中添加令牌的，请求是否被处理需要看桶中的令牌是否足够，当令牌数减为零时，拒绝新的请求。令牌桶算法允许突发请求，只要有令牌就可以处理，允许一定程度的突发流量。漏桶算法限制的是常量流出速率，从而使突发流入速率平滑。

比如服务器空闲时，理论上使用漏桶算法服务器可以直接处理一次洪峰（一次洪水过程的最大流量），但是漏桶算法处理请求的速率是恒定的，因此，前期服务器资源只能根据恒定的漏水速度逐步处理请求，无法直接处理这次洪峰。而使用令牌桶算法就不存在这个问题，因为它可以先把令牌桶一次性装满，处理一次洪峰之后再走限流。

### 总结 ###

限流的常见算法有以下 3 种：

1.  计数器算法：实现简单，但有突刺现象；
2.  漏桶算法：固定速率处理请求，处理任意流量更加平滑，可以实现流量整形；
3.  令牌桶算法：通过控制桶中的令牌实现限流，可以处理一定的突发流量，比如处理一次洪峰。

##### 参考 & 鸣谢 #####

《分布式微服务架构》

https://blog.csdn.net/chengqiuming/article/details/122385943

--------------------

### 作者介绍 ###

磊哥，14 年编程和框架从业经验，前 360 技术专家、CSDN 签约作者、阿里云专家博主、拉勾网签约作者、掘金优秀作者、慕课网讲师等。期待与你相遇，一起探讨和分享技术的乐趣。

磊哥最近新出了一个 20 万字的《Java面试提高课（2023版）》，非常不错，并配有 **6 大服务：简历辅导、面试辅导、一对一答疑、专属复习规划、项目评审、职业规划**等，推荐给你哦~

![ed5c6cda8657ab18cd4411b6da428a1a.png][]

[b07a3e0fc8e5d6bd54940908d17b0142.jpeg]: https://img-blog.csdnimg.cn/img_convert/b07a3e0fc8e5d6bd54940908d17b0142.jpeg
[cabeb3040947bbe362507400abe539d5.png]: https://img-blog.csdnimg.cn/img_convert/cabeb3040947bbe362507400abe539d5.png
[d592feb2d6ccc5ec9898f472ddf8495a.png]: https://img-blog.csdnimg.cn/img_convert/d592feb2d6ccc5ec9898f472ddf8495a.png
[957e89f7dabf0326e6c6be4840cbef25.png]: https://img-blog.csdnimg.cn/img_convert/957e89f7dabf0326e6c6be4840cbef25.png
[ed5c6cda8657ab18cd4411b6da428a1a.png]: https://img-blog.csdnimg.cn/img_convert/ed5c6cda8657ab18cd4411b6da428a1a.png