订阅专栏
本文已收录于专栏
❤️《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 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()就知道了!多思考问题,技术其实都在心里!