本文讲述基于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中的实现，我们使用了触发式添加令牌的方式。
作者：Java邵先生
链接：https://www.jianshu.com/p/bf7e448c3678