热门标签
热门文章
- 1华为Mate忘记密码如何强制清除刷机被华为机主已锁定被激活锁账号锁清除教程_华为手机刷机清除用户锁
- 2idea 工具的使用_idea的diagnostictool
- 3Android DrawerLayout 布局的打开展开侧滑和关闭收缩侧滑代码_android drawerlayout通过点击打开
- 4微搭低代码官方模板解析（一）_微搭 表单输入进行公式计算
- 5【小白成长记】页面上表格高度需根据页面高度进行动态计算赋值
- 6新火种AI|GPT-4诞生1年，OpenAI把它放到了机器人上
- 7Whisper实现语音识别转文本
- 8正规方程、、、_正规方程 特征相关性高
- 9自动白平衡算法_自动白平衡 代码
- 10技术积累 — 4294967295 是什么意思？（最大的数）
当前位置: article > 正文
面试必问：四种经典限流算法_限流滑动窗口
作者：IT小白 | 2024-03-20 15:30:59
赞
踩
限流滑动窗口
今天给大家分享一下限流方面的，大家都知道，在分布式系统中，高并发场景下，为了防止系统因突然的流量激增而导致的崩溃，同时保证服务的高可用性和稳定性，限流是最常用的手段。希望能够给大家带来帮助，大家多多点赞关注支持！！
所以面试经常会被问到限流问题，特别是限流的算法，基本上是必问，今天我为大家分享一下，或许许多人都大概都听过四种限流算法，分别是：固定窗口算法、滑动窗口算法、漏桶算法、令牌桶算法。但是对于他们之间的具体优缺点，以及适用的场景，还有具体的实现可能就不是特别的清楚了，所以我今天为大家详细地分享一下其中的根本区别，以及优缺点还有具体场景，以及最终的实现。
固定窗口限流算法
概念
固定窗口限流算法是一种最简单的限流算法，该算法将时间分成固定的窗口，并在每个窗口内限制请求的数量。具体来说，算法将请求按照时间顺序放入时间窗口中，并计算该时间窗口内的请求数量，如果请求数量超出了限制，则拒绝该请求。
举个例子：假设单位时间是1秒，限流阀值为3。在单位时间1秒内，每来一个请求,计数器就加1，如果计数器累加的次数超过限流阀值3，后续的请求全部拒绝。等到1s结束后，计数器清0，重新开始计数。
实现原理
在一个固定长度的时间窗口内限制请求数量，每来一个请求，请求次数加一，如果请求数量超过最大限制，就拒绝该请求。如下图：
具体代码实现
我们先说下具体实现流程：
在一开 始的时候，我们可以设置一个计数器counter，每当一个请求过来的时候，counter就加1，如果counter的值大于100并且该请求与第一个请求的间隔时间还在1分钟之内，那么说明请求数过多,拒绝访问；
如果该请求与第一个请求的间隔时间大于1分钟，且counter的值还在限流范围内，那么就重置 counter。
import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicLong; //计数器 限流 public class CounterLimiter { //起始时间 private static long startTime = System.currentTimeMillis(); //时间间隔1000ms private static long interval = 1000; //每个时间间隔内，限制数量 private static long limit = 3; //累加器 private static AtomicLong accumulator = new AtomicLong(); /** * true 代表放行，请求可已通过 * false 代表限制，不让请求通过 */ public static boolean tryAcquire() { long nowTime = System.currentTimeMillis(); //判断是否在上一个时间间隔内 if (nowTime < startTime + interval) { //如果还在上个时间间隔内 long count = accumulator.incrementAndGet(); if (count <= limit) { return true; } else { return false; } } else { //如果不在上一个时间间隔内 synchronized (CounterLimiter.class) { //防止重复初始化 if (nowTime > startTime + interval) { startTime = nowTime; accumulator.set(0); } } //再次进行判断 long count = accumulator.incrementAndGet(); if (count <= limit) { return true; } else { return false; } } } // 测试 public static void main(String[] args) { //线程池，用于多线程模拟测试 ExecutorService pool = Executors.newFixedThreadPool(10); // 被限制的次数 AtomicInteger limited = new AtomicInteger(0); // 线程数 final int threads = 2; // 每条线程的执行轮数 final int turns = 20; // 同步器 CountDownLatch countDownLatch = new CountDownLatch(threads); long start = System.currentTimeMillis(); for (int i = 0; i < threads; i++) { pool.submit(() -> { try { for (int j = 0; j < turns; j++) { boolean flag = tryAcquire(); if (!flag) { // 被限制的次数累积 limited.getAndIncrement(); } Thread.sleep(200); } } catch (Exception e) { e.printStackTrace(); } //等待所有线程结束 countDownLatch.countDown(); }); } try { countDownLatch.await(); } catch (InterruptedException e) { e.printStackTrace(); } float time = (System.currentTimeMillis() - start) / 1000F; //输出统计结果 System.out.println("限制的次数为：" + limited.get() + ",通过的次数为：" + (threads * turns - limited.get())); System.out.println("限制的比例为：" + (float) limited.get() / (float) (threads * turns)); System.out.println("运行的时长为：" + time + "s"); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
- 98
- 99
- 100
- 101
- 102
- 103
- 104
- 105
- 106
优缺点
- 优点：固定窗口算法非常简单，易于实现和理解。
- 缺点：存在明显的临界问题，假设有一个恶意用户，他在0:59时，瞬间发送了100个请求，并且1:00又瞬间发送了100个请求，那么其实这个用户在 1秒里面，瞬间发送了200个请求。我们刚才规定的是1分钟最多100个请求（规划的吞吐量），也就是每秒钟最多1.7个请求，用户通过在时间窗口的重置节点处突发请求， 可以瞬间超过我们的速率限制。所以用户有可能通过算法的这个漏洞，瞬间压垮我们的应用。
滑动窗口限流算法
概念
滑动窗口限流算法是一种常用的限流算法，用于控制系统对外提供服务的速率，防止系统被过多的请求压垮。它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期的小周期。它可以解决固定窗口临界值的问题。
实现原理
它是对固定窗口算法的一种改进。在滑动窗口算法中，窗口的起止时间是动态的，窗口的大小固定。这种算法能够较好地处理窗口边界问题，但是实现相对复杂，需要记录每个请求的时间戳。
实现原理是： 每来一个请求，就向后推一个时间窗口，计算这个窗口内的请求数量。如果请求数量超过限制就拒绝请求，否则就处理请求，并记录请求的时间戳。另外还需要一个任务清理过期的时间戳。
代码实现
/** * 单位时间划分的小周期（单位时间是1分钟，10s一个小格子窗口，一共6个格子） */ private int SUB_CYCLE = 10; /** * 每分钟限流请求数 */ private int thresholdPerMin = 100; /** * 计数器, k-为当前窗口的开始时间值秒，value为当前窗口的计数 */ private final TreeMap<Long, Integer> counters = new TreeMap<>(); /** * 滑动窗口时间算法实现 */ public synchronized boolean slidingWindowsTryAcquire() { long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //获取当前时间在哪个小周期窗口 int currentWindowNum = countCurrentWindow(currentWindowTime); //当前窗口总请求数 //超过阀值限流 if (currentWindowNum >= thresholdPerMin) { return false; } //计数器+1 counters.get(currentWindowTime)++; return true; } /** * 统计当前窗口的请求数 */ private synchronized int countCurrentWindow(long currentWindowTime) { //计算窗口开始位置 long startTime = currentWindowTime - SUB_CYCLE* (60s/SUB_CYCLE-1); int count = 0; //遍历存储的计数器 Iterator<Map.Entry<Long, Integer>> iterator = counters.entrySet().iterator(); while (iterator.hasNext()) { Map.Entry<Long, Integer> entry = iterator.next(); // 删除无效过期的子窗口计数器 if (entry.getKey() < startTime) { iterator.remove(); } else { //累加当前窗口的所有计数器之和 count =count + entry.getValue(); } } return count; }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
优缺点
优点
- 简单易懂
- 精度高（通过调整时间窗口的大小来实现不同的限流效果）
- 可扩展性强（可以非常容易地与其他限流算法结合使用）
缺点
- 突发流量无法处理，无法应对短时间内的大量请求，但是一旦到达限流后，请求都会直接暴力被拒绝。所以需要合理调整时间窗口大小。
漏桶限流算法
概念
漏桶限流算法是一种流量控制算法，用于控制流入网络的数据速率，以防止网络拥塞。它的思想是将数据包看作是水滴，漏桶看作是一个固定容量的水桶，数据包像水滴一样从桶的顶部流入桶中，并通过桶底的一个小孔以一定的速度流出，从而限制了数据包的流量。
实现原理
漏桶算法限流的基本原理为：水（对应请求）从进水口进入到漏桶里，漏桶以一定的速度出水（请求放行），当水流入速度过大，桶内的总水量大于桶容量会直接溢出，请求被拒绝。
漏桶限流规则如下：
- 进水口（对应客户端请求）以任意速率流入进入漏桶。
- 漏桶的容量是固定的，出水（放行）速率也是固定的。
- 漏桶容量是不变的，如果处理速度太慢，桶内水量会超出了桶的容量，则后面流入的水滴会溢出，表示请求拒绝。
如下图：
具体代码实现
import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicLong; //漏斗限流 public class LeakBucketLimiter { //桶的大小 private static long capacity = 10; //流出速率,每秒两个 private static long rate = 2; //开始时间 private static long startTime = System.currentTimeMillis(); //桶中剩余的水 private static AtomicLong water = new AtomicLong(); /** * true 代表放行，请求可已通过 * false 代表限制，不让请求通过 */ public synchronized static boolean tryAcquire() { //如果桶的余量问0，直接放行 if (water.get() == 0) { startTime = System.currentTimeMillis(); water.set(1); return true; } //计算从当前时间到开始时间流出的水，和现在桶中剩余的水 //桶中剩余的水 water.set(water.get() - (System.currentTimeMillis() - startTime) / 1000 * rate); //防止出现<0的情况 water.set(Math.max(0, water.get())); //设置新的开始时间 startTime += (System.currentTimeMillis() - startTime) / 1000 * 1000; //如果当前水小于容量，表示可以放行 if (water.get() < capacity) { water.incrementAndGet(); return true; } else { return false; } } // 测试 public static void main(String[] args) { //线程池，用于多线程模拟测试 ExecutorService pool = Executors.newFixedThreadPool(10); // 被限制的次数 AtomicInteger limited = new AtomicInteger(0); // 线程数 final int threads = 2; // 每条线程的执行轮数 final int turns = 20; // 同步器 CountDownLatch countDownLatch = new CountDownLatch(threads); long start = System.currentTimeMillis(); for (int i = 0; i < threads; i++) { pool.submit(() -> { try { for (int j = 0; j < turns; j++) { boolean flag = tryAcquire(); if (!flag) { // 被限制的次数累积 limited.getAndIncrement(); } Thread.sleep(200); } } catch (Exception e) { e.printStackTrace(); } //等待所有线程结束 countDownLatch.countDown(); }); } try { countDownLatch.await(); } catch (InterruptedException e) { e.printStackTrace(); } float time = (System.currentTimeMillis() - start) / 1000F; //输出统计结果 System.out.println("限制的次数为：" + limited.get() + ",通过的次数为：" + (threads * turns - limited.get())); System.out.println("限制的比例为：" + (float) limited.get() / (float) (threads * turns)); System.out.println("运行的时长为：" + time + "s"); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
- 90
- 91
- 92
- 93
- 94
- 95
- 96
- 97
优缺点
优点
- 可以平滑限制请求的处理速度，避免瞬间请求过多导致系统崩溃或者雪崩。
- 可以控制请求的处理速度，使得系统可以适应不同的流量需求，避免过载或者过度闲置。
- 可以通过调整桶的大小和漏出速率来满足不同的限流需求，可以灵活地适应不同的场景。
缺点
- 需要对请求进行缓存，会增加服务器的内存消耗。
- 对于流量波动比较大的场景，需要较为灵活的参数配置才能达到较好的效果。
- 但是面对突发流量的时候，漏桶算法还是循规蹈矩地处理请求，流量变突发时，我们肯定希望系统尽量快点处理请求，提升用户体验。
令牌桶算法
概念
令牌桶算法是一种常用的限流算法，可以用于限制单位时间内请求的数量。该算法维护一个固定容量的令牌桶，每秒钟会向令牌桶中放入一定数量的令牌。当有请求到来时，如果令牌桶中有足够的令牌，则请求被允许通过并从令牌桶中消耗一个令牌，否则请求被拒绝。
实现原理
令牌桶算法中新请求到来时会从桶里拿走一个令牌，如果桶内没有令牌可拿，就拒绝服务。 当然，令牌的数量也是有上限的。令牌的数量与时间和发放速率强相关，时间流逝的时间越长，会不断往桶里加入越多的令牌，如果令牌发放的速度比申请速度快，令牌桶会放满令牌，直到令牌占满整个令牌桶。
令牌桶限流大致的规则如下：
- 进水口按照某个速度，向桶中放入令牌。
- 令牌的容量是固定的，但是放行的速度不是固定的，只要桶中还有剩余令牌，一旦请求过来就能申请成功，然后放行。
- 如果令牌的发放速度，慢于请求到来速度，桶内就无牌可领，请求就会被拒绝。
总之，令牌的发送速率可以设置，从而可以对突发的出口流量进行有效的应对。
代码实现
import java.util.concurrent.CountDownLatch; import java.util.concurrent.ExecutorService; import java.util.concurrent.Executors; import java.util.concurrent.atomic.AtomicInteger; import java.util.concurrent.atomic.AtomicLong; //令牌桶 public class TokenBucketLimiter { //桶的容量 private static long capacity = 10; //放入令牌的速率,每秒2个 private static long rate = 2; //上次放置令牌的时间 private static long lastTime = System.currentTimeMillis(); //桶中令牌的余量 private static AtomicLong tokenNum = new AtomicLong(); /** * true 代表放行，请求可已通过 * false 代表限制，不让请求通过 */ public synchronized static boolean tryAcquire() { //更新桶中剩余令牌的数量 long now = System.currentTimeMillis(); tokenNum.addAndGet((now - lastTime) / 1000 * rate); tokenNum.set(Math.min(capacity, tokenNum.get())); //更新时间 lastTime += (now - lastTime) / 1000 * 1000; //桶中还有令牌就放行 if (tokenNum.get() > 0) { tokenNum.decrementAndGet(); return true; } else { return false; } } //测试 public static void main(String[] args) { //线程池，用于多线程模拟测试 ExecutorService pool = Executors.newFixedThreadPool(10); // 被限制的次数 AtomicInteger limited = new AtomicInteger(0); // 线程数 final int threads = 2; // 每条线程的执行轮数 final int turns = 20; // 同步器 CountDownLatch countDownLatch = new CountDownLatch(threads); long start = System.currentTimeMillis(); for (int i = 0; i < threads; i++) { pool.submit(() -> { try { for (int j = 0; j < turns; j++) { boolean flag = tryAcquire(); if (!flag) { // 被限制的次数累积 limited.getAndIncrement(); } Thread.sleep(200); } } catch (Exception e) { e.printStackTrace(); } //等待所有线程结束 countDownLatch.countDown(); }); } try { countDownLatch.await(); } catch (InterruptedException e) { e.printStackTrace(); } float time = (System.currentTimeMillis() - start) / 1000F; //输出统计结果 System.out.println("限制的次数为：" + limited.get() + ",通过的次数为：" + (threads * turns - limited.get())); System.out.println("限制的比例为：" + (float) limited.get() / (float) (threads * turns)); System.out.println("运行的时长为：" + time + "s"); } }
- 1
- 2
- 3
- 4
- 5
- 6
- 7
- 8
- 9
- 10
- 11
- 12
- 13
- 14
- 15
- 16
- 17
- 18
- 19
- 20
- 21
- 22
- 23
- 24
- 25
- 26
- 27
- 28
- 29
- 30
- 31
- 32
- 33
- 34
- 35
- 36
- 37
- 38
- 39
- 40
- 41
- 42
- 43
- 44
- 45
- 46
- 47
- 48
- 49
- 50
- 51
- 52
- 53
- 54
- 55
- 56
- 57
- 58
- 59
- 60
- 61
- 62
- 63
- 64
- 65
- 66
- 67
- 68
- 69
- 70
- 71
- 72
- 73
- 74
- 75
- 76
- 77
- 78
- 79
- 80
- 81
- 82
- 83
- 84
- 85
- 86
- 87
- 88
- 89
优缺点
优点
- 稳定性高：令牌桶算法可以控制请求的处理速度，可以使系统的负载变得稳定。
- 精度高：令牌桶算法可以根据实际情况动态调整生成令牌的速率，可以实现较高精度的限流。
- 弹性好：令牌桶算法可以处理突发流量，可以在短时间内提供更多的处理能力，以处理突发流量。
Guava的RateLimiter限流组件，就是基于令牌桶算法实现的。
缺点
- 实现复杂：相对于固定窗口算法等其他限流算法，令牌桶算法的实现较为复杂。
- 对短时请求难以处理：在短时间内有大量请求到来时，可能会导致令牌桶中的令牌被快速消耗完，从而限流。这种情况下，可以考虑使用漏桶算法。
- 时间精度要求高：令牌桶算法需要在固定的时间间隔内生成令牌，因此要求时间精度较高，如果系统时间不准确，可能会导致限流效果不理想。
总体来说，令牌桶算法具有较高的稳定性和精度，但实现相对复杂，适用于对稳定性和精度要求较高的场景。
最终对比
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/IT小白/article/detail/274640
推荐阅读
相关标签
