每天净瞎搞

关注:CS/AI/数学/自我提升等

0%

5种限流算法总结

限流的定义是什么

  • 限流就是对请求的速率进行限制,即限制到达系统的并发请求数,避免瞬时的大量请求击垮软件系统

限流算法有哪些?

  • 计数限流
  • 固定窗口限流
  • 滑动窗口限流
  • 漏桶算法
  • 令牌桶算法

计数限流算法原理、代码、优缺点

  • 原理
    • 根据系统能同时处理的请求数,保存一个计数器,处理一个请求加一,处理完后减一,若超过阈值拒绝请求
  • 代码
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
     boolean tryAcquire() {
    if (counter < threshold) {
    counter++;
    return true;
    }
    return false;
    }

    boolean tryRelease() {
    if (counter > 0) {
    counter--;
    return true;
    }
    return false;
    }
  • 优点
    • 简单粗暴,单机在 java 可用 Atomic 等原子类、分布式就 Redis incr
  • 缺点
    • 假设单机设的 1 万阈值,计数器为 0,若在 1 秒内收到 1 万个突发请求,可能超过机器的处理上限而导致机器崩溃

固定窗口限流算法的原理、代码、问题

  • 原理
    • 相比于计数限流主要是多了个时间窗口的概念,计数器每过一个时间窗口就重置,规则为:
      • 1.请求次数小于阈值,允许访问并且计数器 +1
      • 2.请求次数大于阈值,拒绝访问
      • 3.这个时间窗口过了之后,计数器清零
    • 代码
      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      boolean tryAcquire() {
      // 获取当前时间
      bool now = currentTimeMillis();

      // 若过了时间窗口把计数器清零
      if (now - lastAcquireTime > TimeWindow) {
      counter = 0;
      lastAcquireTime = now;
      }

      if (counter < threshold) {
      counter++;
      return true;
      }
      return false;
      }
  • 问题
    • 无法保证限流速率,因而无法保证突然激增的流量,会遇到固定窗口临界问题,即这个算法有时会让通过请求量允许为限制的两倍
    • 如图,限制 1 秒内最多通过 5 个请求,在第一个窗口的最后半秒内通过了 5 个请求,第二个窗口的前半秒内又通过了 5 个请求。这样看来就是在 1 秒内通过了 10 个请求

滑动窗口限流算法的原理、代码

  • 原理
    • 1.将时间划分为多个区间
    • 2.在每个区间内每有一次请求就将计数器加一维持一个时间窗口,占据多个区间
    • 3.每经过一个区间的时间,则抛弃最老的一个区间,并纳入最新的一个区间
    • 4.如果当前窗口内的请求计数总和超过了限制数量,则本窗口内所有的请求都被丢弃
  • 代码
    • 实现:记录每次请求的时间,统计每次请求的时间至往前一个时间窗口的请求数,如果小于阈值就记录这个请求的时间,反之拒绝
      1
      2
      3
      4
      5
      6
      7
      8
      9
      boolean tryAcquire() {
      long now = currentTimeMillis();
      long counter = getCounterInTimeWindow(now);
      if (counter < threshold) {
      addToTimeWindow(now);
      return true;
      }
      return false;
      }
  • 优点
    • 避免了固定窗口计数器带来的双倍突发请求
  • 缺点
    • 时间区间的精度越高,算法所需的空间容量就越大
    • 无法解决短时间集中流量的突击,到流量处理不够平滑

桶漏算法的原理、实现、优缺点

  • 原理
    • 水滴持续漏到桶中,底部定速流出,如果桶空了则停止漏水,如果满了多余的水会被直接抛弃
  • 实现
    • 使用队列,服务的请求会存在队列中,服务的提供方按照固定的速率从队列中取出请求并执行,过多的请求则放在队列中排队或直接拒绝
  • 优点
    • 宽进严出,无论请求数量和速率多大,都能按照固定速率流出,流量处理非常平滑
  • 缺点
    • 当短时间内有大量的突发请求时,即便此时服务器没有任何负载,每个请求也都得在队列中等待一段时间才能被响应

令牌桶算法的原理、优缺点

  • 原理
    • 以固定速率生成令牌存入到令牌桶中
    • 如果令牌数量超过桶的限制则直接丢弃
    • 当请求到达是,会先从令牌桶中取令牌,取到了令牌的请求可以执行,如果桶空了,那么取令牌的请求会被直接丢弃
  • 优点
    • 能够将所有的请求平均分布到时间区间内,又能接受服务器能够承受范围内的突发请求

参考