作者&＃xff1a;邬凯强
https://www.jianshu.com/p/a3d068f2586d
本文讲述基于 Redis 的限流系统的设计&＃xff0c;主要会谈及限流系统中限流策略这个功能的设计&＃xff1b;在实现方面&＃xff0c;算法使用的是令牌桶算法来&＃xff0c;访问 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
用我的理解翻译一下&＃xff1a;限流是对系统的出入流量进行控制&＃xff0c;防止大流量出入&＃xff0c;导致资源不足&＃xff0c;系统不稳定。
限流系统是对资源访问的控制组件&＃xff0c;控制主要的两个功能&＃xff1a;限流策略和熔断策略&＃xff0c;对于熔断策略&＃xff0c;不同的系统有不同的熔断策略诉求&＃xff0c;有的系统希望直接拒绝、有的系统希望排队等待、有的系统希望服务降级、有的系统会定制自己的熔断策略&＃xff0c;很难一一列举&＃xff0c;所以本文只针对限流策略这个功能做详细的设计。
针对限流策略这个功能&＃xff0c;限流系统中有两个基础概念&＃xff1a;资源和策略。
熔断策略&＃xff1a;超出速率阈值的请求的处理策略&＃xff0c;是我自己理解的一个叫法&＃xff0c;不是业界主流的说法。
2、限流算法
2.1、限制瞬时并发数
定义&＃xff1a;瞬时并发数&＃xff0c;系统同时处理的请求 / 事务数量
优点&＃xff1a;这个算法能够实现控制并发数的效果
缺点&＃xff1a;使用场景比较单一&＃xff0c;一般用来对入流量进行控制
java 伪代码实现&＃xff1a;
AtomicInteger atomic &＃61; new AtomicInteger(1)
try { if(atomic.incrementAndGet() > 限流数) { //熔断逻辑 } else {//处理逻辑}
} finally { atomic.decrementAndGet();}
2.2、限制时间窗最大请求数
定义&＃xff1a;时间窗最大请求数&＃xff0c;指定的时间范围内允许的最大请求数
优点&＃xff1a;这个算法能够满足绝大多数的流控需求&＃xff0c;通过时间窗最大请求数可以直接换算出最大的 QPS&＃xff08;QPS &＃61; 请求数 / 时间窗&＃xff09;
缺点&＃xff1a;这种方式可能会出现流量不平滑的情况&＃xff0c;时间窗内一小段流量占比特别大
lua 代码实现&＃xff1a;
--- 资源唯一标识
local key &＃61; KEYS[1]
--- 时间窗最大并发数
local max_window_concurrency &＃61; tonumber(ARGV[1])
--- 时间窗
local window &＃61; tonumber(ARGV[2])
--- 时间窗内当前并发数
local curr_window_concurrency &＃61; tonumber(redis.call(&＃39;get&＃39;, key) or 0)
if current &＃43; 1 > limit thenreturn false
elseredis.call("INCRBY", key,1) if window > -1 thenredis.call("expire", key,window) endreturn true
end
2.3、令牌桶
算法描述
假如用户配置的平均发送速率为 r&＃xff0c;则每隔 1/r 秒一个令牌被加入到桶中
假设桶中最多可以存放 b 个令牌。如果令牌到达时令牌桶已经满了&＃xff0c;那么这个令牌会被丢弃
当流量以速率 v 进入&＃xff0c;从桶中以速率 v 取令牌&＃xff0c;拿到令牌的流量通过&＃xff0c;拿不到令牌流量不通过&＃xff0c;执行熔断逻辑
属性
优点&＃xff1a;流量比较平滑&＃xff0c;并且可以抵挡一定的流量突发情况
因为我们限流系统的实现就是基于令牌桶这个算法&＃xff0c;具体的代码实现参考下文。
3、工程实现
3.1、技术选型
mysql: 存储限流策略的参数等元数据
redis&＃43;lua: 令牌桶算法实现
说明&＃xff1a;因为我们把 redis 定位为&＃xff1a;缓存、计算媒介&＃xff0c;所以元数据都是存在 db 中
3.2、架构图
3.3、 数据结构
| 字段 | 描述 |
|---|
| name | 令牌桶的唯一标示 |
| apps | 能够使用令牌桶的应用列表 |
| max_permits | 令牌桶的最大令牌数 |
| rate | 向令牌桶中添加令牌的速率 |
| created_by | 创建人 |
| updated_by | 更新人 |
限流系统的实现是基于 redis 的&＃xff0c;本可以和应用无关&＃xff0c;但是为了做限流元数据配置的统一管理&＃xff0c;按应用维度管理和使用&＃xff0c;在数据结构中加入了 apps 这个字段&＃xff0c;出现问题&＃xff0c;排查起来也比较方便。
3.4、代码实现
3.4.1、代码实现遇到的问题
参考令牌桶的算法描述&＃xff0c;一般思路是在 RateLimiter-client 放一个重复执行的线程&＃xff0c;线程根据配置往令牌桶里添加令牌&＃xff0c;这样的实现由如下缺点&＃xff1a;
3.4.2、解决方案
基于上面的缺点&＃xff0c;参考了 google 的 guava 中 RateLimiter 中的实现&＃xff0c;我们使用了触发式添加令牌的方式。
算法描述
3.4.3、 lua 代码实现
--- 获取令牌
--- 返回码
--- 0 没有令牌桶配置
--- -1 表示取令牌失败&＃xff0c;也就是桶里没有令牌
--- 1 表示取令牌成功
--- &＃64;param key 令牌&＃xff08;资源&＃xff09;的唯一标识
--- &＃64;param permits 请求令牌数量
--- &＃64;param curr_mill_second 当前毫秒数
--- &＃64;param context 使用令牌的应用标识
local function acquire(key, permits, curr_mill_second, context)local rate_limit_info &＃61; redis.pcall("HMGET", key, "last_mill_second", "curr_permits", "max_permits", "rate", "apps") local last_mill_second &＃61; rate_limit_info[1] local curr_permits &＃61; tonumber(rate_limit_info[2]) local max_permits &＃61; tonumber(rate_limit_info[3]) local rate &＃61; rate_limit_info[4] local apps &＃61; rate_limit_info[5] --- 标识没有配置令牌桶if type(apps) &＃61;&＃61; &＃39;boolean&＃39; or apps &＃61;&＃61; nil or not contains(apps, context) thenreturn 0endlocal local_curr_permits &＃61; max_permits; --- 令牌桶刚刚创建&＃xff0c;上一次获取令牌的毫秒数为空--- 根据和上一次向桶里添加令牌的时间和当前时间差&＃xff0c;触发式往桶里添加令牌--- 并且更新上一次向桶里添加令牌的时间--- 如果向桶里添加的令牌数不足一个&＃xff0c;则不更新上一次向桶里添加令牌的时间if (type(last_mill_second) ~&＃61; &＃39;boolean&＃39; and last_mill_second ~&＃61; false and last_mill_second ~&＃61; nil) thenlocal reverse_permits &＃61; math.floor(((curr_mill_second - last_mill_second) / 1000) * rate) local expect_curr_permits &＃61; reverse_permits &＃43; curr_permits;local_curr_permits &＃61; math.min(expect_curr_permits, max_permits); --- 大于0表示不是第一次获取令牌&＃xff0c;也没有向桶里添加令牌if (reverse_permits > 0) thenredis.pcall("HSET", key, "last_mill_second", curr_mill_second) endelseredis.pcall("HSET", key, "last_mill_second", curr_mill_second) endlocal result &＃61; -1if (local_curr_permits - permits >&＃61; 0) thenresult &＃61; 1redis.pcall("HSET", key, "curr_permits", local_curr_permits - permits) elseredis.pcall("HSET", key, "curr_permits", local_curr_permits) endreturn result
end
关于限流系统的所有实现细节&＃xff0c;我都已经放到 github 上&＃xff0c;gitbub 地址&＃xff1a;https://github.com/wukq/rate-limiter&＃xff0c;有兴趣的同学可以前往查看&＃xff0c;由于笔者经验与知识有限&＃xff0c;代码中如有错误或偏颇&＃xff0c;欢迎探讨和指正。
3.4.4、管理界面
前面的设计中&＃xff0c;限流的配置是和应用关联的&＃xff0c;为了更够更好的管理配置&＃xff0c;需要一个统一的管理页面去对配置进行管控&＃xff1a;
3.5、性能测试
配置&＃xff1a;aws-elasticcache-redis 2 核 4g
因为 Ratelimiter-client 的功能比较简单&＃xff0c;基本上是 redis 的性能打个折扣。
单线程取令牌&＃xff1a;Ratelimiter-client 的 QPS &＃61; 250/s
10 个线程取令牌&＃xff1a;Ratelimiter-client 的 QPS &＃61; 2000/s
100 个线程取令牌&＃xff1a;Ratelimiter-client 的 QPS &＃61; 5000/s
4、总结
限流系统从设计到实现都比较简单&＃xff0c;但是确实很实用&＃xff0c;用四个字来形容就是&＃xff1a;短小强悍&＃xff0c;其中比较重要的是结合公司的权限体系和系统结构&＃xff0c;设计出符合自己公司规范的限流系统。
不足&＃xff1a;
redis 我们用的是单点 redis&＃xff0c;只做了主从&＃xff0c;没有使用 redis 高可用集群&＃xff08;可能使用 redis 高可用集群&＃xff0c;会带来新的问题&＃xff09;
限流系统目前只做了应用层面的实现&＃xff0c;没有做接口网关上的实现
熔断策略需要自己定制&＃xff0c;如果实现的好一点&＃xff0c;可以给一些常用的熔断策略模板
参考书籍&＃xff1a;
1.《Redis 设计与实现》
2.《Lua 编程指南》
参考文章&＃xff1a;
1. redis 官网
2. lua 编码规范
3. 聊聊高并发系统之限流特技
4. guava Ratelimiter 实现
5. Token_bucket wiki 词条
--完--
如果需要Redis视频&＃xff0c;可以在公众号后台聊天框回复【Redis视频】&＃xff0c;可以免费获取编程视频 。
Redis其它推荐阅读&＃xff1a;
Redis 零基础入门视频教程
Linux 安装 Redis 图文教程
刚接触学Redis&＃xff0c;看这一篇就够了&＃xff01;
再来聊聊Redis到底是什么&＃xff1f;
说说 Redis 数据结构和常用命令
Redis最常见面试问题&＃xff0c;附答案&＃xff01;
Redis的字符串是怎么实现的&＃xff1f;
阿里巴巴官方 Redis 开发规范&＃xff01;
如何借助 Redis 实现秒杀系统&＃xff1f;
史上最全 Redis 高可用解决方案总结
10 个正确使用 Redis 的技巧
Redis 分布式锁的正确实现方式
Redis 源码学习之 Redis 事务
详解Redis的内存淘汰策略
Redis 的各项功能&＃xff0c;都解决了哪些问题&＃xff1f;
为什么单线程的Redis却能支撑高并发&＃xff1f;
Redis应用场景&＃xff0c;实现功能 “附近的人”
超详细揭秘 Redis 持久化&＃xff0c;建议收藏&＃xff01;
后端开发都应该掌握的Redis基础
Redis是如何实现点赞、取消点赞的&＃xff1f;
Redis实践&＃xff1a;网站搜索的热搜词
如何用 Redis 做实时订阅推送的&＃xff1f;
Redis 主从复制以及主从复制原理
如何访问 Redis 中的海量数据&＃xff1f;
一文深入了解Redis内存模型&＃xff01;
Redis 导致应用卡死 bug 全过程
Redis常见的几种缓存模式
玩转Redis集群的搭建、命令以及Java整合
长按加入10W&＃43;朋友的IT圈
觉得内容还不错的话&＃xff0c;给我点个“在看”呗
京公网安备 11010802041100号