计数器、滑动窗口、漏桶、令牌算法比较和伪代码实现
- 缓存:说白了,就是让数据尽早进入缓存,离程序近一点,不要大量频繁的访问DB。
- 降级:如果不是核心链路,那么就把这个服务降级掉。打个比喻,现在的APP都讲究千人千面,拿到数据后,做个性化排序展示,如果在大流量下,这个排序就可以降级掉!
- 限流:大家都知道,北京地铁早高峰,地铁站都会做一件事情,就是限流了!想法很直接,就是想在一定时间内把请求限制在一定范围内,保证系统不被冲垮,同时尽可能提升系统的吞吐量
限流常用的方式
计数器、滑动窗口、漏桶、令牌
计数器
计数器是限流里最简单的,简单来说,比如 我限制1分钟内 请求数最多为60个! 当此刻 2018-02-27 16:23:00 到 2018-02-27 16:24:00 时间内,请求最多只能是60个!到了2018-02-27 16:24:00,把计数器归零! 周而复始!
但这种会有问题!比如我在前58s都不请求,而在最后一秒请求60次!这样的效果跟木有啥区别..
伪代码:
class Counter { protected $timeStamp; protected $limitCount = 100; protected $interval = 60; protected $reqCount = 0; public function __construct() { $this->timeStamp = strtotime(date('Y-m-d H:i').':00',time()); $this->reqCount = Cache::get('reqCount'); } public function doLimit() { $now = time(); if ($now < $this->timeStamp + $this->interval) { if ($this->reqCount < $this->limitCount ) { $this->reqCount ++; Cache::put('reqCount',$this->reqCount,1); return true; } else { return false; } } else { Cache::put('reqCount',0,1); return false; } } public function test() { $res = $this->doLimit(); if ($res) { //执行正常业务 } else { //拦截掉 } } }
滑动窗口
之前我没听过这个方式,也是看了图以后才懂的!
滑动窗口其实就是 细分之后的计数器!
这样假设, 先把一分钟划分成6段! 也就是10s一个段!在第一段里,假如请求61次,那么直接触发了规则!肯定就过不去了!如果只请求了1次!则是正常的! 当时间走到第二个段里,即10s~20s这段范围里,我请求数不能超过总的限定条件,且当前段的请求数量 加上 之前段的总数量也不能超过总限定数量!
当时间到了50s~60s,依然是一样!
如果过了60s,所以请求数都是正常的,则把划分段往右移一段!那么此时的6个分段是 10 ~ 20,20 ~ 30,30 ~ 40,40 ~ 50,50 ~ 60,60 ~ 70
然后统计规则还跟上面一样!
所以,只有划分的越细,请求限制越平滑!
伪代码:
class SlidingWindow { protected $timeStamp; //限定时间内请求的最多次数 protected $limitCount = 100; //时间间隔 protected $interval = 60; //请求数 protected $reqCount = 0; //分成多少份 protected $count = 6; public function __construct() { $this->timeStamp = strtotime(date('Y-m-d H:i').':00',time()); $this->reqCount = Cache::get('reqCount'); } public function grant() { $allCounter = Cache::get('allCounterArr'); $nowMinute = date('Y-m-d H:i'); if (empty($allCounter)) { for ($i=1;$i< $this->count;$i++) { $key = date('Y-m-d H:i',strtotime($nowMinute.'00') + ($i * 60)); $allCounter[$key] = 0; } Cache::put('allCounterArr',$allCounter,10); } //当所有间隔的总和大于限制条数 开始限流 || 当前分区请求量大于限定条数, 开始限流 if (array_sum($allCounter) > $this->limitCount || $allCounter[$nowMinute] > $this->limitCount) return false; $allCounter[$nowMinute]++; //如果当前区块是最后一块,那么整体右移一个区块 if (key(end($allCounter)) == $nowMinute) { array_shift($allCounter); $allCounter[date('Y-m-d H:i',strtotime($nowMinute.'00') + 60)] = 0; Cache::put('allCounterArr',$allCounter,10); } return true; } public function test() { $res = $this->grant(); if ($res) { //执行正常程序 } else { //进行限流 } } }
漏桶
如图所示,漏桶就是一个固定的桶,桶底有个漏洞,进水速率不用管不用管,有多少水不用管,反正就这个孔里漏出去! 标准来说,就是不管多少请求,最后给服务的请求数量的速率是恒定的!多余的请求将 “抛弃掉”(抛弃并不代表直接丢掉不处理..)
伪代码:
class LeakyDemo{ private $timeStamp; public $capacity;// 桶的容量 public $rate; // 水漏出的速度 public $water;// 当前水量(当前累积请求数) public function __construct() { $this->timeStamp = time(); } public function grant(){ $now = time(); $this->water = max(0,$this->water - ($now-$this->timeStamp)*$this->rate);// 先执行漏水,计算剩余水量 $this->timeStamp = $now; if(($this->water+1) < $this->capacity){ // 尝试加水,并且水还未满 $this->water+=1; return true; }else{ // 水满,拒绝加水 return false; } } }
令牌桶
开始看图,没有仔细看,没懂..后来看了概念,明白了!
其实是这样的!先以一个恒定的速率生成令牌,把令牌放到桶里!然后每进来一个请求,每个请求去桶里找,有没有令牌,如果有令牌,则”拿着”令牌,继续下一步处理!如果桶里没有令牌了,则这个处理可以”抛弃掉”
令牌桶的好处就是,可以允许匀速,也允许范围内的突发处理!
类似于 我桶容量是100! 这时候1s一个请求,令牌速度也是1s一个!那么速率是恒定的, 突然,来了100个请求,发现桶里有100个令牌,那么这100个可以立即处理了!这时速率是100!
伪代码:
class TokenBucketDemo{ private $timeStamp; public $capacity;// 桶的容量 public $rate; // 令牌放入的速度 public $tokens;// 当前令牌的数量 public function __construct() { $this->timeStamp = time(); } public function grant(){ $now=time(); $this->tokens=min(0,$this->tokens+($now-$this->timeStamp)*$this->rate); $this->timeStamp=$now; if($this->tokens<1){ // 若不到1个令牌,则拒绝 return false; }else{ // 还有令牌,领取令牌 $this->tokens -= 1; return true; } }