君不见长松卧壑困风霜,时来屹立扶明堂。这篇文章主要讲述算法与数据结构系列「限流算法专项」带你认识常用的限流算法的技术指南(分析篇)相关的知识,希望能为你提供帮助。
限流
限流一词常用于计算机网络之中,定义如下:
- 通过控制数据的网络数据的发送或接收速率来防止可能出现的DOS攻击。而实际的软件服务过程中,限流也可用于API服务的保护。
- 由于提供服务的计算机资源(包括CPU、内存、磁盘及网络带宽等)是有限的,则其提供的API服务的QPS也是有限的,限流工具就是通过限流算法对API访问进行限制,保证服务不会超过其能承受的负载压力。
- Token bucket-令牌桶
- Leaky bucket-漏桶
- Fixed window counter-固定窗口计数
- Sliding window log-滑动窗口日志
- Sliding window counter-滑动窗口计数
- 以上几种方式其实可以简单的分为计数算法、漏桶算法和令牌桶算法。
- 固定窗口计数法思想比较简单,只需要确定两个参数:计数周期T及周期内最大访问(调用)数N。请求到达时使用以下流程进行操作:
- 固定窗口计数实现简单,并且只需要记录上一个周期起始时间与周期内访问总数,几乎不消耗额外的存储空间。
文章图片
简化模型
- 两个周期T0中a时刻有n1个访问同时到达;
- 周期T1中b时刻有n2个访问同时到达;
- n1和n2均小于设定的最高访问次数N(否则会触发限流)。
- 举例,限制QPS为10,某用户在周期切换的前后的0.1秒内,分两次发送10次请求,根据算法规则此20次请求可通过限流器,则0.1面秒请求数20,超过每秒最多10次请求的限制。
限流流程如下:
文章图片
周期切换问题非计数限流法常用的限流算法有两种:漏桶算法和令牌桶算法
- 漏桶算法思路很简单,水(请求)先进入到漏桶里,漏桶以一定的速度出水,当水流入速度过大会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。
文章图片
- 设定漏桶流出速度及漏桶的总容量,在请求到达时判断当前漏桶容量是否已满,不满则可将请求存入桶中,否则抛弃请求。
- 采用一个线程以设定的速率取出请求进行处理。
- 需要确定参数为漏桶流出速度r及漏桶容量N
文章图片
算法特点
- 漏桶算法主要特点在于可以保证无论收到请求的速率如何,真正抵达服务方接口的请求速率最大为r,能够对输入的请求进行平滑处理。
- 漏桶算法的缺点也非常明显,由于其只能以特定速率处理请求,则如何确定该速率就是核心问题,如果速率设置太小则会浪费性能资源,设置太大则会造成资源不足。
- 并且由于速率的设置,无论输入速率如何波动,均不会体现在服务端,即使资源有空余,对于突发请求也无法及时处理,故对有突发请求处理需求时,不宜选择该方法。
- 对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。
- 令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。
根据描述需要设置的参数为,令牌添加速率r,令牌桶中最大容量N,流程如下:
文章图片
算法特点限流算法比较
文章图片
文章图片
文章图片
文章图片
文章图片
文章图片
【算法与数据结构系列「限流算法专项」带你认识常用的限流算法的技术指南(分析篇)】
文章图片
文章图片
推荐阅读
- 如何理解 Vue 中的生命周期
- 如何确保我的WordPress插件的样式不会被全局/主题样式覆盖()
- 如何仅在自定义帖子类型的单个页面和存档页面上排队脚本和样式()
- 如何使用WordPress functions.php中的ACF使脚本入队和出队()
- 如何使用语法高亮显示来编辑wordpress页面的html
- 如何在WordPress中编辑默认页面((index页面))
- 如何编辑wordpress主题以自动加载产品而不是分页产品
- 如何在子主题上编辑函数()
- 如何显示WordPress类别页面的自定义分类法()