常见的几种限流算法

这篇具有很好参考价值的文章主要介绍了常见的几种限流算法。希望对大家有所帮助。如果存在错误或未考虑完全的地方,请大家不吝赐教,您也可以点击"举报违法"按钮提交疑问。

前言:

失踪人口回归,哈哈哈,最近项目比较忙,然后还要学习前端的知识,后端性能治理也比较有挑战性,还是没有太多时间沉下心来写文章,等之后好好补上。
今天1024,在此奉上本人在掘金上面的一篇文章,虽然是在其他平台发布过的文章,但还是很值得学习的。

好了话不多说,下面进入正文。

什么是限流?

限流可以认为服务降级的一种,限流就是限制系统的输入和输出流量已达到保护系统 的目的。一般来说系统的吞吐量是可以被测算的,为了保证系统的稳定运行,一旦达到的需要限制的阈值,就需要限制流量并采取一些措施以完成限制流量的目的。比如:延迟处理,拒绝处理,或者部分拒绝处理等等。接下来我们来讲解一下常见的限流算法。

1.计数器(也可称为固定窗口)

固定窗口,相比其他的限流算法,这应该是最简单的一种。

它简单地对一个固定的时间窗口内的请求数量进行计数,如果超过请求数量的阈值,将被直接丢弃。

比如我们下图中的黄色区域就是固定时间窗口,默认时间范围是60s,限流数量是100。

如图中括号内所示:

  1. 第一个黄色框(也就是第一个60s),前面一段时间都没有流量,刚好最后面20秒内来了100个请求,为没有超过限流阈值,所以请求全部通过,
  2. 第二个黄色框(也就是第二个60s),刚开始的20秒内来了100个请求,此时因为按照的是第二个黄色框来计算的,所以这个时候认为刚好达到限流数量,所以通过了100个请求。

此时我们结合第一个黄色框的后20s和第二个黄色框的前20s,这个时候在40s内,是有200个请求通过了,超过了我们限流的阈值,这很有可能让我们的服务崩溃。

常见的几种限流算法

这种方式既可以称为计算机,也就是60s内限制计数100个,下个60s内又重新限制100个,这种方式也可以抽象的理解成固定窗口。

2.滑动窗口

刚才我们提到了固定窗口有严重的弊端,所以为了优化这个问题,于是有了滑动窗口算法,顾名思义,滑动窗口就是时间窗口在随着时间推移不停地移动。

如果还是60s,限流数量是100那么就变成如下:

窗口不在固定,以当前时间为窗口末端,往前推60s为一个窗口,计算窗口内的流量是否超过100,超过则执行拒绝策略(可以加入等待队列,可以直接拒绝请求),没超过则放行。

大家可以去看一下滑动窗口的算法,leetcode里面有很多题目都用到了这个,大致差不多。

临界问题:

常见的几种限流算法

假设我们1s内的限流阀值是5个请求,0.8~1.0s内(比如0.9s的时候)来了5个请求,落在黄色格子里。时间过了1.0s这个点之后,又来5个请求,落在紫色格子里。如果是固定窗口算法,是不会被限流的,但是滑动窗口的话,每过一个小周期,它会右移一个小格。过了1.0s这个点后,会右移一小格,当前的单位时间段是0.2~1.2s,这个区域的请求已经超过限定的5了,已触发限流啦,实际上,紫色格子的请求都被拒绝啦。

TIPS: 当滑动窗口的格子周期划分的越多,那么滑动窗口的滚动就越平滑,限流的统计就会越精确。

3.漏桶Leaky bucket

漏桶算法,人如其名,他就是一个漏的桶,不管请求的数量有多少,最终都会以固定的出口流量大小匀速流出,如果请求的流量超过漏桶大小,那么超出的流量将会被丢弃。

也就是说流量流入的速度是不定的,但是流出的速度是恒定的。

常见的几种限流算法

漏桶算法的优势是匀速,匀速是优点也是缺点,很多人说漏桶不能处理突增流量,这个说法并不准确。

漏桶本来就应该是为了处理间歇性的突增流量,流量一下起来了,然后系统处理不过来,可以在空闲的时候去处理,防止了突增流量导致系统崩溃,保护了系统的稳定性。

但是,换一个思路来想,其实这些突增的流量对于系统来说完全没有压力,你还在慢慢地匀速排队,其实是对系统性能的浪费。

所以,对于这种有场景来说,令牌桶算法比漏桶就更有优势。

4.令牌桶token bucket

令牌桶算法是指系统以一定地速度往令牌桶里丢令牌,当一个请求过来的时候,会去令牌桶里申请一个令牌,如果能够获取到令牌,那么请求就可以正常进行,反之被丢弃。

常见的几种限流算法

  • a. 按特定的速率向令牌桶投放令牌,这个速率可以慢慢增减,也可以减少,也可以恒定速率。
  • b. 根据预设的匹配规则先对报文进行分类,不符合匹配规则的报文不需要经过令牌桶的处理,直接发送;
  • c. 符合匹配规则的报文,则需要令牌桶进行处理。当桶中有足够的令牌则报文可以被继续发送下去,同时令牌桶中的令牌 量按报文的长度做相应的减少;
  • d. 当令牌桶中的令牌不足时,报文将不能被发送,只有等到桶中生成了新的令牌,报文才可以发送。这就可以限制报文的流量只能是小于等于令牌生成的速度,达到限制流量的目的。

现在的令牌桶算法,像Guava和Sentinel的实现都有冷启动/预热的方式,为了避免在流量激增的同时把系统打挂,令牌桶算法会在最开始一段时间内冷启动(可类比JVM中的热机与冷机),随着流量的增加,系统会根据流量大小动态地调整生成令牌的速度,最终直到请求达到系统的阈值。

5.滑动日志

滑动日志是一个比较“冷门”,但是确实好用的限流算法。滑动日志限速算法需要记录请求的时间戳,通常使用有序集合来存储,我们可以在单个有序集合中跟踪用户在一个时间段内所有的请求。

假设我们要限制给定T时间内的请求不超过N,我们只需要存储最近T时间之内的请求日志,每当请求到来时判断最近T时间内的请求总数是否超过阈值。

实现如下:

Copypublic class SlidingLogRateLimiter extends MyRateLimiter {
    /**
     * 每分钟限制请求数
     */
    private static final long PERMITS_PER_MINUTE = 60;
    /**
     * 请求日志计数器, k-为请求的时间(秒),value当前时间的请求数量
     */
    private final TreeMap<Long, Integer> requestLogCountMap = new TreeMap<>();
​
    @Override
    public synchronized boolean tryAcquire() {
        // 最小时间粒度为s
        long currentTimestamp = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC);
        // 获取当前窗口的请求总数
        int currentWindowCount = getCurrentWindowCount(currentTimestamp);
        if (currentWindowCount >= PERMITS_PER_MINUTE) {
            return false;
        }
        // 请求成功,将当前请求日志加入到日志中
        requestLogCountMap.merge(currentTimestamp, 1, Integer::sum);
        return true;
    }
​
    /**
     * 统计当前时间窗口内的请求数
     *
     * @param currentTime 当前时间
     * @return -
     */
    private int getCurrentWindowCount(long currentTime) {
        // 计算出窗口的开始位置时间
        long startTime = currentTime - 59;
        // 遍历当前存储的计数器,删除无效的子窗口计数器,并累加当前窗口中的所有计数器之和
        return requestLogCountMap.entrySet()
                .stream()
                .filter(entry -> entry.getKey() >= startTime)
                .mapToInt(Map.Entry::getValue)
                .sum();
    }
}

滑动日志能够避免突发流量,实现较为精准的限流;同样更加灵活,能够支持更加复杂的限流策略,如多级限流,每分钟不超过100次,每小时不超过300次,每天不超过1000次,我们只需要保存最近24小时所有的请求日志即可实现。

灵活并不是没有代价的,带来的缺点就是占用存储空间要高于其他限流算法

6.总结

  1. 固定窗口算法实现简单,性能高,但是会有临界突发流量问题,瞬时流量最大可以达到阈值的2倍。

  2. 为了解决临界突发流量,可以将窗口划分为多个更细粒度的单元,每次窗口向右移动一个单元,于是便有了滑动窗口算法。

    滑动窗口当流量到达阈值时会瞬间掐断流量,所以导致流量不够平滑。

  3. 想要达到限流的目的,又不会掐断流量,使得流量更加平滑?可以考虑漏桶算法!需要注意的是,漏桶算法通常配置一个FIFO的队列使用以达到允许限流的作用。

    由于速率固定,即使在某个时刻下游处理能力过剩,也不能得到很好的利用,这是漏桶算法的一个短板。

  4. 限流和瞬时流量其实并不矛盾,在大多数场景中,短时间突发流量系统是完全可以接受的。令牌桶算法就是不二之选了,令牌桶以固定的速率v产生令牌放入一个固定容量为n的桶中,当请求到达时尝试从桶中获取令牌。

    当桶满时,允许最大瞬时流量为n;当桶中没有剩余流量时则限流速率最低,为令牌生成的速率v。

  5. 如何实现更加灵活的多级限流呢?滑动日志限流算法了解一下!这里的日志则是请求的时间戳,通过计算制定时间段内请求总数来实现灵活的限流。

    当然,由于需要存储时间戳信息,其占用的存储空间要比其他限流算法要大得多。

以上几种限流算法的实现都仅适合单机限流。虽然给每台机器平均分配限流配额可以达到限流的目的,但是由于机器性能,流量分布不均以及计算数量动态变化等问题,单机限流在分布式场景中的效果总是差强人意。

分布式限流最简单的实现就是利用中心化存储,即将单机限流存储在本地的数据存储到同一个存储空间中,如常见的Redis等。

当然也可以从上层流量入口进行限流,Nginx代理服务就提供了限流模块,同样能够实现高性能,精准的限流,其底层是漏桶算法。

不管黑猫白猫,能抓到老鼠的就是好猫。限流算法并没有绝对的好劣之分,如何选择合适的限流算法呢?不妨从性能,是否允许超出阈值落地成本流量平滑度是否允许突发流量以及系统资源大小限制多方面考虑。

当然,市面上也有比较成熟的限流工具和框架。如Google出品的Guava中基于令牌桶实现的限流组件,拿来即用;以及alibaba开源的面向分布式服务架构的流量控制框架Sentinel更会让你爱不释手,它是基于滑动窗口实现的。文章来源地址https://www.toymoban.com/news/detail-442461.html

到了这里,关于常见的几种限流算法的文章就介绍完了。如果您还想了解更多内容,请在右上角搜索TOY模板网以前的文章或继续浏览下面的相关文章,希望大家以后多多支持TOY模板网!

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处: 如若内容造成侵权/违法违规/事实不符,请点击违法举报进行投诉反馈,一经查实,立即删除!

领支付宝红包 赞助服务器费用

相关文章

  • 常见的几种排序

    🐶博主主页: @ᰔᩚ. 一怀明月ꦿ  ❤️‍🔥 专栏系列: 线性代数,C初学者入门训练,题解C,C的使用文章,「初学」C++ 🔥 座右铭: “不要等到什么都没有了,才下定决心去做” 🚀🚀🚀大家觉不错的话,就恳求大家点点关注,点点小爱心,指点指点🚀🚀🚀 目录 冒泡

    2024年02月15日
    浏览(39)
  • 常见的几种排序方式

    排序: 所谓排序,就是使一串记录,按照其中的某个或某些的大小,递增或递减的排列起来的操作 稳定性: 假定在待排序的记录序列中,存在多个具有相同的的记录,若经过排序,这些记录的相对次序保持不变,即在原序列中,r[i]=r[j],且r[i]在r[j]之前,而在

    2024年02月07日
    浏览(46)
  • Jmeter常见的几种报错

    1、Java.net.UnknownHostException 这个错的含义是 没有连接到服务器地址,因此很可能是 内部网络中断导致。 2、502 Bad gateway 这个和本地的线程数无关 可能原因是网络抖动不稳定导致 3、java.net.SocketException: Socket closed 强制停止线程,连接中断产生的错误,正常压测我们等测试结束就

    2024年02月13日
    浏览(68)
  • 题目中常见的几种距离

    在几何学里面距离并不单指直线距离,有很多其他的距离没有那么常用,但考场上可能会出现,为了防止题目不给出定义等,我们有必要认识一下各种距离。 后面的角标为了清楚直接打到字母后面了 也被称作欧式距离,在平面直角坐标系中,设有两点 (A(x_{1},y_{1}),B(x_{2},y_

    2024年02月06日
    浏览(94)
  • flink的几种常见的执行模式

    在运行flink时,我们经常会有几种不同的执行模式,比如在IDE中启动时,通过提交到YARN上,还有通过Kebernates启动时,本文就来记录一下这几种模式 flink嵌入式模式: 这是一种我们在IDE开发和调试flink应用时最常使用的模式,他会在一个JVM进程中以线程的方式开启所有flink的各

    2024年02月09日
    浏览(32)
  • 常见路由跳转的几种方式

    常见的路由跳转有以下四种: 1. router-link to=\\\"跳转路径\\\"  也可,如 2. this.$router.push() 跳转到指定的url,并在history中添加记录(即,点击回退,会退回上一个页面) 。 html中,如: 3. this.$router.replace() 跳转到指定的url, 但不会在history记录(即,点击回退 退回到上上个页) 4

    2024年02月10日
    浏览(40)
  • 常见的异步编程的几种方法

    回调函数 Promise Rxjs 1、回调函数   2、Promise   3、Rxjs 注意:不管是通过 Promise 的 resolve返回,还是通过 getRxjsData 的 observer 返回,返回的时间用户都不能马上得到,必须分别使用 then 和 subscribe 来订阅   4、Rxjs取消订阅   5、rxjs订阅后多次执行  

    2024年01月20日
    浏览(46)
  • MySQL加密的几种常见方式

    MySQL提供了多种加密方式来保护数据的安全性。下面是几种常见的MySQL加密方式: 密码加密: MySQL5.7及以上版本使用SHA-256算法对密码进行加密。这种加密方式更安全,可以防止密码泄露。 之前的MySQL版本使用SHA-1算法进行密码加密。这种加密方式相对较弱,不建议使用。 数据

    2024年02月09日
    浏览(49)
  • 寻找网站后台的几种常见的方法

    (注:本教程仅供学习交流使用,不可用于一切未授权的网络攻击和违法行为!) 当我们进入一个网站时,如何对其后台进行查找、从而进一步渗透?今天给大家介绍几种常见的方法: 查看网站图片中的属性 我们可以随机点击一些图片的属性,看看它的路径能否加以利用

    2024年01月16日
    浏览(37)
  • python操作PDF的几种常见方法

    大家好,有关python操作pdf的方法,各种语言处理起来都比较麻烦,而且各种第三方库的应用场景都不同。下面说明一下python如何通过第三方库如何处理pdf文件。 1.1、pdfplumber提取文本内容 安装pdfplumber pdfplumber提取PDF中文字代码思路如下 利用pdfplumber打开一个 PDF 文件 获取指定

    2024年02月03日
    浏览(43)

觉得文章有用就打赏一下文章作者

支付宝扫一扫打赏

博客赞助

微信扫一扫打赏

请作者喝杯咖啡吧~博客赞助

支付宝扫一扫领取红包,优惠每天领

二维码1

领取红包

二维码2

领红包