大话常用限流算法与应用场景

红太狼 2022-12-25 03:59 108阅读 0赞

## 计数器限流算法 ##

### 模拟需求描述 ###

公司产品老大让做一个抢金币的活动，规定一个用户5秒内最多抢10个金币

### 解决办法 ###

初级工程师小J(junior)同学拿到这个需求后立马就开干,直接用userid为key在redis中存储，来一个请求就让计数器自增一下再拿到自增后的结果，判断结果值是否超过了规定的阀值，再来个将key设为5秒过期

小A然后快速写出代码：

/**
         * 限制为5秒10次
         */
        private Long rangeSeconds = 5L;
        private Integer maxRate = 10;
    
    
        /**
         * 优点：编码简单
         * 缺点：边界值统计不准确
         */
        @RequestMapping(value = "setnxlimit")
        public Object setnxlimit(Long userId) {
            String key = "setnxlimit:userid:" + userId;
            Long increment = redisTemplate.opsForValue().increment(key);
            redisTemplate.expire(key, rangeSeconds, TimeUnit.SECONDS);
            if (increment > maxRate) {
                return "限流了!";
            }
            return increment;
        }

小J开发好后这个需求他开始膨胀了，心想着：没错，我就是个人才，分分钟搞定了这个需求

### 实现结果分析 ###

测试大佬大T对小A发布后的代码进行了测试，初步测试发现确实实现了一个用户5秒内最多只能有10个请求可以成功的要求。但是测试大佬大T在测试时发现对于如果每秒持续发送请求，会造成一直提示限流的情况，统计在边界点有并不准确  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70_pic_center]

因为小J的功能统计不准确，大T向小J打回了BUG，说他这个功能有问题，统计不准确。于是身为人才的小A与测试测试大佬大T吵起来了

此时小J的研发小组长大H过来了，分析了下原因，是因为计数器算法限流对于最后一次请求时会一直对KEY进行续期导致的。为了快速搞定这个功能，大H让中级工程师小N(normal)来协助下小J来实现限流这个需求

## 滑动窗口限流算法 ##

### 模拟需求描述 ###

公司产品老大让做一个抢金币的活动，规定一个用户5秒内最多抢3个金币

### 解决办法 ###

小N决定用时间窗口来解决这个问题。每次统计时以5秒为单位统计当前时间前5秒的请求是否超过限制  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70_pic_center 1]

小N然后快速写出代码：

/**
         * 滑动窗口<br>
         * 优点：统计精准，可以解决边界值
         * 缺点：如果限制范围长，则数据量可能会比较大
         */
        @RequestMapping(value = "windowLimit")
        public Object windowLimit(Long userId) {
            String key = "windowLimit:userid:" + userId;
            ZSetOperations<String, String> zSetOperations = redisTemplate.opsForZSet();
            long currentTimeMillis = System.currentTimeMillis();
            long startTimeMillis = currentTimeMillis - rangeSeconds * 1000;
            zSetOperations.add(key, currentTimeMillis + "", currentTimeMillis);
            //干掉当前时间5秒前的数据
            zSetOperations.removeRangeByScore(key, 0, startTimeMillis);
            //统计
            Long count = zSetOperations.zCard(key);
            //加个过期时间，防止数据过多
            redisTemplate.expire(key, rangeSeconds, TimeUnit.SECONDS);
            if (count > maxRate) {
                return "限制流了.当前:" + count;
            }
            return count;
        }

小N开发好后这个需求他开始膨胀了，心想着：没错，我就是个人才，分分钟搞定了这个小A搞不定的需求

### 实现结果分析 ###

测试大佬大T对小N发布后的代码进行了测试，发现确实实现了产品所提的需求

因为小N的功能统计准确，然后大T同意了小N的代码进行上线

大N心想着：看来姜还是老的辣呀，小N是个人才

## 令牌桶限流算法 ##

在小N的代码上线到服务器后，运维大佬大G通过监控发现redis的内存占用随着用户量的增加暴增了许多，这时大G慌了，心想着：这可不行，redis内存使用增长太快了，万一redis崩了他的地位可不保了呀，赶紧向研发小组长大H求助寻求支援吧  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70_pic_center 2]

研发小组长大H看了下小N提交的代码,一下就发现了问题的所在。因为滑动窗口算法用到了zset实现的，它会将用户的每次请求都记录到zset中，这样就会导致redis内存占用过高

为了快速解决滑动窗口限流算法占用内存过多的问题，大H决定将派出高级软件工程师小S(senior)来协助小N解决解决上面的需求

### 模拟需求描述 ###

公司产品老大让做一个抢金币的活动，规定一个用户5秒内最多抢10个金币

### 解决办法 ###

为了解决滑动窗口限流算法占用过多存储空间的问题，小S决定采用令牌桶限流算法来解决这个问题

小S在脑海中将令牌桶算法的思路回忆了一下：假设每个请求想要访问某个资源，在访问前必须先拿到一个门票(token)才能进入访问，token的产生是按照一定的速度恒定产生的，token产生后放在一个桶内，顺便给这个桶取个名字就叫它令牌桶。当令牌桶内的令牌充足时，才能向请求者下发令牌，令牌桶内令牌不足时则进行限流。如果某段时间内桶内的令牌数太多，则令牌则会溢出。令牌桶限流算法因为只需要很少的几个变量便可实现，相比于滑动窗口限流算法来讲漏斗算法更加节约内存空间  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70_pic_center 3]

小S然后快速写出代码：

### 实现结果分析 ###

/**
         * 令牌桶<br>
         */
        @RequestMapping(value = "tokenBucketLimit")
        public Object tokenBucketLimit(Long userId) {
            String key = "tokenBucketLimit:userid:" + userId;
            //令牌桶容量
            int tokenBucketCapacity = 10;
            //token生成速率
            int tokenProduceRate = 2;
            Object lastOperationTime = redisTemplate.opsForHash().get(key, "lastOperationTime");
            if (lastOperationTime == null) {
                //令牌桶初始化
                redisTemplate.opsForHash().put(key, "lastOperationTime", System.currentTimeMillis() + "");
                //当前剩余令牌数
                redisTemplate.opsForHash().put(key, "leftTokenCount", 0 + "");
            } else {
                Long lastOperationTimeValue = Long.valueOf(redisTemplate.opsForHash().get(key, "lastOperationTime") + "");
                //剩余令牌数
                Long leftTokenCount = Long.valueOf(redisTemplate.opsForHash().get(key, "leftTokenCount") + "");
                //距离上一次请求产生的token数
                long newGenrateToken = ((System.currentTimeMillis() - lastOperationTimeValue) / 1000) * tokenProduceRate;
                leftTokenCount = Math.min(tokenBucketCapacity, leftTokenCount + newGenrateToken);
                if ((leftTokenCount) > tokenBucketCapacity) {
                    //剩余token数自减
                    redisTemplate.opsForHash().put(key, "leftTokenCount", (--leftTokenCount) + "");
                    return true;
                } else {
                    return "已限流";
                }
            }
            return null;
        }

小S开发好后这个需求他开始膨胀了，心想着：没错，我就是个人才，分分钟搞定了这个小N搞不定的需求

### 实现结果分析 ###

测试大佬大T对小S发布后的代码进行了测试，发现确实实现了产品所提的需求

因为小S的功能统计准确，然后大T同意了小S的代码进行上线

上线后运维大佬大G通过观察系统监控，观察redis的内存使用情况发现小S的代码比之前小N时提交的代码更加节约了内存

大N心想着：这TM究竟修改了个啥?我TM还真没有测出来,感觉结果没得啥变化呀。不管了，总之小N和小S都是人才

大G心想着：看来真是强中更有强中手，小S是个人才

## 漏斗限流算法 ##

在小S的代码上线到服务器后，运维大佬大G通过监控发现虽然redis的内存占用量低了，但某段时间内的服务器CPU资源占用很高，这时大G又慌了，心想着：这可不行，cpu使用率不稳定，万一服务器崩了他的地位还是保不住呀，赶紧再次向研发小组长大H求助寻求支援吧

### 模拟需求描述 ###

公司产品老大让做一个抢金币的活动，规定一个用户5秒内最多抢10个金币，并保证请求稳定,不允许有突发请求

### 解决办法 ###

为了实现请求限流并保证请求平稳，研发小组长大H决定亲自出马了

大H决定采用漏斗限流算法来解决限流时不允许有突发的需求

其解决思路大致辞是这样的：根据漏斗流水的结构来进行类比，通过维护漏斗容量、漏斗流水速度、当前漏斗内水总量这几个变量来进行限流控制。因为漏斗的出水率的速度是恒定的，则可以确保服务器的请求平稳  
![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70_pic_center 4]

大H然后快速写出代码：

/**
         * 漏斗算法限流<br>
         */
        @RequestMapping(value = "funnelLimit")
        public Object funnelLimit(Long userId) {
            String key = "windowLimit:userid:" + userId;
            HashOperations<String, Object, Object> opsForHash = redisTemplate.opsForHash();
            Object capacityValue = opsForHash.get(key, "capacity");
            Object passRateValue = opsForHash.get(key, "passRate");
            if (capacityValue == null) {
                //初始化漏斗容量,最多10个请求,
                opsForHash.put(key, "capacity", maxRate.longValue() + "");
                //初始化上次操作时间
                opsForHash.put(key, "lastOperationTime", System.currentTimeMillis() + "");
                //通过速率,每秒最多处理几个请求,2杯水
                opsForHash.put(key, "passRate", 2L + "");
                //当前水量
                opsForHash.put(key, "currentWater", 0L + "");
                return true;
            } else {
                //获取出上次的请求时间
                Long lastOperationTime = Long.valueOf(opsForHash.get(key, "lastOperationTime") + "");
                //当前时间
                Long currentTimeMillis = System.currentTimeMillis();
                //计算本次请求到上次请求期间的水量;将时间差转为秒,再乘以每秒允许通过的速率;水继续流着
                long waterPass = ((currentTimeMillis - lastOperationTime) / 1000) * Long.valueOf(passRateValue + "");
                //获取出当前水量
                Long currentWater = Long.valueOf(opsForHash.get(key, "currentWater") + "");
                //桶里的水量-这段期间应该通过的水量
                currentWater = Math.max(0, currentWater - waterPass);
                //判断桶内剩余空间是否足够;
                if (Long.valueOf(capacityValue + "") >= currentWater + 1) {
                    //允许通过；加水
                    currentWater = currentWater + 1;
                    opsForHash.put(key, "currentWater", currentWater + "");
                    opsForHash.put(key, "lastOperationTime", currentTimeMillis + "");
                    return true;
                } else {
                    return "已限流!" + (currentWater + 1);
                }
            }
        }

大H开发好后这个需求他仍然淡定着

### 实现结果分析 ###

测试大佬大N对大H发布后的代码进行了测试，发现确实实现了产品所提的需求

因为大H的功能统计准确，然后大N同意了大H的代码进行上线

上线后运维大佬大G通过观察系统监控，发现在用户量很多时cpu资源也达到平稳了

测试大佬大N心想着：这TM究竟又修改了个啥?实不相瞒我TM还真没有测出来,感觉结果仍然没得啥变化呀。不管了，总之小N和小S和大H都是人才

运维大佬大G心想着：研发小组长大H并非浪得虚名呀，大H才真的是个人才

## 总结 ##

*  计数器限流算法(简单粗暴但边界值统计不准确)
 *  滑动窗口限流算法(统计准确易理解，占用存储空间高，且不能保证请求稳定)
 *  令牌桶限流算法(相比滑动窗口限流算法占用空间少，但不能避免请求某段时间内请求被突然打满(突发情况)的场景)
 *  漏斗限流算法(相比滑动窗口限流算法占用空间少，可以严格限制突发情况)

限流算法的选择就像谈恋爱，不同的限流算法对应着不同的妹子各有特点，至于究竟最后要和哪个妹子谈恋爱，需要在深入了解了各自的特点后再进行选择

总之还是那句话，没有最好的，只有最合适的(具体要用哪种限流算法得要看具体的项目和应用场景)

[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70_pic_center]: /images/20221120/28d899d2a0f74820acdf1c2d427fc890.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70_pic_center 1]: /images/20221120/ad0fdb791ef74656837833c34658e38f.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70_pic_center 2]: /images/20221120/b25bb408fb24477ab5802df351ce9885.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70_pic_center 3]: /images/20221120/3bc809c40a064bd0b50c3ebc18a06dbe.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3B1aGFpeWFuZw_size_16_color_FFFFFF_t_70_pic_center 4]: /images/20221120/9e52ca7ae00f4699aa2f026d318bcd7a.png