限流系列文章——滑动窗口限流

2021 年 11 月 27 日
本文字数：2832 字
阅读完需：约 9 分钟

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

发布于: 2021 年 11 月 27 日阅读数: 9

原文链接:【http://xie.infoq.cn/article/a171932f9236ab38c578eb66c】。

李子捌

关注

华为云享专家 2020.07.20 加入

公众号【李子捌】

发布

暂无评论

创作场景

限流系列文章——滑动窗口限流

1、需求

2、常见的错误设计

3、滑动窗口算法

3.1 解决方案

3.2 pipeline 代码实现

3.3 lua 代码实现

李子捌

评论