限流算法

在高并发的网络应用中，保护系统的稳定性和可用性是至关重要的。

缓存、熔断、降级、限流

缓存的目的是为了降低系统的访问延迟，提高系统能力，给用户更好的体验
熔断的目的是为了在发现某个服务故障熔断对下游依赖的请求，减少不必要的损耗
降级的目的是为了在系统在某个环节故障（比如某个下游故障）不影响整体核心链路，比如返回作者列表，关注服务故障了获取不了关注真实的关注情况，这种情况可以考虑降级关注按钮，全部显示为未关注
限流的目的是为了保证系统处理的请求量在可以承受的范围内，防止突发流量压垮系统，保证系统稳定性。

目标：限定请求量在系统可承受范围内。

1.计数器（固定窗口）算法

1.1算法介绍

固定窗口算法又叫计数器算法，是一种简单方便的限流算法。主要通过一个支持原子操作的计数器来累计 1 秒内的请求次数，当 1 秒内计数达到限流阈值时触发拒绝策略。每过 1 秒，计数器重置为 0 开始重新计数。

1.2结合redis实现

比如我们需要在10秒内限定20个请求，那么我们在setnx的时候可以设置过期时间10，当请求的setnx数量达到20时候即达到了限流效果。代码比较简单就不做展示了。

1.3 算法优缺点

优点

• 在固定的时间内出现流量溢出可以立即做出限流。每个时间窗口不会相互影响
• 在时间单元内保障系统的稳定。保障的时间单元内系统的吞吐量上限

缺点

• 正如图示一样，他的最大问题就是临界状态。在临界状态最坏情况会受到两倍流量请求
• 除了临界的情况，还有一种是在一个单元时间窗内前期如果很快的消耗完请求阈值。那么剩下的时间将会无法请求。这样就会因为一瞬间的流量导致一段时间内系统不可用。这在互联网高可用的系统中是不能接受的。

计数器算法是使用计数器在周期内累加访问次数，当达到设定的限流值时，触发限流策略。下一个周期开始时，进行清零，重新计数。此算法可用性不高，存在一个非常严重的问题，那就是临界问题（0-1秒限定20次，1-2秒限定20次，但可能出现1.5-2.5这个1秒周期内请求了40次），其实只是为了引出滑动窗口算法。

---

2.滑动窗口算法

2.1 算法介绍

滑动窗口算法是将时间周期分为N个小周期，分别记录每个小周期内访问次数，并且根据时间滑动删除过期的小周期。

假设时间周期为1min，将1min再分为2个小周期，统计每个小周期的访问数量，则可以看到，第一个时间周期内，访问数量为75，第二个时间周期内，访问数量为100，超过100的访问则被限流掉了由此可见，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。此算法可以很好的解决固定窗口算法的临界问题。

2.2 结合redis实现

可以结合redis的zset实现

• 为什么选择zset呢，因为redis的zset中除了值以外还有一个权重。会根据这个权重进行排序。如果我们将我们的时间单元及时间戳作为我们的权重，那么我们获取统计的时候只需要按照一个时间戳范围就可以了。
• 因为zset内元素是唯一的，所以我们的值采用uuid或者雪花算法一类的id生成器

public Response limitFlow(){
        Long currentTime = new Date().getTime();
        System.out.println(currentTime);
        if(redisTemplate.hasKey("limit")) {
            Integer count = redisTemplate.opsForZSet().rangeByScore("limit", currentTime -  intervalTime, currentTime).size();        // intervalTime是限流的时间 
            System.out.println(count);
            if (count != null && count > 5) {
                return Response.ok("每分钟最多只能访问5次");
            }
        }
        redisTemplate.opsForZSet().add("limit",UUID.randomUUID().toString(),currentTime);
        return Response.ok("访问成功");
    }

2.3算法优缺点

2.3.1优点

• 实质上就是固定时间窗口算法的改进。所以固定时间窗口的缺点就是他的优点。
• 内部抽象一个滑动的时间窗，将时间更加小化。存在边界的问题更加小。客户感知更弱了。

2.3.2缺点

• 不管是固定时间窗口算法还是滑动时间窗口算法，他们都是基于计数器算法进行优化，但是他们对待限流的策略太粗暴了。
• 为什么说粗暴呢，未限流他们正常放行。一旦达到限流后就会直接拒绝。这样我们会损失一部分请求。这对于一个产品来说不太友好

---

3.漏桶算法

3.1 算法思想

漏桶算法是访问请求到达时直接放入漏桶，如当前容量已达到上限（限流值），则进行丢弃（触发限流策略）。漏桶以固定的速率进行释放访问请求（即请求通过），直到漏桶为空。


3.2 结合redis实现

• ```java
  import org.redisson.Redisson;
  import org.redisson.api.RBucket;
  import org.redisson.api.RedissonClient;
  import org.redisson.config.Config; public class RedissonLeakyBucket {

   private static final String BUCKET_KEY = "leaky_bucket";
   private static final long BUCKET_CAPACITY = 100; // 桶的容量，表示能够容纳的最大请求数量
   private static final long REFILL_RATE = 10; // 单位时间内桶的补充速率，表示每秒钟允许通过的请求数量
  
   public static boolean allowRequest(RedissonClient redisson) {
       long currentTime = System.currentTimeMillis();
  
       // 获取当前桶中的请求数量
       RBucket<Long> bucket = redisson.getBucket(BUCKET_KEY);
       Long currentRequests = bucket.get();
       if (currentRequests == null) {
           currentRequests = 0L;
       }
  
       // 计算桶中的请求数量是否超过容量
       if (currentRequests < BUCKET_CAPACITY) {
           // 计算需要向桶中添加的请求数量
           long refillAmount = Math.min(BUCKET_CAPACITY - currentRequests, (currentTime - getLastRefillTime(redisson)) * REFILL_RATE / 1000);
  
           // 向桶中添加请求数量
           bucket.set(currentRequests + refillAmount);
       }
  
       // 移除桶中过期的请求数量
       while (bucket.get() != null && bucket.get() > 0 && bucket.get() * 1000 + 1000 < currentTime) {
           bucket.set(bucket.get() - 1);
       }
  
       // 检查桶中的请求数量是否超过容量
       return bucket.get() != null && bucket.get() <= BUCKET_CAPACITY;
   }
  
   private static long getLastRefillTime(RedissonClient redisson) {
       RBucket<Long> lastRefillTimeBucket = redisson.getBucket(BUCKET_KEY + ":last_refill_time");
       Long lastRefillTime = lastRefillTimeBucket.get();
       if (lastRefillTime == null) {
           return System.currentTimeMillis();
       } else {
           return lastRefillTime;
       }
   }
  
   public static void main(String[] args) {
       // 创建 Redisson 客户端
       Config config = new Config();
       config.useSingleServer().setAddress("redis://127.0.0.1:6379");
       RedissonClient redisson = Redisson.create(config);
  
       // 模拟请求
       for (int i = 0; i < 200; i++) {
           if (allowRequest(redisson)) {
               System.out.println("Request " + i + " allowed");
           } else {
               System.out.println("Request " + i + " rejected");
           }
       }
  
       // 关闭 Redisson 客户端
       redisson.shutdown();
   }
  

  }

      
      ### 3.3优缺点
  
  **优点**：
  
  1. **固定的输出速率**：漏桶算法能够以固定的速率处理请求，这样可以有效地平滑流量，防止突发流量对系统造成影响。
  2. **简单直观**：漏桶算法的原理非常简单，易于理解和实现。
  
  **缺点**：
  
  1. **不灵活**：漏桶算法的输出速率是固定的，无法根据系统的实际情况动态调整。
  2. **延迟增加**：当流量超出漏桶容量时，漏桶算法会拒绝请求，这可能会导致请求的延迟增加。
  
  
  
  ---
  
  
  
  ## 4.令牌桶算法
  
  ## 4.1 算法思想
  
  令牌桶算法是程序以r（r=时间周期/限流值）的速度向令牌桶中增加令牌，直到令牌桶满，请求到达时向令牌桶请求令牌，如获取到令牌则通过请求，否则触发限流策略。
  
  生成令牌的速度是恒定的，而请求去拿令牌是没有速度限制的。这意味，面对瞬时大流量，该算法可以在短时间内请求拿到大量令牌，而且拿令牌的过程并不是消耗很大的事情。
  
  ![image-20240514141636328](限流算法/:Users:seven:Library:Application Support:typora-user-images:image-20240514141636328.png)
  
  ### 4.2 结合reids实现（redisson）
  
  ```java
  import org.redisson.Redisson;
  import org.redisson.api.RSemaphore;
  import org.redisson.api.RedissonClient;
  import org.redisson.config.Config;
  
  public class RedissonTokenBucketWithRefillRate {
      private static final String BUCKET_KEY = "token_bucket";
      private static final long BUCKET_CAPACITY = 100; // 桶的容量，表示能够容纳的最大令牌数量
      private static final long REFILL_RATE = 10; // 单位时间内桶的补充速率，表示每秒钟补充的令牌数量
  
      public static boolean allowRequest(RedissonClient redisson) {
          // 获取令牌桶
          RSemaphore tokenBucket = redisson.getSemaphore(BUCKET_KEY);
          
          // 尝试从令牌桶中获取令牌，如果获取到了，则允许请求通过；否则拒绝请求
          return tokenBucket.tryAcquire();
      }
      
      public static void main(String[] args) {
          // 创建 Redisson 客户端
          Config config = new Config();
          config.useSingleServer().setAddress("redis://127.0.0.1:6379");
          RedissonClient redisson = Redisson.create(config);
      
          // 初始化令牌桶，设置初始令牌数量为桶的容量
          RSemaphore tokenBucket = redisson.getSemaphore(BUCKET_KEY);
          tokenBucket.trySetPermits(BUCKET_CAPACITY);
      
          // 使用 REFILL_RATE 控制每秒钟向令牌桶中补充的令牌数量
          Thread refillThread = new Thread(() -> {
              while (true) {
                  try {
                      Thread.sleep(1000); // 每秒钟补充一次令牌
                      tokenBucket.trySetPermits(Math.min(BUCKET_CAPACITY, tokenBucket.availablePermits() + REFILL_RATE));
                  } catch (InterruptedException e) {
                      e.printStackTrace();
                  }
              }
          });
          refillThread.setDaemon(true);
          refillThread.start();
      
          // 模拟请求
          for (int i = 0; i < 200; i++) {
              if (allowRequest(redisson)) {
                  System.out.println("Request " + i + " allowed");
              } else {
                  System.out.println("Request " + i + " rejected");
              }
          }
      
          // 关闭 Redisson 客户端
          redisson.shutdown();
      }
  
  }

4.3 优缺点

优点：

1. 动态调整：令牌桶算法允许动态调整令牌的生成速率，从而灵活地控制请求的处理速率。
2. 流量突发处理：令牌桶算法允许一定程度的流量突发，因为令牌可以被积累到桶中，使得一段时间内的请求处理速率可以超过平均速率。

缺点：

1. 复杂度高：相对于漏桶算法，令牌桶算法的实现较为复杂。
2. 令牌浪费：在低负载情况下，令牌桶算法可能会导致令牌的浪费，因为桶中的令牌未被使用而被丢弃。

---

5.各限流算法对比

5.1漏桶算法VS令牌桶算法

漏桶算法与令牌桶算法的区别在于：

漏桶算法能够强行限制数据的传输速率。

令牌桶算法能够在限制数据的平均传输速率的同时还允许某种程度的突发传输。

需要说明的是：在某些情况下，漏桶算法不能够有效地使用网络资源。因为漏桶的漏出速率是固定的，所以即使网络中没有发生拥塞，漏桶算法也不能使某一个单独的数据流达到端口速率。因此，漏桶算法对于存在突发特性的流量来说缺乏效率。而令牌桶算法则能够满足这些具有突发特性的流量。通常，漏桶算法与令牌桶算法结合起来为网络流量提供更高效的控制。

总结：自己的系统扛不了大量请求，用令牌桶。对接的下游系统抗不了突发大量请求，可以用漏桶算法。

算法	确定参数	空间复杂度	时间复杂度	限制突发流量	平滑限流	分布式环境下实现难度
固定窗口	计数周期T、周期内最大访问数N	低O(1)（记录周期内访问次数及周期开始时间）	低O(1)	否	否	低
滑动窗口	计数周期T、周期内最大访问数N	高O(N)（记录每个小周期中的访问数量）	中O(N)	是	相对实现。滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑	中
漏桶	漏桶流出速度r、漏桶容量N	低O(1)（记录当前漏桶中容量）	高O(N)	是	是	高
令牌桶	令牌产生速度r、令牌桶容量N	低O(1)（记录当前令牌桶中令牌数）	高O(N)	是	是	高