限流方法

• 两个概念

  • 阈值
    • 在一个单位时间内允许的请求量
    • 比如: QPS限制为10，代表1秒内最多10个请求
  • 拒绝策略
    • 超过阈值时的拒绝方式
    • 比如: 直接拒绝、排队等待

• 固定窗口算法(计数器算法)

  • 原理
    • 通过一个计数器来统计1秒内的请求次数，达到上限则触发拒绝策略
    • 每过1秒，计数器重置为0，重新计数
  • 缺点
    • 在2秒内，有可能中间那1秒是会突破上限的
  • 【改进1】滑动窗口算法
    • 1秒窗口会进行滑动，减少2秒内的其中1秒突破上限的可能
    • 但只要滑动不够密集，还是有可能突破上限
  • 【改进2】滑动日志算法
    • 记录下所有请求的时间点，新请求到达时进行判断
    • 限流准确，但内存占用大

• 漏桶算法

  • 原理
    • 把请求想象成一滴水，滴入固定大小的水桶里
    • 桶底有一个孔会漏水，代表处理这些请求，处理的速率是恒定均匀的，就等于限流阈值
    • 当水桶满了(即请求超限)，就触发拒绝策略
  • 缺点
    • 请求量不多的时候，不能并发处理，而是要遵循恒定的速率

• 令牌桶算法

  • 原理
    • 把请求资格当成令牌，由系统按指定速率派发，放入固定大小的桶里
    • 当桶中令牌达到阈值，则不再添加，此时若有大量请求到来，就可以把令牌全部取走，处理速率可以达到一个峰值
    • 当桶中无令牌可以取，就触发拒绝策略
  • 实现例子
    • Java开发工具包Guava中的ReteLimiter类
    • 引入依赖

      <exclusion>
          <groupId>com.google.guava</groupId>
          <artifactId>guava</artifactId>
          <version>31.0.1-jre</version>
      </exclusion>
      

    • 使用例子

      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);
      }