四种限流算法详细介绍及Java代码实现

前言

在BI项目中接触和了解限流算法，目的是为了限制用户疯狂调用AI生成接口，但是当时学习时并不够系统和深入，基本都是跟着教程敲代码，于是有了这篇文章和大家介绍一下四种限流算法。

固定窗口限流

将单位时间内作为一个时间窗口，同时维护一个计数器，记录次时间窗口内接收的请求次数。

  • 当次数小于等于限流阈值，允许请求通过，并且计数器 +1
  • 当次数大于限流阈值，不允许请求通过，计数器不变
  • 当系统时间（当前时间）超过时间窗口，计数器重置为0并且开始记录新的窗口内接收的请求次数

缺陷：定义时间窗口为1s，允许请求数量为3（请求阈值），说明1s内只能接收并处理3个请求。然而如果0.80.9s来了三个请求，1.11.2s来了三个请求。虽然这6个请求都没超过各自窗口的请求阈值，但是已经违背了1s内接收并处理3个请求了，因为在不到1s内其接收了6个请求，存在临界问题。

优点：简单易实现

缺点：

  1. 有临界问题（流量突刺）
  2. 不适用于分布式系统

Java代码实现

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
JAVA
public class FixedWindowRateLimiter {
    private final int requestLimit; // 限流阈值
    private final long windowSize; // 时间窗口大小（毫秒）
    private int count; // 计数器
    private volatile long windowStart; // 时间窗口起始时间

    public FixedWindowRateLimiter(long windowSize, int requestLimit) {
        this.windowSize = windowSize;
        this.requestLimit = requestLimit;
        this.count = 0;
        this.windowStart = System.currentTimeMillis() / 1000;
    }

    public synchronized boolean tryAcquire() {
        long currentTime = System.currentTimeMillis();
        if (currentTime - windowStart > windowSize) { // 如果当前时间已经超出窗口时间，则重置窗口
            windowStart = currentTime;
            count = 0;
        }
        if (count < requestLimit) {
            count++; // 增加计数
            return true;
        } else {
            return false;
        }
    }

    public static void main(String[] args) {
        FixedWindowRateLimiter fixedWindowRateLimiter = new FixedWindowRateLimiter(10, 2); // 时间窗口大小，请求阈值（请求限制）
        for (int i = 0;i < 10;i++) {
            boolean allowed = fixedWindowRateLimiter.tryAcquire();
            System.out.println("请求" + (i+1) + "：" + (allowed ? "被允许" : "被拒绝"));
        }
    }
}

结果：

img

滑动窗口限流

为了解决固定窗口限流的临界问题，便有了滑动窗口限流算法。

滑动窗口将单位时间划分n个小周期，通过计数器记录每个小周期内的请求次数，每过0.2s后时间窗口就往后推移1小格即一个小周期（0.2s），那么最初的小周期就会被删除，并且随着时间的推移删除已过期的小周期。

比如，将单位时间1s划分5个小周期，每个小周期为0.2s。每个小周期内的请求次数由各自且独立的计数器记录，统计5个小周期的计数器总和是否超过请求阈值，没有就请求允许，否则请求被拒绝。起初滑动窗口是01s；当过了0.2s后，00.2s这个小周期就会被删除，同时滑动窗口后移0.2s（一个小周期），那么新的滑动窗口变为了0.2~1.2s。

用上述固定窗口的临界例子应用到滑动窗口：0.80.9来了三个请求，这三个请求被允许了（此时滑动窗口是01.0s）。过了0.2s后，新的滑动窗口变为了0.21.2s，当1.11.2s来了三个请求，这三个请求就会被拒绝。因为此时新的5个小周期的计数器总和为3达到了请求阈值，所以.1~1.2s来的三个请求会被拒绝。

优点：解决了固定限流算法的临界（流量突刺）问题

缺点：

  1. 相比固定限流难理解和实现
  2. 不适用分布式系统
  3. 超过请求阈值的请求直接被拒绝了，而不是丢弃，给用户的体验不好
  4. 限流效果与划分的小周期的数量有关，但往往很难选取

Java实现

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
JAVA
public class SlidingWindowRateLimiter {
    private final int windowSize;  // 时间窗口大小，单位为秒
    private final int requestLimit;  // 在时间窗口内允许的最大请求数
    private final LinkedList<Long> timestamps;  // 存储请求的时间戳

    public SlidingWindowRateLimiter(int windowSize, int requestLimit) {
        this.windowSize = windowSize;
        this.requestLimit = requestLimit;
        this.timestamps = new LinkedList<>();
    }

    public synchronized boolean allowRequest() {
        long currentTime = System.currentTimeMillis() / 1000;  // 获取当前时间戳（秒）

        // 移除时间窗口之外的时间戳
        while (!timestamps.isEmpty() && timestamps.getFirst() <= currentTime - windowSize) {
            timestamps.removeFirst();
        }

        // 检查当前请求数是否超过限制
        if (timestamps.size() < requestLimit) {
            timestamps.addLast(currentTime);
            return true;  // 允许请求
        } else {
            return false;  // 请求超过限制
        }
    }

    public static void main(String[] args) {
        SlidingWindowRateLimiter rateLimiter = new SlidingWindowRateLimiter(10, 2);

        // 模拟请求
        for (int i = 0; i < 10; i++) {
            boolean allowed = rateLimiter.allowRequest();
            System.out.println("请求 " + (i + 1) + ": " + (allowed ? "被允许" : "被拒绝"));
        }
    }
}

结果：

img

漏桶限流

漏桶限流算法又算是解决了固定窗口限流和滑动窗口限流出现的请求被拒绝的问题，其对于超出请求阈值的请求会直接丢弃。

水（请求）以任意的速率流入桶内，以固定的速率从桶底流出（处理请求），如果水的流入速度大于流出速度（系统请求速度大于处理请求的速度），水就会溢出（即请求直接被丢弃）。

优点：

  1. 解决了请求被直接拒绝的问题
  2. 一定程度上解决了临界问题（流量突刺）

缺点：不能迅速处理一批请求（并发处理请求），因为水的流出速率是固定的（请求的处理速率是固定的，只能处理一个请求后再去处理下一个）

Java实现：

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
JAVA
package DataStructure.RateLimtAlgorithm;

import java.time.Instant;
import java.util.concurrent.atomic.AtomicLong;

public class LeakyBucketRateLimiter {
    private final int capacity; // 桶的容量
    private final int rate; // 漏水速率，单位：请求/秒
    private AtomicLong water; // 当前桶中的水量
    private Instant lastLeakTime; // 上一次漏水的时间点

    public LeakyBucketRateLimiter(int capacity, int rate) {
        this.capacity = capacity;
        this.rate = rate;
        this.water = new AtomicLong(0);
        this.lastLeakTime = Instant.now();
    }

    public synchronized boolean allowed() {
        leak(); // 漏水
        if (water.get() < capacity) {
            water.incrementAndGet();
            return true; // 桶未满，允许请求通过
        } else {
            return false; // 桶已满，拒绝请求
        }
    }

    private synchronized void leak() {
        Instant now = Instant.now();
        long interval = now.getEpochSecond() - lastLeakTime.getEpochSecond();
        long leakedWater = interval * rate; // 计算漏水的数量
        if (leakedWater > 0) {
            water.set(Math.max(0, water.get() - leakedWater)); // 更新桶中的水量
            lastLeakTime = now; // 更新上一次漏水的时间点
        }
    }

    public static void main(String[] args) {
        LeakyBucketRateLimiter leakyBucketRateLimiter = new LeakyBucketRateLimiter(5, 2); // 创建一个容量为10，速率为1个请求/秒的漏桶
        for (int i = 0; i < 10; i++) {
            boolean allowed = leakyBucketRateLimiter.allowed();
            System.out.println("请求 " + (i + 1) + ": " + (allowed ? "被允许" : "被拒绝"));
            try {
                Thread.sleep(100); // 模拟请求间隔
            } catch (InterruptedException e) {
                e.printStackTrace();
            }
        }
    }
}

结果：

img

令牌桶限流

根据请求的数量多少，管理员匀速生成一批令牌。只有拥有令牌的请求才会被允许，否则就会被丢弃，不予通过。比如管理员生成了5个令牌，此时来了10个请求，那么拿到令牌的5个请求会被同时处理，另外5个请求就会被丢弃。

一般令牌桶限流可以通过Redisson限流器实现，因此其适用于分布式系统，当然前面三种限流算也可用于分布式系统但是需要手动实现。既然令牌桶限流算法这么好，Redisson还帮我们实现了，所以一般我们都会选择它，因为专业 [doge]。

优点：以上三种算法的所有优点，并且支持并发处理请求。

缺点：不适合长时间限流，对资源消耗高，依赖Redis实现，不适用于突发性任务

Java实现：

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
JAVA
@Service
public class RedisLimiterManager {

    @Resource
    private RedissonClient redissonClient;

    /**
     * 限流操作
     *
     * @param key 区分不同的限流器，比如不同的用户 id 应该分别统计
     */
    public void doRateLimit(String key) {
        // 创建一个名称为user_limiter的限流器，每秒最多访问2次
        RRateLimiter rateLimiter = redissonClient.getRateLimiter(key);
        rateLimiter.trySetRate(RateType.OVERALL, 2, 1, RateIntervalUnit.SECONDS); // OVERALL类型：不管有多少台服务器都是放在一起统计的，请求阈值，生成令牌的频率
        // 每当一个操作来了后，请求一个令牌
        boolean canOp = rateLimiter.tryAcquire(1);// 令牌请求数，处理请求需消耗的令牌
        if (!canOp) {
            throw new BusinessException(ErrorCode.TOO_MANY_REQUEST);
        }
    }
}

@SpringBootTest
class RedisLimiterManagerTest {
    @Resource
    private RedisLimiterManager redisLimiterManager;

    @Test
    void doRateLimit() throws InterruptedException {
        String userId = "1";
        for (int i=0;i<10;i++) {
            redisLimiterManager.doRateLimit(userId);
            System.out.println("success");
        }
    }
}

结果：

img