工作上在开发类似淘宝开放平台的点评到综的开放平台,需要针对不同的API做流量控制,后期还需要针对不同属性的服务商(上线状态,部分api的购买状态)做不同的流量控制策略,如 淘宝开放平台应用API流量规则。流量控制的维度主要有QPS流量控制以及一定时间区间(如/天、/小时)的调用次数。

网络流量控制(Network traffic control)是一种利用软件或硬件方式来实现对电脑网络流量的控制。它的最主要方法,是引入QoS的概念,从通过为不同类型的网络数据包标记,从而决定数据包通行的优先次序(from wiki)。

一般开发高并发系统常见的限流有:限制总并发数(比如数据库连接池、线程池)、限制瞬时并发数(如nginx的limit_conn模块,用来限制瞬时并发连接数)、限制时间窗口内的平均速率(如Guava的RateLimiter、nginx的limit_req模块,限制每秒的平均速率);其他还有如限制远程接口调用速率、限制MQ的消费速率。另外还可以根据网络连接数、网络流量、CPU或内存负载等来限流。

1 限流算法

做限流(Rate Limiting/Throttling)的时候,除了简单的控制并发,如果要准确的控制TPS,简单的做法是维护一个单位时间内的Counter,如判断单位时间已经过去,则将Counter重置零。此做法被认为没有很好的处理单位时间的边界,比如在前一秒的最后一毫秒里和下一秒的第一毫秒都触发了最大的请求数,将目光移动一下,就看到在两毫秒内发生了两倍的TPS。

常用的更平滑的限流算法有两种:漏桶算法和令牌桶算法。很多传统的服务提供商如华为中兴都有类似的专利,参考采用令牌漏桶进行报文限流的方法 。

1.1 漏桶算法

漏桶算法(Leaky bucket):水(请求)先进入到漏桶中,漏桶以一定速度出水(接口有响应速率),当水流入速度过大直接溢出(访问频率超过接口响应速率)。

算法过程:

  • 一个固定容量的漏桶,按照常量固定速率流出水滴;
  • 如果桶是空的,则不需流出水滴;
  • 可以以任意速率流入水滴到漏桶;
  • 如果流入水滴超出了桶的容量,则流入的水滴溢出了(被丢弃),而漏桶容量是不变的。

因此,漏桶算法中两个变量:

  • 桶的大小——支持流量突发增多时可以存多少水(burst)
  • 桶漏桶大小(rate)

算法实现思路如下:

double rate;               // leak rate in calls/s
double burst;              // bucket size in calls

long refreshTime;          // time for last water refresh
double water;              // water count at refreshTime

refreshWater() {
    long  now = getTimeOfDay();

    //水随着时间流逝,不断流走,最多就流干到0.
    water = max(0, water- (now - refreshTime)*rate); 
    refreshTime = now;
}

bool permissionGranted() {
    refreshWater();
    if (water < burst) { // 水桶还没满,继续加1
        water ++;
        return true;
    } else {
        return false;
    }
}

1.2 令牌桶算法

令牌桶算法是一个存放固定容量令牌的桶,按照固定速率往桶里添加令牌。随着时间流逝,系统会按恒定1/QPS时间间隔(如果QPS=100,则间隔是10ms)往桶里加入Token,如果桶已经满了就不再加了。新请求来临时,会各自拿走一个Token,如果没有Token可拿了就阻塞或者拒绝服务。

Guava中的RateLimiter采用了令牌桶的算法,详细的算法实现参见源码

Guava中RateLimiter的设计思路参见 How is the RateLimiter designed, and why?,下面是对其的翻译:

RateLimiter的主要功能就是提供一个稳定的速率,实现方式就是通过限制请求流入的速度,比如计算请求等待合适的时间阈值。

实现QPS速率的最简单的方式就是记住上一次请求的最后授权时间,然后保证1/QPS秒内不允许请求进入。比如QPS=5,如果我们保证最后一个被授权请求之后的200ms的时间内没有请求被授权,那么我们就达到了预期的速率。如果一个请求现在过来但是最后一个被授权请求是在100ms之前,那么我们就要求当前这个请求等待100ms.按照这个思路,请求15个新令牌(许可证)就需要3秒。

有一点很重要:上面这个设计思路的RateLimiter记忆非常的浅,它的脑容量非常的小,只记得上一次被授权的请求的时间。如果RateLimiter的一个被授权请求q之前很长一段时间没有被使用会怎么样?这个RateLimiter会立马忘记过去这一段时间的利用不足,而只记得刚刚的请求。

过去一段时间的利用不足意味着有过剩的资源是可以利用的。这种情况下,RateLimiter应该加把劲(speed up for a while)将这些过剩的资源利用起来.比如在向网络中发生数据的场景(限流),过去一段时间的利用不足可能意味着网卡缓冲区是空的,这种场景下,我们是可以加速发送来将这些过程的资源利用起来。

另一方面,过去一段时间的利用不足可能意味着处理请求的服务器对即将到来的请求是准备不足的(less ready for future requests),比如因为很长一段时间没有请求当前服务器的cache是陈旧的,进而导致即将到来的请求会触发一个昂贵的操作(比如重新刷新全量的缓存)。

为了处理这种情况,RateLimiter中增加了一个维度的信息,就是过去一段时间的利用不足(past underutilization),代码中使用storedPermits变量表示。当没有利用不足这个变量为0,最大能达到maxStoredPermits(maxStoredPermits表示完全没有利用)。因此,请求的令牌可能从两个地方来:

1.过去剩余的令牌(stored permits, 可能没有)
2.现有的令牌(fresh permits,当前这段时间还没用完的令牌)

我们将通过一个例子来解释它是如何工作的:

对一个每秒产生一个令牌的RateLimiter,每有一个没有使用令牌的一秒,我们就将storedPermits加1,如果RateLimiter在10秒都没有使用,则storedPermits变成10.0。这个时候,一个请求到来并请求三个令牌(acquire(3)),我们将从storedPermits中的令牌为其服务,storedPermits变为7.0。这个请求之后立马又有一个请求到来并请求10个令牌,我们将从storedPermits剩余的7个令牌给这个请求,剩下还需要三个令牌,我们将从RateLimiter新产生的令牌中获取。我们已经知道,RateLimiter每秒新产生1个令牌,就是说上面这个请求还需要的3个请求就要求其等待3秒。

想象一个RateLimiter每秒产生一个令牌,现在完全没有使用(处于初始状态),限制一个昂贵的请求acquire(100)过来.如果我们选择让这个请求等待100秒再允许其执行,这显然很荒谬。我们为什么什么也不做而只是傻傻的等待100秒,一个更好的做法是允许这个请求立即执行(和acquire(1)没有区别),然后将随后到来的请求推迟到正确的时间点.这种策略,我们允许这个昂贵的任务立即执行,并将随后到来的请求推迟100秒。这种策略就是让任务的执行和等待同时进行。

一个重要的结论:RateLimiter不会记最后一个请求,而是即下一个请求允许执行的时间。这也可以很直白的告诉我们到达下一个调度时间点的时间间隔。然后定一个一段时间未使用的Ratelimiter也很简单:下一个调度时间点已经过去,这个时间点和现在时间的差就是Ratelimiter多久没有被使用,我们会将这一段时间翻译成storedPermits。所以如果每秒钟产生一个令牌(rate==1),并且正好每秒来一个请求,那么storedPermits就不会增长。

RateLimiter实际上由两种实现策略,其实现分别见SmoothBurstySmoothWarmingUp,其中SmoothWarmingUp的实现类似漏桶算法,但与之又有不同。

  /**


   * This implements the following function where coldInterval = coldFactor * stableInterval.

   *


   * <pre>
   *          ^ throttling
   *          |
   *    cold  +                  /
   * interval |                 /.
   *          |                / .
   *          |               /  .   ← "warmup period" is the area of the trapezoid between
   *          |              /   .     thresholdPermits and maxPermits
   *          |             /    .
   *          |            /     .
   *          |           /      .
   *   stable +----------/  WARM .
   * interval |          .   UP  .
   *          |          . PERIOD.
   *          |          .       .
   *        0 +----------+-------+--------------→ storedPermits
   *          0 thresholdPermits maxPermits
   * </pre>

2 分布式流量控制

分布式控制最关键的是要将限流服务做成原子化,针对集群维度进行流量限制。
可以使使用redis+lua或者nginx+lua技术进行实现

使用redis实现时,可以采用guava中ratelimiter的算法实现。

import redis
from redis import WatchError
import time

RATE = 0.1
# 令牌桶的最大容量
DEFAULT = 100
# redis key 的过期时间
TIMEOUT = 60 * 60

r = redis.Redis()

def token_bucket(tokens, key):

    pipe = r.pipeline()
    while 1:
        try:
            pipe.watch('%s:available' % key)
            pipe.watch('%s:ts' % key)

            current_ts = time.time()

            # 获取令牌桶中剩余令牌
            old_tokens = pipe.get('%s:available' % key)
            if old_tokens is None:
                current_tokens = DEFAULT
            else:
                old_ts = pipe.get('%s:ts' % key)
                # 通过时间戳计算这段时间内应该添加多少令牌,如果桶满,令牌数取桶满数。
                current_tokens = float(old_tokens) + min(
                    (current_ts - float(old_ts)) * RATE,
                    DEFAULT - float(old_tokens)
                )
            # 判断剩余令牌是否足够
            if 0 <= tokens <= current_tokens:
                current_tokens -= tokens
                consumes = True
            else:
                consumes = False

            # 以下动作为更新 redis 中key的值,并跳出循环返回结果。
            pipe.multi()
            pipe.set('%s:available' % key, current_tokens)
            pipe.expire('%s:available' % key, TIMEOUT)
            pipe.set('%s:ts' % key, current_ts)
            pipe.expire('%s:ts' % key, TIMEOUT)
            pipe.execute()
            break
        except WatchError:
            continue
        finally:
            pipe.reset()
    return consumes

if __name__ == "__main__":
    tokens = 5
    key = '192.168.1.1'
    if token_bucket(tokens, key):
        print 'haz tokens'
    else:
        print 'cant haz tokens'

不过因为redis不能使用自身的时间戳,因此只能依靠应用传入,在一些情况下(机器时钟偏差),会出现令牌发放问题。且使用redis在流量很高的情况下会出现:

  • 单KEY热点问题,当单KEY QPS超过几十万时,单台缓存服务器响应时间(RT)明显增加;
  • 缓存集群QPS达到数百万时,服务器投入较高。

References

 TCP的流量控制和拥塞控制
流量调整和限流技术
聊聊高并发系统之限流特技
服务限流(Rate Limiting)
RateLimiter
Redis 与网络流量整形
历经8年双11流量洗礼,淘宝开放平台如何攻克技术难关?