服务限流设计

服务限流

固定窗口限流

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

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

假设单位时间是1秒，限流阀值为3。在单位时间1秒内，每来一个请求,计数器就加1，如果计数器累加的次数超过限流阀值3，后续的请求全部拒绝。等到1s结束后，计数器清0，重新开始计数。如下图：

限定：1小时只允许10个用户操作

优点：最简单

缺点：可出现流量突刺

比如：前59分钟没有1个操作，第59分钟来了10个操作；第1小时01分钟又来了10个操作。相当于2分钟内执行了20个操作，服务器仍然有高峰危险

/**
 * 固定窗口时间算法
 * @return
 */
boolean fixedWindowsTryAcquire() {
    long currentTime = System.currentTimeMillis();  //获取系统当前时间
    if (currentTime - lastRequestTime > windowUnit) {  //检查是否在时间窗口内
        counter = 0;  // 计数器清0
        lastRequestTime = currentTime;  //开启新的时间窗口
    }
    if (counter < threshold) {  // 小于阀值
        counter++;  //计数器加1
        return true;
    }

    return false;
}

滑动窗口限流

假设单位时间还是1s，滑动窗口算法把它划分为5个小周期，也就是滑动窗口（单位时间）被划分为5个小格子。每格表示0.2s。每过0.2s，时间窗口就会往右滑动一格。然后呢，每个小周期，都有自己独立的计数器，如果请求是0.83s到达的，0.8~1.0s对应的计数器就会加1。

只要窗口中所有单元格的计数总和不超过阈值都可以放行

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

   /**
    * 每分钟限流请求数
    */
   private int thresholdPerMin = 100;

   /**
    * 计数器, k-为当前窗口的开始时间值秒，value为当前窗口的计数
    */
   private final TreeMap<Long, Integer> counters = new TreeMap<>();

  /**
    * 滑动窗口时间算法实现
    */
   boolean slidingWindowsTryAcquire() {
       long currentWindowTime = LocalDateTime.now().toEpochSecond(ZoneOffset.UTC) / SUB_CYCLE * SUB_CYCLE; //获取当前时间在哪个小周期窗口
       int currentWindowNum = countCurrentWindow(currentWindowTime); //当前窗口总请求数

       //超过阀值限流
       if (currentWindowNum >= thresholdPerMin) {
           return false;
       }

       //计数器+1
       counters.get(currentWindowTime)++;
       return true;
   }

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

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

解决了固定窗口限流存在的问题

优点：能够解决上述流量突刺的问题，因为第59分钟时，限流窗口是59分~1小时59分，这个时间段内只能接受10次请求，只要还在这个窗口内，更多的操作就会被拒绝。

缺点：实现相对固定窗口来说比较复杂，限流效果和你的滑动单位有关，滑动单位越小，限流效果越好，但往往很难选取到一个特别合适的滑动单位。滑动窗口算法虽然解决了固定窗口的临界问题，但是一旦到达限流后，请求都会直接暴力被拒绝。我们会损失一部分请求，这其实对于产品来说，并不太友好。

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

漏桶限流

把请求比作是水滴，需要进入桶才能被处理，同时桶会有一定的容量，超出容量的请求将会被拒绝，漏桶以固定速率处理请求。

特点：以固定的速率处理请求（漏水），当请求桶满了后，拒绝请求。

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

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

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

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

   /**
    * 漏桶算法
    * @return
    */
   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;
   }

举例：每秒处理10个请求，桶的容量是10，每0.1秒固定处理一次请求，如果1秒内来了10个请求，这10此请求都可以处理完，但如果1秒内来了11个请求，最后那个请求就会溢出桶，被拒绝请求。

优点：能够一定程度上应对流量突刺，能够固定速率处理请求，保证服务器的安全。

缺点：漏桶算法存在目的主要是用来平滑突发的流量，提供一种机制来确保网络中的突发流量被整合成平滑稳定的额流量。不过由于漏桶对流量的控制过于严格，在有些场景下不能充分使用系统资源，因为漏桶的漏出速率是固定的，即使在某一时刻下游能够处理更大的流量，漏桶也不允许突发流量通过。

令牌桶限流

可以解决漏桶存在的问题

• 有一个令牌管理员，根据限流大小，定速往令牌桶里放令牌。
• 如果令牌数量满了，超过令牌桶容量的限制，那就丢弃。
• 系统在接受到一个用户请求时，都会先去令牌桶要一个令牌。如果拿到令牌，那么就处理这个请求的业务逻辑；
• 如果拿不到令牌，就直接拒绝这个请求。

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

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

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

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

/**
 * 漏桶算法
 * @return
 */
boolean tokenBucketTryAcquire() {

    long currentTime = System.currentTimeMillis();  //获取系统当前时间
    long generateToken = (currentTime - refreshTime) / 1000 * putTokenRate; //生成的令牌 =(当前时间-上次刷新时间)* 放入令牌的速率
    currentToken = Math.min(capacity, generateToken + currentToken); // 当前令牌数量 = 之前的桶内令牌数量+放入的令牌数量
    refreshTime = currentTime; // 刷新时间
    
    //桶里面还有令牌，请求正常处理
    if (currentToken > 0) {
        currentToken--; //令牌数量-1
        return true;
    }
    
    return false;
}

管理员先生成一批令牌，每秒生成10个令牌；当用户要操作前，先去拿到一个令牌，有令牌的人就有资格执行操作、同时执行操作；拿不到令牌的就等着

优点：能够并发处理同时的请求，并发性能会更高

比如，当令牌桶满的时候有10个可用令牌，此时允许10个请求同时通过限流器（允许流量一定程度的突发），这10个请求瞬间消耗完令牌后，后续的流量只能按照速率r通过限流器。

需要考虑的问题：还是存在时间单位选取的问题

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

缺点：令牌桶算法可以缓解漏桶算法的缺点，但在一些场景下可能存在一定问题。比如在应对短时间内的高并发请求时，由于令牌数有限，引入过大的并发请求会导致严重的性能问题，也可能会造成请求失败或者拒绝。

限流粒度

1. 针对某个方法限流，即单位时间内最多允许同时X个操作使用这个方法
2. 针对某个用户限流，比如单个用户单位时间内最多执行X次操作
3. 针对某个用户X方法限流，比如单个用户单位时间内最多执行X次这个方法