PHP 滑动窗口限流算法

PHP 滑动窗口限流算法

author: he xiaodong date: 2020-04-24

代码在 Laravel 6.0 上测试成功

滑动窗口其实就是 细分之后的计数器 滑动窗口 这样假设, 先把一分钟划分成6段! 也就是10s一个段!在第一段里,假如请求61次,那么直接触发了规则!肯定就过不去了!如果只请求了1次!则是正常的! 当时间走到第二个段里,即10s~20s这段范围里,我请求数不能超过总的限定条件,且当前段的请求数量 加上 之前段的总数量也不能超过总限定数量!

当时间到了50s~60s,依然是一样!

如果过了60s,所以请求数都是正常的,则把划分段往右移一段!那么此时的6个分段是 10 ~ 20,20 ~ 30,30 ~ 40,40 ~ 50,50 ~ 60,60 ~ 70

然后统计规则还跟上面一样!

所以,只有划分的越细,请求限制越平滑!

PHP 实现

class SlidingWindow
{
    protected $timeStamp;

    // 限定时间内请求的最多次数
    protected $limitCount = 100;

    // 时间间隔
    protected $interval = 10;

    // 请求数
    protected $reqCount = 0;

    // 分成多少份
    protected $count = 6;

    public function __construct()
    {
        $this->timeStamp = strtotime(date('Y-m-d H:i').':00');
        $this->reqCount = \Cache::get('reqCount');
    }

    public function grant()
    {
        $allCounter = \Cache::get('allCounterArr');
        $nowMinute = date('Y-m-d H:i');

        if (empty($allCounter)) {
            for ($i = 0; $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 (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) {
            echo 1 . PHP_EOL;
            // 执行正常程序
        } else {
            echo 0 . PHP_EOL;
            // 进行限流
        }
    }
}

调用实例:

Route::get('2', function () {
    $slide = new SlidingWindow();
    for ($i = 0; $i < 106; $i++) {
        $slide->test();
    }
});

参考文章:

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