滑动窗口算法

概述

滑动窗口算法（Sliding Window Algorithm）是一种常用的限流（Rate Limiting）技术，广泛应用于接口防刷、API限流、网络流量控制等场景。它的核心思想是：在一个固定长度的时间窗口内，统计请求的数量，如果超过了设定的阈值，则拒绝后续请求，否则允许通过。

原理

窗口定义

设定一个时间窗口（如1分钟），窗口内最多允许N次请求。

窗口滑动

窗口不是固定的，而是随着时间的推移不断“滑动”。每次有新请求到来时，窗口的起止时间会根据当前时间动态调整。

请求统计

统计当前窗口内的请求数。如果请求数未超过阈值，则允许通过；否则拒绝。

实现

代码定义

 @Autowired
    private RedisTemplate<String, Object> redisTemplate;

 /**
     * 是否能通过滑动窗口的验证
     * 滑动窗口算法：
     *     描述：滑动窗口校验算法是一种用于数据流处理的高效技术，特别适用于网络通信、数据压缩和实时系统等领域。它通过维护一个动态窗口来校验数据的完整性或检测重复数据。
     *     核心概念：
     *      1. 窗口定义：固定大小的缓冲区，用于存储最近处理的数据
     *      2. 窗口滑动：新数据加入时，最旧的数据被移出窗口
     *      3. 校验机制：对窗口内的数据进行特定校验（如CRC、哈希或重复检测）
     * @param key 事件标识
     * @param windowPeriod 窗口限流的周期，单位是毫秒
     * @param windowSize 滑动窗口大小
     * @return
     */
 public boolean passThough(String key, long windowPeriod, int windowSize) {
        //风控key
        String riskControlKey = IMPlatformConstants.getKey(IMPlatformConstants.RISK_CONTROL_KEY_PREFIX, key);
        //获取当前时间
        long currentTimeStamp = System.currentTimeMillis();
        // 表示整个滑动窗口的总时长，也就是系统会在这个时长内统计请求数量，判断是否超过限流阈值。
        long length = windowPeriod * windowSize;
        long start = currentTimeStamp - length;
        //计算过期时间
        long expireTime = length + windowPeriod;
        redisTemplate.opsForZSet().add(riskControlKey, String.valueOf(currentTimeStamp), currentTimeStamp);
        // 移除[0,start]区间内的值
        redisTemplate.opsForZSet().removeRangeByScore(riskControlKey, 0, start);
        // 获取窗口内元素个数
        Long count = redisTemplate.opsForZSet().zCard(riskControlKey);
        // 过期时间 窗口长度+一个时间间隔
        redisTemplate.expire(riskControlKey, expireTime, TimeUnit.MILLISECONDS);
        //count为空不能通过
        if (count == null) {
            return false;
        }
        return count <= windowSize;
    }

可以看到，passThough 方法基于Redis 容器实现了一个滑动窗口算法。

示例

IP限流控制

比如：我们现在有一个需求，需要根据IP 进行限流控制 1秒内同一个IP 只允许访问10 次，那么调用

public static void main(String[] args) {
        RedisSlidingWindowLimitService limitService = new RedisSlidingWindowLimitService();
        // 需要限制的IP地址, 实际业务动态获取
        String ip = "127.0.0.1";
        // 窗口限流的最小周期，单位是毫秒，计算方式就是 windowPeriod = 限制周期 / 窗口大小，在这里就是 1000 / 10 = 100；
        long windowPeriod = 100;
        // 滑动窗口大小, 也就是限制的数量
        int windowSize = 10;
        boolean result = limitService.passThough(ip, windowPeriod, 10);
        if (!result) {
            System.out.println("当前IP访问达到阈值，不允许访问了！");
        }

    }

注意点：算法中 length 代表需要统计窗口的周期，我们的需求是 1秒内同一个IP最大访问10次, 所以 windowPeriod = 1000（毫秒） / 10；