常用限流算法详解

一、有哪些常用的限流算法

1.固定窗口限流； 2.滑动窗口限流； 3.漏桶算法限流； 4.令牌桶算法限流。

二、4种限流算法介绍

1.固定窗口限流

举例说明：假设时间窗口大小为5s，则0到5s为第一个窗口，5到10s为第二个窗口，依次类推。假设限流规则为：5s内只能接受5个请求，如果在第1s的时候过来6个请求，那第6个请求会被拒绝，以及后续过来的请求都会被拒绝，知道开启一个新的窗口即第二个窗口，计数累计从0再开始。

考虑以下场景：在第4s的时候过来5个请求，按照算法这四个请求都会被处理，然后在第6s的时候也过来5个请求，按照算法这是第二个窗口的请求了，也能够被正常处理。也就是在第4s到第6s这个时间段内处理了10个请求，这其实没有达到我们预期的限流规则：5s内只能接受5个请求。

以上场景就是固定窗口限流最大的问题：第一个窗口与第二个窗口临界没有平滑过度！

2.滑动窗口

为了解决固定窗口限流的临界问题，就引入了滑动窗口算法。那滑动窗口是如何解决的呢？滑动窗口首先把1个固定窗口再细分为多个小窗口，继续接着上文的例子，把0到5s拆分为5个小窗口：0-1, 1-2, 2-3, 3-4, 4-5;同理6到10s也拆分为5个小窗口:5-6, 6-7, 7-8, 8-9, 9-10;然后每个小窗口都有自己的计数（1）在第5s的时候统计的是：0-1, 1-2, 2-3, 3-4, 4-5这5个小窗口的计数之和；（2）在第6s的时候统计的是：1-2, 2-3, 3-4, 4-5, 5-6这5个小窗口的计数之后；（3）在第7s的时候统计的是：2-3, 3-4, 4-5, 5-6, 6-7这5个小窗口的计数之后；依次类推再回到上文中，第4s有5个请求过来，第6s有5个请求过来，按照滑动窗口的算法，第6s过来的5个请求会全部被拒绝，这就解决了固定窗口的临界问题。总结：通过把固定窗口拆分为更小的窗口的方式，来解决临界问题，窗口拆分的越细，限流就会越精确，但是算法的时间复杂度和空间复杂度也会越高。

3.漏桶算法

简单描述就是水流入速度不固定，但是流出速度是固定的，如果桶满了，水就漏出来了。单机代码实现如下：

1public class LeakyBucketRateLimiter extends MyRateLimiter {
2    // 桶的容量
3    private final int capacity;
4    // 漏出速率
5    private final int permitsPerSecond;
6    // 剩余水量
7    private long leftWater;
8    // 上次注入时间
9    private long timeStamp = System.currentTimeMillis();
10
11    public LeakyBucketRateLimiter(int permitsPerSecond, int capacity) {
12        this.capacity = capacity;
13        this.permitsPerSecond = permitsPerSecond;
14    }
15
16    @Override
17    public synchronized boolean tryAcquire() {
18        //1. 计算剩余水量
19        long now = System.currentTimeMillis();
20        long timeGap = (now - timeStamp) / 1000;
21        leftWater = Math.max(0, leftWater - timeGap * permitsPerSecond);
22        timeStamp = now;
23
24        // 如果未满，则放行；否则限流
25        if (leftWater < capacity) {
26            leftWater += 1;
27            return true;
28        }
29        return false;
30    }
31}

漏桶算法不能应对突发流量，不能充分利用系统资源，适用于流量绝对平滑的场景

4.令牌桶算法

令牌痛算法就是按照固定速率往桶里面丢令牌，如果桶满了则不会继续丢，每个请求过来的时候都会去桶里面获取令牌，如果获取到则继续处理请求，否则拒绝请求。令牌桶算法是对漏桶算法的优化，允许系统的突发流量，但是又能保证平滑限流。单机代码如下：

1public class TokenBucketRateLimiter extends MyRateLimiter {
2    /**
3     * 令牌桶的容量「限流器允许的最大突发流量」
4     */
5    private final long capacity;
6    /**
7     * 令牌发放速率
8     */
9    private final long generatedPerSeconds;
10    /**
11     * 最后一个令牌发放的时间
12     */
13    long lastTokenTime = System.currentTimeMillis();
14    /**
15     * 当前令牌数量
16     */
17    private long currentTokens;
18
19    public TokenBucketRateLimiter(long generatedPerSeconds, int capacity) {
20        this.generatedPerSeconds = generatedPerSeconds;
21        this.capacity = capacity;
22    }
23
24    /**
25     * 尝试获取令牌
26     *
27     * @return true表示获取到令牌，放行；否则为限流
28     */
29    @Override
30    public synchronized boolean tryAcquire() {
31          /**
32           * 计算令牌当前数量
33           * 请求时间在最后令牌是产生时间相差大于等于额1s（为啥时1s？因为生成令牌的最小时间单位时s），则
34           * 1. 重新计算令牌桶中的令牌数
35           * 2. 将最后一个令牌发放时间重置为当前时间
36           */
37        long now = System.currentTimeMillis();
38        if (now - lastTokenTime >= 1000) {
39            long newPermits = (now - lastTokenTime) / 1000 * generatedPerSeconds;
40            currentTokens = Math.min(currentTokens + newPermits, capacity);
41            lastTokenTime = now;
42        }
43        if (currentTokens > 0) {
44            currentTokens--;
45            return true;
46        }
47        return false;
48    }
49}

分布式基于redis+lua代码如下：

1local ratelimit_info = redis.pcall('HMGET',KEYS[1],'last_time','current_token')
2local last_time = ratelimit_info[1]
3local current_token = tonumber(ratelimit_info[2])
4local max_token = tonumber(ARGV[1])
5local token_rate = tonumber(ARGV[2])
6local current_time = tonumber(ARGV[3])
7local reverse_time = 1000/token_rate
8if current_token == nil then
9  current_token = max_token
10  last_time = current_time
11else
12  local past_time = current_time-last_time
13  local reverse_token = math.floor(past_time/reverse_time)
14  current_token = current_token+reverse_token
15  last_time = reverse_time*reverse_token+last_time
16  if current_token>max_token then
17    current_token = max_token
18  end
19end
20local result = 0
21if(current_token>0) then
22  result = 1
23  current_token = current_token-1
24end
25redis.call('HMSET',KEYS[1],'last_time',last_time,'current_token',current_token)
26redis.call('pexpire',KEYS[1],math.ceil(reverse_time*(max_token-current_token)+(current_time-last_time)))
27return result

代码参考：https://www.infoq.cn/article/qg2tx8fyw5vt-f3hh673

5.限流算法整体对比

（1）QPS 限流算法（固定窗口和滑动窗口）通过限制单位时间内允许通过的请求数来限流。

优点：

计算简单，是否限流只跟请求数相关，放过的请求数是可预知的（令牌桶算法放过的请求数还依赖于流量是否均匀），比较符合用户直觉和预期。

可以通过拉长限流周期来应对突发流量。如 1 秒限流 10 个，想要放过瞬间 20 个请求，可以把限流配置改成 3 秒限流 30 个。拉长限流周期会有一定风险，用户可以自主决定承担多少风险。

缺点：放过的请求不均匀。突发流量时，请求总在限流周期的前一部分放过。如 10 秒限 100 个，高流量时放过的请求总是在限流周期的第一秒。

（2）令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌，而如果请求需要被处理，则需要先从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务。

优点：

放过的流量比较均匀，有利于保护系统。

存量令牌能应对突发流量，很多时候，我们希望能放过脉冲流量。而对于持续的高流量，后面又能均匀地放过不超过限流值的请求数。

缺点：

存量令牌没有过期时间，突发流量时第一个周期会多放过一些请求，可解释性差。即在突发流量的第一个周期，默认最多会放过 2 倍限流值的请求数。

实际限流数难以预知，跟请求数和流量分布有关。