PHP语言描述|保障服务稳定之服务限流算法

一、前言
对于一个系统而言，最重要的要求之一肯定就是服务的稳定性了，一个不稳定的系统可能给企业带来巨大的损失，包括经济和品牌等等方面的损失。

我们都希望系统能稳定可靠地对外提供服务，响应快，不宕机，不故障，但是在实际情况中，常常会遇到一些异常的情况，这就考验我们系统的稳定性了。

今天就来讲讲保障服务稳定性的手段之一的服务限流。

二、解决的问题

我们系统运行过程中有时候可能会遇到突发异常大流量，如果系统无法正确处理这些突然涌入大量请求，就会导致系统轻则响应慢，经常超时，重则导致整个系统宕机，因此这就要求我们系统能以一定的策略处理大流量的涌入，这样才不对被突发大流量压垮，导致完全无法对外提供服务。

注意，这里大流量说的是突发异常大流量，是非正常情况，所以我们的处理策略是对部分请求进行丢弃或者排队处理，保证我们系统对外还是可用的，而非全部请求都需要处理完。而对于系统正常的普通流量来说，如果其请求量逐渐达到了我们系统的负载能力的上限的话，这时候需要进行的就是服务的扩容，而不是限流并丢弃请求了。

我们系统可能遇到的突发大流量的场景有很多，但统一的表现都是，某些接口请求量激增，导致超过了系统的处理能力了，例如：

突发热点事件（例如微博热搜）
爬虫
恶意攻击
恶意刷单（如12306）

面对突发大流量，我们系统能使用的手段之一就是服务限流了。限流是通过对一个时间段处理内的请求量进行限制来保护系统，一旦达到限制速率则可以丢弃请求，从而控制了系统处理的请求量不会超过其处理能力。

限流可能在整个网络请求过程的各个层面发生，例如nginx，业务代码层等，这里主要介绍的是限流的思想，也就是限流算法，并给出业务层的代码实现例子。

三、限流算法
1、计数器算法
计数器限流算法是比较简单粗暴的算法，主要通过一个或者多个计数器来统计一段时间内的请求总量，然后判断是否超过限制，超过则进行限流，不超过则对应的计数器数量加1。

计数器限流算法又可以分为固定窗口和滑动窗口两种。

固定窗口

固定窗口计数器限流算法是统计固定一个时间窗口内的请求总数来判断是否进行限流，例如限制每分钟请求总数为100，则可以通过一个计数器来统计当前分钟的请求总数，每来一个请求判断当前分钟对应的计数器的数量，没有超过限制则在当前分钟对应的计数器加1，超过则拒绝请求。

PHP实现逻辑如下:

/**
 * 固定窗口计数器限流算法
 * @param $key string 限流依据，例如uid，url等
 * @param $time int 限流时间段，单位秒
 * @param $limit int 限流总数
 */
function limit($key, $time, $limit) {

    //当前时间所在分片
    $current_segment=floor(time() / $time);
    //按当前时间和限流参数生成key
    $current_key = $key . '_' . $time . '_' . $limit . '_' . $current_segment;

    $redis = new Redis();
    //key不存在才设置，且设置过期时间
    $redis->set($current_key, 0, ['nx', 'ex' => $time]);
    $current = $redis->incr($current_key);

    //为了解决请求并发的问题，代码实现上要先加再判断
    if ($current > $limit) {
        return false;
    }
    return true;
}

缺点

固定窗口计数器限流算法实现起来虽然很简单，但是有一个十分致命的问题，那就是临界突刺问题：最后一秒和最开始1秒的流量集中一起，会出现大量流量。

计数器的限制数量判断是按时间段的，在两个时间段的交界时间点，限制数量的当前值会发生一个抖动的变化，从而使瞬间流量突破了我们期望的限制。例如以下的情况：

请输入图片描述

可以看到在0:59的时候，如果突然来了100个请求，这时候当前值是100，而到了1:00的时候，因为是下一个时间段了，当前值陡降到0，这时候又进来100个请求，都能通过限流判断，虽然两个时间段平均下来还是没超过限制，但是在临界时间点的请求量却达到了两倍之多，这种情况下就可能压垮我们的系统。

滑动窗口

上面会出现突刺的问题其实就在于固定窗口算法的窗口时间跨度太大，且是固定不变的，为了解决突刺的问题，我们就有了滑动窗口计数器限流算法。

滑动窗口算法是固定窗口算法的优化版，主要有两个特点：

划分多个小的时间段，各时间段各自进行计数。
根据当前时间，动态往前滑动来计算时间窗口范围，合并计算总数。

请输入图片描述

可以看到，每次时间往后，窗口也会动态往后滑动，从而丢弃一些更早期的计数数据，从而实现总体计数的平稳过度。当滑动窗口划分的格子越多，那么滑动窗口的滑动就越平滑，限流的统计就会越精确。事实上，固定窗口算法就是只划分成一个格子的滑动窗口算法。

PHP实现逻辑如下:

/**
 * 滑动窗口计数器限流算法
 * @param $key string 限流依据，例如uid，url等
 * @param $time int 限流时间段，单位秒
 * @param $limit int 限流总数
 * @param $segments_num int 分段个数
 */
function limit($key, $time, $limit, $segments_num) {

    //小分片时间长度
    $segments_time=floor($time/$segments_num);
    //当前时间所在小分片
    $current_segment=floor(time() / $segments_time);
    //按限流时间段生成key
    $current_key = $key . '_' . $time . '_' . $limit . '_' . $current_segment;
    
    $redis = new Redis();
    //先更新当前时间所在小分片计数，key不存在才设置，且设置过期时间
    $redis->set($current_key, 0, ['nx', 'ex' => $time]);
    $current = $redis->incr($current_key);

    for($window=$segments_time;$window<$time;$window+=$segments_time){
        $current_segment=$current_segment-1;
        $tmp_key = $key . '_' . $time . '_' . $limit . '_' . $current_segment;
        //计算时间窗口内的总数
        $current+=intval($redis->get($tmp_key));
        if ($current > $limit) {
            //超过限制的话要回滚本次加的次数
            $redis->decr($current_key);
            return false;
        }
    }
    
    return true;
}

缺点

滑动窗口限流算法虽然可以保证任意时间窗口内接口请求次数都不会超过最大限流值，但是相对来说对系统的瞬时处理能力还是没有考虑到，无法防止在更细的时间粒度上访问过于集中的问题，例如在同一时刻（同一秒）大量请求涌入，还是可能会超过系统负荷能力。

2、漏桶算法
漏桶算法就是一种从系统的处理能力出发进行限流的算法。类似生活用到的漏斗，上面进水，下面有个小口出水，当请求进来时，相当于水倒入漏斗，然后从下端小口慢慢匀速的流出。不管上面流量多大，下面流出的速度始终保持不变，超过漏斗容量的则丢弃。漏桶算法以固定的速率释放访问请求（即请求通过），直到漏桶为空。
请输入图片描述
漏桶算法有两个关键数据：桶的容量V和流出的速率R。假设每个请求的平均处理时间是S，最大超时时间是SS，则V/R+S<=SS。

可以使用队列来实现，队列设置最大容量，访问请求先进入队列，队列满了的话就丢弃丢弃后续请求，然后通过另外一个woker以固定速率从队列出口拿请求去处理。具体实现逻辑不展示了。

缺点
漏桶算法的缺陷很明显，由于出口的处理速率是固定的，当短时间内有大量的突发请求时，即便此时服务器没有任何负载，每个请求也都得在队列中等待一段时间才能被响应，因此漏桶算法无法应对突发流量。

3、令牌桶算法
令牌桶算法也是有一个桶，但是它不是通过限制漏出的请求来控制流量，而是通过控制桶的令牌的生成数量来达到限流的目的的。令牌桶定时往桶里面丢一定的令牌，令牌桶满了就不再往里面加令牌。每来一个请求就要先在桶里拿一个令牌，拿到令牌则通过，拿不到则拒绝。

请输入图片描述
当访问量小于令牌桶的生成速率时，令牌桶可以慢慢积累令牌直到桶满，这样当短时间的突发访问量来时，其积累的令牌数保证了大量请求都能立刻拿到令牌进行后续处理。当访问量持续大量流入时，积累的令牌被消耗完了之后，后续请求又依赖于一定速率产生的新令牌，这时候就变成类似漏桶算法那样的固定流量限制。

由此可见，相比于漏桶算法，令牌桶算法能够在限制调用的平均速率的同时还允许一定程度的突发调用。

PHP实现逻辑如下:

/**
 * 令牌桶限流算法
 * @param $key string 限流依据，例如uid，url等
 * @param $rate float 令牌生成速率，每秒$rate个
 * @param $volume int 容量
 * @return bool
 */
function limit($key, $rate, $volume) {

    //按限流参数生成key
    $current_key = $key . '_' . $rate . '_' . $volume;

    $redis = new Redis();
    $time=time();
    
    //没有则初始化
    $redis->hSetNx($current_key, 'num', $volume);
    $redis->hSetNx($current_key, 'time', $time);

    //以下逻辑在高并发情况下要用lua脚本或者加分布式锁，这里仅用于说明算法的逻辑，就不考虑并发情况了
    //计算从上次到现在，需要添加的令牌数量
    $last=$redis->hMGet($current_key,['num','time']);
    $last_time=$last['time'];
    $last_num=$last['num'];
    $incr=($time-$last_time)*$rate;
    $current=min($volume,($last_num+$incr));//计算当前令牌数
    
    if($current>0){
        $redis->hMSet($current_key,[
            'num'=>$current-1,
            'time'=>time()
        ]);
        return true;
    }
    
    return false;
}

上面的实现方案是令牌按时间回复数量，事实上令牌的生成也可以通过另外的服务去生成，这样可以按一定策略去调控令牌的生成速率。

作者: X先生
https://segmentfault.com/a/1190000023411052

#PHP

第一百零一次闯荡江湖的无名游侠