基于Redission 实现限流2-固定窗口算法

概述：

上文中已经介绍了限流的意义及基于Redission 实现令牌桶算法，本文将接着介绍基于Redission 实现固定窗口算法

固定窗口算法（也称为计数器算法）是一种简单的限流算法，它按照预设的固定时间窗口（例如每分钟、每小时等）对请求进行计数，并在达到限制阈值时拒绝额外的请求。以下是基于 Redisson 实现固定窗口算法的原理和优缺点：

原理：

1. 时间窗口：选择一个固定的时间窗口大小，比如 1 分钟。 2. 计数器：为每个时间窗口维护一个计数器，该计数器记录该时间窗口内的请求次数。 3. 限流检查：当一个新请求到来时，检查当前时间窗口的计数器值。 - 如果计数器的值小于预设的阈值，请求被允许并且计数器增加。 - 如果计数器的值已经达到阈值，请求被拒绝。 4. 窗口切换：当时间进入下一个窗口时，计数器重置为 0。

Redisson 实现：

在 Redisson 中，可以使用 Redis 的键值对和过期机制来实现固定窗口算法： - 使用 Redis 的键来代表每个时间窗口的计数器。 - 在键不存在时创建它，并设置过期时间为窗口的大小。 - 使用 Redis 的 INCR 命令来原子性地增加计数器的值，并在同一操作中检查是否超过了限流阈值。 - 使用 Lua 脚本来确保整个判断和增加的过程是原子性的。

优点

- 简单易懂：算法逻辑简单，容易理解和实现。 - 高效：使用 Redis 的 INCR 和键过期机制可以高效地实现计数器。 - 性能好：由于 Redis 命令的高性能，固定窗口算法可以支持高并发的请求。

缺点

- 临界问题：在窗口切换的瞬间，可能会有两倍于限制的请求被允许通过。这是因为在窗口的最后一刻和下一个窗口的第一刻，请求都被计数器允许。 - 突发流量问题：在每个窗口开始时，即使服务能够处理更多的请求，也无法充分利用，因为限流是基于固定的阈值。 - 不够平滑：请求在时间窗口内不均匀分布时，可能导致服务时而空闲时而过载。

尽管固定窗口算法有其缺点，但它在一些场景下仍然是一个有效的限流选择，特别是当应用程序需要简单而快速的限流机制时。对于更平滑的限流，可以考虑使用滑动窗口算法或令牌桶算法。

代码实现：

源码：

import org.redisson.api.RAtomicLong;
import org.redisson.api.RBucket;
import org.redisson.api.RScript;
import org.redisson.api.RedissonClient;
import org.redisson.client.codec.LongCodec;

import java.util.Arrays;
import java.util.List;
import java.util.concurrent.TimeUnit;
/**
 * @Author derek_smart
 * @Date 202/5/12 10:21
 * @Description 固定窗口实现限流器
 * <p>
 */
public class FixedWindowRateLimiter {
    private final RedissonClient redissonClient;
    private final String key;
    private final long limit;
    private final long windowSize; // in seconds

    public FixedWindowRateLimiter(RedissonClient redissonClient, String key, long limit, long windowSizeInSeconds) {
        this.redissonClient = redissonClient;
        this.key = "rate_limiter:" + key;
        this.limit = limit;
        this.windowSize = windowSizeInSeconds;
    }

    /**
     * 由于我们在达到限制时对计数器进行了递减操作，这可能会导致在极端高并发的情况下，窗口内的请求次数短暂地超过限制。如果需要严格控制请求数量不超过限制，
     * 可以考虑使用 Lua 脚本来确保整个判断和增加的过程是原子性的。
     * @return
     */
    public boolean tryAcquire() {
        RAtomicLong atomicLong = redissonClient.getAtomicLong(key);
        long currentValue = atomicLong.getAndIncrement();

        if (currentValue == 0) {
            // 第一次请求，设置过期时间
            atomicLong.expire(windowSize, TimeUnit.SECONDS);
            return true;
        } else if (currentValue < limit) {
            // 如果计数值小于限制，请求通过
            return true;
        } else {
            // 如果计数值达到或超过限制，递减计数器并拒绝请求
            atomicLong.decrementAndGet();
            return false;
        }
    }

    /**
     * 使用 Redis  Lua 脚本来保证原子性操作。
     *
     * @return
     */
    public boolean tryAcquireLua() {
        /***
         *  Lua 脚本用于实现固定时间窗口的限流器。它检查当前的请求计数是否超过了限制，并在未超过限制的情况下增加计数，并设置计数器的过期时间。
         *  如果超过了限制，则不增加计数，并返回一个标志表示请求被限流。通过在 Redis 中执行这个脚本，我们可以确保即使在多个客户端同时请求时，限流器的计数也是准确和同步的
         */
        String luaScript =
                "local key = KEYS[1] " +
                        "local limit = tonumber(ARGV[1]) " +
                        "local current = tonumber(redis.call('get', key) or '0') " +
                        "if current + 1 > limit then return 0 end " +
                        "redis.call('incr', key) " +
                        "redis.call('expire', key, ARGV[2]) " +
                        "return 1";

        RBucket<Long> bucket = redissonClient.getBucket(key, LongCodec.INSTANCE);
        Long result = bucket.get();
        if (result == null) {
            List<Object> keys = Arrays.asList((Object) key);
            List<Object> values = Arrays.asList((Object) limit, (Object) windowSize);
            // 使用 Lua 脚本确保操作的原子性
            return redissonClient.getScript().eval(RScript.Mode.READ_WRITE,
                    luaScript,
                    RScript.ReturnType.INTEGER,
                    keys,
                    values.toArray());
        } else {
            return result < limit;
        }
    }
}

时序图:

FixedWindowRateLimiter 类的时序图，展示了客户端如何与限流器交互，以及限流器如何与 Redis 服务器进行通信：

在这个时序图中：

1. 客户端 发起一个 tryAcquire() 或 tryAcquireLua() 请求到 FixedWindowRateLimiter 类。
2. FixedWindowRateLimiter 类根据当前的计数和限制进行判断：
   • 如果是第一次请求或当前计数小于限制，它将向 Redis 发送 INCR 命令来增加计数器的值，并设置过期时间（EXPIRE 命令）。
   • 如果当前计数已经达到或超过限制，则不会向 Redis 发送任何命令，直接返回 false 给客户端，表示请求被拒绝。
3. Redis 服务器执行 INCR 和 EXPIRE 命令，并将结果返回给 FixedWindowRateLimiter 类。
4. 最后，FixedWindowRateLimiter 类将操作结果返回给 客户端，告知请求是否被允许。

以下是类和方法的详细介绍：

类成员变量

- redissonClient：Redisson 客户端实例，用于与 Redis 服务器进行交互。 - key：Redis 中用于存储计数器的键，通常以 "rate_limiter:" 为前缀，后跟具体的限流器名称，以区分不同的限流器。 - limit：在给定时间窗口内允许的最大请求次数。 - windowSize：时间窗口的大小，以秒为单位。

构造函数

构造函数接收 Redisson 客户端实例、限流器的名称、请求限制次数和时间窗口大小，并初始化类成员变量。

方法

- tryAcquire()：这个方法尝试获取访问权限。它使用 RAtomicLong 来原子性地增加计数器并检查当前的计数是否超过了限制。如果是第一次请求或计数器当前值小于限制，则请求被允许。如果计数器值达到或超过限制，则递减计数器并拒绝请求。这个方法在达到限制时对计数器进行递减操作，这可能在极端高并发的情况下导致窗口内的请求次数短暂地超过限制。

- tryAcquireLua()：这个方法使用 Lua 脚本来保证操作的原子性。Lua脚本检查当前的请求计数是否超过了限制，并在未超过限制的情况下增加计数，并设置计数器的过期时间。如果超过了限制，则不增加计数，并返回表示请求被限流的标志。通过在 Redis 中执行这个脚本，可以确保即使在多个客户端同时请求时，限流器的计数也是准确和同步的。

分析总结：

FixedWindowRateLimiter 类提供了两种方法来实现固定窗口限流：

- tryAcquire() 方法简单易懂，但在高并发场景下可能会短暂地允许超出限制的请求通过，因为它在达到限制后会递减计数器，这不是原子操作。 - tryAcquireLua() 方法通过使用 Lua 脚本在 Redis 服务器端执行原子操作，从而提高了限流逻辑的准确性和并发安全性。这个方法更适合高并发场景，因为它可以防止计数超限。

在实际使用中，为了确保限流器的准确性和并发性，推荐使用 tryAcquireLua() 方法。这种方法通过原子操作保证了即使在极端高并发的情况下，也不会超过设定的请求限制。

FixedWindowRateLimiter 概述

FixedWindowRateLimiter 是一个基于 Redisson 的 Java 类，实现了固定窗口限流算法。它使用 Redis 作为后端存储，以确保跨多个服务器和应用实例的限流状态共享和同步。该类提供了方法来尝试获取访问权限，根据预定义的时间窗口和请求计数限制来决定是否允许请求通过。

固定窗口算法限流概述

固定窗口算法是一种限流策略，它将时间分割成等长的窗口，对每个窗口内的请求进行计数，并限制每个窗口内允许的最大请求数量。当请求到达时，算法检查当前窗口内的请求数量是否已经达到设定的阈值。

固定窗口算法适用于对限流精度要求不是特别高的场景，以及可以接受窗口切换时可能的请求峰值的应用。在实际应用中，固定窗口算法常被用于控制 API 的调用频率或限制网站的访问速率。