高并发下限流-漏桶、令牌桶算法及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\mathrm{/}$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毫秒），保持每隔一段时间令牌桶会加满，然后接口请求的时候每次减少一个直到没有限流。

三、总结

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