algorithm  

限流算法介绍

前言

最近在看好未来开源的微服务框架go-zero,看到其中的限流算法时,感觉这方面自己不是很清楚,就查阅了下网上相关的资料,下面算是对查阅资料的整理吧。

限流介绍

限流,顾名思义就是“限制流量”,可以避免高并发系统中,在短时间内由于请求太多导致系统崩溃的问题。

常见的限流算法

常见的限流算法主要是计数器算法令牌桶算法漏桶算法

计数器算法

计数器算法是限流算法里最简单、最容易实现的一种算法。使用计数器来进行限流,主要用来限制总并发数,比如数据库连接池、线程池、秒杀的并发数;只要全局总请求数或者一定时间段的总请求数达到设定的阀值则进行限流,是粗暴的总数量限流,而不是平均速率限流。

设置一个计数器counter,来一个请求counter的数值就+1,没超过counter设置的最大值就不限流,一段时间后就重置counter。这个算法简单粗暴,但是有一个漏洞就是,在重置counter的时刻前后有临界问题,这可能导致我们的系统流量瞬时超过counter的最大值。

为了降低临界问题带来的影响,这里我们可以引入滑动窗口算法,将原本的一段时间,平均分成多个时间窗口,每个时间窗口单独维护一个counter,当每过一个时间窗口的时段后,我们会把时间窗口向右移动一格,这样就能避免计数器算法的临界问题。(如下图) 滑动窗口图示 回顾计数器算法,其实它就是滑动窗口算法,只不过它没有对时间段进行划分,时间窗口只有一格。由此可见,当滑动窗口的数量越多,窗口的移动就会更平滑,这样我们限流的统计也就越精确。

令牌桶算法

令牌桶算法的原理是系统会以一个恒定的速度往桶里放入令牌,而如果请求需要被处理,则需要先从桶里获取一个令牌,当桶里没有令牌可取时,则拒绝服务。桶中最多存放一定数量的令牌,当桶满时,新添加的令牌被丢弃或拒绝。

如图所示: 滑动窗口图示

漏桶算法

漏桶作为计量工具(The Leaky Bucket Algorithm as a Meter)时,可以用于流量整形(Traffic Shaping)和流量控制(TrafficPolicing),漏桶算法的描述如下:

令牌桶和漏桶对比:

参考资料

聊聊高并发系统之限流特技-1

Related Posts

经典排序算法ruby实现
算法学习纪要
© 2019 - 2020 · GenkinHe Powered by [Hugo] ·