常见的限流算法 | 熊猫小二

常见限流算法有哪些？

简单介绍4种非常好理解并且容易实现的限流算法！

图片来源于InfoQ的一篇文章《分布式服务限流实战，已经为你排好坑了》。

固定窗口计数器算法

固定窗口其实就是时间窗口。固定窗口计数器算法规定了我们单位时间处理的请求数量。假如我们规定系统中某个接口1分钟只能访问33次的话，使用固定窗口计数器算法的实现思路如下：

给定一个变量counter来记录当前接口处理的请求数量，初始值为0（代表接口当前1分钟内还未处理请求）。
1分钟之内每处理一个请求之后就将counter+1，当counter=33之后（也就是说在这1分钟内接口已经被访问33次的话），后续的请求就会被全部拒绝。
等到1分钟结束后，将counter重置0，重新开始计数。

这种限流算法无法保证限流速率，因而无法保证突然激增的流量。就比如说我们限制某个接口1分钟只能访问1000次，该接口的QPS为500，前55s这个接口1个请求没有接收，后1s突然接收了1000个请求。然后，在当前场景下，这1000个请求在1s内是没办法被处理的，系统直接就被瞬时的大量请求给击垮了。

固定窗口计数器算法

滑动窗口计数器算法

滑动窗口计数器算法算的上是固定窗口计数器算法的升级版。滑动窗口计数器算法相比于固定窗口计数器算法的优化在于：它把时间以一定比例分片。例如我们的接口限流每分钟处理60个请求，我们可以把1分钟分为60个窗口。每隔1秒移动一次，每个窗口一秒只能处理不大于60(请求数)/60（窗口数）的请求，如果当前窗口的请求计数总和超过了限制的数量的话就不再处理其他请求。很显然，当滑动窗口的格子划分的越多，滑动窗口的滚动就越平滑，限流的统计就会越精确。

滑动窗口计数器算法

漏桶算法

我们可以把发请求的动作比作成注水到桶中，我们处理请求的过程可以比喻为漏桶漏水。我们往桶中以任意速率流入水，以一定速率流出水。当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。如果想要实现这个算法的话也很简单，准备一个队列用来保存请求，然后我们定期从队列中拿请求来执行就好了（和消息队列削峰/限流的思想是一样的）。

漏桶算法

令牌桶算法

令牌桶算法也比较简单。和漏桶算法算法一样，我们的主角还是桶。不过现在桶里装的是令牌了，请求在被处理之前需要拿到一个令牌，请求处理完毕之后将这个令牌丢弃（删除）。我们根据限流大小，按照一定的速率往桶里添加令牌。如果桶装满了，就不能继续往里面继续添加令牌了。

令牌桶算法

单机限流怎么做？

单机限流针对的是单体架构应用。单机限流可以直接使用Google Guava自带的限流工具类RateLimiter。RateLimiter基于令牌桶算法，可以应对突发流量。

Guava地址

除了最基本的令牌桶算法(平滑突发限流)实现之外，Guava的RateLimiter还提供了平滑预热限流的算法实现。平滑突发限流就是按照指定的速率放令牌到桶里，而平滑预热限流会有一段预热时间，预热时间之内，速率会逐渐提升到配置的速率。

实战

<dependency>
    <groupId>com.google.guava</groupId>
    <artifactId>guava</artifactId>
    <version>31.0.1-jre</version>
</dependency>

下面是一个简单的Guava平滑突发限流的Demo。

import com.google.common.util.concurrent.RateLimiter;
public class RateLimiterDemo {
    public static void main(String[] args) {
        // 1s放5个令牌到桶里也就是0.2s放1个令牌到桶里
        RateLimiter rateLimiter = RateLimiter.create(5);
        for (int i = 0; i < 10; i++) {
            double sleepingTime = rateLimiter.acquire(1);
            System.out.printf("get 1 tokens: %ss%n", sleepingTime);
        }
    }
}

输出：

get 1 tokens: 0.0s
get 1 tokens: 0.188413s
get 1 tokens: 0.197811s
get 1 tokens: 0.198316s
get 1 tokens: 0.19864s
get 1 tokens: 0.199363s
get 1 tokens: 0.193997s
get 1 tokens: 0.199623s
get 1 tokens: 0.199357s
get 1 tokens: 0.195676s

下面是一个简单的Guava平滑预热限流的Demo。

import com.google.common.util.concurrent.RateLimiter;
import java.util.concurrent.TimeUnit;
public class RateLimiterDemo {
    public static void main(String[] args) {
        // 1s放5个令牌到桶里也就是0.2s放1个令牌到桶里
        // 预热时间为3s,也就说刚开始的3s内发牌速率会逐渐提升到0.2s放1个令牌到桶里
        RateLimiter rateLimiter = RateLimiter.create(5, 3, TimeUnit.SECONDS);
        for (int i = 0; i < 20; i++) {
            double sleepingTime = rateLimiter.acquire(1);
            System.out.printf("get 1 tokens: %sds%n", sleepingTime);
        }
    }
}

输出：

get 1 tokens: 0.0s
get 1 tokens: 0.561919s
get 1 tokens: 0.516931s
get 1 tokens: 0.463798s
get 1 tokens: 0.41286s
get 1 tokens: 0.356172s
get 1 tokens: 0.300489s
get 1 tokens: 0.252545s
get 1 tokens: 0.203996s
get 1 tokens: 0.198359s

另外，Bucket4j是一个非常不错的基于令牌/漏桶算法的限流库。

Bucket4j地址

相对于，Guava的限流工具类来说，Bucket4j提供的限流功能更加全面。不仅支持单机限流和分布式限流，还可以集成监控，搭配Prometheus和Grafana使用。不过，毕竟Guava也只是一个功能全面的工具类库，其提供的开箱即用的限流功能在很多单机场景下还是比较实用的。Spring Cloud Gateway中自带的单机限流的早期版本就是基于Bucket4j实现的。后来，替换成了Resilience4j。Resilience4j是一个轻量级的容错组件，其灵感来自于Hystrix。自Netflix宣布不再积极开发Hystrix之后，Spring官方和Netflix都更推荐使用Resilience4j来做限流熔断。

Resilience4j地址

一般情况下，为了保证系统的高可用，项目的限流和熔断都是要一起做的。Resilience4j不仅提供限流，还提供了熔断、负载保护、自动重试等保障系统高可用开箱即用的功能。并且，Resilience4j的生态也更好，很多网关都使用Resilience4j来做限流熔断的。因此，在绝大部分场景下Resilience4j或许会是更好的选择。如果是一些比较简单的限流场景的话，Guava或者Bucket4j也是不错的选择。

分布式限流怎么做？

分布式限流针对的分布式/微服务应用架构应用，在这种架构下，单机限流就不适用了，因为会存在多种服务，并且一种服务也可能会被部署多份。

分布式限流常见的方案：

借助中间件架限流：可以借助Sentinel或者使用Redis来自己实现对应的限流逻辑。
网关层限流：比较常用的一种方案，直接在网关层把限流给安排上了。不过，通常网关层限流通常也需要借助到中间件/框架。就比如Spring Cloud Gateway的分布式限流实现RedisRateLimiter就是基于Redis+Lua来实现的，再比如SpringCloudGateway还可以整合Sentinel来做限流。

如果你要基于Redis来手动实现限流逻辑的话，建议配合Lua脚本来做。为什么建议Redis+Lua的方式？主要有两点原因：