关于java:面试官限流算法有哪些

3次阅读

共计 2482 个字符，预计需要花费 7 分钟才能阅读完成。

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

计数器算法是在肯定的工夫距离里，记录申请次数，当申请次数超过该工夫限度时，就把计数器清零，而后从新计算。当申请次数超过距离内的最大次数时，回绝拜访。

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

突刺景象是指，比方限流 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);
                    }
                }
            }
        }
    }
}

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

漏桶算法提供了一种机制，通过它能够让突发流量被整形，以便为零碎提供稳固的申请，比方 Sentinel 中流量整形（匀速排队性能）就是此算法实现的，如下图所示：

更多 Sentinel 内容详见：https://mp.weixin.qq.com/s/nF5f18BP8hscqIEmIFRN8Q

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

漏桶算法是依照常量固定速率流出申请的，流入申请速率任意，当流入的申请数累积到漏桶容量时，新流入的申请被回绝。令牌桶算法是依照固定速率往桶中增加令牌的，申请是否被解决须要看桶中的令牌是否足够，当令牌数减为零时，回绝新的申请。令牌桶算法容许突发申请，只有有令牌就能够解决，容许肯定水平的突发流量。漏桶算法限度的是常量流出速率，从而使突发流入速率平滑。

比方服务器闲暇时，实践上应用漏桶算法服务器能够间接解决一次洪峰（一次洪水过程的最大流量），然而漏桶算法解决申请的速率是恒定的，因而，后期服务器资源只能依据恒定的漏水速度逐渐解决申请，无奈间接解决这次洪峰。而应用令牌桶算法就不存在这个问题，因为它能够先把令牌桶一次性装满，解决一次洪峰之后再走限流。

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

计数器算法：实现简略，但有突刺景象；
漏桶算法：固定速率解决申请，解决任意流量更加平滑，能够实现流量整形；
令牌桶算法：通过管制桶中的令牌实现限流，能够解决肯定的突发流量，比方解决一次洪峰。

《散布式微服务架构》

https://blog.csdn.net/chengqi…

本文已收录到 Gitee 开源仓库《Java 面试突击》，其中蕴含的内容有：Redis、JVM、并发、并发、MySQL、Spring、Spring MVC、Spring Boot、Spring Cloud、MyBatis、设计模式、音讯队列等模块。Java 面试有它就够了：最全 Java 面试题库 (2023 版)，继续更新 …

正文完