四种经典限流算法的实现思路以及各自的优缺点_限流算法的 代码实现

限流算法：固定窗口，滑动窗口，漏桶算法和令牌桶算法

在互联网应用中，为了防止恶意请求对系统造成的影响，通常需要采用限流算法来限制请求的速率。本文将介绍四种经典的限流算法：固定窗口，滑动窗口，漏桶算法和令牌桶算法，并通过 Java 代码示例阐述它们的实现思路和优缺点。

1. 固定窗口算法

固定窗口算法是一种简单直接的限流算法。它通过维护一个固定大小的窗口，统计窗口内的请求数量，并根据设定的阈值进行限流。

public class FixedWindowLimiter {
    private final int windowSize;
    private final int threshold;
    private int requestsInWindow;

    public FixedWindowLimiter(int windowSize, int threshold) {
        this.windowSize = windowSize;
        this.threshold = threshold;
    }

    public boolean allowRequest() {
        if (requestsInWindow < threshold) {
            requestsInWindow++;
            return true;
        } else {
            return false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

在上面的代码中，FixedWindowLimiter类表示一个固定窗口限流器，它有两个参数：windowSize表示窗口的大小，threshold表示请求的阈值。类中使用一个变量requestsInWindow来存储窗口内的请求数量。

allowRequest方法用于判断是否允许请求通过。如果窗口内的请求数量小于阈值，则允许请求通过，并将请求数量加1；否则，返回false表示不允许请求通过。

这种算法的优点是实现简单，易于理解和实现。但它也存在一些缺点。首先，固定窗口大小可能会导致请求速率的突然变化，因为新请求可能会被立刻加入到窗口中，而不是等到窗口结束。其次，固定窗口大小无法适应请求速率的动态变化，需要手动调整窗口大小以适应不同的场景。

2. 滑动窗口算法

为了解决固定窗口算法的缺点，滑动窗口算法采用了多个固定大小的窗口，并按照时间顺序依次滑动。每个窗口都可以独立进行限流，从而实现对请求速率的更加精细的控制。

public class SlidingWindowLimiter {
    private final int windowSize;
    private final int threshold;
    private final Deque<Integer> requestsInWindow = new LinkedList<>();

    public SlidingWindowLimiter(int windowSize, int threshold) {
        this.windowSize = windowSize;
        this.threshold = threshold;
    }

    public boolean allowRequest() {
        if (requestsInWindow.size() < threshold) {
            requestsInWindow.add(1);
            return true;
        } else {
            return false;
        }
    }

    public void advanceWindow() {
        requestsInWindow.removeFirst();
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

在上面的代码中，SlidingWindowLimiter类表示一个滑动窗口限流器，它有两个参数：windowSize表示窗口的大小，threshold表示请求的阈值。类中使用一个Deque队列requestsInWindow来存储窗口内的请求数量。

allowRequest方法用于判断是否允许请求通过。如果窗口内的请求数量小于阈值，则允许请求通过，并将请求数量加1；否则，返回false表示不允许请求通过。

advanceWindow方法用于推进窗口，将最旧的请求从窗口中移除。

这种算法的优点是能够更好地适应请求速率的动态变化，因为窗口大小可以根据需要进行调整。但它也存在一些缺点。首先，窗口数量过多可能会导致内存使用量的增加。其次，窗口的滑动可能会导致请求速率的突然变化，因为新窗口的请求数量可能会比旧窗口的请求数量多。

3. 漏桶算法

漏桶算法是一种基于速率限制的算法。它将请求看作是水流入到一个固定大小的漏桶中，漏桶以一定的速率流出请求，从而实现对请求速率的限制。如果水流入的速率超过了漏桶的流出速率，则多余的水流会被丢弃。

public class LeakyBucketLimiter {
    private final int bucketSize;
    private final int leakRate;
    private long lastRequestTime;
    private long currentRequestCount;

    public LeakyBucketLimiter(int bucketSize, int leakRate) {
        this.bucketSize = bucketSize;
        this.leakRate = leakRate;
    }

    public boolean allowRequest() {
        long now = System.currentTimeMillis();
        long elapsedTime = now - lastRequestTime;
        currentRequestCount += elapsedTime * leakRate;
        lastRequestTime = now;
        if (currentRequestCount < bucketSize) {
            return true;
        } else {
            currentRequestCount -= bucketSize;
            return false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

在上面的代码中，LeakyBucketLimiter类表示一个漏桶限流器，它有两个参数：bucketSize表示漏桶的大小，leakRate表示漏桶的流出速率。类中使用两个变量lastRequestTime和currentRequestCount来记录上一次请求的时间和当前请求的数量。

allowRequest方法用于判断是否允许请求通过。它首先计算当前时间与上一次请求时间之间的时间间隔，并乘以漏桶的流出速率，得到当前请求的数量。然后，它比较当前请求数量与漏桶的大小，如果当前请求数量小于漏桶的大小，则允许请求通过，并将请求数量更新为漏桶的大小；否则，返回false表示不允许请求通过。

这种算法的优点是能够实现对请求速率的精确控制，并且不需要维护窗口或计数器等复杂结构。但它也存在一些缺点。首先，漏桶的大小和流出速率需要根据具体场景进行调整，否则可能会导致请求被过度限制或不足限制。其次，漏桶算法无法区分请求的优先级，所有请求都被平等对待。

4. 令牌桶算法

令牌桶算法是另一种基于速率限制的算法。它与漏桶算法类似，但使用了一个令牌桶来存储允许请求通过的令牌。请求需要先获取令牌才能通过，如果令牌桶中没有足够的令牌，则请求被阻塞。

public class TokenBucketLimiter {
    private final int bucketSize;
    private final int tokenRate;
    private long lastTokenGenerateTime;
    private long currentTokenCount;

    public TokenBucketLimiter(int bucketSize, int tokenRate) {
        this.bucketSize = bucketSize;
        this.tokenRate = tokenRate;
    }

    public boolean acquireToken() {
        long now = System.currentTimeMillis();
        long elapsedTime = now - lastTokenGenerateTime;
        currentTokenCount += elapsedTime * tokenRate;
        lastTokenGenerateTime = now;
        if (currentTokenCount >= bucketSize) {
            currentTokenCount -= bucketSize;
            return true;
        } else {
            return false;
        }
    }
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24

在上面的代码中，TokenBucketLimiter类表示一个令牌桶限流器，它有两个参数：bucketSize表示令牌桶的大小，tokenRate表示令牌的生成速率。类中使用两个变量lastTokenGenerateTime和currentTokenCount来记录上一次令牌生成的时间和当前令牌的数量。

acquireToken方法用于获取令牌。它首先计算当前时间与上一次令牌生成时间之间的时间间隔，并乘以令牌的生成速率，得到当前令牌的数量。然后，它比较当前令牌数量与令牌桶的大小，如果当前令牌数量大于等于令牌桶的大小，则将令牌数量更新为令牌桶的大小，并返回true表示成功获取令牌；否则，返回false表示无法获取令牌。

这种算法的优点是能够实现对请求速率的精确控制，并且可以根据请求的优先级分配不同数量的令牌。但它也存在一些缺点。首先，令牌桶的大小和令牌的生成速率需要根据具体场景进行调整，否则可能会导致请求被过度限制或不足限制。其次，令牌桶算法可能会导致请求被延迟，因为请求需要等待令牌的生成。

最后，给大家介绍一款成熟的实现了令牌桶限流算法的包：
Guava 是 Google 开源的一个 Java 库，提供了许多实用的工具类和函数。其中，Guava 包中的限流器提供了一种简单而高效的方法来限制并发请求的数量，以保护系统免受恶意攻击或高负载的影响。

Guava 包中的限流器主要有以下几种：

1. RateLimiter：这是一个基于令牌桶算法的限流器，可以根据请求的特征和系统的处理能力来限制请求的速率。它提供了多种配置选项，例如每秒允许的请求数量、请求的最大等待时间等。

 RateLimiter rateLimiter = RateLimiter.create(20); // 每秒允许 20 个请求
 boolean acquired = rateLimiter.tryAcquire(); // 尝试获取令牌
 if (acquired) {
     // 请求通过
 } else {
     // 请求被阻塞
 }
1
2
3
4
5
6
7

2. SmoothRateLimiter：这是一个基于滑动窗口算法的限流器，可以实现更加平滑的请求速率限制。它通过维护一个固定大小的窗口，并根据请求的时间戳来计算窗口内的请求数量，从而实现对请求速率的限制。

 SmoothRateLimiter rateLimiter = SmoothRateLimiter.create(20, 1000); // 每秒允许 20 个请求，窗口大小为 1000 毫秒
 boolean acquired = rateLimiter.tryAcquire(); // 尝试获取令牌
 if (acquired) {
     // 请求通过
 } else {
     // 请求被阻塞
 }
1
2
3
4
5
6
7

3. RequestLimiter：这是一个基于请求队列的限流器，可以根据请求的特征和系统的处理能力来限制请求的速率。它将请求放入一个队列中，并根据队列的长度来限制请求的速率。

 RequestLimiter limiter = RequestLimiter.create(20); // 每秒允许 20 个请求
 limiter.acquire(); // 尝试获取令牌
 try {
     // 执行请求
 } finally {
     limiter.release
}
1
2
3
4
5
6
7

这些限流器都具有简单易用、高效稳定的特点，可以帮助开发人员快速实现并发请求的限流。同时，它们也提供了多种配置选项和监控接口，方便开发人员进行调整和监控。
需要注意的是，使用限流器时需要根据具体场景和需求进行调整和优化。例如，需要根据请求的特征和系统的处理能力来设置合适的请求速率和窗口大小，以保证系统的稳定性和响应时间。同时，也需要考虑限流器的失效时间和重置策略，以避免请求被长时间阻塞或重复限制。

总之，限流算法的选择需要根据具体场景和需求进行权衡。在选择限流算法时，需要考虑请求的特征、系统的处理能力和响应时间等因素，并选择最适合的算法来满足需求。