RateLimitAlgorithm

限流算法

为了保证接口调用的性能、稳定性和可用性，在网关层面通过Redisson的RateLimiter实现限流保护（1s最多请求1次）

我们需要控制用户使用系统的次数，以避免超支。但是限制用户调用次数仍存在一定风险，用户仍有可能疯狂调用来刷量，从而导致系统成本过度消耗。

限流（流量控制）：指系统在面临高并发，或者大流量请求的情况下，限制新的请求对系统的访问，从而保证系统的稳定性。限流会导致部分用户请求处理不及时或者被拒绝，影响了用户体验，所以一般需要在系统稳定和用户体验之间选择平衡。

问题：使用系统是需要消耗成本的，用户有可能疯狂刷量

解决方案：

1. 控制成本 => 限制用户调用次数
2. 用户在短时间内疯狂使用，导致服务器资源被占满，其他用户无法使用 => 限流

常见的限流算法

固定窗口限流算法

首先维护一个计数器，将单位时间段当做一个窗口，计数器记录这个窗口接收请求的次数

• 当次数小于限流阈值，就允许访问，并且计数器+1
• 当次数大于限流阈值，就拒绝访问
• 当前的时间窗口过去之后，计数器清零

【栗子🌰】假设单位时间是1秒，限流阈值是3。在单位时间1s内，每次来一个请求，计数器就+1，如果计数器累加的次数超过了限流阈值3，后续在1s内的请求全部拒绝。等到1s结束后，计数器清零，重新开始计数。

/**
  * 固定时间窗口限流算法（伪代码）
  * 
  * @return true - 请求在阈值内，正常响应
  */
boolean fixedWindowsTryAcquire() {
  // 获取当前系统的时间
  long currentTime = System.currentTimeMillis();
  // 检查是否在时间窗口内
  if (currentTime - lastReqTime > windowUnit) {
    // 不在时间窗口内，计数器清零
    counter = 0;
    // 开启新的时间窗口
    lastReqTime = currentTime;
  }
  // 判断计数器是否小于阈值
  if (counter < threshold) {
    // 小于阈值，计数器 + 1，正常响应请求
    counter++;
    return true;
  }
  // 超过阈值，拒绝响应
  return false;
}

问题：

这种算法存在一个很明显的临界问题：假设限流阈值为5个请求，单位时间窗口是1s，若我们在单位时间内的前[0.8, 1)和[1, 1.2)时间段内，分别发送5个请求，虽然都没有超过阈值，但是如果算这[0.8, 1.2)时间段内，并发数高达10，超过了单位时间1s不超过5阈值的定义。

滑动窗口限流算法

滑动窗口限流解决了固定窗口限流临界问题。它将单位时间周期分成n个小周期，分别记录每个小周期内接口的访问次数，并且根据时间滑动删除过期的小周期。

假设单位时间还是1s，滑动窗口算法把它划分成5个小周期，也就是滑动窗口（单位时间）被划分为5个小区间。每个区间代表0.2s。每过0.2s，时间窗口就会往右滑动一格。每个小周期都有自己独立的计数器，假设请求是在0.85s到达的，[0.8, 1.0)对应的计数器+1。

滑动窗口是如何解决固定窗口临界问题的呢？

假设1s内的限流阈值还是5，[0.8, 1.0)内来了5个请求，落在黄色格子内，时间点过了1.0s点之后，又来了5个请求，落在了虹色格子内。如果是固定窗口算法，是不会触发限流的，但是滑动窗口每过一个小周期，它会右移一小格。过了1.0s这个点后，右移一小格，也就是当前的单位时间段为[0.2, 1.2)，这个时间段内的请求已经超过阈值限定5了，触发了限流。实际上，红色格子的请求都会被拒绝。

当滑动窗口的格子周期划分的越多，滑动窗口的滚动越平滑，限流的统计就会越精确。

/**
  * 单位时间划分的小周期秒数（单位时间是1分钟，10s一个小格子窗口，一共6个格子）
  */
private int SUB_CYCLE = 10;

/**
  * 每分钟限流阈值
  */
private int perMinThreshold = 100;

/**
  * 计数器 {当前窗口的开始时间（秒）: 当前窗口的计数值}
  */
private final TreeMap<Long, Integer> COUNTER = new TreeMap<>();

/**
  * 滑动窗口时间算法实现（伪代码）
  * 
  * @return true - 请求在阈值内，正常响应
  */
boolean slidingWindowsTryAcquire() {
  // 获取当前时间在哪个小周期窗口
  long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE;
  int currWindowCount = countCurrWindow(currentWindowTime);

  // 判断是否超过阈值
  if (currWindowCount > perMinThreshold) {
    return false;
  }

  // 计数器 + 1
  COUNTER.put(currentWindowTime,
              (Objects.isNull(COUNTER.get(currentWindowTime)) ? 0 : CUNTER.get(currentWindowTime)) + 1);
  return true;
}

/**
  * 统计当前窗口的计数值
  */
private int countCurrWindow(long currentWindowTime) {
  // 计算窗口开始位置
  long startTime = currentWindowTime - SUB_CYCLE * (60 / SUB_CYCLE - 1);
  int count = 0;

  Iterator<Map.Entry<Long, Integer>> iterator = COUNTER.entrySet().iterator();
  while (iterator.hasNext()) {
    Map.Entry<Long, Integer> entry = iterator.next();
    // 删除无效过期的子窗口计数器
    if (entry.getKey() < startTime) {
      iterator.remove();
    } else {
      // 累加当前窗口的所有计数器之和
      count += entry.getValue();
    }
  }
  return count;
}

滑动窗口限流算法虽然解决了固定窗口的临界问题，但是一旦到达限流后，请求都会直接暴力被拒绝，这样子我们会损失一部分请求，这对于产品来说，不太友好。

漏桶算法

漏桶算法面对限流，更加具有柔性，不存在直接的暴力拒绝。

原理：就是注水漏水的过程。往漏桶中以任意速率注水，以固定的速率漏水。当水超过桶的容量时，就会溢出，也就是被丢弃。因为桶的容量是不变的，保证了整体的速率。

几点说明：

1. 流入的水，可以看做是访问系统的请求，这个流入速率是不确定的
2. 桶的容量一般表示系统所能处理的请求数
3. 如果桶的容量满了，就是达到限流的阈值，丢弃水（拒绝请求）
4. 水流出的速率是恒定的，对应系统按照固定的速率处理请求

/**
  * 每秒处理请求数（出水率）
  */
private long rate;

/**
  * 当前剩余水量
  */
private long currentWater;

/**
  * 最后刷新时间
  */
private long refreshTime;

/**
  * 桶容量
  */
private long capacity;

/**
  * 漏桶算法（伪代码）
  * 
  * @return true - 请求在阈值内，正常响应
  */
boolean leakyBucketLimitTryAcquire() {
  // 获取当前时间
  long currentTime = System.currentTimeMillis();
  // 流出的水量 = （当前时间 - 上次刷新时间）* 出水率 
  long outWater = (currentTime - refreshTime) / 1000 * rate;
  // 当前水量 = 之前桶内水量 - 流出的水量
  long currentWater = Math.max(0, currentWater - outWater);
  // 刷新时间
  refreshTime = currentTime;
  // 判断剩余水量是否小于桶的容量
  if (currentWater < capacity) {
    // 小于，请求放行
    currentWater++;
    return true;
  }

  // 溢出，限流
  return false;
}

在正常流量的时候，系统按照我们固定的速率处理请求，这是我们想要的。但是面对突发流量的时候，漏桶算法还是在循规蹈矩的处理请求，这就不是我们想要的。

令牌桶算法

面对突发流量时，我们可以使用令牌桶算法限流。

算法原理：

1. 有一个令牌管理员，根据限流大小，定速像令牌桶中放入令牌
2. 如果令牌数量满了，超过令牌桶容量的限制，那就丢弃
3. 系统在接收到请求时，都会先去向令牌桶要一个令牌。如果拿到令牌，那么就处理这个请求
4. 如果拿不到令牌，拒绝这个请求

/**
  * 每秒处理数（放入令牌速率）
  */
private long putTokenRate;

/**
  * 最后刷新时间
  */
private long refreshTime;

/**
  * 桶容量
  */
private long capacity;

/**
  * 当前桶内令牌数
  */
private long currentToken = 0L;

/**
  * 令牌桶算法
  * 
  * @return true - 请求在阈值内，正常响应
  */
boolean tokenBucketTryAcquire() {
  // 获取当前时间
  long currentTime = System.currentTimeMillis();

  // 计算生成的令牌数量
  long elapsedTime = currentTime - refreshTime;
  long generatedTokens = elapsedTime * putTokenRate / 1000; // 放入令牌速率是每秒处理的令牌数，因此需要除以1000转换为毫秒

  // 计算当前令牌数量，但不超过桶的容量
  currentToken = Math.min(capacity, currentToken + generatedTokens);

  // 更新刷新时间
  refreshTime = currentTime;

  // 判断是否有足够的令牌处理请求
  if (currentToken > 0) {
    // 消耗一个令牌
    currentToken--;
    return true;
  }

  // 限流
  return false;
}

如果令牌发放的策略正确，这个系统即不会被拖垮，也能提高机器的利用率。Guava的RateLimiter限流组件、Redisson的RRateLimiter组件，就是基于令牌桶算法实现的。