[大数据]Redis之zset实现滑动窗口限流

本文已收录于专栏

??《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次，很显然这种设计是错误的。

3、滑动窗口算法

3.1 解决方案

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

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

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中元素覆盖！

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

?TimeUnit.MILLISECONDS.sleep(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()就知道了！多思考问题，技术其实都在心里！