您的位置 首页 php

PHP 限流算法介绍

1535637978049501d5c2676

高并发的处理有三个比较常用的手段, 缓存 ,限流和降级。缓存的使用相信很多开发者都很了解了,诸如redis,memcache等工具都会活跃在我们的系统当中。但是假如在某一时间段内出现了远超预想的流量访问到系统,例如在搞秒杀活动之类的,这样一来我们应该如何保护业务系统呢?

在参加一些秒杀活动的时候,我们可以看到,有时候会有 系统繁忙,请稍后再试 或者 请稍等 的提示,那这个系统就很可能是使用了限流的手段。

限流是限制系统的输入和输出流量,以达到保护系统的目的。而限流的实现主要是依靠限流算法,限流算法主要有4种:

1、固定时间窗口(计数器);

2、滑动时间窗口;

3、令牌桶算法;

4、漏桶算法;

1、计数器:

计数器就是统计记录单位时间内进入系统或者某一接口的请求次数,在限定的次数内的请求则正常接收处理,超过次数的请求则拒绝掉,或者改为异步处理。

153563791249922e10d0cce

假设我们设定单位时间内进入系统的的最大请求数为100,如果有超过100个请求集中在刷新计数器的临界点前后进入系统,而且单位时间的粒度比较粗的话,那就容易误伤很多正常请求。

 // 算法 伪代码  ++counter; if(counter > limit) { return '系统繁忙,请稍后再试'; } 

2.滑动时间窗口

这个名称要跟TCP的窗口滑动区分开来,但是理解之后会发现其实也是有点相似。

计数器算法对流量的限制比较粗放,而滑动时间窗口的算法则是对流量进行更加平稳的控制。上面的计数器的单位时间是1分钟,而在使用滑动时间窗口,可以把1分钟分成6格,每格时间长度是10s,每一格又各自管理一个计数器,单位时间用一个长度为60s的窗口描述。一个请求进入系统,对应的时间格子的计数器便会+1,而每过10s,这个窗口便会向右滑动一格。只要窗口包括的所有格子的计数器总和超过限流上限,便会拒绝后面的请求。

15356379130230cf4fde620

 // 算法伪代码 var cellIndex = time % cellNum; ++cellCounter[cellIndex]; var sum = 0; for(var i = cellIndex; i >= cellIndex - cellNum; --i) { sum += cellCounter[i]; } if(sum > limit) { return '系统繁忙,请稍后再试'; } 

3、漏桶算法

漏桶算法,又称leaky bucket。下图是wiki上的漏桶图解:

1535637912604e13002a660

一个系统处理请求,就像一个固定容量的水桶去溜进来的水,同时也让水流出去,但是它无法预见有多少水流进来和水流进来的速度,它只能够控制从桶底水流出去的速度,多出来的水,就只好让它从桶边流出去了。这个从桶底流出去的水就是系统正常处理的请求,从旁边流出去的水就是系统拒绝掉的请求。如此一来,我们只要监控系统单位时间内处理请求的速率就可以了,速率超过上限后的请求都给拒绝掉就可以了。

 // 算法伪代码 ++counter; var time = nowTime - (nowTime %  interval ); var rate = counter / time; if(rate> limitRate) { return '系统繁忙,请稍后再试'; } 

4、令牌桶算法

15356379128824d9ce85625

令牌桶即是以一定速率生成token并放入桶中,请求进入系统需要先拿到token才能进行业务处理,无token的请求则拒绝掉。令牌桶算法实际上跟漏桶算法很相似,而实际使用中其实也不需要另起线程生成token,只需要把握好token生成速率和当前应该剩余的token数量即可。

在时间点刷新的临界点上,只要剩余token足够,令牌桶算法会允许对应数量的请求通过,而后刷新时间因为token不足,流量也会被限制在外,这样就比较好的控制了瞬时流量。因此,令牌桶算法也被广泛使用。

文章来源:智云一二三科技

文章标题:PHP 限流算法介绍

文章地址:https://www.zhihuclub.com/54295.shtml

关于作者: 智云科技

热门文章

网站地图