5种限流算法，7种限流方式，挡住突发流量？（三）-阿里云开发者社区

5种限流算法，7种限流方式，挡住突发流量？（三）

2022-04-14 570

版权

本文内容由阿里云实名注册用户自发贡献，版权归原作者所有，阿里云开发者社区不拥有其著作权，亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容，填写侵权投诉表单进行举报，一经查实，本社区将立刻删除涉嫌侵权内容。

本文涉及的产品

云数据库 Redis 版，社区版 2GB

简介： 5种限流算法，7种限流方式，挡住突发流量？

7. Redis 分布式限流

Redis 是一个开源的内存数据库，可以用来作为数据库、缓存、消息中间件等。Redis 是单线程的，又在内存中操作，所以速度极快，得益于 Redis 的各种特性，所以使用 Redis 实现一个限流工具是十分方便的。

下面的演示都基于Spring Boot 项目，并需要以下依赖。

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

配置 Redis 信息。

spring:
  redis:
    database: 0
    password: 
    port: 6379
    host: 127.0.0.1
    lettuce:
      shutdown-timeout: 100ms
      pool:
        min-idle: 5
        max-idle: 10
        max-active: 8
        max-wait: 1ms

7.1. 固定窗口限流

Redis 中的固定窗口限流是使用 incr 命令实现的，incr 命令通常用来自增计数；如果我们使用时间戳信息作为 key，自然就可以统计每秒的请求量了，以此达到限流目的。

这里有两点要注意。

对于不存在的 key，第一次新增时，value 始终为 1。
INCR 和 EXPIRE 命令操作应该在一个原子操作中提交，以保证每个 key 都正确设置了过期时间，不然会有 key 值无法自动删除而导致的内存溢出。

由于 Redis 中实现事务的复杂性，所以这里直接只用 lua 脚本来实现原子操作。下面是 lua 脚本内容。

local count = redis.call("incr",KEYS[1])
if count == 1 then
  redis.call('expire',KEYS[1],ARGV[2])
end
if count > tonumber(ARGV[1]) then
  return 0
end
return 1

下面是使用 Spring Boot 中 RedisTemplate 来实现的 lua 脚本调用测试代码。

/**
 * @author https://www.wdbyte.com
 */
@SpringBootTest
class RedisLuaLimiterByIncr {
    private static String KEY_PREFIX = "limiter_";
    private static String QPS = "4";
    private static String EXPIRE_TIME = "1";
    @Autowired
    private StringRedisTemplate stringRedisTemplate;
    @Test
    public void redisLuaLimiterTests() throws InterruptedException, IOException {
        for (int i = 0; i < 15; i++) {
            Thread.sleep(200);
            System.out.println(LocalTime.now() + " " + acquire("user1"));
        }
    }
    /**
     * 计数器限流
     *
     * @param key
     * @return
     */
    public boolean acquire(String key) {
        // 当前秒数作为 key
        key = KEY_PREFIX + key + System.currentTimeMillis() / 1000;
        DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
        redisScript.setResultType(Long.class);
        //lua文件存放在resources目录下
        redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("limiter.lua")));
        return stringRedisTemplate.execute(redisScript, Arrays.asList(key), QPS, EXPIRE_TIME) == 1;
    }
}

代码中虽然限制了 QPS 为 4，但是因为这种限流实现是把毫秒时间戳作为 key 的，所以会有临界窗口突变的问题，下面是运行结果，可以看到因为时间窗口的变化，导致了 QPS 超过了限制值 4。

17:38:23.122044 true
17:38:23.695124 true
17:38:23.903220 true
# 此处有时间窗口变化，所以下面继续 true
17:38:24.106206 true
17:38:24.313458 true
17:38:24.519431 true
17:38:24.724446 true
17:38:24.932387 false
17:38:25.137912 true
17:38:25.355595 true
17:38:25.558219 true
17:38:25.765801 true
17:38:25.969426 false
17:38:26.176220 true
17:38:26.381918 true

7.3. 滑动窗口限流

通过对上面的基于 incr 命令实现的 Redis 限流方式的测试，我们已经发现了固定窗口限流所带来的问题，在这篇文章的第三部分已经介绍了滑动窗口限流的优势，它可以大幅度降低因为窗口临界突变带来的问题，那么如何使用 Redis 来实现滑动窗口限流呢？

这里主要使用 ZSET 有序集合来实现滑动窗口限流，ZSET 集合有下面几个特点：

ZSET 集合中的 key 值可以自动排序。
ZSET 集合中的 value 不能有重复值。
ZSET 集合可以方便的使用 ZCARD 命令获取元素个数。
ZSET 集合可以方便的使用 ZREMRANGEBYLEX 命令移除指定范围的 key 值。

基于上面的四点特性，可以编写出基于 ZSET 的滑动窗口限流 lua 脚本。

--KEYS[1]: 限流 key
--ARGV[1]: 时间戳 - 时间窗口
--ARGV[2]: 当前时间戳（作为score）
--ARGV[3]: 阈值
--ARGV[4]: score 对应的唯一value
-- 1. 移除时间窗口之前的数据
redis.call('zremrangeByScore', KEYS[1], 0, ARGV[1])
-- 2. 统计当前元素数量
local res = redis.call('zcard', KEYS[1])
-- 3. 是否超过阈值
if (res == nil) or (res < tonumber(ARGV[3])) then
    redis.call('zadd', KEYS[1], ARGV[2], ARGV[4])
    return 1
else
    return 0
end

下面是使用 Spring Boot 中 RedisTemplate 来实现的 lua 脚本调用测试代码。

@SpringBootTest
class RedisLuaLimiterByZset {
    private String KEY_PREFIX = "limiter_";
    private String QPS = "4";
    @Autowired
    private StringRedisTemplate stringRedisTemplate;
    @Test
    public void redisLuaLimiterTests() throws InterruptedException, IOException {
        for (int i = 0; i < 15; i++) {
            Thread.sleep(200);
            System.out.println(LocalTime.now() + " " + acquire("user1"));
        }
    }
    /**
     * 计数器限流
     *
     * @param key
     * @return
     */
    public boolean acquire(String key) {
        long now = System.currentTimeMillis();
        key = KEY_PREFIX + key;
        String oldest = String.valueOf(now - 1_000);
        String score = String.valueOf(now);
        String scoreValue = score;
        DefaultRedisScript<Long> redisScript = new DefaultRedisScript<>();
        redisScript.setResultType(Long.class);
        //lua文件存放在resources目录下
        redisScript.setScriptSource(new ResourceScriptSource(new ClassPathResource("limiter2.lua")));
        return stringRedisTemplate.execute(redisScript, Arrays.asList(key), oldest, score, QPS, scoreValue) == 1;
    }
}

代码中限制 QPS 为 4，运行结果信息与之一致。

17:36:37.150370 true
17:36:37.716341 true
17:36:37.922577 true
17:36:38.127497 true
17:36:38.335879 true
17:36:38.539225 false
17:36:38.745903 true
17:36:38.952491 true
17:36:39.159497 true
17:36:39.365239 true
17:36:39.570572 false
17:36:39.776635 true
17:36:39.982022 true
17:36:40.185614 true
17:36:40.389469 true

这里介绍了 Redis 实现限流的两种方式，当然使用 Redis 也可以实现漏桶和令牌桶两种限流算法，这里就不做演示了，感兴趣的可以自己研究下。

8. 总结

这篇文章介绍实现限流的几种方式，主要是窗口算法和桶算法，两者各有优势。

窗口算法实现简单，逻辑清晰，可以很直观的得到当前的 QPS 情况，但是会有时间窗口的临界突变问题，而且不像桶一样有队列可以缓冲。
桶算法虽然稍微复杂，不好统计 QPS 情况，但是桶算法也有优势所在。

漏桶模式消费速率恒定，可以很好的保护自身系统，可以对流量进行整形，但是面对突发流量不能快速响应。
令牌桶模式可以面对突发流量，但是启动时会有缓慢加速的过程，不过常见的开源工具中已经对此优化。

单机限流与分布式限流

上面演示的基于代码形式的窗口算法和桶算法限流都适用于单机限流，如果需要分布式限流可以结合注册中心、负载均衡计算每个服务的限流阈值，但这样会降低一定精度，如果对精度要求不是太高，可以使用。

而 Redis 的限流，由于 Redis 的单机性，本身就可以用于分布式限流。使用 Redis 可以实现各种可以用于限流算法，如果觉得麻烦也可以使用开源工具如 redisson，已经封装了基于 Redis 的限流。

其他限流工具

文中已经提到了 Guava 的限流工具包，不过它毕竟是单机的，开源社区中也有很多分布式限流工具，如阿里开源的 Sentinel 就是不错的工具，Sentinel 以流量为切入点，从流量控制、熔断降级、系统负载保护等多个维度保护服务的稳定性。

一如既往，文章中的代码存放在：github.com/niumoo/JavaNotes

参考

Redis INCR:https://redis.io/commands/incr

Rate Limiting Wikipedia：https://en.wikipedia.org/wiki/Rate_limiting

SpringBoot Redis:https://www.cnblogs.com/lenve/p/10965667.html

5种限流算法，7种限流方式，挡住突发流量？（三）

7. Redis 分布式限流

7.1. 固定窗口限流

7.3. 滑动窗口限流

8. 总结

参考

热门文章

最新文章

相关课程

相关电子书

相关实验场景