devbox
繁依Fanyi0
这个屌丝很懒，什么也没留下！
关注作者
热门标签
热门文章
当前位置:   article > 正文

基于Redis限流（固定窗口、滑动窗口、漏桶、令牌桶）（肝货！！！）_redis 固定窗口和滑动窗口

作者：繁依Fanyi0 | 2024-05-21 20:56:43

赞

踩

redis 固定窗口和滑动窗口

近期redis复习的比较多，在限流这方面发现好像之前理解的限流算法有问题，索性花了一天“带薪摸鱼”时间肝了一天，有问题可以评论区探讨。

废话不多说，正片开始

目录

Maven

有些不用的可以自行注释，注意：这里博主springboot版本为2.7.14

<dependencies>
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter</artifactId>
        </dependency>

        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-test</artifactId>
            <scope>test</scope>
        </dependency>

        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-web</artifactId>
        </dependency>

        <!-- redis -->
        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-data-redis</artifactId>
        </dependency>

        <!-- https://mvnrepository.com/artifact/redis.clients/jedis -->
        <dependency>
            <groupId>redis.clients</groupId>
            <artifactId>jedis</artifactId>
            <version>3.2.0</version>
        </dependency>

        <!-- https://mvnrepository.com/artifact/org.redisson/redisson-spring-boot-starter -->
        <!--redisson-->
        <dependency>
            <groupId>org.redisson</groupId>
            <artifactId>redisson-spring-boot-starter</artifactId>
            <version>3.17.6</version>
        </dependency>

        <dependency>
            <groupId>org.springframework.boot</groupId>
            <artifactId>spring-boot-starter-aop</artifactId>
        </dependency>

        <dependency>
            <groupId>org.apache.commons</groupId>
            <artifactId>commons-lang3</artifactId>
            <version>3.12.0</version>
        </dependency>
        <dependency>
            <groupId>org.apache.commons</groupId>
            <artifactId>commons-lang3</artifactId>
        </dependency>

        <dependency>
            <groupId>com.google.guava</groupId>
            <artifactId>guava</artifactId>
            <version>21.0</version>
        </dependency>
    </dependencies>

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44
  • 45
  • 46
  • 47
  • 48
  • 49
  • 50
  • 51
  • 52
  • 53
  • 54
  • 55
  • 56
  • 57
  • 58
  • 59

固定窗口

固定窗口算法实现限流其实在之前已经写过博客（基于Redis限流（aop切面+redis实现“固定窗口算法”）），这里也简单讲解下。

固定窗口算法（计数法）即是限制在指定时间内累计数量达到峰值后，触发限流条件，例如10秒内允许访问3次，当访问第4次的时候，就被限流住了，用redis在实现的话其实用的就是incr原子自增性，然后在限制时间过期达到一个时间限制的效果。

核心代码

/**
 * 固定窗口算法lua
 */
public String gdckLuaScript() {
    StringBuilder lua = new StringBuilder();
    lua.append("local c");
    lua.append("\nc = redis.call('get',KEYS[1])");
    // 调用不超过最大值，则直接返回
    lua.append("\nif c and tonumber(c) > tonumber(ARGV[1]) then");
    lua.append("\nreturn c;");
    lua.append("\nend");
    // 执行计算器自加
    lua.append("\nc = redis.call('incr',KEYS[1])");
    lua.append("\nif tonumber(c) == 1 then");
    // 从第一次调用开始限流，设置对应键值的过期
    lua.append("\nredis.call('expire',KEYS[1],ARGV[2])");
    lua.append("\nend");
    lua.append("\nreturn c;");
    return lua.toString();
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20

获取lua执行语句后进行填值调用

String luaScript = gdckLuaScript();
RedisScript<Number> redisScript = new DefaultRedisScript<>(luaScript, Number.class);
//固定窗口法
Number count = limitRedisTemplate.execute(redisScript, keys, limitCount, limitPeriod);
if (count != null && count.intValue() <= limitCount) {
    isNeedLimit = false;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7

滑动窗口算法

滑动窗口算法是在“固定窗口算法”进行的优化，固定窗口算法有个弊端，那就是限制指定时间内只能有这么多访问量，剩余全部丢弃。那对于滑动窗口算法，是将时间周期分为N个小周期，分别记录每个小周期内访问次数，并且根据时间滑动删除过期的小周期，对于删除过期的小周期这个操作，在redis中其实是采用了zset对象的做法，score控制时间窗口，只查指定时间前到现在的一个区间（窗口）的数量，随着时间的变化，窗口一直在动。

核心代码

/**
 * 滑动窗口算法lua
 */
public String hdckLuaScript() {
    StringBuilder sb = new StringBuilder();
    sb.append(" local key = KEYS[1] ");
    //sb.append(" -- 限流请求数 ");
    sb.append(" local limitCount = ARGV[1] ");
    //sb.append(" -- 限流开始时间戳（一般是当前时间减去前多少范围时间，例如前5秒） ");
    sb.append(" local startTime = ARGV[2] ");
    //sb.append(" -- 限流结束时间戳（当前时间） ");
    sb.append(" local endTime = ARGV[3] ");
    //sb.append(" -- 限流超时时间-用于清除内存-毫秒（默认与限制时间一致） ");
    sb.append(" local timeout = ARGV[4] ");
    //当前请求数
    sb.append(" local currentCount = redis.call('zcount', key, startTime, endTime)  ");
    //sb.append(" -- 限流存在并且超过限流大小，则返回剩余可用请求数=0 ");
    sb.append(" if (currentCount and tonumber(currentCount) >= tonumber(limitCount)) then ");
    sb.append("     return 0 ");
    sb.append(" end ");
    //sb.append(" -- 记录本次请求 ");
    sb.append(" redis.call('zadd', key, endTime, endTime) ");
    //sb.append(" -- 设置超时时间 ");
    sb.append(" redis.call('expire', key, timeout) ");
    //sb.append(" -- 返回剩余可用请求数 ");
    sb.append(" return tonumber(limitCount) - tonumber(currentCount) ");
    return sb.toString();
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28

获取lua执行语句后进行填值调用

String luaScript = hdckLuaScript();
RedisScript<Number> redisScript = new DefaultRedisScript<>(luaScript, Number.class);
long currentMillis = System.currentTimeMillis();
//限制时间区间毫秒
int limitPeriodHm = limitPeriod * 1000;
//之前的时间戳（用于框定窗口滑动，（之前时间到当前时间））
long beforeMillis = currentMillis - limitPeriodHm;
//滑动窗口算法
Number count = limitRedisTemplate.execute(redisScript, keys, limitCount, beforeMillis, currentMillis,limitPeriod);
if (count != null && count.intValue() > 0){
    isNeedLimit = false;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12

漏桶算法

漏桶算法的思路是访问请求到达时直接放入漏桶，如当前容量已达到上限（限流值），则进行丢弃（触发限流策略）。漏桶以固定的速率进行释放访问请求（即请求通过），直到漏桶为空。

核心代码

/**
 * 漏桶算法lua
 */
public String ltLuaScript(){
    StringBuilder sb = new StringBuilder();
    //sb.append(" --参数说明：key[1]为对应服务接口的信息，capacity为容量,passRate为漏水速率,addWater为每次请求加水量（默认为1）,water为当前水量,lastTs为时间戳 ");
    sb.append(" local limitInfo = redis.call('hmget', KEYS[1], 'capacity', 'passRate','water', 'lastTs') ");
    sb.append(" local capacity = limitInfo[1] ");
    sb.append(" local passRate = limitInfo[2] ");
    //加水量固定为1（一次请求）
    sb.append(" local addWater= 1 ");
    sb.append(" local water = limitInfo[3] ");
    sb.append(" local lastTs = limitInfo[4] ");
    //sb.append(" --初始化漏斗 ");
    sb.append(" if capacity == false or passRate == false then ");
    sb.append("     capacity = tonumber(ARGV[1]) ");
    sb.append("     passRate = tonumber(ARGV[2]) ");
    //sb.append("     --当前水量（第一次加水量） ");
    sb.append("     water = addWater ");
    sb.append("     lastTs = tonumber(ARGV[3]) ");
    sb.append("     redis.call('hmset', KEYS[1], 'capacity', capacity, 'passRate', passRate,'addWater',addWater,'water', water, 'lastTs', lastTs) ");
    sb.append("     return 1 ");
    sb.append(" else ");
    sb.append("     local nowTs = tonumber(ARGV[3]) ");
    //sb.append("     --计算距离上一次请求到现在的漏水量 ");
    sb.append("     local waterPass = tonumber((nowTs - lastTs)* passRate/1000) ");
    //sb.append("     --计算当前水量,即执行漏水 ");
    sb.append("     water=math.max(0,water-waterPass) ");
    //sb.append("     --设置本次请求的时间 ");
    sb.append("     lastTs = nowTs ");
    //sb.append("     --判断是否可以加水 ");
    sb.append("     addWater=tonumber(addWater) ");
    sb.append("     if capacity-water >= addWater then ");
    //sb.append("         --加水 ");
    sb.append("         water=water+addWater ");
    //sb.append("         --更新当前水量和时间戳 ");
    sb.append("         redis.call('hmset', KEYS[1], 'water', water, 'lastTs', lastTs) ");
    sb.append("         return 1 ");
    sb.append("     end ");
    sb.append("     return 0 ");
    sb.append(" end ");
    return sb.toString();
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43

获取lua执行语句后进行填值调用

long currentMillis = System.currentTimeMillis();
String luaScript = ltLuaScript();
RedisScript<Number>redisScript = new DefaultRedisScript<>(luaScript, Number.class);
//漏桶算法
//漏水速率（这里用的是平均速率，也可以自定义）
double passRate = limitCount / (double) limitPeriod;
//注意注意，currentMillis、passRate千万不要转字符串，会报错。。。
Number count = limitRedisTemplate.execute(redisScript, keys, limitCount, passRate, currentMillis);
if (count != null && count.intValue() > 0){//此处count为1正常加水，0加水失败即限流
    isNeedLimit = false;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11

令牌桶算法

令牌桶算法是程序以r（r=时间周期/限流值）的速度向令牌桶中增加令牌，直到令牌桶满，请求到达时向令牌桶请求令牌，如获取到令牌则通过请求，否则触发限流策略，跟漏桶有点像，不过漏桶算法是请求方是加水（自动漏水），而令牌桶算法是减少“水”（自动加“水”）。

核心代码

/**
 * 令牌桶算法lua
 */
public String lptLuaScript(){
    StringBuilder sb = new StringBuilder();
    //sb.append(" --参数说明：key[1]为对应服务接口的信息，capacity为最大容量，rate为令牌生成速率（例如500ms生成一个则为0.5）,leftTokenNum为剩余令牌数,lastTs为时间戳 ");
    sb.append(" local limitInfo = redis.call('hmget', KEYS[1], 'capacity', 'rate','leftTokenNum', 'lastTs') ");
    sb.append(" local capacity = limitInfo[1] ");
    sb.append(" local rate = limitInfo[2] ");
    sb.append(" local leftTokenNum= limitInfo[3] ");
    sb.append(" local lastTs = limitInfo[4] ");
    // 本次需要令牌数
    sb.append(" local need = 1 ");
    //sb.append(" --初始化令牌桶 ");
    sb.append(" if capacity == false or rate == false or leftTokenNum == false then ");
    sb.append("     capacity = tonumber(ARGV[1]) ");
    sb.append("     rate = tonumber(ARGV[2]) ");
    sb.append("     leftTokenNum = tonumber(ARGV[1]) - need ");
    sb.append("     lastTs = tonumber(ARGV[3]) ");
    sb.append("     redis.call('hmset', KEYS[1], 'capacity', capacity, 'rate', rate, 'leftTokenNum', leftTokenNum, 'lastTs', lastTs) ");
    sb.append("     return leftTokenNum ");
    sb.append(" else ");
    sb.append(" 	local nowTs = tonumber(ARGV[3]) ");
//        sb.append("     rate = tonumber(ARGV[2])");
    //sb.append("     --计算距离上一次请求到现在生产令牌数 ");
    sb.append("     local createTokenNum = tonumber((nowTs - lastTs)* rate/1000) ");
    //sb.append(" 	--计算该段时间的剩余令牌（当前总令牌数） ");
    sb.append("     leftTokenNum = createTokenNum + leftTokenNum ");
    //sb.append(" 	--设置剩余令牌（留下最小数） ");
    sb.append("     leftTokenNum = math.min(capacity, leftTokenNum) ");
    //sb.append(" 	--设置本次请求的时间 ");
    sb.append("     lastTs = nowTs ");
    //sb.append("     --判断是否还有令牌 ");
    sb.append("     if leftTokenNum >= need then ");
    //sb.append("         --减去需要的令牌 ");
    sb.append("         leftTokenNum = leftTokenNum - need ");
    //sb.append("         --更新剩余空间和上一次的生成令牌时间戳 ");
    sb.append("         redis.call('hmset', KEYS[1], 'capacity', capacity, 'rate', rate,'leftTokenNum', leftTokenNum, 'lastTs', lastTs) ");
    sb.append("         return leftTokenNum ");
    sb.append("     end ");
    sb.append("     return -1 ");
    sb.append(" end ");
    return sb.toString();
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
  • 34
  • 35
  • 36
  • 37
  • 38
  • 39
  • 40
  • 41
  • 42
  • 43
  • 44

获取lua执行语句后进行填值调用

long currentMillis = System.currentTimeMillis();
long luaScript = lptLuaScript();
RedisScript<Number> redisScript = new DefaultRedisScript<>(luaScript, Number.class);
//令牌桶算法
//生成令牌速率（这里用的是平均速率，也可以自定义）
double createRate = limitCount / (double) limitPeriod;
count = limitRedisTemplate.execute(redisScript, keys, limitCount, createRate, currentMillis);
if (count != null && count.intValue() >= 0){
    isNeedLimit = false;
}

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10

由于代码量过大，放置在博主资源啦，核心部分均已贴出
调用整体示例如图在这里插入图片描述

声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/繁依Fanyi0/article/detail/604605
推荐阅读
相关标签

Copyright © 2003-2013 www.wpsshop.cn 版权所有，并保留所有权利。

  

闽ICP备14008679号