1、常见限流算法有哪些？

限流算法有很多种，常见工作使用的一般是以下几种：
分别是：固定窗口计数器算法、滑动窗口计数器算法、漏桶算法、和令牌桶算法

固定窗口计数器算法

固定窗口其实就是时间窗口。固定窗口计数器算法 规定了我们单位时间处理的请求数量。

假如我们规定系统中某个接口 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（窗口数） 的请求， 如果当前窗口的请求计数总和超过了限制的数量的话就不再处理其他请求。

很显然， 当滑动窗口的格子划分的越多，滑动窗口的滚动就越平滑，限流的统计就会越精确。

漏桶算法

我们可以把发请求的动作比作成注水到桶中，我们处理请求的过程可以比喻为漏桶漏水。我们往桶中以任意速率流入水，以一定速率流出水。当水超过桶流量则丢弃，因为桶容量是不变的，保证了整体的速率。

如果想要实现这个算法的话也很简单，准备一个队列用来保存请求，然后我们定期从队列中拿请求来执行就好了（和消息队列削峰/限流的思想是一样的）

漏桶算法

令牌桶算法

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

令牌桶算法

2、单机限流怎么做

单机限流针对的是单体架构应用。

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

除了最基本的令牌桶算法(平滑突发限流)实现之外，Guava 的RateLimiter还提供了 平滑预热限流 的算法实现。

平滑突发限流就是按照指定的速率放令牌到桶里，而平滑预热限流会有一段预热时间，预热时间之内，速率会逐渐提升到配置的速率。

我们下面通过两个简单的小例子来详细了解吧！我们直接在项目中引入 Guava 相关的依赖即可使用。

<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

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

分布式限流常见的方案：

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

为什么建议 Redis+Lua 的方式？
主要有两点原因：

• 减少了网络开销：我们可以利用 Lua 脚本来批量执行多条Redis 命令，这些 Redis 命令会被提交到 Redis 服务器一次性执行完成，大幅减小了网络开销。

• 原子性：一段 Lua 脚本可以视作一条命令执行，一段 Lua 脚本执行过程中不会有其他脚本或 Redis 命令同时执行，保证了操作不会被其他指令插入或打扰。

网上也有很多现成的优秀的限流脚本供你参考，就比如 Apache 网关项目 ShenYu的 RateLimiter 限流插件就基于 Redis + Lua 实现了令牌桶算法/并发令牌桶算法、漏桶算法、滑动窗口算法。