基于Redis设计的限流系统【100012681】

# 基于 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 伪代码实现： ``` AtomicInteger atomic = new AtomicInteger(1) try { if(atomic.incrementAndGet() > 限流数) { //熔断逻辑 } else { //处理逻辑 } } finally { atomic.decrementAndGet(); } ``` ### 2.2、限制时间窗最大请求数 定义：时间窗最大请求数，指定的时间范围内允许的最大请求数 优点：这个算法能够满足绝大多数的流控需求，通过时间窗最大请求数可以直接换算出最大的 QPS（QPS = 请求数/时间窗） 缺点：这种方式可能会出现流量不平滑的情况，时间窗内一小段流量占比特别大 lua 代码实现： ``` --- 资源唯一标识 local key = KEYS[1] --- 时间窗最大并发数 local max_window_concurrency = tonumber(ARGV[1]) --- 时间窗 local window = tonumber(ARGV[2]) --- 时间窗内当前并发数 local curr_window_concurrency = tonumber(redis.call('get', key) or 0) if current + 1 > limit then return false else redis.call("INCRBY", key,1) if window > -1 then redis.call("expire", key,window) end return true end ``` ### 2.3、令牌桶  算法描述 - 假如用户配置的平均发送速率为 r，则每隔 1/r 秒一个令牌被加入到桶中 - 假设桶中最多可以存放 b 个令牌。如果令牌到达时令牌桶已经满了，那么这个令牌会被丢弃 - 当流量以速率 v 进入，从桶中以速率 v 取令牌，拿到令牌的流量通过，拿不到令牌流量不通过，执行熔断逻辑 属性 - 长期来看，符合流量的速率是受到令牌添加速率的影响，被稳定为：r - 因为令牌桶有一定的存储量，可以抵挡一定的流量突发情况 - - M 是以字节/秒为单位的最大可能传输速率：M>r - T max = b/(M-r) 承受最大传输速率的时间 - B max = T max * M 承受最大传输速率的时间内传输的流量 优点：流量比较平滑，并且可以抵挡一定的流量突发情况 因为我们限流系统的实现就是基于令牌桶这个算法，具体的代码实现参考下文。 ## 3、工程实现 ### 3.1、技术选型 - mysql:存储限流策略的参数等元数据 - redis+lua:令牌桶算法实现 > 说明：因为我们把 Redis 定位为：缓存、计算媒介，所以元数据都是存在 db 中 ### 3.2、架构图  ### 3.3、 数据结构 | 字段 | 描述 | | ----------- | :----------------------: | | name | 令牌桶的唯一标示 | | apps | 能够使用令牌桶的应用列表 | | max_permits | 令牌桶的最大令牌数 | | rate | 向令牌桶中添加令牌的速率 | | created_by | 创建人 | | updated_by | 更新人 | 限流系统的实现是基于 Redis 的，本可以和应用无关，但是为了做限流元数据配置的统一管理，按应用维度管理和使用，在数据结构中加入了 apps 这个字段，出现问题，排查起来也比较方便。 ### 3.4、代码实现 #### 3.4.1、代码实现遇到的问题 参考令牌桶的算法描述，一般思路是在 RateLimiter-client 放一个重复执行的线程，线程根据配置往令牌桶里添加令牌，这样的实现由如下缺点： - 需要为每个令牌桶配置添加一个重复执行的线程 - 重复的间隔精度不够精确：线程需要每 1/r 秒向桶里添加一个令牌，当 r>1000 时间线程执行的时间间隔根本没办法设置（从后面性能测试的变现来看 RateLimiter-client 是可以承担 QPS > 5000 的请求速率） #### 3.4.2、解决方案 基于上面的缺点，参考了 Google 的 guava 中 RateLimiter 中的实现，我们使用了触发式添加令牌的方式。  算法描述 - 基于上述的令牌桶算法 - 将添加令牌改成触发式的方式，取令牌的是做添加令牌的动作 - 在去令牌的时候，通过计算上一次添加令牌和当前的时间差，计算出这段间应该添加的令牌数，然后往桶里添加 - - curr_mill_second = 当前毫秒数 - last_mill_second = 上一次添加令牌的毫秒数 - r = 添加令牌的速率 - reserve_permits = (curr_mill_second-last_mill_second)/1000 * r - 添加完令牌之后再执行取令牌逻辑 #### 3.4.3、 lua 代码实现 ``` --- 获取令牌 --- 返回码 --- 0 没有令牌桶配置 --- -1 表示取令牌失败，也就是桶里没有令牌 --- 1 表示取令牌成功 --- @param key 令牌（资源）的唯一标识 --- @param permits 请求令牌数量 --- @param curr_mill_second 当前毫秒数 --- @param context 使用令牌的应用标识 local function acquire(key, permits, curr_mill_second, context) local rate_limit_info = redis.pcall("HMGET", key, "last_mill_second", "curr_permits", "max_permits", "rate", "apps") local last_mill_second = rate_limit_info[1] local curr_permits = tonumber(rate_limit_info[2]) local max_permits = tonumber(rate_limit_info[3]) local rate = rate_limit_info[4] local apps = rate_limit_info[5] --- 标识没有配置令牌桶 if type(apps) == 'boolean' or apps == nil or not contains(apps, context) then return 0 end local local_curr_permits = max_permits; --- 令牌桶刚刚创建，上一次获取令牌的毫秒数为空 --- 根据和上一次向桶里添加令牌的时间和当前时间差，触发式往桶里添加令牌 --- 并且更新上一次向桶里添加令牌的时间 --- 如果向桶里添加的令牌数不足一个，则不更新上一次向桶里添加令牌的时间 if (type(last_mill_second) ~= 'boolean' and last_mill_second ~= false and last_mill_second ~= nil) then local reverse_permits = math.floor(((curr_mill_second - last_mill_second) / 1000) * rate) local expect_curr_permits = reverse_permits + curr_permits; local_curr_permits = math.min(expect_c