心得技巧

html5 HTML/Xhtml CSS XML/XSLT Dreamweaver教程 Frontpage教程心得技巧

上一篇: 秒懂设计模式之访问者模式（Visi... 下一篇:常见的排序算法（上）

5种限流算法，7种限流方式，挡住突发流量？

发布时间：2022-06-23 发布网站：脚本宝典

脚本宝典收集整理的这篇文章主要介绍了5种限流算法，7种限流方式，挡住突发流量？，脚本宝典觉得挺不错的，现在分享给大家，也给大家做个参考。

最近几年，随着微服务的流行，服务和服务之间的依赖越来越强，调用关系越来越复杂，服务和服务之间的稳定性越来越重要。在遇到突发的请求量激增，恶意的用户访问，亦或请求频率过高给下游服务带来较大压力时，我们常常需要通过缓存、限流、熔断降级、负载均衡等多种方式保证服务的稳定性。其中限流是不可或缺的一环，这篇文章介绍限流相关知识。

1. 限流

限流顾名思义，就是对请求或并发数进行限制；通过对一个时间窗口内的请求量进行限制来保障系统的正常运行。如果我们的服务资源有限、处理能力有限，就需要对调用我们服务的上游请求进行限制，以防止自身服务由于资源耗尽而停止服务。

在限流中有两个概念需要了解。

阈值：在一个单位时间内允许的请求量。如 QPS 限制为10，说明 1 秒内最多接受 10 次请求。
拒绝策略：超过阈值的请求的拒绝策略，常见的拒绝策略有直接拒绝、排队等待等。

2. 固定窗口算法

固定窗口算法又叫计数器算法，是一种简单方便的限流算法。主要通过一个支持原子操作的计数器来累计 1 秒内的请求次数，当 1 秒内计数达到限流阈值时触发拒绝策略。每过 1 秒，计数器重置为 0 开始重新计数。

2.1. 代码实现

下面是简单的代码实现，QPS 限制为 2，这里的代码做了一些优化，并没有单独开一个线程去每隔 1 秒重置计数器，而是在每次调用时进行时间间隔计算来确定是否先重置计数器。

/**
 * @author https://www.wdbyte.com
 */
public class RateLimiterSimpleWindow {
    // 阈值
    private static Integer QPS = 2;
    // 时间窗口（毫秒）
    private static long TIME_WINDOWS = 1000;
    // 计数器
    private static AtomicInteger REQ_COUNT = new AtomicInteger();
    
    private static long START_TIME = System.currentTimeMillis();

    public synchronized static boolean tryAcquire() {
        if ((System.currentTimeMillis() - START_TIME) > TIME_WINDOWS) {
            REQ_COUNT.set(0);
            START_TIME = System.currentTimeMillis();
        }
        return REQ_COUNT.incrementAndGet() <= QPS;
    }

    public static void main(String[] args) throws InterruptedException {
        for (int i = 0; i < 10; i++) {
            Thread.sleep(250);
            LocalTime now = LocalTime.now();
            if (!tryAcquire()) {
                System.out.println(now + " 被限流");
            } else {
                System.out.println(now + " 做点什么");
            }
        }
    }
}

运行结果：

20:53:43.038922 做点什么
20:53:43.291435 做点什么
20:53:43.543087 被限流
20:53:43.796666 做点什么
20:53:44.050855 做点什么
20:53:44.303547 被限流
20:53:44.555008 被限流
20:53:44.809083 做点什么
20:53:45.063828 做点什么
20:53:45.314433 被限流

从输出结果中可以看到大概每秒操作 3 次，由于限制 QPS 为 2，所以平均会有一次被限流。看起来可以了，不过我们思考一下就会发现这种简单的限流方式是有问题的，虽然我们限制了 QPS 为 2，但是当遇到时间窗口的临界突变时，如 1s 中的后 500 ms 和第 2s 的前 500ms 时，虽然是加起来是 1s 时间，却可以被请求 4 次。

5种限流算法，7种限流方式，挡住突发流量？

简单修改测试代码，可以进行验证：

// 先休眠 400ms，可以更快的到达时间窗口。
Thread.sleep(400);
for (int i = 0; i < 10; i++) {
    Thread.sleep(250);
    if (!tryAcquire()) {
        System.out.println("被限流");
    } else {
        System.out.println("做点什么");
    }
}

得到输出中可以看到连续 4 次请求，间隔 250 ms 没有却被限制：

20:51:17.395087 做点什么
20:51:17.653114 做点什么
20:51:17.903543 做点什么
20:51:18.154104 被限流
20:51:18.405497 做点什么
20:51:18.655885 做点什么
20:51:18.906177 做点什么
20:51:19.158113 被限流
20:51:19.410512 做点什么
20:51:19.661629 做点什么

3. 滑动窗口算法

我们已经知道固定窗口算法的实现方式以及它所存在的问题，而滑动窗口算法是对固定窗口算法的改进。既然固定窗口算法在遇到时间窗口的临界突变时会有问题，那么我们在遇到下一个时间窗口前也调整时间窗口不就可以了吗？

下面是滑动窗口的示意图。

5种限流算法，7种限流方式，挡住突发流量？

上图的示例中，每 500ms 滑动一次窗口，可以发现窗口滑动的间隔越短，时间窗口的临界突变问题发生的概率也就越小，不过只要有时间窗口的存在，还是有可能发生时间窗口的临界突变问题。

3.1. 代码实现

下面是基于以上滑动窗口思路实现的简单的滑动窗口限流工具类。

package com.wdbyte.rate.limiter;

import java.time.LocalTime;
import java.util.concurrent.atomic.AtomicInteger;

/**
 * 滑动窗口限流工具类
 *
 * @author https://www.wdbyte.com
 */
public class RateLimiterSlidingWindow {
    /**
     * 阈值
     */
    private int qps = 2;
    /**
     * 时间窗口总大小（毫秒）
     */
    private long windowSize = 1000;
    /**
     * 多少个子窗口
     */
    private Integer windowCount = 10;
    /**
     * 窗口列表
     */
    private WindowInfo[] windowArray = new WindowInfo[windowCount];

    public RateLimiterSlidingWindow(int qps) {
        this.qps = qps;
        long currentTimeMillis = System.currentTimeMillis();
        for (int i = 0; i < windowArray.length; i++) {
            windowArray[i] = new WindowInfo(currentTimeMillis, new AtomicInteger(0));
        }
    }

    /**
     * 1. 计算当前时间窗口
     * 2. 更新当前窗口计数 & 重置过期窗口计数
     * 3. 当前 QPS 是否超过限制
     *
     * @return
     */
    public synchronized boolean tryAcquire() {
        long currentTimeMillis = System.currentTimeMillis();
        // 1. 计算当前时间窗口位置
        int currentIndex = (int)(currentTimeMillis % windowSize / (windowSize / windowCount));
        // 2.  更新当前窗口计数 & 重置过期窗口计数
        int sum = 0;
        for (int i = 0; i < windowArray.length; i++) {
            WindowInfo windowInfo = windowArray[i];
            if ((currentTimeMillis - windowInfo.getTime()) > windowSize) {
                windowInfo.getNumber().set(0);
                windowInfo.setTime(currentTimeMillis);
            }
            if (currentIndex == i && windowInfo.getNumber().get() < qps) {
                windowInfo.getNumber().incrementAndGet();
            }
            sum = sum + windowInfo.getNumber().get();
        }
        // 3. 当前 QPS 是否超过限制
        return sum <= qps;
    }

    private class WindowInfo {
        // 窗口开始时间
        private Long time;
        // 计数器
        private AtomicInteger number;

        public WindowInfo(long time, AtomicInteger number) {
            this.time = time;
            this.number = number;
        }
        // get...set...
    }
}

下面是测试用例，设置 QPS 为 2,测试次数 20 次，每次间隔 300 毫秒，预计成功次数在 12 次左右。

public static void main(String[] args) throws InterruptedException {
    int qps = 2, count = 20, sleep = 300, success = count * sleep / 1000 * qps;
    System.out.println(String.format("当前QPS限制为:%d,当前测试次数:%d,间隔:%dms,预计成功次数:%d", qps, count, sleep, success));
    success = 0;
    RateLimiterSlidingWindow myRateLimiter = new RateLimiterSlidingWindow(qps);
    for (int i = 0; i < count; i++) {
        Thread.sleep(sleep);
        if (myRateLimiter.tryAcquire()) {
            success++;
            if (success % qps == 0) {
                System.out.println(LocalTime.now() + ": success, ");
            } else {
                System.out.print(LocalTime.now() + ": success, ");
            }
        } else {
            System.out.println(LocalTime.now() + ": fail");
        }
    }
    System.out.println();
    System.out.println("实际测试成功次数:" + success);
}

下面是测试的结果。

当前QPS限制为:2,当前测试次数:20,间隔:300ms,预计成功次数:12
16:04:27.077782: success, 16:04:27.380715: success, 
16:04:27.684244: fail
16:04:27.989579: success, 16:04:28.293347: success, 
16:04:28.597658: fail
16:04:28.901688: fail
16:04:29.205262: success, 16:04:29.507117: success, 
16:04:29.812188: fail
16:04:30.115316: fail
16:04:30.420596: success, 16:04:30.725897: success, 
16:04:31.028599: fail
16:04:31.331047: fail
16:04:31.634127: success, 16:04:31.939411: success, 
16:04:32.242380: fail
16:04:32.547626: fail
16:04:32.847965: success, 
实际测试成功次数:11

4. 滑动日志算法

滑动日志算法是实现限流的另一种方法，这种方法比较简单。基本逻辑就是记录下所有的请求时间点，新请求到来时先判断最近指定时间范围内的请求数量是否超过指定阈值，由此来确定是否达到限流，这种方式没有了时间窗口突变的问题，限流比较准确，但是因为要记录下每次请求的时间点，所以占用的内存较多。

4.1. 代码实现

下面是简单实现的一个滑动日志算法，因为滑动日志要每次请求单独存储一条记录，可能占用内存过多。所以下面这个实现其实不算严谨的滑动日志，更像一个把 1 秒时间切分成 1000 个时间窗口的滑动窗口算法。

package com.wdbyte.rate.limiter;

import java.time.LocalTime;
import java.util.HashSet;
import java.util.Set;
import java.util.TreeMap;

/**
 * 滑动日志方式限流
 * 设置 QPS 为 2.
 *
 * @author https://www.wdbyte.com
 */
public class RateLimiterSildingLog {

    /**
     * 阈值
     */
    private Integer qps = 2;
    /**
     * 记录请求的时间戳,和数量
     */
    private TreeMap<Long, Long> treeMap = new TreeMap<>();

    /**
     * 清理请求记录间隔, 60 秒
     */
    private long claerTime = 60 * 1000;

    public RateLimiterSildingLog(Integer qps) {
        this.qps = qps;
    }

    public synchronized boolean tryAcquire() {
        long now = System.currentTimeMillis();
        // 清理过期的数据老数据，最长 60 秒清理一次
        if (!treeMap.isEmpty() && (now - treeMap.firstKey()) > claerTime) {
            Set<Long> keySet = new HashSet<>(treeMap.subMap(0L, now - 1000).keySet());
            for (Long key : keySet) {
                treeMap.remove(key);
            }
        }
        // 计算当前请求次数
        int sum = 0;
        for (Long value : treeMap.subMap(now - 1000, now).values()) {
            sum += value;
        }
        // 超过QPS限制，直接返回 false
        if (sum + 1 > qps) {
            return false;
        }
        // 记录本次请求
        if (treeMap.containsKey(now)) {
            treeMap.compute(now, (k, v) -> v + 1);
        } else {
            treeMap.put(now, 1L);
        }
        return sum <= qps;
    }

    public static void main(String[] args) throws InterruptedException {
        RateLimiterSildingLog rateLimiterSildingLog = new RateLimiterSildingLog(3);
        for (int i = 0; i < 10; i++) {
            Thread.sleep(250);
            LocalTime now = LocalTime.now();
            if (rateLimiterSildingLog.tryAcquire()) {
                System.out.println(now + " 做点什么");
            } else {
                System.out.println(now + " 被限流");
            }
        }
    }
}

代码中把阈值 QPS 设定为 3，运行可以得到如下日志：

20:51:17.395087 做点什么
20:51:17.653114 做点什么
20:51:17.903543 做点什么
20:51:18.154104 被限流
20:51:18.405497 做点什么
20:51:18.655885 做点什么
20:51:18.906177 做点什么
20:51:19.158113 被限流
20:51:19.410512 做点什么
20:51:19.661629 做点什么

5. 漏桶算法

转载：https://mp.weixin.qq.com/s/MSLajKSeLthzSGyy0nOPIg

脚本宝典总结

以上是脚本宝典为你收集整理的5种限流算法，7种限流方式，挡住突发流量？全部内容，希望文章能够帮你解决5种限流算法，7种限流方式，挡住突发流量？所遇到的问题。

如果觉得脚本宝典网站内容还不错，欢迎将脚本宝典推荐好友。

本图文内容来源于网友网络收集整理提供，作为学习参考使用，版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ：384754419，请注明来意。

标签：并发

上一篇: 秒懂设计模式之访问者模式（Visi... 下一篇:常见的排序算法（上）

猜你在找的心得技巧相关文章

clion结合vcpkg以及GTest的使用 2022-07-07
EGF 2022-06-06
ExtJS 布局-Column布局（Column layout） 2022-06-05
颜色之ARGB与RGB、RGBA的区别与介绍 2022-04-15
rgba中的a是什么意思 CSS之RGBA颜色指南 2022-04-15
rootfs -根文件系统制作 2022-07-07
网页简单布局之结构与表现原则分享 2022-04-15
小项目中怎么防止Vue的闪现画面效果 2022-04-15
隐藏 Web 中的元素方法及优缺点教程详解 2022-04-15
告别硬编码让你的前端表格自动计算的实例代码 2022-04-15

全站导航更多

Arabic	Hebrew	Polish
Bulgarian	Hindi	Portuguese
Catalan	Hmong Daw	Romanian
Chinese Simplified	Hungarian	Russian
Chinese Traditional	Indonesian	Slovak
Czech	Italian	Slovenian
Danish	Japanese	Spanish
Dutch	Klingon	Swedish
English	Korean	Thai
Estonian	Latvian	Turkish
Finnish	Lithuanian	Ukrainian
French	Malay	Urdu
German	Maltese	Vietnamese
Greek	Norwegian	Welsh
Haitian Creole	Persian

5种限流算法，7种限流方式，挡住突发流量？

目录

前言

1. 限流

2. 固定窗口算法

2.1. 代码实现

3. 滑动窗口算法

3.1. 代码实现

4. 滑动日志算法

4.1. 代码实现

5. 漏桶算法

脚本宝典总结