限流的算法有哪些?

固定窗口限流算法

原理是在固定时间窗口(单位时间)内限制请求的数量。

  • 该算法将时间分成固定的窗口，并在每个窗口内限制请求的数量。

将请求按照时间顺序放入时间窗口中，并计算该时间窗口内的请求数量，如果请求数量超出了限制，则拒绝该请求。

假设单位时间(固定时间窗口)是1秒，限流阀值为3。

在单位时间1秒内，每来一个请求，计数器就加1，如果计数器累加的次数超过限流阀值3，后续的请求全部拒绝。

  • 等到1s结束后，计数器清0，重新开始计数。

image-20231012113713037

固定窗口算法缺点:

存在明显的临界问题。

假设限流阀值为5个请求，单位时间窗口是1s。

如果在单位时间内的前0.8-1s和1-1.2s，分别并发5个请求。

虽然都没有超过阀值，但是如果算0.8-1.2s，则并发数高达10，已经超过单位时间1s不超过5阀值的定义了。

滑动窗口限流算法

它将单位时间周期分为n个小周期，分别记录每个小周期内接口的访问次数。

  • 并且根据时间滑动删除过期的小周期。

它可以解决固定窗口临界值的问题。

假设单位时间还是1s，滑动窗口算法把它划分为5个小周期，也就是滑动窗口（单位时间）被划分为5个小格子。

每格表示0.2s，每过0.2s，时间窗口就会往右滑动一格。

然后每个小周期，都有自己独立的计数器。

  • 如果请求是0.83s到达的，0.8~1.0s对应的计数器就会加1。

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

伪代码实现：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
/**
    * 单位时间划分的小周期（单位时间是1分钟，10s一个小格子窗口，一共6个格子）
    */
   private int SUB_CYCLE = 10;

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

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

  /**
    * 滑动窗口时间算法实现
    */
    public synchronized 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 synchronized 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;
   }

算法特点：

因为窗口顺延，所以可以抵御窗口间突发流量。

在实际应用中我们要的限流效果往往不希望一下子把流量掐断，而是让流量平滑地进入系统当中。

  • 这就需要对流速进行平滑控制。

假如限流10万次/小时，若某个调用者在前10分钟就调用了10万次。

那么他必须再等待1小时才能发起下一次正常请求，所以没有做到前后请求隔离。

漏桶限流算法

对于每个到来的数据包，都将其加入到漏桶中，并检查漏桶中当前的水量是否超过了漏桶的容量。

  • 如果超过了容量，就将多余的数据包丢弃。

如果漏桶中还有水，就以一定的速率从桶底输出数据包。

  • 保证输出的速率不超过预设的速率，从而达到限流的目的。

算法特点：

因为流出的速度是一定的，可以抵御突发流量，做到更加平滑的限流，而且不允许流量突发。

由于是限定消费速度，无法应对突发流量的来袭，以及处理请求会有延迟，不符合互联网业务低延时的要求。

令牌桶算法

该算法维护一个固定容量的令牌桶，每秒钟会向令牌桶中放入一定数量的令牌。

当有请求到来时，如果令牌桶中有足够的令牌，则请求被允许通过并从令牌桶中消耗一个令牌，否则请求被拒绝。

算法特点：

可以抵御突发流量，因为桶内的令牌数不会超过给定的最大值。

可以做到更加平滑的限流，因为令牌是匀速放入的。

令牌桶算法相比漏桶算法，允许流量一定程度的突发。

在时间点刷新的临界点上，只要剩余Token足够，令牌桶算法会允许对应数量的请求通过。

而后刷新时间因为Token不足，流量也会被限制在外，这样就比较好的控制了瞬时流量，因此令牌桶算法也被广泛使用。

限流组件

限流组件 简介 限流实现方式
Sentinel 阿里巴巴开源服务稳定性保障组件 令牌桶算法
Resilience4j 开源社区服务稳定性保障组件，被spring官方推荐 令牌桶算法
Guava RateLimiter google开源限流组件 令牌桶算法
Uber RateLimiter Uber开源go语言限流组件 漏桶算法