大话常用限流算法与应用场景_限流算法优缺点

计数器限流算法

模拟需求描述

公司产品老大让做一个抢金币的活动，规定一个用户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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21

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

实现结果分析

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

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

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

滑动窗口限流算法

模拟需求描述

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

解决办法

小N决定用时间窗口来解决这个问题。每次统计时以5秒为单位统计当前时间前5秒的请求是否超过限制

小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;
    }
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23

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

实现结果分析

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

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

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

令牌桶限流算法

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

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

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

模拟需求描述

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

解决办法

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

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

小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;
    }
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

小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决定采用漏斗限流算法来解决限流时不允许有突发的需求

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

大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);
            }
        }
    }
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

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

实现结果分析

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

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

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

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

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

总结

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

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

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