基于Redis的限流系统的设计

心已赠人 2022-01-13 12:07 190阅读 0赞

本文讲述**基于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、令牌桶**

![Image 1][]

**算法描述**

假如用户配置的平均发送速率为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、架构图**

![Image 1][]

**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中的实现，我们使用了触发式添加令牌的方式。

![Image 1][]

**算法描述**

基于上述的令牌桶算法

将添加令牌改成触发式的方式，取令牌的是做添加令牌的动作

在去令牌的时候，通过计算上一次添加令牌和当前的时间差，计算出这段间应该添加的令牌数，然后往桶里添加

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\_curr\_permits, max\_permits);

\--- 大于0表示不是第一次获取令牌，也没有向桶里添加令牌

if (reverse\_permits > 0) then

redis.pcall("HSET", key, "last\_mill\_second", curr\_mill\_second)

end

else

redis.pcall("HSET", key, "last\_mill\_second", curr\_mill\_second)

end

local result = -1

if (local\_curr\_permits - permits >= 0) then

result = 1

redis.pcall("HSET", key, "curr\_permits", local\_curr\_permits - permits)

else

redis.pcall("HSET", key, "curr\_permits", local\_curr\_permits)

end

return result

end

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

**3.4.4、管理界面**

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

按应用对限流配置进行管理

不同的人分配不同的权限；相关人员有查看配置的权限，负责人有修改和删除配置的权限

![Image 1][]

**3.5、性能测试**

**配置**：aws-elasticcache-redis 2核4g

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

单线程取令牌：Ratelimiter-client的 QPS = 250/s

10个线程取令牌：Ratelimiter-client的 QPS = 2000/s

100个线程取令牌：Ratelimiter-client的 QPS = 5000/s

**4、总结**

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

**不足**：

redis 我们用的是单点redis，只做了主从，没有使用redis高可用集群（可能使用redis高可用集群，会带来新的问题）

限流系统目前只做了应用层面的实现，没有做接口网关上的实现

熔断策略需要自己定制，如果实现的好一点，可以给一些常用的熔断策略模板

参考书籍：

1.《*Redis* 设计与实现》

2.《*Lua*编程指南》

参考文章：

1. redis官网

2. lua编码规范

3. 聊聊高并发系统之限流特技

4. guava Ratelimiter 实现

5. Token\_bucket wiki 词条

[Image 1]:

基于Redis的限流系统的设计

发表评论取消回复

还没有评论，来说两句吧...

相关阅读

相关 JAVA：基于Redis 实现计数器限流

相关基于Redis的限流实现方案

相关 redis限流

相关基于Redis有序集合的PHP接口限流的实现

相关基于Redis接口限流策略

相关基于nginx的限流

相关 Redis 简单限流、漏斗限流

相关基于Redis的限流系统的设计

相关基于Redis的限流系统的设计（LUA）

相关基于redis的分布式RateLimiter(限流)实现