Redis之zset实现滑动窗口限流

左手的ㄟ右手 2022-09-10 09:23 115阅读 0赞

**本文已收录于专栏**

[❤️《Redis之大厂必备技能包》❤️][Redis]

**上千人点赞收藏的，全套Redis学习资料，大厂必备技能！**

--------------------

**目录**

1、需求

2、常见的错误设计

3、滑动窗口算法

3.1 解决方案

3.2 pipeline代码实现

3.3 lua代码实现

--------------------

## 1、需求 ##

限定用户的某个行为在指定时间T内，只允许发生N次。假设T为1秒钟，N为1000次。

## 2、常见的错误设计 ##

程序员设计了一个在每分钟内只允许访问1000次的限流方案，如下图01:00s-02:00s之间只允许访问1000次，这种设计最大的问题在于，请求可能在01:59s-02:00s之间被请求1000次，02:00s-02:01s之间被请求了1000次，这种情况下01:59s-02:01s间隔0.02s之间被请求2000次，很显然这种设计是错误的。

![错误限流.png][.png]

## 3、滑动窗口算法 ##

### 3.1 解决方案 ###

指定时间T内，只允许发生N次。我们可以将这个指定时间T，看成一个滑动时间窗口（定宽）。我们采用Redis的zset基本数据类型的score来圈出这个滑动时间窗口。在实际操作zset的过程中，我们只需要保留在这个滑动时间窗口以内的数据，其他的数据不处理即可。

*  每个用户的行为采用一个zset存储，score为毫秒时间戳，value也使用毫秒时间戳（比UUID更加节省内存）
 *  只保留滑动窗口时间内的行为记录，如果zset为空，则移除zset，不再占用内存（节省内存）

![zset滑动窗口限流.png][zset_.png]

### 3.2 pipeline代码实现 ###

代码的实现的逻辑是统计滑动窗口内zset中的行为数量，并且与阈值maxCount直接进行比较就可以判断当前行为是否被允许。这里涉及多个redis操作，因此使用pipeline可以大大提升效率

package com.lizba.redis.limit;
    
    import redis.clients.jedis.Jedis;
    import redis.clients.jedis.Pipeline;
    import redis.clients.jedis.Response;
    
    /**
     * <p>
     *     通过zset实现滑动窗口算法限流
     * </p>
     *
     * @Author: Liziba
     * @Date: 2021/9/6 18:11
     */
    public class SimpleSlidingWindowByZSet {
    
        private Jedis jedis;
    
        public SimpleSlidingWindowByZSet(Jedis jedis) {
            this.jedis = jedis;
        }
    
        /**
         * 判断行为是否被允许
         *
         * @param userId        用户id
         * @param actionKey     行为key
         * @param period        限流周期
         * @param maxCount      最大请求次数（滑动窗口大小）
         * @return
         */
        public boolean isActionAllowed(String userId, String actionKey, int period, int maxCount) {
            String key = this.key(userId, actionKey);
            long ts = System.currentTimeMillis();
            Pipeline pipe = jedis.pipelined();
            pipe.multi();
            pipe.zadd(key, ts, String.valueOf(ts));
            // 移除滑动窗口之外的数据
            pipe.zremrangeByScore(key, 0, ts - (period * 1000));
            Response<Long> count = pipe.zcard(key);
            // 设置行为的过期时间，如果数据为冷数据，zset将会删除以此节省内存空间
            pipe.expire(key, period);
            pipe.exec();
            pipe.close();
            return count.get() <= maxCount;
        }
    
    
        /**
         * 限流key
         *
         * @param userId
         * @param actionKey
         * @return
         */
        public String key(String userId, String actionKey) {
            return String.format("limit:%s:%s", userId, actionKey);
        }
    
    }

**测试代码：**

package com.lizba.redis.limit;
    
    import redis.clients.jedis.Jedis;
    
    /**
     *
     * @Author: Liziba
     * @Date: 2021/9/6 20:10
     */
    public class TestSimpleSlidingWindowByZSet {
    
        public static void main(String[] args) {
            Jedis jedis = new Jedis("192.168.211.108", 6379);
            SimpleSlidingWindowByZSet slidingWindow = new SimpleSlidingWindowByZSet(jedis);
            for (int i = 1; i <= 15; i++) {
                boolean actionAllowed = slidingWindow.isActionAllowed("liziba", "view", 60, 5);
    
                System.out.println("第" + i +"次操作" + (actionAllowed ? "成功" : "失败"));
            }
    
            jedis.close();
        }
    
    }

**测试效果：**  
从测试输出的数据可以看出，起到了限流的效果，从第11次以后的请求操作都是失败的，但是这个和我们允许的5次误差还是比较大的。这个问题的原因是我们测试System.currentTimeMillis()的毫秒可能相同，而且此时value也是System.currentTimeMillis()也相同，会导致zset中元素覆盖！

![image.png][]

**修改代码测试：**  
在循环中睡眠1毫秒即可，测试结果符合预期！

TimeUnit.MILLISECONDS.sleep(1);

![image.png][image.png 1]

### 3.3 lua代码实现 ###

我们在项目中使用原子性的lua脚步来实现限流的使用会更多，因此这里也提供一个基于操作zset的lua版本

package com.lizba.redis.limit;
    
    import com.google.common.collect.ImmutableList;
    import redis.clients.jedis.Jedis;
    import redis.clients.jedis.Pipeline;
    import redis.clients.jedis.Response;
    
    /**
     * <p>
     *     通过zset实现滑动窗口算法限流
     * </p>
     *
     * @Author: Liziba
     * @Date: 2021/9/6 18:11
     */
    public class SimpleSlidingWindowByZSet {
    
        private Jedis jedis;
    
        public SimpleSlidingWindowByZSet(Jedis jedis) {
            this.jedis = jedis;
        }
    
        /**
         * lua脚本限流
         *
         * @param userId
         * @param actionKey
         * @param period
         * @param maxCount
         * @return
         */
        public boolean isActionAllowedByLua(String userId, String actionKey, int period, int maxCount) {
            String luaScript = this.buildLuaScript();
    
            String key = key(userId, actionKey);
            long ts = System.currentTimeMillis();
            System.out.println(ts);
            ImmutableList<String> keys = ImmutableList.of(key);
            ImmutableList<String> args = ImmutableList.of(String.valueOf(ts),String.valueOf((ts - period * 1000)), String.valueOf(period));
            Number count = (Number) jedis.eval(luaScript, keys, args);
    
            return count != null && count.intValue() <= maxCount;
        }
    
    
        /**
         * 限流key
         *
         * @param userId
         * @param actionKey
         * @return
         */
        private String key(String userId, String actionKey) {
            return String.format("limit:%s:%s", userId, actionKey);
        }
    
    
        /**
         * 针对某个key使用lua脚本限流
         *
         * @return
         */
        private String buildLuaScript() {
            return "redis.call('ZADD', KEYS[1], tonumber(ARGV[1]), ARGV[1])" +
                    "\nlocal c" +
                    "\nc = redis.call('ZCARD', KEYS[1])" +
                    "\nredis.call('ZREMRANGEBYSCORE', KEYS[1], 0, tonumber(ARGV[2]))" +
                    "\nredis.call('EXPIRE', KEYS[1], tonumber(ARGV[3]))" +
                    "\nreturn c;";
    
        }
    
    }

测试代码不变，大家可以自行测试，记得还是要考虑我们测试的时候System.currentTimeMillis()相等的问题，不信你输出System.currentTimeMillis()就知道了！多思考问题，技术其实都在心里！

[Redis]: https://blog.csdn.net/qq_41125219/category_11179094.html
[.png]: /images/20220829/7220aa53547a4e10a9d5cad10e413fa2.png
[zset_.png]: /images/20220829/cc0610421e2042d6b6c81b4c44e91c30.png
[image.png]: /images/20220829/ddf88e98434f40159e54c0144ed66019.png
[image.png 1]: /images/20220829/97434e04b83c4f76848d472a4a24e760.png