在开发高并发系统时有三把利器用来保护系统:缓存、降级和限流。缓存的目的是提升系统访问速度和增大系统能处理的容量,可谓是抗高并发流量的银弹;而降级是当服务出问题或者影响到核心流程的性能则需要暂时屏蔽掉,待高峰或者问题解决后再打开;而有些场景并不能用缓存和降级来解决,比如稀缺资源(秒杀、抢购)、写服务(如评论、下单)、频繁的复杂查询(评论的最后几页),因此需有一种手段来限制这些场景的并发/请求量,即限流。
限流的目的是通过对并发访问/请求进行限速或者一个时间窗口内的的请求进行限速来保护系统,一旦达到限制速率则可以拒绝服务(定向到错误页或告知资源没有了)、排队或等待(比如秒杀、评论、下单)、降级(返回兜底数据或默认数据,如商品详情页库存默认有货)。
一般开发高并发系统常见的限流有:限制总并发数(比如数据库连接池、线程池)、限制瞬时并发数(如nginx的limit_conn模块,用来限制瞬时并发连接数)、限制时间窗口内的平均速率(如Guava的RateLimiter、nginx的limit_req模块,限制每秒的平均速率);其他还有如限制远程接口调用速率、限制MQ的消费速率。另外还可以根据网络连接数、网络流量、CPU或内存负载等来限流。
先有缓存这个银弹,后有限流来应对618、双十一高并发流量,在处理高并发问题上可以说是如虎添翼,不用担心瞬间流量导致系统挂掉或雪崩,最终做到有损服务而不是不服务;限流需要评估好,不可乱用,否则会正常流量出现一些奇怪的问题而导致用户抱怨。
在实际应用时也不要太纠结算法问题,因为一些限流算法实现是一样的只是描述不一样;具体使用哪种限流技术还是要根据实际场景来选择,不要一味去找最佳模式,白猫黑猫能解决问题的就是好猫。
因在实际工作中遇到过许多人来问如何进行限流,因此本文会详细介绍各种限流手段。那么接下来我们从限流算法、应用级限流、分布式限流、接入层限流来详细学习下限流技术手段。
一、限流算法
常见的限流算法有:令牌桶、漏桶。计数器也可以进行粗暴限流实现。
令牌桶算法
令牌桶算法是一个存放固定容量令牌的桶,按照固定速率往桶里添加令牌。令牌桶算法的描述如下:
- 假设限制2r/s,则按照500毫秒的固定速率往桶中添加令牌;
- 桶中最多存放b个令牌,当桶满时,新添加的令牌被丢弃或拒绝;
- 当一个n个字节大小的数据包到达,将从桶中删除n个令牌,接着数据包被发送到网络上;
- 如果桶中的令牌不足n个,则不会删除令牌,且该数据包将被限流(要么丢弃,要么缓冲区等待)。
漏桶算法
漏桶作为计量工具(The Leaky Bucket Algorithm as a Meter)时,可以用于流量整形(Traffic Shaping)和流量控制(TrafficPolicing),漏桶算法的描述如下:
- 一个固定容量的漏桶,按照常量固定速率流出水滴;
- 如果桶是空的,则不需流出水滴;
- 可以以任意速率流入水滴到漏桶;
- 如果流入水滴超出了桶的容量,则流入的水滴溢出了(被丢弃),而漏桶容量是不变的。
令牌桶和漏桶对比:
- 令牌桶是按照固定速率往桶中添加令牌,请求是否被处理需要看桶中令牌是否足够,当令牌数减为零时则拒绝新的请求;
- 漏桶则是按照常量固定速率流出请求,流入请求速率任意,当流入的请求数累积到漏桶容量时,则新流入的请求被拒绝;
- 令牌桶限制的是平均流入速率(允许突发请求,只要有令牌就可以处理,支持一次拿3个令牌,4个令牌),并允许一定程度突发流量;
- 漏桶限制的是常量流出速率(即流出速率是一个固定常量值,比如都是1的速率流出,而不能一次是1,下次又是2),从而平滑突发流入速率;
- 令牌桶允许一定程度的突发,而漏桶主要目的是平滑流入速率;
- 两个算法实现可以一样,但是方向是相反的,对于相同的参数得到的限流效果是一样的。
另外有时候我们还使用计数器来进行限流,主要用来限制总并发数,比如数据库连接池、线程池、秒杀的并发数;只要全局总请求数或者一定时间段的总请求数设定的阀值则进行限流,是简单粗暴的总数量限流,而不是平均速率限流。
到此基本的算法就介绍完了,接下来我们首先看看应用级限流。
二、应用级限流
限流总并发/连接/请求数
对于一个应用系统来说一定会有极限并发/请求数,即总有一个TPS/QPS阀值,如果超了阀值则系统就会不响应用户请求或响应的非常慢,因此我们最好进行过载保护,防止大量请求涌入击垮系统。
如果你使用过Tomcat,其Connector 其中一种配置有如下几个参数:
- acceptCount:如果Tomcat的线程都忙于响应,新来的连接会进入队列排队,如果超出排队大小,则拒绝连接;
- maxConnections: 瞬时最大连接数,超出的会排队等待;
- maxThreads:Tomcat能启动用来处理请求的最大线程数,如果请求处理量一直远远大于最大线程数则可能会僵死。
详细的配置请参考官方文档。另外如Mysql(如max_connections)、Redis(如tcp-backlog)都会有类似的限制连接数的配置。
限流总资源数
如果有的资源是稀缺资源(如数据库连接、线程),而且可能有多个系统都会去使用它,那么需要限制应用;可以使用池化技术来限制总资源数:连接池、线程池。比如分配给每个应用的数据库连接是100,那么本应用最多可以使用100个资源,超出了可以等待或者抛异常。
限流某个接口的总并发/请求数
如果接口可能会有突发访问情况,但又担心访问量太大造成崩溃,如抢购业务;这个时候就需要限制这个接口的总并发/请求数总请求数了;因为粒度比较细,可以为每个接口都设置相应的阀值。可以使用Java中的AtomicLong进行限流:
适合对业务无损的服务或者需要过载保护的服务进行限流,如抢购业务,超出了大小要么让用户排队,要么告诉用户没货了,对用户来说是可以接受的。而一些开放平台也会限制用户调用某个接口的试用请求量,也可以用这种计数器方式实现。这种方式也是简单粗暴的限流,没有平滑处理,需要根据实际情况选择使用;
限流某个接口的时间窗请求数
即一个时间窗口内的请求数,如想限制某个接口/服务每秒/每分钟/每天的请求数/调用量。如一些基础服务会被很多其他系统调用,比如商品详情页服务会调用基础商品服务调用,但是怕因为更新量比较大将基础服务打挂,这时我们要对每秒/每分钟的调用量进行限速;一种实现方式如下所示:
我们使用Guava的Cache来存储计数器,过期时间设置为2秒(保证1秒内的计数器是有的),然后我们获取当前时间戳然后取秒数来作为KEY进行计数统计和限流,这种方式也是简单粗暴,刚才说的场景够用了。
平滑限流某个接口的请求数
之前的限流方式都不能很好地应对突发请求,即瞬间请求可能都被允许从而导致一些问题;因此在一些场景中需要对突发请求进行整形,整形为平均速率请求处理(比如5r/s,则每隔200毫秒处理一个请求,平滑了速率)。这个时候有两种算法满足我们的场景:令牌桶和漏桶算法。Guava框架提供了令牌桶算法实现,可直接拿来使用。
Guava RateLimiter提供了令牌桶算法实现:平滑突发限流(SmoothBursty)和平滑预热限流(SmoothWarmingUp)实现。
SmoothBursty
- RateLimiter.create(5) 表示桶容量为5且每秒新增5个令牌,即每隔200毫秒新增一个令牌;
- limiter.acquire表示消费一个令牌,如果当前桶中有足够令牌则成功(返回值为0),如果桶中没有令牌则暂停一段时间,比如发令牌间隔是200毫秒,则等待200毫秒后再去消费令牌(如上测试用例返回的为0.198239,差不多等待了200毫秒桶中才有令牌可用),这种实现将突发请求速率平均为了固定请求速率。
再看一个突发示例:
limiter.acquire(5)表示桶的容量为5且每秒新增5个令牌,令牌桶算法允许一定程度的突发,所以可以一次性消费5个令牌,但接下来的limiter.acquire(1)将等待差不多1秒桶中才能有令牌,且接下来的请求也整形为固定速率了。
同上边的例子类似,第一秒突发了10个请求,令牌桶算法也允许了这种突发(允许消费未来的令牌),但接下来的limiter.acquire(1)将等待差不多2秒桶中才能有令牌,且接下来的请求也整形为固定速率了。
接下来再看一个突发的例子:
- 创建了一个桶容量为2且每秒新增2个令牌;
- 首先调用limiter.acquire消费一个令牌,此时令牌桶可以满足(返回值为0);
- 然后线程暂停2秒,接下来的两个limiter.acquire都能消费到令牌,第三个limiter.acquire也同样消费到了令牌,到第四个时就需要等待500毫秒了。
此处可以看到我们设置的桶容量为2(即允许的突发量),这是因为SmoothBursty中有一个参数:最大突发秒数(maxBurstSeconds)默认值是1s,突发量/桶容量=速率*maxBurstSeconds,所以本示例桶容量/突发量为2,例子中前两个是消费了之前积攒的突发量,而第三个开始就是正常计算的了。令牌桶算法允许将一段时间内没有消费的令牌暂存到令牌桶中,留待未来使用,并允许未来请求的这种突发。
SmoothBursty通过平均速率和最后一次新增令牌的时间计算出下次新增令牌的时间的,另外需要一个桶暂存一段时间内没有使用的令牌(即可以突发的令牌数)。另外RateLimiter还提供了tryAcquire方法来进行无阻塞或可超时的令牌消费。
因为SmoothBursty允许一定程度的突发,会有人担心如果允许这种突发,假设突然间来了很大的流量,那么系统很可能扛不住这种突发。因此需要一种平滑速率的限流工具,从而系统冷启动后慢慢的趋于平均固定速率(即刚开始速率小一些,然后慢慢趋于我们设置的固定速率)。Guava也提供了SmoothWarmingUp来实现这种需求,其可以认为是漏桶算法,但是在某些特殊场景又不太一样。
SmoothWarmingUp创建方式:
permitsPerSecond表示每秒新增的令牌数,warmupPeriod表示在从冷启动速率过渡到平均速率的时间间隔。
示例如下:
速率是梯形上升速率的,也就是说冷启动时会以一个比较大的速率慢慢到平均速率;然后趋于平均速率(梯形下降到平均速率)。可以通过调节warmupPeriod参数实现一开始就是平滑固定速率。
到此应用级限流的一些方法就介绍完了。假设将应用部署到多台机器,应用级限流方式只是单应用内的请求限流,不能进行全局限流。因此我们需要分布式限流和接入层限流来解决这个问题。
三、分布式限流
分布式限流最关键的是要将限流服务做成原子化,而解决方案可以使用redis+lua或者nginx+lua技术进行实现,通过这两种技术可以实现的高并发和高性能。
首先我们来使用redis+lua实现时间窗内某个接口的请求数限流,实现了该功能后可以改造为限流总并发/请求数和限制总资源数。Lua本身就是一种编程语言,也可以使用它实现复杂的令牌桶或漏桶算法。
redis+lua实现中的lua脚本:
如上操作因是在一个lua脚本中,又因Redis是单线程模型,因此是线程安全的。如上方式有一个缺点就是当达到限流大小后还是会递增的,可以改造成如下方式实现:
如下是Java中判断是否需要限流的代码:
因为Redis的限制(Lua中有写操作不能使用带随机性质的读操作,如TIME)不能在Redis Lua中使用TIME获取时间戳,因此只好从应用获取然后传入,在某些极端情况下(机器时钟不准的情况下),限流会存在一些小问题。
使用Nginx+Lua实现的Lua脚本:
实现中我们需要使用lua-resty-lock互斥锁模块来解决原子性问题(在实际工程中使用时请考虑获取锁的超时问题),并使用ngx.shared.DICT共享字典来实现计数器。如果需要限流则返回0,否则返回1。使用时需要先定义两个共享字典(分别用来存放锁和计数器数据):
有人会纠结如果应用并发量非常大那么redis或者nginx是不是能抗得住;不过这个问题要从多方面考虑:你的流量是不是真的有这么大,是不是可以通过一致性哈希将分布式限流进行分片,是不是可以当并发量太大降级为应用级限流;对策非常多,可以根据实际情况调节;像在京东使用Redis+Lua来限流抢购流量,一般流量是没有问题的。
对于分布式限流目前遇到的场景是业务上的限流,而不是流量入口的限流;流量入口限流应该在接入层完成,而接入层笔者一般使用Nginx。
四、接入层限流
接入层通常指请求流量的入口,该层的主要目的有:负载均衡、非法请求过滤、请求聚合、缓存、降级、限流、A/B测试、服务质量监控等等,可以参考笔者写的《使用Nginx+Lua(OpenResty)开发高性能Web应用》。
对于Nginx接入层限流可以使用Nginx自带了两个模块:连接数限流模块
ngx_http_limit_conn_module和漏桶算法实现的请求限流模块ngx_http_limit_req_module。还可以使用OpenResty提供的Lua限流模块lua-resty-limit-traffic进行更复杂的限流场景。
limit_conn用来对某个KEY对应的总的网络连接数进行限流,可以按照如IP、域名维度进行限流。limit_req用来对某个KEY对应的请求的平均速率进行限流,并有两种用法:平滑模式(delay)和允许突发模式(nodelay)。
ngx_http_limit_conn_module
limit_conn是对某个KEY对应的总的网络连接数进行限流。可以按照IP来限制IP维度的总连接数,或者按照服务域名来限制某个域名的总连接数。但是记住不是每一个请求连接都会被计数器统计,只有那些被Nginx处理的且已经读取了整个请求头的请求连接才会被计数器统计。
配置示例:
- limit_conn:要配置存放KEY和计数器的共享内存区域和指定KEY的最大连接数;此处指定的最大连接数是1,表示Nginx最多同时并发处理1个连接;
- limit_conn_zone:用来配置限流KEY、及存放KEY对应信息的共享内存区域大小;此处的KEY是“$binary_remote_addr”其表示IP地址,也可以使用如$server_name作为KEY来限制域名级别的最大连接数;
- limit_conn_status:配置被限流后返回的状态码,默认返回503;
- limit_conn_log_level:配置记录被限流后的日志级别,默认error级别。
limit_conn的主要执行过程如下所示:
1、请求进入后首先判断当前limit_conn_zone中相应KEY的连接数是否超出了配置的最大连接数;
2.1、如果超过了配置的最大大小,则被限流,返回limit_conn_status定义的错误状态码;
2.2、否则相应KEY的连接数加1,并注册请求处理完成的回调函数;
3、进行请求处理;
4、在结束请求阶段会调用注册的回调函数对相应KEY的连接数减1。
limt_conn可以限流某个KEY的总并发/请求数,KEY可以根据需要变化。
按照IP限制并发连接数配置示例:
首先定义IP维度的限流区域:
接着在要限流的location中添加限流逻辑:
即允许每个IP最大并发连接数为2。
使用AB测试工具进行测试,并发数为5个,总的请求数为5个:
将得到如下access.log输出:
此处我们把access log格式设置为log_format main '[$time_local] [$msec] $status';分别是“日期 日期秒/毫秒值 响应状态码”。
如果被限流了,则在error.log中会看到类似如下的内容:
按照域名限制并发连接数配置示例:
首先定义域名维度的限流区域:
接着在要限流的location中添加限流逻辑:
即允许每个域名最大并发请求连接数为2;这样配置可以实现服务器最大连接数限制。
ngx_http_limit_req_module
limit_req是令牌桶算法实现,用于对指定KEY对应的请求进行限流,比如按照IP维度限制请求速率。
配置示例:
- limit_req:配置限流区域、桶容量(突发容量,默认0)、是否延迟模式(默认延迟);
- limit_req_zone:配置限流KEY、及存放KEY对应信息的共享内存区域大小、固定请求速率;此处指定的KEY是“$binary_remote_addr”表示IP地址;固定请求速率使用rate参数配置,支持10r/s和60r/m,即每秒10个请求和每分钟60个请求,不过最终都会转换为每秒的固定请求速率(10r/s为每100毫秒处理一个请求;60r/m,即每1000毫秒处理一个请求)。
- limit_conn_status:配置被限流后返回的状态码,默认返回503;
- limit_conn_log_level:配置记录被限流后的日志级别,默认error级别。
limit_req的主要执行过程如下所示:
1、请求进入后首先判断最后一次请求时间相对于当前时间(第一次是0)是否需要限流,如果需要限流则执行步骤2,否则执行步骤3;
2.1、如果没有配置桶容量(burst),则桶容量为0;按照固定速率处理请求;如果请求被限流,则直接返回相应的错误码(默认503);
2.2、如果配置了桶容量(burst>0)且延迟模式(没有配置nodelay);如果桶满了,则新进入的请求被限流;如果没有满则请求会以固定平均速率被处理(按照固定速率并根据需要延迟处理请求,延迟使用休眠实现);
2.3、如果配置了桶容量(burst>0)且非延迟模式(配置了nodelay);不会按照固定速率处理请求,而是允许突发处理请求;如果桶满了,则请求被限流,直接返回相应的错误码;
3、如果没有被限流,则正常处理请求;
4、Nginx会在相应时机进行选择一些(3个节点)限流KEY进行过期处理,进行内存回收。
场景2.1测试
首先定义IP维度的限流区域:
限制为每秒500个请求,固定平均速率为2毫秒一个请求。
接着在要限流的location中添加限流逻辑:
即桶容量为0(burst默认为0),且延迟模式。
使用AB测试工具进行测试,并发数为2个,总的请求数为10个:
将得到如下access.log输出:
虽然每秒允许500个请求,但是因为桶容量为0,所以流入的请求要么被处理要么被限流,无法延迟处理;另外平均速率在2毫秒左右,比如1465381556.410和1465381556.411被处理了;有朋友会说这固定平均速率不是1毫秒嘛,其实这是因为实现算法没那么精准造成的。
如果被限流在error.log中会看到如下内容:
如果被延迟了在error.log(日志级别要INFO级别)中会看到如下内容:
场景2.2测试
首先定义IP维度的限流区域:
为了方便测试设置速率为每秒2个请求,即固定平均速率是500毫秒一个请求。
接着在要限流的location中添加限流逻辑:
固定平均速率为500毫秒一个请求,通容量为3,如果桶满了新的请求被限流,否则可以进入桶中排队并等待(实现延迟模式)。
为了看出限流效果我们写了一个req.sh脚本:
首先进行6个并发请求6次URL,然后休眠300毫秒,然后再进行6个并发请求6次URL;中间休眠目的是为了能跨越2秒看到效果,如果看不到如下的效果可以调节休眠时间。
将得到如下access.log输出:
桶容量为3,即桶中在时间窗口内最多流入3个请求,且按照2r/s的固定速率处理请求(即每隔500毫秒处理一个请求);桶计算时间窗口(1.5秒)=速率(2r/s)/桶容量(3),也就是说在这个时间窗口内桶最多暂存3个请求。因此我们要以当前时间往前推1.5秒和1秒来计算时间窗口内的总请求数;另外因为默认是延迟模式,所以时间窗内的请求要被暂存到桶中,并以固定平均速率处理请求:
- 第一轮:有4个请求处理成功了,按照漏桶桶容量应该最多3个才对;这是因为计算算法的问题,第一次计算因没有参考值,所以第一次计算后,后续的计算才能有参考值,因此第一次成功可以忽略;这个问题影响很小可以忽略;而且按照固定500毫秒的速率处理请求。
- 第二轮:因为第一轮请求是突发来的,差不多都在1465433203.959时间点,只是因为漏桶将速率进行了平滑变成了固定平均速率(每500毫秒一个请求);而第二轮计算时间应基于1465433203.959;而第二轮突发请求差不多都在1465433205.766时间点,因此计算桶容量的时间窗口应基于1465433203.959和1465433205.766来计算,计算结果为1465433205.766这个时间点漏桶为空了,可以流入桶中3个请求,其他请求被拒绝;又因为第一轮最后一次处理时间是1465433205.453,所以第二轮第一个请求被延迟到了1465433205.950。这里也要注意固定平均速率只是在配置的速率左右,存在计算精度问题,会有一些偏差。
如果桶容量改为1(burst=1),执行req.sh脚本可以看到如下输出:
桶容量为1,按照每1000毫秒一个请求的固定平均速率处理请求。
场景2.3测试
首先定义IP维度的限流区域:
为了方便测试配置为每秒2个请求,固定平均速率是500毫秒一个请求。
接着在要限流的location中添加限流逻辑:
桶容量为3,如果桶满了直接拒绝新请求,且每秒2最多两个请求,桶按照固定500毫秒的速率以nodelay模式处理请求。
为了看到限流效果我们写了一个req.sh脚本:
将得到类似如下access.log输出:
桶容量为3(,即桶中在时间窗口内最多流入3个请求,且按照2r/s的固定速率处理请求(即每隔500毫秒处理一个请求);桶计算时间窗口(1.5秒)=速率(2r/s)/桶容量(3),也就是说在这个时间窗口内桶最多暂存3个请求。因此我们要以当前时间往前推1.5秒和1秒来计算时间窗口内的总请求数;另外因为配置了nodelay,是非延迟模式,所以允许时间窗内突发请求的;另外从本示例会看出两个问题:
- 第一轮和第七轮:有4个请求处理成功了;这是因为计算算法的问题,本示例是如果2秒内没有请求,然后接着突然来了很多请求,第一次计算的结果将是不正确的;这个问题影响很小可以忽略;
- 第五轮:1.0秒计算出来是3个请求;此处也是因计算精度的问题,也就是说limit_req实现的算法不是非常精准的,假设此处看成相对于2.75的话,1.0秒内只有1次请求,所以还是允许1次请求的。
如果限流出错了,可以配置错误页面:
limit_conn_zone/limit_req_zone定义的内存不足,则后续的请求将一直被限流,所以需要根据需求设置好相应的内存大小。
此处的限流都是单Nginx的,假设我们接入层有多个nginx,此处就存在和应用级限流相同的问题;那如何处理呢?一种解决办法:建立一个负载均衡层将按照限流KEY进行一致性哈希算法将请求哈希到接入层Nginx上,从而相同KEY的将打到同一台接入层Nginx上;另一种解决方案就是使用Nginx+Lua(OpenResty)调用分布式限流逻辑实现。
lua-resty-limit-traffic
之前介绍的两个模块使用上比较简单,指定KEY、指定限流速率等就可以了,如果我们想根据实际情况变化KEY、变化速率、变化桶大小等这种动态特性,使用标准模块就很难去实现了,因此我们需要一种可编程来解决我们问题;而OpenResty提供了lua限流模块lua-resty-limit-traffic,通过它可以按照更复杂的业务逻辑进行动态限流处理了。其提供了limit.conn和limit.req实现,算法与nginx limit_conn和limit_req是一样的。
此处我们来实现ngx_http_limit_req_module中的【场景2.2测试】,不要忘记下载lua-resty-limit-traffic模块并添加到OpenResty的lualib中。
配置用来存放限流用的共享字典:
以下是实现【场景2.2测试】的限流代码limit_req.lua:
即限流逻辑再nginx access阶段被访问,如果不被限流继续后续流程;如果需要被限流要么sleep一段时间继续后续流程,要么返回相应的状态码拒绝请求。
在分布式限流中我们使用了简单的Nginx+Lua进行分布式限流,有了这个模块也可以使用这个模块来实现分布式限流。
另外在使用Nginx+Lua时也可以获取
ngx.var.connections_active进行过载保护,即如果当前活跃连接数超过阈值进行限流保护。
nginx也提供了limit_rate用来对流量限速,如limit_rate 50k,表示限制下载速度为50k。
到此笔者在工作中涉及的限流用法就介绍完,这些算法中有些允许突发,有些会整形为平滑,有些计算算法简单粗暴;其中令牌桶算法和漏桶算法实现上是类似的,只是表述的方向不太一样,对于业务来说不必刻意去区分它们;因此需要根据实际场景来决定如何限流,最好的算法不一定是最适用的。
参考资料
- https://en.wikipedia.org/wiki/Token_bucket
- https://en.wikipedia.org/wiki/Leaky_bucket
- http://redis.io/commands/incr
- http://nginx.org/en/docs/http/ngx_http_limit_req_module.html
- http://nginx.org/en/docs/http/ngx_http_limit_conn_module.html
- https://github.com/openresty/lua-resty-limit-traffic
- http://nginx.org/en/docs/http/ngx_http_core_module.html#limit_rate
作者介绍 张开涛
- 2014年加入京东,目前在保险业务部做研发工作。
- 工作之余喜欢写技术博客,有《跟我学 Spring》、《跟我学Spring MVC》、《跟我学Nginx+Lua开发》等系列教程,目前博客访问量有800万+。
经平台及作者同意授权转载