高并发系统的限流详解及实现

在开发高并发系统时有三把利器用来保护系统：缓存、降级和限流。本文结合作者的一些经验介绍限流的相关概念、算法和常规的实现方式。

缓存

缓存比较好理解，在大型高并发系统中，如果没有缓存数据库将分分钟被爆，系统也会瞬间瘫痪。使用缓存不单单能够提升系统访问速度、提高并发访问量，也是保护数据库、保护系统的有效方式。大型网站一般主要是“读”，缓存的使用很容易被想到。在大型“写”系统中，缓存也常常扮演者非常重要的角色。比如累积一些数据批量写入，内存里面的缓存队列（生产消费），以及hbase写数据的机制等等也都是通过缓存提升系统的吞吐量或者实现系统的保护措施。甚至消息中间件，你也可以认为是一种分布式的数据缓存。

降级

服务降级是当服务器压力剧增的情况下，根据当前业务情况及流量对一些服务和页面有策略的降级，以此释放服务器资源以保证核心任务的正常运行。降级往往会指定不同的级别，面临不同的异常等级执行不同的处理。根据服务方式：可以拒接服务，可以延迟服务，也有时候可以随机服务。根据服务范围：可以砍掉某个功能，也可以砍掉某些模块。总之服务降级需要根据不同的业务需求采用不同的降级策略。主要的目的就是服务虽然有损但是总比没有好。

限流

限流可以认为服务降级的一种，限流就是限制系统的输入和输出流量已达到保护系统的目的。一般来说系统的吞吐量是可以被测算的，为了保证系统的稳定运行，一旦达到的需要限制的阈值，就需要限制流量并采取一些措施以完成限制流量的目的。比如：延迟处理，拒绝处理，或者部分拒绝处理等等。

限流的算法

常见的限流算法有：计数器、漏桶和令牌桶算法。

计数器

计数器是最简单粗暴的算法。比如某个服务最多只能每秒钟处理100个请求。我们可以设置一个1秒钟的滑动窗口，窗口中有10个格子，每个格子100毫秒，每100毫秒移动一次，每次移动都需要记录当前服务请求的次数。内存中需要保存10次的次数。可以用数据结构linkedlist来实现。格子每次移动的时候判断一次，当前访问次数和linkedlist中最后一个相差是否超过100，如果超过就需要限流了。

高并发系统的限流详解及实现

很明显，当滑动窗口的格子划分的越多，那么滑动窗口的滚动就越平滑，限流的统计就会越精确。

示例代码如下：

									//服务访问次数，可以放在redis中，实现分布式系统的访问计数

									long counter = 0l;

									//使用linkedlist来记录滑动窗口的10个格子。

									linkedlist<long> ll = new linkedlist<long>();

									public static void main(string[] args)

									{

									  counter counter = new counter();

									  counter.docheck();

									}

									private void docheck()

									{

									  while (true)

									  {

									    ll.addlast(counter);

									    if (ll.size() > 10)

									    {

									      ll.removefirst();

									    }

									    //比较最后一个和第一个，两者相差一秒

									    if ((ll.peeklast() - ll.peekfirst()) > 100)

									    {

									      //to limit rate

									    }

									    thread.sleep(100);

									  }

									}

漏桶算法

漏桶算法即leaky bucket是一种非常常用的限流算法，可以用来实现流量整形（traffic shaping）和流量控制（traffic policing）。贴了一张维基百科上示意图帮助大家理解：

高并发系统的限流详解及实现

漏桶算法的主要概念如下：

一个固定容量的漏桶，按照常量固定速率流出水滴；

如果桶是空的，则不需流出水滴；

可以以任意速率流入水滴到漏桶；

如果流入水滴超出了桶的容量，则流入的水滴溢出了（被丢弃），而漏桶容量是不变的。

漏桶算法比较好实现，在单机系统中可以使用队列来实现（.net中tpl dataflow可以较好的处理类似的问题，你可以在这里找到相关的介绍），在分布式环境中消息中间件或者redis都是可选的方案。

令牌桶算法

令牌桶算法是一个存放固定容量令牌（token）的桶，按照固定速率往桶里添加令牌。令牌桶算法基本可以用下面的几个概念来描述：

令牌将按照固定的速率被放入令牌桶中。比如每秒放10个。
桶中最多存放b个令牌，当桶满时，新添加的令牌被丢弃或拒绝。
当一个n个字节大小的数据包到达，将从桶中删除n个令牌，接着数据包被发送到网络上。
如果桶中的令牌不足n个，则不会删除令牌，且该数据包将被限流（要么丢弃，要么缓冲区等待）。

如下图：

高并发系统的限流详解及实现

令牌算法是根据放令牌的速率去控制输出的速率，也就是上图的tonetwork的速率。tonetwork我们可以理解为消息的处理程序，执行某段业务或者调用某个rpc。

漏桶和令牌桶的比较

令牌桶可以在运行时控制和调整数据处理的速率，处理某时的突发流量。放令牌的频率增加可以提升整体数据处理的速度，而通过每次获取令牌的个数增加或者放慢令牌的发放速度和降低整体数据处理速度。而漏桶不行，因为它的流出速率是固定的，程序处理速度也是固定的。

整体而言，令牌桶算法更优，但是实现更为复杂一些。

限流算法实现

guava

guava是一个google开源项目，包含了若干被google的java项目广泛依赖的核心库，其中的ratelimiter提供了令牌桶算法实现：平滑突发限流(smoothbursty)和平滑预热限流(smoothwarmingup)实现。

1.常规速率：

创建一个限流器，设置每秒放置的令牌数：2个。返回的ratelimiter对象可以保证1秒内不会给超过2个令牌，并且是固定速率的放置。达到平滑输出的效果

									public void test()

									{

									  /**

									   * 创建一个限流器，设置每秒放置的令牌数：2个。速率是每秒可以2个的消息。

									   * 返回的ratelimiter对象可以保证1秒内不会给超过2个令牌，并且是固定速率的放置。达到平滑输出的效果

									   */

									  ratelimiter r = ratelimiter.create(2);

									  while (true)

									  {

									    /**

									     * acquire()获取一个令牌，并且返回这个获取这个令牌所需要的时间。如果桶里没有令牌则等待，直到有令牌。

									     * acquire(n)可以获取多个令牌。

									     */

									    system.out.println(r.acquire());

									  }

									}

上面代码执行的结果如下图，基本是0.5秒一个数据。拿到令牌后才能处理数据，达到输出数据或者调用接口的平滑效果。acquire()的返回值是等待令牌的时间，如果需要对某些突发的流量进行处理的话，可以对这个返回值设置一个阈值，根据不同的情况进行处理，比如过期丢弃。

高并发系统的限流详解及实现

2. 突发流量：

突发流量可以是突发的多，也可以是突发的少。首先来看个突发多的例子。还是上面例子的流量，每秒2个数据令牌。如下代码使用acquire方法，指定参数。

system.out.println(r.acquire(2));
system.out.println(r.acquire(1));
system.out.println(r.acquire(1));
system.out.println(r.acquire(1));

得到如下类似的输出。

高并发系统的限流详解及实现

如果要一次新处理更多的数据，则需要更多的令牌。代码首先获取2个令牌，那么下一个令牌就不是0.5秒之后获得了，还是1秒以后，之后又恢复常规速度。这是一个突发多的例子，如果是突发没有流量，如下代码：

system.out.println(r.acquire(1));
thread.sleep(2000);
system.out.println(r.acquire(1));
system.out.println(r.acquire(1));
system.out.println(r.acquire(1));

得到如下类似的结果：

高并发系统的限流详解及实现

等了两秒钟之后，令牌桶里面就积累了3个令牌，可以连续不花时间的获取出来。处理突发其实也就是在单位时间内输出恒定。这两种方式都是使用的ratelimiter的子类smoothbursty。另一个子类是smoothwarmingup，它提供的有一定缓冲的流量输出方案。

									/**

									* 创建一个限流器，设置每秒放置的令牌数：2个。速率是每秒可以210的消息。

									* 返回的ratelimiter对象可以保证1秒内不会给超过2个令牌，并且是固定速率的放置。达到平滑输出的效果

									* 设置缓冲时间为3秒

									*/

									ratelimiter r = ratelimiter.create(2,3,timeunit.seconds);

									while (true) {

									  /**

									   * acquire()获取一个令牌，并且返回这个获取这个令牌所需要的时间。如果桶里没有令牌则等待，直到有令牌。

									   * acquire(n)可以获取多个令牌。

									   */

									  system.out.println(r.acquire(1));

									  system.out.println(r.acquire(1));

									  system.out.println(r.acquire(1));

									  system.out.println(r.acquire(1));

									}

输出结果如下图，由于设置了缓冲的时间是3秒，令牌桶一开始并不会0.5秒给一个消息，而是形成一个平滑线性下降的坡度，频率越来越高，在3秒钟之内达到原本设置的频率，以后就以固定的频率输出。图中红线圈出来的3次累加起来正好是3秒左右。这种功能适合系统刚启动需要一点时间来“热身”的场景。

高并发系统的限流详解及实现

nginx

对于nginx接入层限流可以使用nginx自带了两个模块：连接数限流模块ngx_http_limit_conn_module和漏桶算法实现的请求限流模块ngx_http_limit_req_module。

1. ngx_http_limit_conn_module

我们经常会遇到这种情况，服务器流量异常，负载过大等等。对于大流量恶意的攻击访问，会带来带宽的浪费，服务器压力，影响业务，往往考虑对同一个ip的连接数，并发数进行限制。ngx_http_limit_conn_module 模块来实现该需求。该模块可以根据定义的键来限制每个键值的连接数，如同一个ip来源的连接数。并不是所有的连接都会被该模块计数，只有那些正在被处理的请求（这些请求的头信息已被完全读入）所在的连接才会被计数。

我们可以在nginx_conf的http{}中加上如下配置实现限制：

									#限制每个用户的并发连接数，取名one

									limit_conn_zone $binary_remote_addr zone=one:10m;

									#配置记录被限流后的日志级别，默认error级别

									limit_conn_log_level error;

									#配置被限流后返回的状态码，默认返回503

									limit_conn_status 503;

然后在server{}里加上如下代码：

1 2	`#限制用户并发连接数为1` `limit_conn one` `1;`

然后我们是使用ab测试来模拟并发请求：
ab -n 5 -c 5 http://10.23.22.239/index.html

得到下面的结果，很明显并发被限制住了，超过阈值的都显示503：

高并发系统的限流详解及实现

另外刚才是配置针对单个ip的并发限制，还是可以针对域名进行并发限制，配置和客户端ip类似。

									#http{}段配置

									limit_conn_zone $ server_name zone=perserver:10m;

									#server{}段配置

									limit_conn perserver 1;

2. ngx_http_limit_req_module

上面我们使用到了ngx_http_limit_conn_module 模块，来限制连接数。那么请求数的限制该怎么做呢？这就需要通过ngx_http_limit_req_module 模块来实现，该模块可以通过定义的键值来限制请求处理的频率。特别的，可以限制来自单个ip地址的请求处理频率。限制的方法是使用了漏斗算法，每秒固定处理请求数，推迟过多请求。如果请求的频率超过了限制域配置的值，请求处理会被延迟或被丢弃，所以所有的请求都是以定义的频率被处理的。

在http{}中配置

#区域名称为one，大小为10m，平均处理的请求频率不能超过每秒一次。