好刚:视频介绍限流算法

视频介绍限流算法,分析漏桶算法和令牌算法的应用场景,算法原理和算法实现方法

你好,我是好刚,这一讲我们来了解限流算法 (Rate Limiting Throttling)。

1. 应用场景

首先我们看一个典型的应用场景,比如在商品抢购的场景里面,可能会有百万级别的用户请求我们的抢购接口,这个时候如果不做任何保护措施,服务器就会承受很大的处理压力,请求量很高,服务器负载也很高,并且当请求超过服务器承载极限的时候,系统就会崩溃,导致所有人都不能访问。为了保证抢购服务的可用性,一个常用的办法是对秒杀请求进行限流,拦截掉大部分请求,只允许一部分请求真正进入后端服务器,这样就可以防止大量请求造成系统压力过大导致的系统崩溃,从而保护服务正常可用。这里限流的常用算法有漏桶算法和令牌桶算法。

2. 漏桶算法

我们先来看漏桶算法(Leaky Bucket),先想象有一个木桶,新请求就像水滴一样,不断地滴进来,水滴进来的速度是不确定的,有时会快一点,有时会慢一点,同时桶底下有个洞,可以按照固定的速度把水漏走,如果水进来的速度比漏走的快,桶就会满了,桶满了水就会漫出来,对应的就是拒绝请求。

漏桶算法的主要特点是可以平滑网络上的突发流量,请求可以被整形成稳定的流量。

算法伪代码如下:

3. 令牌桶算法

我们再看下令牌桶算法(Token Bucket)。也是先有一个木桶,系统按照固定速度,往桶里加入Token,如果桶已经满了就不再添加。当有请求到来时,会各自拿走一个Token,取到Token 才能继续进行请求处理,没有Token 就拒绝服务。

这里如果一段时间没有请求时,桶内就会积累一些Token,下次一旦有突发流量,只要Token 足够,也能一次处理。所以令牌桶算法的特点是允许突发流量。

我们看一个例子,看看令牌桶如何允许突发流量,假如令牌则按照每秒5 个的速度放入令牌桶,桶中最多存放20 个令牌,那系统可以支持两种类型的请求流量,一种是允许持续的每秒处理5 个请求,第二种是每隔4 秒,等桶中20 个令牌攒满后,就可以处理一次有20 个请求的突发情况。

算法伪代码如下:

4. 两种算法比较

最后我们对比下漏桶算法和令牌桶算法。其实在实现上,两种算法是效果一样但方向相反的算法。

漏桶算法是请求流入的速度不确定,有时快有时慢,是存在突发情况的;但是请求流出的速度是固定的,它是流入会有突发情况,但是流出速度固定。

令牌桶算法就是固定的Token 流入速度,一个Token 代表一个请求可以被处理的机会;当系统有一段空闲时间之后,桶内有足够的token,这样可以处理突发的请求流量,它是流入速度固定,但是流出不固定。

总结下特点:漏桶算法因为流出速度固定,可以用来整流,无论你流入速率多大,我都按照固定的速度去处理。令牌桶算法的特点则是,支持突发情况,两种算法在实际使用时,应该根据具体场景灵活选用。

限流算法就介绍到这,我是好刚,好刚用在刀刃上。如果讲解对你有帮助,那就请你帮忙转发吧。

5. 令牌通算法实现

PHP 实现

参考资料

发表评论