[关闭]
@kay2 2017-12-10T10:44:07.000000Z 字数 4732 阅读 4983

基于Redis的限流系统的设计

流控 redis

该文章已经迁移到了简书,地址:基于Redis的限流系统的设计,笔者以后的文章也都会放到简书上。

本文讲述基于Redis的限流系统的设计,主要会谈及限流系统中限流策略这个功能的设计;在实现方面,算法使用的是令牌桶算法来,访问Redis使用lua脚本。

1、概念

In computer networks, rate limiting is used to control the rate of traffic sent or received by a network interface controller and is used to prevent DoS attacks

用我的理解翻译一下:限流是对系统的出入流量进行控制,防止大流量出入,导致资源不足,系统不稳定。

限流系统是对资源访问的控制组件,控制主要的两个功能:限流策略熔断策略,对于熔断策略,不同的系统有不同的熔断策略诉求,有的系统希望直接拒绝、有的系统希望排队等待、有的系统希望服务降级、有的系统会定制自己的熔断策略,很难一一列举,所以本文只针对限流策略这个功能做详细的设计。

针对找出超出速率阈值的请求这个功能,限流系统中有两个基础概念:资源和策略。

熔断策略:超出速率阈值的请求的处理策略,是我自己理解的一个叫法,不是业界主流的说法。

2、限流算法

2.1、限制瞬时并发数

定义:瞬时并发数,系统同时处理的请求/事务数量

优点:这个算法能够实现控制并发数的效果

缺点:使用场景比较单一,一般用来对入流量进行控制

java伪代码实现

  1. AtomicInteger atomic = new AtomicInteger(1)
  2. try {
  3. if(atomic.incrementAndGet() > 限流数) {
  4. //熔断逻辑
  5. } else {
  6. //处理逻辑
  7. }
  8. } finally {
  9. atomic.decrementAndGet();
  10. }

2.2、限制时间窗最大请求数

定义:时间窗最大请求数,指定的时间范围内允许的最大请求数

优点:这个算法能够满足绝大多数的流控需求,通过时间窗最大请求数可以直接换算出最大的QPS(QPS = 请求数/时间窗)

缺点:这种方式可能会出现流量不平滑的情况,时间窗内一小段流量占比特别大

lua代码实现

  1. --- 资源唯一标识
  2. local key = KEYS[1]
  3. --- 时间窗最大并发数
  4. local max_window_concurrency = tonumber(ARGV[1])
  5. --- 时间窗
  6. local window = tonumber(ARGV[2])
  7. --- 时间窗内当前并发数
  8. local curr_window_concurrency = tonumber(redis.call('get', key) or 0)
  9. if current + 1 > limit then
  10. return false
  11. else
  12. redis.call("INCRBY", key,1)
  13. if window > -1 then
  14. redis.call("expire", key,window)
  15. end
  16. return true
  17. end

2.3、令牌桶

令牌桶

算法描述

属性

优点:流量比较平滑,并且可以抵挡一定的流量突发情况

因为我们限流系统的实现就是基于令牌桶这个算法,具体的代码实现参考下文。

3、工程实现

3.1、技术选型

说明:因为我们把redis 定位为:缓存、计算媒介,所以元数据都是存在db中

3.2、架构图

限流系统

3.3、 数据结构

字段 描述
name 令牌桶的唯一标示
apps 能够使用令牌桶的应用列表
max_permits 令牌桶的最大令牌数
rate 向令牌桶中添加令牌的速率
created_by 创建人
updated_by 更新人

限流系统的实现是基于redis的,本可以和应用无关,但是为了做限流元数据配置的统一管理,by应用维度管理和使用,在数据结构中加入了apps这个字段,出现问题,排查起来也比较方便。

3.4、代码实现

3.4.1、代码实现遇到的问题

参考令牌桶的算法描述,一般思路是在RateLimiter-client放一个重复执行的线程,线程根据配置往令牌桶里添加令牌,这样的实现由如下缺点:

3.4.2、解决方案

基于上面的缺点,参考了google的guava中RateLimiter中的实现,我们使用了触发式添加令牌的方式。

令牌桶实现

算法描述

3.4.3、 lua代码实现

  1. --- 获取令牌
  2. --- 返回码
  3. --- 0 没有令牌桶配置
  4. --- -1 表示取令牌失败,也就是桶里没有令牌
  5. --- 1 表示取令牌成功
  6. --- @param key 令牌(资源)的唯一标识
  7. --- @param permits 请求令牌数量
  8. --- @param curr_mill_second 当前毫秒数
  9. --- @param context 使用令牌的应用标识
  10. local function acquire(key, permits, curr_mill_second, context)
  11. local rate_limit_info = redis.pcall("HMGET", key, "last_mill_second", "curr_permits", "max_permits", "rate", "apps")
  12. local last_mill_second = rate_limit_info[1]
  13. local curr_permits = tonumber(rate_limit_info[2])
  14. local max_permits = tonumber(rate_limit_info[3])
  15. local rate = rate_limit_info[4]
  16. local apps = rate_limit_info[5]
  17. --- 标识没有配置令牌桶
  18. if type(apps) == 'boolean' or apps == nil or not contains(apps, context) then
  19. return 0
  20. end
  21. local local_curr_permits = max_permits;
  22. --- 令牌桶刚刚创建,上一次获取令牌的毫秒数为空
  23. --- 根据和上一次向桶里添加令牌的时间和当前时间差,触发式往桶里添加令牌
  24. --- 并且更新上一次向桶里添加令牌的时间
  25. --- 如果向桶里添加的令牌数不足一个,则不更新上一次向桶里添加令牌的时间
  26. if (type(last_mill_second) ~= 'boolean' and last_mill_second ~= false and last_mill_second ~= nil) then
  27. local reverse_permits = math.floor(((curr_mill_second - last_mill_second) / 1000) * rate)
  28. local expect_curr_permits = reverse_permits + curr_permits;
  29. local_curr_permits = math.min(expect_curr_permits, max_permits);
  30. --- 大于0表示不是第一次获取令牌,也没有向桶里添加令牌
  31. if (reverse_permits > 0) then
  32. redis.pcall("HSET", key, "last_mill_second", curr_mill_second)
  33. end
  34. else
  35. redis.pcall("HSET", key, "last_mill_second", curr_mill_second)
  36. end
  37. local result = -1
  38. if (local_curr_permits - permits >= 0) then
  39. result = 1
  40. redis.pcall("HSET", key, "curr_permits", local_curr_permits - permits)
  41. else
  42. redis.pcall("HSET", key, "curr_permits", local_curr_permits)
  43. end
  44. return result
  45. end

关于限流系统的所有实现细节,我都已经放到github上,gitbub地址:https://github.com/wukq/rate-limiter,有兴趣的同学可以前往查看,由于笔者经验与知识有限,代码中如有错误或偏颇,欢迎探讨和指正。

3.4.4、管理界面

前面的设计中,限流的配置是和应用关联的,为了更够更好的管理配置,需要一个统一的管理页面去对配置进行管控:

限流管理平台

3.5、性能测试

配置:aws-elasticcache-redis 2核4g

因为Ratelimiter-client的功能比较简单,基本上是redis的性能打个折扣。

4、总结

限流系统从设计到实现都比较简单,但是确实很实用,用四个字来形容就是:短小强悍,其中比较重要的是结合公司的权限体系和系统结构,设计出符合自己公司规范的限流系统。

不足

最后鸣谢一下贡献自己想法的“前人”:guava Ratelimiter、聊聊高并发系统之限流特技--开涛、API 调用次数限制实现--yigwoo


转载声明:未经授权不得转载,授权后转载请注明出处并附上原文链接。

参考书籍:

1.《Redis 设计与实现》
2.《Lua编程指南》

参考文章:

  1. https://en.wikipedia.org/wiki/Token_bucket
  2. redis官网
  3. lua编码规范
  4. 聊聊高并发系统之限流特技
  5. API 调用次数限制实现
  6. guava Ratelimiter 实现
添加新批注
在作者公开此批注前,只有你和作者可见。
回复批注