架构师

您现在的位置是:首页 > 技术博客 > 编程基础

编程基础

6种限流方法之服务端漏桶算法

架构师小跟班 2020-05-19 编程基础
漏桶算法漏桶算法的思路来源于日常生活中常见的漏斗。之前介绍过的滑动时间算法有一个很大的问题就是在一定范围内,比如 60s 内只能有 10 个请求,当第一秒时就到达了 10 个请

漏桶算法

漏桶算法的思路来源于日常生活中常见的漏斗。

之前介绍过的滑动时间算法有一个很大的问题就是在一定范围内,比如 60s 内只能有 10 个请求,当第一秒时就到达了 10 个请求,那么剩下的 59s 只能把所有的请求都给拒绝掉,而漏桶算法刚好可以解决这个问题。

在漏桶算法中,无论上面的水流倒入漏斗有多大,也就是无论请求有多少,它都是以均匀的速度慢慢流出的。当上层的水流速度大于下层的流出速度时,漏斗就会慢慢充满,当漏斗满了之后就会溢出(丢弃)新来的请求;当上面的水流速度小于下面流出的速度时,漏斗永远不会被装满,也就可以一直流出。

漏桶算法的实现步骤是,

1)先声明一个队列用来保存请求,这个队列相当于漏斗,

2)当队列容量满了之后就丢弃(溢出)新来的请求,

3)声明一个线程定期从任务队列中获取一个或多个任务进行处理。

这样就实现了漏桶算法。

上面我们讲过的Nginx 的控制速率其实使用的就是漏桶算法,当然我们也可以借助 Redis 很方便的实现漏桶算法。

我们可以使用redis提供的 Redis-Cell 模块,该模块使用的是漏斗算法,并且提供了原子的限流指令,而且依靠 Redis 这个天生的分布式程序就可以实现比较完美的限流了。

Redis-Cell 实现限流的方法也很简单,只需要使用一条指令 cl.throttle 即可,使用示例如下:

> cl.throttle mylimit 15 30 60

1)(integer)0 # 0 表示获取成功,1 表示拒绝

2)(integer)15 # 漏斗容量

3)(integer)14 # 漏斗剩余容量

4)(integer)-1 # 被拒绝之后,多长时间之后再试(单位:秒)-1 表示无需重试

5)(integer)2 # 多久之后漏斗完全空出来

其中 15 为漏斗的容量,30 / 60s 为漏斗的速率。

相关阅读:

6种常见的限流方案

https://www.jiagou1216.com/blog/plan/842.html

6种限流方法之服务端时间窗口算法(结合redis):

https://www.jiagou1216.com/blog/plan/843.html

6种限流方法之服务端漏桶算法:

https://www.jiagou1216.com/blog/plan/844.html

6种限流方法之服务端令牌算法(结合guava工具包):

https://www.jiagou1216.com/blog/plan/845.html


文章评论