限流

限流对资源进行速率限制，即在一个时间窗口内对请求加限制。

阈值：单位时间内允许的请求量。例如 QPS 是10，就是1秒最多10个请求

拒绝策略：超过阈值的处理出策略，例如直接抛弃，排队等待。

固定窗口算法

• 将时间划分为多个窗口

• 每个窗口内有一次请求就将计数器+1

• 如果计数器超过了阈值，后续请求使用拒绝策略

• 下一个时间窗口，计数器重置

滑动窗口算法

• 将时间划分为多个区间

• 每个区间内有一次请求就将计数器+1，一个时间窗口占据多个区间

• 每经过一个区间的时间，抛弃最老的区间，纳入新区间

• 如果当前窗口计数器超过阈值，后续请求使用拒绝策略

漏桶算法

• 恒定速率通过请求

• 当短时间内大量突发请求时，每个请求都要在队列中等待。

令牌桶算法

• 令牌以固定速率生成

• 生成的令牌放入桶中存放，请求到达时，尝试从桶中获取令牌，取到了令牌才可执行

• 令牌桶空了，后续请求使用决绝策略

是目前广泛使用的限流算法。

实际应用

Google的开源项目 guava 提供了 RateLimiter ，实现了单点的 令牌桶 限流。

// qps 2
RateLimiter rateLimiter = RateLimiter.create(2);
for (int i = 0; i < 10; i++) {
    String time = LocalDateTime.now().format(DateTimeFormatter.ISO_LOCAL_TIME);
    System.out.println(time + ":" + rateLimiter.tryAcquire());
    Thread.sleep(250);
}

如果按照时间间隔区添加令牌，那么需要一个单独的线程去定时添加，如果有很多个 RateLimiter 实例，线程数也会随着增加，显然这不是一个好方法。Google 也考虑到了这个问题，在 RateLimiter 中，是在每次令牌获取时才进行计算令牌是否足够的。它通过存储的下一个令牌生成的时间，和当前获取令牌的时间差，再结合阈值，去计算令牌是否足够，同时再记录下一个令牌的生成时间以便下一次调用。

  // 申请令牌
  public double acquire(int permits) {
      //下一个令牌需要的等待时间
      long microsToWait = reserve(permits);
      //Thread.sleep
      stopwatch.sleepMicrosUninterruptibly(microsToWait);
      return 1.0 * microsToWait / SECONDS.toMicros(1 L);
  }

  //最终调用
  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);

      this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros);
      this.storedPermits -= storedPermitsToSpend;
      return returnValue;
  }

  //超时 重置令牌数
  void resync(long nowMicros) { // 当前微秒时间
      // 如果超时 更新存储的令牌数量
      if (nowMicros > this.nextFreeTicketMicros) {
          double newPermits = (double)(nowMicros - this.nextFreeTicketMicros) / this.coolDownIntervalMicros();
          // 更新令牌库存 storedPermits。
          this.storedPermits = Math.min(this.maxPermits, this.storedPermits + newPermits);
          // 更新下一个令牌生成时间 nextFreeTicketMicros
          this.nextFreeTicketMicros = nowMicros;
      }
  }

为了避免启动时就有阈值数量的请求过来，可以使用有预热功能的 RateLimiter。如果在预热器内未使用，它会逐渐回到冷状态。

RateLimiter create(double permitsPerSecond, long warmupPeriod, TimeUnit unit)