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

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.漏桶算法

漏桶算法的完成思路是，有一个固定容量的漏桶，水流（恳求）能够依照恣意速率先进入到漏桶里，但漏桶总是以固定的速率匀速流出，当流入量过大的时分（超过桶的容量），则多余水流（恳求）直接溢出。如下图所示：

面试官：限流算法有哪些？
漏桶算法提供了一种机制，经过它能够让突发流量被整形，以便为体系提供安稳的恳求，比方 Sentinel 中流量整形（匀速排队功能）就是此算法完成的，如下图所示：
面试官：限流算法有哪些？
更多 Sentinel 内容详见：mp.weixin.qq.com/s/nF5f18BP8…

3.令牌桶算法

令牌按固定的速率被放入令牌桶中，桶中最多存放 N 个令牌（Token），当桶装满时，新增加的令牌被丢掉或回绝。当恳求到达时，将从桶中删去 1 个令牌。令牌桶中的令牌不只能够被移除，还能够往里增加，所以为了保证接口随时稀有据经过，有必要不停地往桶里加令牌。由此可见，往桶里加令牌的速度就决定了数据经过接口的速度。咱们经过操控往令牌桶里加令牌的速度然后操控接口的流量。 令牌桶的完成原理如下图所示：

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

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

漏桶算法是依照常量固定速率流出恳求的，流入恳求速率恣意，当流入的恳求数累积到漏桶容量时，新流入的恳求被回绝。令牌桶算法是依照固定速率往桶中增加令牌的，恳求是否被处理需要看桶中的令牌是否满足，当令牌数减为零时，回绝新的恳求。令牌桶算法答应突发恳求，只要有令牌就能够处理，答应必定程度的突发流量。漏桶算法约束的是常量流出速率，然后使突发流入速率平滑。

比方服务器空闲时，理论上运用漏桶算法服务器能够直接处理一次洪峰（一次洪水进程的最大流量），可是漏桶算法处理恳求的速率是稳定的，因而，前期服务器资源只能依据稳定的漏水速度逐步处理恳求，无法直接处理这次洪峰。而运用令牌桶算法就不存在这个问题，由于它能够先把令牌桶一次性装满，处理一次洪峰之后再走限流。

总结

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

  1. 计数器算法：完成简略，但有突刺现象；
  2. 漏桶算法：固定速率处理恳求，处理恣意流量愈加平滑，能够完成流量整形；
  3. 令牌桶算法：经过操控桶中的令牌完成限流，能够处理必定的突发流量，比方处理一次洪峰。

参考 & 道谢

《散布式微服务架构》

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

本文已收录到 Gitee 开源库房《Java 面试突击》，其间包括的内容有：Redis、JVM、并发、并发、MySQL、Spring、Spring MVC、Spring Boot、Spring Cloud、MyBatis、规划形式、音讯行列等模块。Java 面试有它就够了：最全 Java 面试题库(2023版)，继续更新…