脚本宝典收集整理的这篇文章主要介绍了🏆【算法数据结构专题】「限流算法专项」带你认识常用的限流算法的技术指南(分析篇),脚本宝典觉得挺不错的,现在分享给大家,也给大家做个参考。
限流的目的是通过对并发访问/请求进行限速,或者对一个时间窗口内的请求进行限速来保护系统,一旦达到限制速率则可以拒绝服务、排队或等待、降级等处理
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.
常用限流算法的简单介绍及比较
常用的限流算法主要包括:
无论固定窗口还是滑动窗口核心均是对请求进行计数,区别仅仅在于对于计数时间区间的处理。
固定窗口计数缺点也非常明显,在进行周期切换时,上一个周期的访问总数会立即置为0,这可能导致在进行周期切换时可能出现流量突发,
在发生时间间隔切换的时候,在切换的过程中发生并发突变,所以在实际使用过程中,固定窗口计数器存在突破限额N的可能。
为解决固定窗口计数带来的周期切换处流量突发问题,可以使用滑动窗口计数。滑动窗口计算本质上也是固定窗口计数,区别在于将计数周期进行细化。
滑动窗口计数法与固定窗口计数法相比较,除了计数周期T及周期内最大访问(调用)数N两个参数,增加一个参数M,用于设置周期T内的滑动窗口数。
滑动窗口计数在固定窗口计数记录数据基础上,需要增加一个长度为M的计数数组,用于记录在窗口滑动过程中各窗口访问数据。其流程示例如下:
滑动窗口针对周期进行了细分,不存在周期到后计数直接重置为0的情况,故不会出现跨周期的流量限制问题。
常用的限流算法有两种:漏桶算法和令牌桶算法
漏桶限流算法的实现原理图:
对于很多应用场景来说,除了要求能够限制数据的平均传输速率外,还要求允许某种程度的突发传输。这时候漏桶算法可能就不合适了,令牌桶算法更为适合。
令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。
设定令牌桶中添加令牌的速率,并且设置桶中最大可存储的令牌,当请求到达时,向桶中请求令牌(根据应用需求,可能为1个或多个),若令牌数量满足要求,则删除对应数量的令牌并通过当前请求,若桶中令牌数不足则触发限流规则。
根据描述需要设置的参数为,令牌添加速率r,令牌桶中最大容量N,流程如下:
令牌桶算法通过设置令牌放入速率可以控制请求通过的平均速度,且由于设置的容量为N的桶对令牌进行缓存,可以容忍一定流量的突发。
以上提到四种算法,本小节主要对四种算法做简单比较算法进行对比。
以上是脚本宝典为你收集整理的🏆【算法数据结构专题】「限流算法专项」带你认识常用的限流算法的技术指南(分析篇)全部内容,希望文章能够帮你解决🏆【算法数据结构专题】「限流算法专项」带你认识常用的限流算法的技术指南(分析篇)所遇到的问题。
本图文内容来源于网友网络收集整理提供,作为学习参考使用,版权属于原作者。
如您有任何意见或建议可联系处理。小编QQ:384754419,请注明来意。