分布式限流器学习笔记

一、限流器算法

1.1、固定窗口计数器

• 图示

• 实现概念

  • 将时间划分为多个窗口；
  • 在每个窗口内每有一次请求就将计数器加一；
  • 如果计数器超过了限制数量，则本窗口内所有的请求都被丢弃当时间到达下一个窗口时，计数器重置。

• 问题

固定窗口计数器是最为简单的算法，但这个算法有时会让通过请求量允许为限制的两倍。考虑如下情况：限制 1 秒内最多通过 5 个请求，在第一个窗口的最后半秒内通过了 5 个请求，第二个窗口的前半秒内又通过了 5 个请求。这样看来就是在 1 秒内通过了 10 个请求。

1.2、滑动窗口计数器

• 图示

• 相关概念
  • 将时间划分为多个区间；
  • 在每个区间内每有一次请求就将计数器加一维持一个时间窗口，占据多个区间；
  • 每经过一个区间的时间，则抛弃最老的一个区间，并纳入最新的一个区间；
  • 如果当前窗口内区间的请求计数总和超过了限制数量，则本窗口内所有的请求都被丢弃。

1.3、令牌桶模式

• 图示

• 令牌桶算法概念如下
  • 令牌以固定速率生成
  • 生成的令牌放入令牌桶中存放，如果令牌桶满了则多余的令牌会直接丢弃，当请求到达时，会尝试从令牌桶中取令牌，取到了令牌的请求可以执行
  • 如果桶空了，那么尝试取令牌的请求会被直接丢弃。
• 优点

令牌桶算法既能够将所有的请求平均分布到时间区间内，又能接受服务器能够承受范围内的突发请求，因此是目前使用较为广泛的一种限流算法。

1.4、漏桶模式

• 图示

• 算法解析

  • 将每个请求视作”水滴”放入”漏桶”进行存储；
  • “漏桶”以固定速率向外”漏”出请求来执行如果”漏桶”空了则停止”漏水”；
  • 如果”漏桶”满了则多余的”水滴”会被直接丢弃。

• 缺点

  • 当短时间内有大量的突发请求时，即便此时服务器没有任何负载，每个请求也都得在队列中等待一段时间才能被响应。

二、单机限流实现

2.1、Guava RateLimiter

2.1.1、相关实现

RateLimiter：抽象类，定义了主要的对外接口以及整个流程的模板
SmoothRateLimiter：RateLimiter的实现类，实现了RateLimiter的部分方法
SmoothWarmingUp：SmoothRateLimiter的实现类，渐进模式，令牌生成速度缓慢提升直到维持在一个稳定值
SmoothBursty：SmoothRateLimiter的实现类，稳定模式，令牌生成速度恒定

2.1.2、关键参数

/**
   * The currently stored permits.
   * 当前存储的令牌数
   */
  double storedPermits;
  /**
   * The maximum number of stored permits.
   * 最大能存储的令牌数
   */
  double maxPermits;
  /**
   * The interval between two unit requests, at our stable rate. E.g., a stable rate of 5 permits
   * per second has a stable interval of 200ms.
   * 添加令牌的时间间隔
   */
  double stableIntervalMicros;
  /**
   * The time when the next request (no matter its size) will be granted. After granting a
   * request, this is pushed further in the future. Large requests push this further than small
   * requests.
   * 下一次请求可以获取令牌的起始时间
   * 由于RateLimiter允许预消费，上次请求预消费令牌后
   * 下次请求需要等待相应的时间到nextFreeTicketMicros时刻才可以获取令牌
   */
  private long nextFreeTicketMicros = 0L; // could be either in the past or future

2.1.2、设置令牌发放速率

• doSetRate ```java //com.google.common.util.concurrent.SmoothRateLimiter#doSetRate(double, long)
  @Override final void doSetRate(double permitsPerSecond, long nowMicros) {

  //更新令牌

  resync(nowMicros);

  //计算每个令牌发放间隔 200ms

  double stableIntervalMicros = SECONDS.toMicros(1L) / permitsPerSecond; this.stableIntervalMicros = stableIntervalMicros; doSetRate(permitsPerSecond, stableIntervalMicros); }

@Override void doSetRate(double permitsPerSecond, double stableIntervalMicros) { double oldMaxPermits = this.maxPermits; //最大令牌数 maxPermits = maxBurstSeconds permitsPerSecond; if (oldMaxPermits == Double.POSITIVE_INFINITY) { // if we don’t special-case this, we would get storedPermits == NaN, below storedPermits = maxPermits; } else { storedPermits = (oldMaxPermits == 0.0) ? 0.0 // initial state : storedPermits maxPermits / oldMaxPermits; } }

<a name="arQso"></a>
#### 2.1.3、更新令牌
```java
void resync(long nowMicros) {
    // if nextFreeTicket is in the past, resync to now
    //如果下次发放时间 小于 当前时间    
    if (nowMicros > nextFreeTicketMicros) {
        //计算归还令牌数
        //如果速率是 每秒发放5个令牌
        //时间间隔 (nowMicros - nextFreeTicketMicros) = 0.5秒 = 500ms
        // coolDownIntervalMicros() = 每个领牌间隔 200ms
        // 新发放令牌数是 500ms / 200ms = 2.5 个令牌
      double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
        //更新令牌数量
      storedPermits = min(maxPermits, storedPermits + newPermits);
        //更新下次令牌发放时间
      nextFreeTicketMicros = nowMicros;
    }
  }
class SmoothBursty{
    @Override
    double coolDownIntervalMicros() {
        //稳定发放速率时间间隔
        //如：每秒发放5个令牌，则每个领牌间隔 200ms
      return stableIntervalMicros;
    }
}

2.1.3、消费令牌

  @Override
  final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
    resync(nowMicros);
    long returnValue = nextFreeTicketMicros;
      //获取需要的令牌
    double storedPermitsToSpend = min(requiredPermits, this.storedPermits);
    double freshPermits = requiredPermits - storedPermitsToSpend;
      //计算下次令牌等待时间
    long waitMicros =
        storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
            + (long) (freshPermits * stableIntervalMicros);
    // 更新 nextFreeTicketMicros，这里更新的其实是下一次请求的时间，是一种“预消费”
    //目的是等当前请求的令牌数全部得到后，才进行下一次请求
    this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
        //更新令牌
      this.storedPermits -= storedPermitsToSpend;
    return returnValue;
  }

三、分布式限流实现

3.1、Redis + Lua 脚本

• 令牌桶实现 ```lua — 令牌桶限流: 不支持预消费, 初始桶是满的 — KEYS[1] string 限流的key

— ARGV[1] int 桶最大容量 — ARGV[2] int 每次添加令牌数 — ARGV[3] int 令牌添加间隔(秒) — ARGV[4] int 当前时间戳

local bucket_capacity = tonumber(ARGV[1]) local add_token = tonumber(ARGV[2]) local add_interval = tonumber(ARGV[3]) local now = tonumber(ARGV[4])

— 保存上一次更新桶的时间的key local LAST_TIME_KEY = KEYS[1]..”_time”;
— 获取当前桶中令牌数 local token_cnt = redis.call(“get”, KEYS[1])
— 桶完全恢复需要的最大时长 local reset_time = math.ceil(bucket_capacity / add_token) * add_interval;

if token_cnt then — 令牌桶存在 — 上一次更新桶的时间 local last_time = redis.call(‘get’, LAST_TIME_KEY) — 恢复倍数 local multiple = math.floor((now - last_time) / add_interval) — 恢复令牌数 local recovery_cnt = multiple * add_token — 确保不超过桶容量 local token_cnt = math.min(bucket_capacity, token_cnt + recovery_cnt) - 1

if token_cnt < 0 then
    return -1;
end
-- 重新设置过期时间, 避免key过期
redis.call('set', KEYS[1], token_cnt, 'EX', reset_time)                     
redis.call('set', LAST_TIME_KEY, last_time + multiple * add_interval, 'EX', reset_time)
return token_cnt

else — 令牌桶不存在 token_cnt = bucket_capacity - 1 — 设置过期时间避免key一直存在 redis.call(‘set’, KEYS[1], token_cnt, ‘EX’, reset_time); redis.call(‘set’, LAST_TIME_KEY, now, ‘EX’, reset_time + 1);
return token_cnt
end ```

3.2、Redisson 版本实现

四、其他限流处理

4.1、前端处理

4.1.1、前端节流（throttle）

4.1.2、防抖动（debounce）

4.2、Nginx 限流

4.2.1、请求数限流

4.2.2、连接数限流

参考

• https://segmentfault.com/a/1190000019477128
• https://www.infoq.cn/article/qg2tx8fyw5vt-f3hh673
• https://juejin.cn/post/6915591543797596174