千与千寻-限流策略介绍

限流策略介绍

限流策略是后端服务比较重要的一个组件，它可以防止服务器在极端情况下挂掉（比如高并发），提高服务可用性。一般并发量较大的系统都会做限流。

目前比较流行的限流算法包括计数器法，滑动窗口算法，漏通算法，令牌桶算法等等。

1、计数器算法

计数器算法比较简单，就是记录在某个单位时间内，记录对应的访问次数。如果在时间范围内，访问次数达到了最大限制，直接拒绝访问；如果当前请求已经超过了规定的时间且未达到最大的次数限制，重置访问次数。

在laravel中就有该中算法的实现，ThrottleRequests就是采用该算法。我们看一下其源码的核心：

public function handle($request, Closure $next, $maxAttempts = 60, $decayMinutes = 1)
    {
        $key = $this->resolveRequestSignature($request);

        $maxAttempts = $this->resolveMaxAttempts($request, $maxAttempts);

        if ($this->limiter->tooManyAttempts($key, $maxAttempts, $decayMinutes)) {
            throw $this->buildException($key, $maxAttempts);
        }

        $this->limiter->hit($key, $decayMinutes);

        $response = $next($request);

        return $this->addHeaders(
            $response, $maxAttempts,
            $this->calculateRemainingAttempts($key, $maxAttempts)
        );
    }

上面的代码，就是对于某一类请求（可以针对某个url，可以针对某个用户），在某个时间范围内，如果达到了次数限制就拒绝，否则就会将计数器加1，并放行。

它将计数保存在缓存中，使用了门面Cache(底层驱动可以是文件，可以是Redis，可以是Memcache等等）。

 public function tooManyAttempts($key, $maxAttempts, $decayMinutes = 1)
    {
       //attempt就是获取对应的次数，如果超过最大次数，且没有过期，就拒绝；如果过期了，次数就重置
        if ($this->attempts($key) >= $maxAttempts) {
            if ($this->cache->has($key.':timer')) {
                return true;
            }

            $this->resetAttempts($key);
        }

        return false;
    }

再看一下增加计数的方法：

 public function hit($key, $decayMinutes = 1)
    {
        //类似一个计时器，我觉得并没有什么卵用，画蛇添足。
        $this->cache->add(
            $key.':timer', $this->availableAt($decayMinutes * 60), $decayMinutes
        );
         //真正存储计数的key
        $added = $this->cache->add($key, 0, $decayMinutes);

        $hits = (int) $this->cache->increment($key);

        if (! $added && $hits == 1) {
            $this->cache->put($key, 1, $decayMinutes);
        }

        return $hits;
    }

可以看到，其采用的就是计数器算法，一种比较简单的实现。这种算法的一个弊端是如果时间范围内，达到了限制，其他的所有请求都不能访问了，这种是非常不灵活的，会出现所谓的突刺现象。

计数器法采用的是一中固定窗口的模式，假如有人恶意在前一分钟的最后一秒和后一分钟的第一妙并发最高的QPS，这个时候系统的限流就是失效的。

针对上述问题，还有一种限流策略叫滑动窗口技术法。滑动窗口就是将时间分成多个小格，随着时间推移，统计的窗口是滑动的。比如针对上述问题，还是以1分钟为一个窗口，每秒为一个小格，那么前一分钟的最后一秒和后一分钟的第一妙会处于同一个滑动窗口中，限流是起到作用的。

阿里的sentinel使用的限流算法就是滑动窗口限流法。

2、漏桶算法

网上有一张对于该算法清晰得描述：

它的基本思想就是不管你怎么进来，处理的时侯都是以恒定的速率去做。一般都是队列去实现，处理线程可以到队列中去拿请求。

Nginx的ngx_http_limit_req_lookup就是采用漏桶算法实现的，数据结构采用的是红黑树和LRU队列。感兴趣的可以看看Nginx的限流源码。

其最重要的代码：

ngx_http_limit_req_lookup(ngx_http_limit_req_limit_t *limit, ngx_uint_t hash,
ngx_str_t *key, ngx_uint_t *ep, ngx_uint_t account)
{
//在红黑树中查找是否有这个请求
while (node != sentinel) {
    //本次请求和上次请求之间的间隔时间
    ms = (ngx_msec_int_t) (now - lr->last);
    //当前队列里的请求数目=之前剩余的请求数目-请求时间差内的消耗的数目+当前的本次请求即1
    excess = lr->excess - ctx->rate * ms / 1000 + 1000;
 
 
    if ((ngx_uint_t) excess > limit->burst) { //如果超出流桶的大小，则拒绝请求
                return NGX_BUSY;
            }
 
 
    //由于Nginx可以配置多个限流策略，如果这个是最后一条，则更新相关变量，返回OK，该请求可以通过
    if (account) {
                lr->excess = excess;
                if (ms) {
                    lr->last = now;
                }
                return NGX_OK;
            }
    }
}
//没找到，说明是第一次来，则创建节点放入红黑树及LRU队列
    lr->excess = 0;
    ngx_rbtree_insert(&ctx->sh->rbtree, node);
 
if (account) {
        lr->last = now;
        lr->count = 0;
        return NGX_OK;
    }
 
//返回
return NGX_AGAIN;
}

上述的 excess = lr->excess - ctx->rate * ms / 1000 + 1000是关键，rate是设定的速率。

上述是避免了计数法出现突刺的问题，但是无法应对突发请求的场景。

3、令牌桶算法

令牌桶是漏通算法的一种改进，它是用一个存放令牌的固定大小的桶。令牌是以恒定的速度放入桶中，如果令牌达到了桶大小的限制，则被拒绝继续放入。请求过来，只有拿到了令牌，才可以放行；否则拒绝访问。

这种算法是控制了流入速率，解决了突发请求的问题，理论上，只要令牌足够，可以拿到多个令牌。

大名鼎鼎的Guava的RateLimiter就是采用令牌桶算法来实现的，具体可以看下面的参考资料，讲解的非常清晰，这里就不赘述了。只放上几个重要的方法。

一是设置产生令牌的方法，其主要有两种：一个是一直以一个恒定的速率产生；一种是令牌生成速度由慢到快，一直达到一个稳定的值。

令牌的发生并不是使用定时任务，而是使用延迟产生，即在获取令牌前会调用一个叫做resync的函数，该方法用来产生令牌。而当前令牌数就根据当前时间和下此增加令牌时间来刷新。

即在调用acquire获取令牌时会调用，acquire会调用下面方法。

   final long reserveEarliestAvailable(int requiredPermits, long nowMicros) {
        this.resync(nowMicros);
        long returnValue = this.nextFreeTicketMicros;
        double storedPermitsToSpend = Math.min((double)requiredPermits, this.storedPermits);
        double freshPermits = (double)requiredPermits - storedPermitsToSpend;
        long waitMicros = this.storedPermitsToWaitTime(this.storedPermits, storedPermitsToSpend) + (long)(freshPermits * this.stableIntervalMicros);
        this.nextFreeTicketMicros = LongMath.saturatedAdd(this.nextFreeTicketMicros, waitMicros);
        this.storedPermits -= storedPermitsToSpend;
        return returnValue;
    }

Guava的限流策略很不错，但不适用集群。目前阿里开源的sentinel是一种不错的限流中间件。Dubbo也使用了。

目前分布式限流框架对比：

对比维度	Sentinel	Hystrix	resilience4j
隔离策略	信号量隔离（并发线程数限流）	线程池隔离/信号量隔离	线程池隔离/信号量隔离
熔断降级策略	基于平均响应时间、异常比例、或异常数	基于失败比率	基于异常比率、响应时间
实时指标实现	滑动窗口（LeapArray）	滑动窗口（基于 RxJava）	Ring Bit Buffer
规则配置	支持多种数据源	支持多种数据源	有限支持
扩展性	多个扩展点	插件的形式	接口的形式
基于注解的支持	支持	支持	支持
限流	基于 QPS、并发数，支持基于调用关系的限流	有限的支持	Rate Limiter
流量整形	支持慢启动、匀速器、排队等待模式	不支持	简单的Rate Limiter模式
系统负载保护	支持	不支持	不支持
控制台	开箱即用，可配置规则、查看秒级监控、机器发现等	简单的监控查看	不提供控制台，可对接其它监控系统
常见框架的适配	Servlet、Spring Cloud、Dubbo、gRPC 等	Servlet、Spring Cloud Netflix