专栏首页呆呆熊的技术路计数器、滑动窗口、漏桶、令牌算法比较和伪代码实现

计数器、滑动窗口、漏桶、令牌算法比较和伪代码实现

  • 缓存:说白了,就是让数据尽早进入缓存,离程序近一点,不要大量频繁的访问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;
        }

    }

本文分享自微信公众号 - 呆呆熊的技术路(gh_93f28f51010a),作者:叶落山城秋

原文出处及转载信息见文内详细说明,如有侵权,请联系 yunjia_community@tencent.com 删除。

原始发表时间:2020-06-08

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

我来说两句

0 条评论
登录 后参与评论

相关文章

  • 设计模式第七讲-责任链模式

    责任链模式的定义:使多个对象都有机会处理请求,从而避免请求的发送者和接受者之间的耦合关系

    用户2825413
  • 设计模式第三讲-装饰者模式

    装饰模式也算一种比较常见的设计模式,工作过程中很少刻意的去实现这种模式,因为这种模式也会带来一些问题。

    用户2825413
  • 微服务-数据聚合CQRS

    微服务经常是按业务维度划分多个服务(当然还有其他各种考虑维度), 划分为多个维度后, 好处自然很多, 其中也会有一些问题, 比如我们讲的数据依赖问题

    用户2825413
  • 商品多种规格属性的选择(sku 算法)

    如上图中每一个单规格选项,例如==珍珠白==、==12GB+512GB==、==不分期==就是一个规格(sku)。商品和 sku 属于一对多的关系,也就是我们可...

    Krry
  • 《你不知道的JavaScript》:js委托设计的真实案例与总结

    实际需求,web开发中有一个典型的前端场景,创建UI控件(按钮、下拉列表等)。用jq的选择器来简化选择过程,与实现思路不冲突。

    前端_AWhile
  • 数据结构与JS也可以成为CP(十)Graph图

    1)深度优先搜索算法比较简单:访问一个没有访问过的顶点,将它标记为已访问,再递归地去访问在初始顶点的邻接表中其他没有访问过的顶点。

    萌兔IT
  • HTML5 Canvas炫酷的火焰风暴动画

    越陌度阡
  • .glb格式的模型怎么在three.js中展示

    3D软件中导出的格式一般有.obj 和.glb ,下面是blender 2.8.2 生成模型并在three.js中展示的流程

    tianyawhl
  • 由for V.S. for each想到的

    一直想写一系列如何提高Performance和Scalability的文章,把我的相关经验和所知道的相关的技巧同大家分享。前一阵在园子里有一篇讨论for eac...

    蒋金楠
  • 云终端系列(一)—— 实时音视频Web端接入体验(Vue基础音视频通话篇)

    这个系列呢,主要给各位观众老爷看看目前有较大趋势的SaaS应用的SDK在各种主流Web终端的使用姿势和异常分析,如果想要纯粹了解开发的或者云原生,云开发的可以去...

    楚歌

扫码关注云+社区

领取腾讯云代金券