基于Redission 实现限流3-滑动窗口算法

概述：

基于之前的基于Redission实现了固定窗口算法，本文将接着介绍基于Redission 实现滑动窗口算法。 滑动窗口算法是一种限流算法，它相比固定窗口算法，能够更平滑地限制请求速率。以下是基于 Redisson 实现滑动窗口算法的原理和优缺点：

原理

1. 窗口划分：将时间划分为多个小的固定窗口（例如每秒），而不是一个大的窗口（例如每分钟）。
2. 计数存储：每个小窗口都有自己的计数器，通常存储在 Redis 的数据结构中，如有序集合（ZSET）。
3. 请求记录：每个请求都以其到达时间作为分数（score）被添加到有序集合中。
4. 滑动计数：在每次新请求到达时，算法会移除旧的窗口中的请求记录，并统计当前窗口内的请求总数。
5. 限流判断：如果当前窗口内的请求总数超过了预设的阈值，则新请求被拒绝；否则，请求被允许。

Redisson 实现

在 Redisson 中，可以使用 Redis 的有序集合（ZSET）来实现滑动窗口算法：

• 使用 ZSET 来存储请求的时间戳作为分数。
• 在每次请求到达时，移除过期的时间戳（即超出当前滑动窗口的时间戳）。
• 使用 Redis 的 ZCOUNT 命令来获取当前窗口内的请求总数。
• 使用 Redis 的 MULTI/EXEC 事务或 Lua 脚本来确保操作的原子性。

优点

• 平滑限流：由于算法考虑了时间的连续性，因此可以更平滑地限制请求速率，避免固定窗口算法中的临界问题。
• 公平性：每个请求都有相等的机会被计算在当前窗口内，避免了窗口切换时的不公平性。
• 高精度：滑动窗口算法可以更精确地控制在任意时间段内的请求速率。

缺点

• 存储开销：由于需要记录每个请求的时间戳，滑动窗口算法可能会增加存储开销。
• 性能开销：算法需要频繁地添加和移除时间戳，以及统计当前窗口内的请求总数，这可能会增加性能开销。
• 复杂性：实现滑动窗口算法相比固定窗口算法更复杂，需要更多的逻辑来处理时间戳的添加、移除和统计。

尽管滑动窗口算法有其缺点，但它提供了更为精细和平滑的限流控制，特别适合于那些对请求速率变化敏感的应用。通过 Redisson 和 Redis 的高性能特性，可以在分布式环境中有效地实现这一算法。

代码实现：

源码：

import org.redisson.api.RScoredSortedSet;
import org.redisson.api.RScript;
import org.redisson.api.RedissonClient;
import org.redisson.client.codec.LongCodec;

import java.util.Collections;

/**
 * @Author derek_smart
 * @Date 202/5/12 11:11
 * @Description 滑动窗口实现限流器
 * <p>
 */
public class SlidingWindowRateLimiter {
    private final RedissonClient redissonClient;
    private final String key;
    private final long limit;
    private final long windowSize; // in milliseconds

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

    public boolean tryAcquire() {
        long currentTime = System.currentTimeMillis();
        long windowStart = currentTime - windowSize;
        RScoredSortedSet<Long> set = redissonClient.getScoredSortedSet(key);

        // Remove old data
        set.removeRangeByScore(0, true, windowStart, false);
        // Check the count in the current window
        if (set.size() < limit) {
            // Add the current timestamp to the set with score being the timestamp
            set.add(currentTime, currentTime);
            return true;
        } else {
            // Limit exceeded
            return false;
        }
    }

    /**
     * 使用 Redis 的事务或 Lua 脚本来保证原子性操作。
     *
     * @return
     */
    public boolean tryAcquireLua() {
        long currentTime = System.currentTimeMillis();
        long windowStart = currentTime - windowSize;
/**
 * Lua 脚本用于检查在一个给定的时间窗口内，对应的 Redis 有序集合中的元素数量（即请求次数）是否超过了限制。如果没有超过，它会将当前时间戳作为一个新的请求记录添加到集合中。
 * 如果超过了，它不会添加新请求，并返回一个标志表明请求被限流。这个操作是原子的，意味着即使在高并发的情况下，也能正确地计数和限流。
 */
        String luaScript =
                "local key = KEYS[1] " +
                        "local limit = tonumber(ARGV[1]) " +
                        "local windowStart = tonumber(ARGV[2]) " +
                        "local currentTime = tonumber(ARGV[3]) " +
                        "redis.call('zremrangebyscore', key, 0, windowStart) " +
                        "local currentSize = tonumber(redis.call('zcard', key)) " +
                        "if currentSize < limit then " +
                        "  redis.call('zadd', key, currentTime, currentTime) " +
                        "  return 1 " +
                        "else " +
                        "  return 0 " +
                        "end";
        // 使用 Lua 脚本确保操作的原子性
        Long result = redissonClient.getScript(LongCodec.INSTANCE)
                .eval(RScript.Mode.READ_WRITE,
                        luaScript,
                        RScript.ReturnType.INTEGER,
                        Collections.singletonList(key), // KEYS 参数
                        limit, windowStart, currentTime); // ARGV 参数
        return result == 1L;
    }
}

时序图：

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

在这个时序图中：

1. 客户端 发起一个 tryAcquire() 或 tryAcquireLua() 请求到 SlidingWindowRateLimiter 类。
2. SlidingWindowRateLimiter 类首先计算出当前滑动窗口的开始时间。
3. 使用 tryAcquire() 方法时，SlidingWindowRateLimiter 类将向 Redis 发送命令以移除过期的时间戳和检查当前窗口内的请求总数。如果当前窗口内的请求总数小于限制，则添加当前时间戳到集合中，并返回 true 允许请求。如果超过了限制，则不添加新请求，并返回 false 拒绝请求。
4. 使用 tryAcquireLua() 方法时，SlidingWindowRateLimiter 类将执行 Lua 脚本，该脚本将移除过期的时间戳，检查当前窗口内的请求总数，并根据结果返回是否允许请求。
5. 最后，SlidingWindowRateLimiter 类将操作结果返回给 客户端，告知请求是否被允许。

分析介绍：

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

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

构造函数

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

方法

• tryAcquire()：这个方法尝试获取访问权限。它首先计算出当前时间窗口的开始时间，然后使用 Redisson 的 RScoredSortedSet 来表示有序集合。方法中进行了两个主要操作：

  • 移除旧的数据：删除当前时间窗口开始之前的所有请求记录。
  • 检查当前窗口的计数：如果当前窗口内的请求总数小于限制，则添加当前时间戳到集合中，并返回 true 允许请求。如果超过了限制，则不添加新请求，并返回 false 拒绝请求。

• tryAcquireLua()：这个方法使用 Lua 脚本来保证操作的原子性。Lua 脚本执行以下操作：

  • 移除旧的数据：删除当前时间窗口开始之前的所有请求记录。
  • 计数当前窗口的请求总数：使用 zcard 命令获取当前窗口内的请求总数。
  • 根据当前大小与限制进行比较：如果当前窗口内的请求总数小于限制，则使用 zadd 命令添加当前时间戳到集合中，并返回 1 表示请求被允许。如果超过了限制，则返回 0 表示请求被拒绝。
  • 使用 Redisson 的 getScript 方法执行 Lua 脚本，并根据返回值确定是否允许请求。

分析

SlidingWindowRateLimiter 类实现了一个滑动窗口限流器，可以更平滑地限制请求速率，避免了固定窗口算法中的临界问题。该类的两个方法分别提供了非原子性和原子性的限流检查：

• tryAcquire() 方法简单易懂，但在高并发场景下可能存在竞态条件，因为它涉及多个 Redis 操作，这些操作不是原子性的。
• tryAcquireLua() 方法通过使用 Lua 脚本在 Redis 服务器端执行原子操作，从而提高了限流逻辑的准确性和并发安全性。这个方法更适合高并发场景，因为它可以防止计数超限。

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

SlidingWindowRateLimiter 概述

SlidingWindowRateLimiter 是一个基于 Redisson 的 Java 类，用于实现滑动窗口限流算法。该类提供了接口允许客户端在分布式环境中进行限流操作，确保在给定的时间窗口内处理的请求不会超过设定的阈值。

滑动窗口算法概述

滑动窗口算法是一种用于限流的算法，它允许在连续的时间窗口内平滑地限制请求的速率。与固定窗口算法相比，滑动窗口算法可以更加精确地控制请求的流量，避免了窗口切换时可能的请求峰值。

滑动窗口算法适用于需要精细限流控制的场景，特别是在高并发环境下，通过原子操作的实现（如 Lua 脚本），可以保证限流的准确性和一致性。