流量控制算法

用户头像
王友
关注
发布于: 2020 年 07 月 18 日
流量控制算法

写在前面的话:

最近在学习架构方面的知识,为了强制让自己能够多思考,就决定对相关内容进行整理一下,一方面希望通过分享文章的方式能够得到一些指点,同时也希望可以给有需要的同学提供一点帮助。由于自己的段位不够,文中难免会有理解不到位的地方,还请大家不吝指教!


流量控制算法也叫流控算法限流算法,主要是为了解决在面对不确定的和不稳定的流量冲击下,能够保障系统的稳定运行,如果系统对流量不进行控制,系统很可能会因为大流量的冲击影响系统的稳定性,情况严重时还会导致系统瘫痪。

流量的不确定性:是指无法预测到的突发流量,例如恶意攻击

流量的不稳定性:是指流量本身存在一定的规律性,例如系统使用情况存在一定的周期性

当无法控制流量入口时,我们就需要考虑流量控制,我们可以对系统整理进行流量控制,也可以对系统接入用户进行独立的流量控制,我们要结合实际业务场景选择合适的流控策略。

本篇文章就主要的流控算法做一个简单的梳理:

  • 固定窗口算法

  • 滑动窗口算法

  • 漏桶算法

  • 令牌桶算法

1. 固定窗口算法

目前处于疫情控制期间,无论走到哪都要进行检查,医院也不例外。前两天带孩子去口腔医院看牙(需提前网上预约),在进入门诊前医院对人流进行了控制,根据预约时间提前30分钟放一批人进去。说实话,这么做了以后就是排队的时候有点难熬(不过可以赶点过去哦),看病的环境和秩序比以前好多了。

我们来分析一下这个过程(暂且忽略顺序的问题,就假设大家都是按照预约时间的先后顺序排队的):

  • 首先:医院每个时段的号源是确定的,号源的个数就是我们的窗口大小

  • 其次:医院门口每30分钟放一批人进入,30分钟就是窗口的有效时间

  • 结果就是医院内部环境和秩序良好,达到了流量控制的目的

固定窗口算法,就是指在固定的时间窗口内按照阈值进行流量控制的算法。这个算法具有以下特点:

  • 原理简单,实现容易

  • 当在时间窗口内突发流量,在时间窗口切换时阻塞请求同时涌入,产生流量踩踏,系统稳定性收到考验

2. 滑动窗口算法

为了能够解决固定窗口算法在时间窗口切换时流量冲击的问题,我们可以将时间窗口划分成多个小的时间片段,每个小的时间片段有独立的计数器,当请求的时间点大于时间窗口的最大时间点时,整个窗口向右移动一个小的时间片段(丢弃最前面的时间片段,请求放在最新的时间片段上),这就是滑动窗口。时间片段划分的越多,滑动窗口的滑动就会越平滑,流量控制的也就越精确。

3. 漏桶算法

漏桶算法是定义一个有一定容量的桶,如果桶的容量未满,新的请求就被放入桶内,如果桶的容量满了,新的请求就会被丢弃,漏桶算法通过控制输出速率,平滑网络流量,起到消峰填谷的作用。

漏桶算法由于漏出的速率是固定的,所以在突发流量的情况下,并不能够有效地使用网络资源,这种情况下对于请求的处理就缺乏效率。

4. 令牌桶算法

在某些场景下除了能够限制数据的传输速率外,还要能够处理一定突发流量的情况,这时漏桶算法就不太合适了。

令牌桶算法:系统以一个恒定的频率生成令牌(token)放入桶内,当有请求需要被处理时,需要从桶里拿出一个或多个令牌(token),当桶里的令牌不足时,则新的请求将会被拒绝。与漏桶不同的是,桶里放入的是令牌,而漏桶放入的是请求,当出现突发流量时,只要桶内的令牌足够时请求就可以得到处理的机会(这里说机会,主要还是要看系统的处理能力)。



用户头像

王友

关注

懒是一种艺术 2018.03.26 加入

间歇性自律,持续性懒散,真的很懒!

评论

发布
暂无评论
流量控制算法