后端程序员必备：四种限流算法，图文结合一篇搞定

私域运营 2022-10-22 17:51 6852人围观限流

前言

比来我们系统引入了Guava的RateLimiter限流组件，它是基于令牌桶算法的实现的。本文将跟大师一路进修几种典范的限流算法。

后端法式员必备：四种限流算法，图文连系一篇搞定

限流是什么?

维基百科的概念以下：

In computer networks, rate limiting is used to control the rate of requests sent orreceived by a network interface controller. It can be used to prevent DoS attacks and limit web scraping

简单翻译一下：在计较机收集合，限流就是控制收集接口发送或接收请求的速度，它可避免DoS进犯和限制Web爬虫。

限流，也称流量控制。是指系统在面临高并发，大概大流量请求的情况下，限制新的请求对系统的拜候，从而保证系统的稳定性。限流会致使部分用户请求处置不实时大概被拒，这就影响了用户体验。所以一般需要在系统稳定和用户体验之间平衡一下。举个生活的例子：

一些热门的旅游景区，一般会对逐日的旅游参观人数有限制的。天天只会卖出牢固数目标门票，比如5000张。假定在五一、国庆假期，你去晚了，能够当天的票就已经卖完了，就没法进去游玩了。即使你进去了，排队也能排到你思疑人生。

常见的限流算法

牢固窗口限流算法

首先保护一个计数器，将单元时候段当做一个窗口，计数器记录这个窗口接收请求的次数。

当次数少于限流阀值，就答应拜候，而且计数器+1
当次数大于限流阀值，就拒绝拜候。
当前的时候窗口曩昔以后，计数器清零。

假定单元时候是1秒，限流阀值为3。在单元时候1秒内，每来一个请求,计数器就加1，假如计数器累加的次数跨越限流阀值3，后续的请责备部拒绝。等到1s竣事后，计数器清0，重新起头计数。以下图：

后端法式员必备：四种限流算法，图文连系一篇搞定

伪代码以下：

    /**     * 牢固窗口时候算法     * @return     */    boolean fixedWindowsTryAcquire() {        long currentTime = System.currentTimeMillis();  //获得系统当前时候        if (currentTime - lastRequestTime > windowUnit) {  //检查能否在时候窗口内            counter = 0;  // 计数器清0            lastRequestTime = currentTime;  //开启新的时候窗口        }        if (counter < threshold) {  // 小于阀值            counter++;  //计数器加1            return true;        }        return false;    }

可是，这类算法有一个很明显的临界题目：假定限流阀值为5个请求，单元时候窗口是1s,假如我们在单元时候内的前0.8-1s和1-1.2s，别离并发5个请求。虽然都没有跨越阀值，可是假如算0.8-1.2s,则并发数高达10，已经跨越单元时候1s不跨越5阀值的界说啦。

后端法式员必备：四种限流算法，图文连系一篇搞定

滑动窗口限流算法

滑动窗口限流处理牢固窗口临界值的题目。它将单元时候周期分为n个小周期，别离记录每个小周期内接口的拜候次数，而且按照时候滑动删除过期的小周期。

一张图诠释滑动窗口的算法，以下：

后端法式员必备：四种限流算法，图文连系一篇搞定

假定单元时候还是1s，滑动窗口算法把它分别为5个小周期，也就是滑动窗口（单元时候）被分别为5个小格子。每格暗示0.2s。每过0.2s，时候窗口就会往右滑动一格。然后呢，每个小周期，都有自己自力的计数器，假如请求是0.83s到达的，0.8~1.0s对应的计数器就会加1。

我们来看下滑动窗口是若何处理临界题目标？

假定我们1s内的限流阀值还是5个请求，0.8~1.0内（比如0.9s的时辰）来了5个请求，落在黄色格子里。时候过了1.0s以后，又来5个请求，落在紫色格子里。假如是牢固窗口算法，是不会限流的，可是滑动窗口的话，每过一个小周期，它会右移一个小格。过了1.0s后，会右移一小格，当前的单元时候段是0.2~1.2s，这个地区的请求已经跨越限制的5了，已触发限流啦，现实上，紫色格子的请求都被拒绝啦。

TIPS: 当滑动窗口的格子周期分别得越多，那末滑动窗口的转动就越平滑，限流的统计就会越切确。