常用限流算法详解 - HelloWorld开发者社区

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

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.漏桶算法

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

public class LeakyBucketRateLimiter extends MyRateLimiter {
    // 桶的容量
    private final int capacity;
    // 漏出速率
    private final int permitsPerSecond;
    // 剩余水量
    private long leftWater;
    // 上次注入时间
    private long timeStamp = System.currentTimeMillis();

    public LeakyBucketRateLimiter(int permitsPerSecond, int capacity) {
        this.capacity = capacity;
        this.permitsPerSecond = permitsPerSecond;
    }

    @Override
    public synchronized boolean tryAcquire() {
        //1. 计算剩余水量
        long now = System.currentTimeMillis();
        long timeGap = (now - timeStamp) / 1000;
        leftWater = Math.max(0, leftWater - timeGap * permitsPerSecond);
        timeStamp = now;

        // 如果未满，则放行；否则限流
        if (leftWater < capacity) {
            leftWater += 1;
            return true;
        }
        return false;
    }
}

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

4.令牌桶算法

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

public class TokenBucketRateLimiter extends MyRateLimiter {
    /**
     * 令牌桶的容量「限流器允许的最大突发流量」
     */
    private final long capacity;
    /**
     * 令牌发放速率
     */
    private final long generatedPerSeconds;
    /**
     * 最后一个令牌发放的时间
     */
    long lastTokenTime = System.currentTimeMillis();
    /**
     * 当前令牌数量
     */
    private long currentTokens;

    public TokenBucketRateLimiter(long generatedPerSeconds, int capacity) {
        this.generatedPerSeconds = generatedPerSeconds;
        this.capacity = capacity;
    }

    /**
     * 尝试获取令牌
     *
     * @return true表示获取到令牌，放行；否则为限流
     */
    @Override
    public synchronized boolean tryAcquire() {
          /**
           * 计算令牌当前数量
           * 请求时间在最后令牌是产生时间相差大于等于额1s（为啥时1s？因为生成令牌的最小时间单位时s），则
           * 1. 重新计算令牌桶中的令牌数
           * 2. 将最后一个令牌发放时间重置为当前时间
           */
        long now = System.currentTimeMillis();
        if (now - lastTokenTime >= 1000) {
            long newPermits = (now - lastTokenTime) / 1000 * generatedPerSeconds;
            currentTokens = Math.min(currentTokens + newPermits, capacity);
            lastTokenTime = now;
        }
        if (currentTokens > 0) {
            currentTokens--;
            return true;
        }
        return false;
    }
}

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

local ratelimit_info = redis.pcall('HMGET',KEYS[1],'last_time','current_token')
local last_time = ratelimit_info[1]
local current_token = tonumber(ratelimit_info[2])
local max_token = tonumber(ARGV[1])
local token_rate = tonumber(ARGV[2])
local current_time = tonumber(ARGV[3])
local reverse_time = 1000/token_rate
if current_token == nil then
  current_token = max_token
  last_time = current_time
else
  local past_time = current_time-last_time
  local reverse_token = math.floor(past_time/reverse_time)
  current_token = current_token+reverse_token
  last_time = reverse_time*reverse_token+last_time
  if current_token>max_token then
    current_token = max_token
  end
end
local result = 0
if(current_token>0) then
  result = 1
  current_token = current_token-1
end
redis.call('HMSET',KEYS[1],'last_time',last_time,'current_token',current_token)
redis.call('pexpire',KEYS[1],math.ceil(reverse_time*(max_token-current_token)+(current_time-last_time)))
return result

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