RateLimiter

1. 高并发时有三把利器来保护系统：缓存、降级和限流

   1. 缓存：缓存目的是提升系统访问速度和增大系统处理容量

   2. 降级：降级是当服务出现问题或者影响核心流程时，需要暂时屏蔽掉，待高峰或者问题解决后再打开

   3. 限流：限流的目的是通过对并发访问、请求进行限速，或者对一个时间窗口内的请求进行限速来保护系统，一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理

2. 常用限流算法

   1. 固定窗口，存在临界问题，如果流量都集中在两个窗口交界处，突发流量会是设置的两倍

   2. 滑动窗口是通过将窗口细分，并且按照时间滑动，这种算法避免了固定窗口算法带来的双倍突发请求。

   3. 漏桶算法，请求来了先放进桶里，不做处理，并以限定速度出水，出水相当于请求。当水来的过猛而出水不够快时就会导致水溢出，拒绝服务

   4. 令牌桶算法，系统以恒定速率往一个桶里放入令牌，而如果请求需要被处理，则需要从桶里获取一个令牌，当桶里没有令牌可取时，则拒绝服务

   5. 漏桶算法和令牌桶算法区别在于，漏桶算法能够强行限制数据的传输速率，令牌桶算法能够在限制数据的平均速率的同时还允许某种程度的突发传输

3. 信号量（Semaphore）

   1. 信号量的本质是控制某个资源可被同时访问的个数，在一定程度上可以控制某资源的访问频率，但不能精确控制

4. RateLimiter

1. Guava有两种限流模式，一种为稳定模式(SmoothBursty:令牌生成速度恒定)，一种为渐进模式(SmoothWarmingUp:令牌生成速度缓慢提升直到维持在一个稳定值)

2. 在解析SmoothBursty原理前，重点解释下SmoothBursty中几个属性的含义

/**
 * 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

1. 令牌生成

void resync(long nowMicros) {
    // if nextFreeTicket is in the past, resync to now
    if (nowMicros > nextFreeTicketMicros) {
      double newPermits = (nowMicros - nextFreeTicketMicros) / coolDownIntervalMicros();
      storedPermits = min(maxPermits, storedPermits + newPermits);
      nextFreeTicketMicros = nowMicros;
    }
}

1. 根据令牌桶算法，桶中令牌是持续生成存放的，有请求时，从桶中取出，那么谁来持续生成令牌存放呢

   1. 开启定时任务，持续生成，但是会极大的消耗资源，如，某一个接口需要对每个用户做访问频率限制，假设系统中有6w个用户，则需要开启6w个定时任务

   2. 延迟计算，如上resync函数，该函数会在每次获取令牌之前调用，其实现思路为，若当前时间晚于nextFreeTicketMicros，则计算该段时间内可以生成多少个令牌，将生成的令牌加入令牌桶中并更新数据。这样一来只需要在获取令牌时计算一次即可。

2. 等待时间

final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
  resync(nowMicros);
  long returnValue = nextFreeTicketMicros; // 返回的是上次计算的nextFreeTicketMicros
  double storedPermitsToSpend = min(requiredPermits, this.storedPermits); // 可以消费的令牌数
  double freshPermits = requiredPermits - storedPermitsToSpend; // 还需要的令牌数
  long waitMicros =
      storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend)
          + (long) (freshPermits * stableIntervalMicros); // 根据freshPermits计算需要等待的时间

  this.nextFreeTicketMicros = LongMath.saturatedAdd(nextFreeTicketMicros, waitMicros); // 本次计算的nextFreeTicketMicros不返回
  this.storedPermits -= storedPermitsToSpend;
  return returnValue;
}

1. 该函数用户获取requirePermits个令牌，并返回需要等待到的时间点，其中，storedPermitsToSpend为桶中可以消费的令牌数，freshPermits为还需要的（需要补充的）令牌数，根据该值计算需要等待的时间，追加更新到nextFreeTicketMicros。需要注意的是，该函数返回的是更新前（上次请求计算的）nextFreeTicketMicros，而不是本次更新的nextFreeTicketMicros，通俗来讲，本次请求需要为上次请求的预消费行为埋单，这也是RateLimiter可以预消费（处理突发）的原理所在。若需要禁止，则修改此处返回更新后的nextFreeTicketMicros值。