滑动窗口限流

李子捌 发表于 2021/10/15 13:19:36 2021/10/15
【摘要】 限定用户的某个行为在指定时间T内,只允许发生N次。假设T为1秒钟,N为1000次。

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

【版权声明】本文为华为云社区用户原创内容,转载时必须标注文章的来源(华为云社区),文章链接,文章作者等基本信息,否则作者和本社区有权追究责任。如果您发现本社区中有涉嫌抄袭的内容,欢迎发送邮件至:cloudbbs@huaweicloud.com进行举报,并提供相关证据,一经查实,本社区将立刻删除涉嫌侵权内容。
  • 点赞
  • 收藏
  • 关注作者

评论(0

0/1000
抱歉,系统识别当前为高风险访问,暂不支持该操作

全部回复

上滑加载中

设置昵称

在此一键设置昵称,即可参与社区互动!

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。

*长度不超过10个汉字或20个英文字符,设置后3个月内不可修改。