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

一 、场景描述（为什么需要限流）

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

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

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

二、常用的限流算法

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

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

2.1、漏桶算法

原理

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

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

示意图如下:

可见这里有两个变量，一个是桶的大小，支持流量突发增多时可以存多少的水(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可拿就阻塞或者拒绝服务。

令牌桶的好处： 可以方便的改变请求速度。 一旦需要提高速率，只需提高放入桶中的令牌的速率。 一般会定时(比如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 /$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毫秒），保持每隔一段时间令牌桶会加满，然后接口请求的时候每次减少一个直到没有限流。

三、总结

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

南京三百云信息科技有限公司（车300）成立于2014年3月27日，是一家扎根于南京的移动互联网企业，目前坐落于南京、北京。经过7年积累，累计估值次数已达52亿次，获得了国内外多家优质投资机构青睐如红杉资本、上汽产业基金等。
三百云是国内优秀的以人工智能为依托、以汽车交易定价和汽车金融风控的标准化为核心产品的独立第三方的汽车交易与金融SaaS服务提供商。

欢迎加入三百云，一起见证汽车行业蓬勃发展，期待与您携手同行!
Java开发、Java实习、PHP实习、测试、测开、产品经理、大数据、算法实习，热招中…
官网：www.sanbaiyun.com/
投递简历：hr@che300.com，请注明来自掘金?