最新公告
  • 欢迎您光临起源地模板网,本站秉承服务宗旨 履行“站长”责任,销售只是起点 服务永无止境!立即加入钻石VIP
  • 高并发下限流-漏桶、令牌桶算法及PHP实现

    正文概述 转载于:掘金(三百云技术中心)   2021-07-08   58

    高并发下限流-漏桶、令牌桶算法及PHP实现

    一 、场景描述(为什么需要限流)

    在做后端服务的时候,每个API接口在大访问量下都可能会有性能瓶颈,当API访问频率或者并发量超过接口承受范围时候,我们就必须考虑通过限流来保证接口的可用性或者降级可用性,防止超出预期的请求对系统造成压力进而导致的系统瘫痪。

    通常都会做服务接口的流量控制策略,一般有 分流、降级、限流等几种形式。

    本文讨论的限流策略中的漏桶和令牌桶,虽然降低了服务接口的访问频率和并发量,但是换取服务接口和业务应用系统的高可用。

    二、常用的限流算法

    常见的限流算法有:令牌桶、漏桶、Redis计数器。

    今天主要介绍一下漏桶和令牌桶算法。

    2.1、漏桶算法

    原理

    漏桶(Leaky Bucket)算法思路是,请求先进入到漏桶里,漏桶以特定的速度发出请求(接口有响应速率),当请求速度过大会直接溢出(访问频率超过接口响应速率),然后就拒绝请求,可以看出漏桶算法可以强行限制数据的传输速率。

    漏桶算法会限制了请求的速度。当使用了漏桶算法,我们可以保证接口会以一个匀速速率来处理请求。所以漏桶算法不会出现临界问题。

    示意图如下:

    高并发下限流-漏桶、令牌桶算法及PHP实现

    可见这里有两个变量,一个是桶的大小,支持流量突发增多时可以存多少的水(burst),另一个是水桶漏洞的大小(rate)。

    因为漏桶的漏出速率是固定的,所以,即使网络中不存在资源冲突(没有发生拥塞),漏桶算法也不能使流突发(burst)到端口速率。因此,漏桶算法对于存在突发特性的流量来说缺乏效率。

    漏桶具体实例

    <?php 
    /**
    * [leaky php实现漏桶算法]
    * @Author
    * @DateTime 
    * @param    [type]     $contain            [int 桶的总容量]
    * @param    [type]     $addNum             [int 每次注入桶中的水量]
    * @param    [type]     $leakRate           [int 桶中漏水的速率,秒为单位。例如2/s,3/s]
    * @param    [type]     &$water             [int 当前水量]
    * @param    [type]     &$preTime           [int 时间戳,记录的上次漏水时间]
    * @return   [type]                         [bool,返回可否继续注入true/false]
    */
    function leaky($contain, $addNum, $leakRate, &$water = 0, &$preTime = 0)
    {
       //参数赋值
       //首次进入默认当前水量为0
       $water = empty($water) ? 0 : $water;
       //首次进入默认上次漏水时间为当前时间
       $preTime = empty($water) ? time() : $preTime;
       $curTime = time();
       //上次结束到本次开始,流出去的水
       $leakWater = ($curTime - $preTime) * $leakRate;
       //上次结束时候的水量减去流出去的水,也就是本次初始水量
       $water = $water - $leakWater;
       //水量不可能为负,漏出大于进入则水量为0
       $water = ($water >= 0) ? $water : 0;
       //更新本次漏完水的时间
       $preTime = $curTime;
       
       //水小于总容量则可注入,否则不可注入
       if (($water + $addNum) <= $contain) {
           $water += $addNum;
           return true;
       } else {
           return false;
       }
    
    }
    
    /**
    * 测试
    * @var integer
    */
    for ($i = 0; $i < 500; $i++) {
       $res = leaky(50, 1, 5, $water, $timeStamp);
       var_dump($res);
       usleep(50000);
    }
    

    2.2、令牌桶算法

    原理

    令牌桶算法(Token Bucket)和 漏桶算法(Leaky Bucket) 效果一样但策略相反的算法,更容易让人理解。令牌桶是按照时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=10,则间隔是100ms)往桶里加入Token(类似水龙头滴水),如果桶已经满了就不在新增或者丢弃。新请求来临时,每次请求都会拿走一个Token,如果发现没有Token可拿就阻塞或者拒绝服务。

    高并发下限流-漏桶、令牌桶算法及PHP实现

    令牌桶的好处: 可以方便的改变请求速度。 一旦需要提高速率,只需提高放入桶中的令牌的速率。 一般会定时(比如100毫秒)往桶中增加一定数量的令牌, 有些变种算法则实时的计算应该增加的令牌的数量。

    令牌桶具体实例

    基于php+Redis实现的令牌桶算法示例一
    <?php
    /**
     * 限流控制令牌桶
     */
    class TokenBucket
    {
        private $minNum = 60; //单个用户每分访问数 
        /**
         * 单个用户示例
         * @param $uid
         */
        public function minLimit($uid)
        {
            $minNumKey = $uid . '_minNum';
            $resMin = $this->getRedis($minNumKey, $this->minNum, 60);
    
            if (!$resMin['status'] || !$resDay['status']) {
                exit($resMin['msg'] . $resDay['msg']);
            }
        }
    
        /**
         * 令牌桶限流主方法
         */
        function getRedis($key, $initNum, $expire)
        {
            $nowtime = time();
            $result = ['status' => true, 'msg' => ''];
            //连接redis
            $redis = $this->di->get('redis');
            $redis->watch($key);
            $limitVal = $redis->get($key);
    
            if ($limitVal) {
                $limitVal = json_decode($limitVal, true);
                $newNum = min($initNum, ($limitVal['num'] - 1) + (($initNum / $expire) * ($nowtime - $limitVal['time'])));
    
                if ($newNum <= 0) {
                    return ['status' => false, 'msg' => '当前时刻令牌消耗完!'];
                }
    
                $redisVal = json_encode(['num' => $newNum, 'time' => time()]);
            } else {
                $redisVal = json_encode(['num' => $initNum, 'time' => time()]);
            }
    
            $redis->multi();
            $redis->set($key, $redisVal);
            $rob_result = $redis->exec();
    
            if (!$rob_result) {
                $result = ['status' => false, 'msg' => '访问频次过多!'];
            }
    
            return $result;
        }
    }
    

    代码要点:

    1:首先定义规则

    单个用户每分钟访问次数($minNum),接口访问次数规则。

    2:计算请求速率

    示例代码是按照秒为最小的时间单位,请求速率 = 访问次数/时间(initNum/initNum / initNum/expire)。

    3:每次访问后补充的令牌个数计算方式

    获取上次访问的时间即上次存入令牌的时间,计算当前时间与上次访问的时间差,乘以速率等于此次需要补充的令牌个数,重点是补充令牌后总的令牌个数不能大于初始化的令牌个数,以补充数和初始化数的最小值为准。

    4:程序使用流程

    第一次访问时初始化令牌个数($minNum),存入Redis同时将当前的时间戳存入以便计算下次需要补充的令牌个数。

    第二次访问时获取剩余的令牌个数,并添加本次应该补充的令牌个数,补充后如何令牌数>0则当前访问是有效的可以访问,否则令牌使用完毕不可访问。先补充令牌再判断令牌是否大于0,是因为还有速率跟临界值的问题。如果上次剩余的令牌为0但是本次应该补充的令牌大于1那么本次依然可以访问。

    5:针对并发的处理

    使用Redis的乐观锁机制

    基于PHP+Redis实现的令牌桶算法二
    /**
     * Class TokenBucket
     */
    class TokenBucket 
    {
        
    
        /**
         * service
         * @var string
         */
        private $_redis;
        private $_queue;   //令牌桶
        private $_max;        //最大令牌数
    
        /**
         * 构造函数
         * Checkupi constructor.
         */
        public function __construct()
        {
            parent::__construct();
            app()->load->config('redis');
            app()->load->driver('cache');
            $this->_redis = $this->cache->redis->getRedis();
            $this->_json['data'] = (object)[];
            $this->_queue = 'tokenbucket';
            $this->_max = 9;
        }
    
        /**
         * 调用令牌桶接口
         */
        public function RateLimit()
        {
            $r = $this->get();
    
            if ($r) {
                $this->_json['code'] = self::CODE_SUCC;
                $this->_json['msg'] = strval(1111);
                $this->_json['data'] = [
                    'ok'
                ];
                $this->y_view($this->_json);
            }
    
            $this->_json['code'] = self::CODE_FAIL;
            $this->_json['msg'] = strval('error');
            $this->y_view($this->_json);
        }
    
        /**
         * 加入令牌
         * @param Int $num 加入的令牌数量
         * @return Int 加入的数量
         */
        public function add($num = 0)
        {
            //当前剩余令牌数
            $curnum = intval($this->_redis->lSize($this->_queue));
            //最大令牌数
            $maxnum = intval($this->_max);
            //计算最大可加入的令牌数量,不能超过最大令牌数
            $num = $maxnum >= ($curnum + $num) ? $num : ($maxnum - $curnum);
    
            //加入令牌
            if ($num > 0) {
                $token = array_fill(0, $num, 1);
                $this->_redis->lPush($this->_queue, ...$token);
                return $num;
            }
    
            return 0;
        }
    
        /**
         * 获取令牌
         */
        public function get()
        {
            return $this->_redis->rPop($this->_queue) ? true : false;
        }
    
        /**
         * 重设令牌桶,填满令牌
         */
        public function reset()
        {
            $this->add($this->_max);
        }
    }
    

    代码要点:

    1. get()

    通过redis的rPop方法获取列表里令牌数如果还有返回true,没有返回false。

    2. reset()

    重置令牌桶,将桶加满。

    3. add()

    增加令牌思路,先查看还剩多少令牌,计算最大可加入的令牌数量,不能超过最大令牌数,加入redis。

    4. 整体思路

    指定时间执行reset(例如每隔100毫秒),保持每隔一段时间令牌桶会加满,然后接口请求的时候每次减少一个直到没有限流。

    三、总结

    限流是一种思想,实现的方式有很多种,这里只是提供几种思路,还有很多不足,需要深入研究。



    起源地 » 高并发下限流-漏桶、令牌桶算法及PHP实现

    常见问题FAQ

    免费下载或者VIP会员专享资源能否直接商用?
    本站所有资源版权均属于原作者所有,这里所提供资源均只能用于参考学习用,请勿直接商用。若由于商用引起版权纠纷,一切责任均由使用者承担。更多说明请参考 VIP介绍。
    提示下载完但解压或打开不了?
    最常见的情况是下载不完整: 可对比下载完压缩包的与网盘上的容量,若小于网盘提示的容量则是这个原因。这是浏览器下载的bug,建议用百度网盘软件或迅雷下载。若排除这种情况,可在对应资源底部留言,或 联络我们.。
    找不到素材资源介绍文章里的示例图片?
    对于PPT,KEY,Mockups,APP,网页模版等类型的素材,文章内用于介绍的图片通常并不包含在对应可供下载素材包内。这些相关商业图片需另外购买,且本站不负责(也没有办法)找到出处。 同样地一些字体文件也是这种情况,但部分素材会在素材包内有一份字体下载链接清单。
    模板不会安装或需要功能定制以及二次开发?
    请QQ联系我们

    发表评论

    还没有评论,快来抢沙发吧!

    如需帝国cms功能定制以及二次开发请联系我们

    联系作者

    请选择支付方式

    ×
    迅虎支付宝
    迅虎微信
    支付宝当面付
    余额支付
    ×
    微信扫码支付 0 元