作者个人研发的在高并发场景下,提供的简单、稳定、可扩展的延迟消息队列框架,具有精准的定时任务和延迟队列处理功能。自开源半年多以来,已成功为十几家中小型企业提供了精准定时调度方案,经受住了生产环境的考验。为使更多童鞋受益,现给出开源框架地址:
https://github.com/sunshinelyz/mykit-delay
PS: 欢迎各位Star源码,也可以pr你牛逼哄哄的代码。
在互联网应用中,高并发系统会面临一个重大的挑战,那就是大量流高并发访问,比如:天猫的双十一、京东618、秒杀、抢购促销等,这些都是典型的大流量高并发场景。关于秒杀,小伙伴们可以参见我的另一篇文章《【高并发】高并发秒杀系统架构解密,不是所有的秒杀都是秒杀!》 关于【冰河技术】微信公众号,解锁更多【高并发】专题文章。 注意:由于原文篇幅比较长,所以被拆分为:理论、算法、实战(HTTP接口实战+分布式限流实战)三大部分。理论篇参见《【高并发】如何实现亿级流量下的分布式限流?这些理论你必须掌握!!》
计数器法
限流算法中最简单粗暴的一种算法,例如,某一个接口1分钟内的请求不超过60次,我们可以在开始时设置一个计数器,每次请求时,这个计数器的值加1,如果这个这个计数器的值大于60并且与第一次请求的时间间隔在1分钟之内,那么说明请求过多;如果该请求与第一次请求的时间间隔大于1分钟,并且该计数器的值还在限流范围内,那么重置该计数器。
使用计数器还可以用来限制一定时间内的总并发数,比如数据库连接池、线程池、秒杀的并发数;计数器限流只要一定时间内的总请求数超过设定的阀值则进行限流,是一种简单粗暴的总数量限流,而不是平均速率限流。
这个方法有一个致命问题:临界问题——当遇到恶意请求,在0:59时,瞬间请求100次,并且在1:00请求100次,那么这个用户在1秒内请求了200次,用户可以在重置节点突发请求,而瞬间超过我们设置的速率限制,用户可能通过算法漏洞击垮我们的应用。
这个问题我们可以使用滑动窗口解决。
滑动窗口
在上图中,整个红色矩形框是一个时间窗口,在我们的例子中,一个时间窗口就是1分钟,然后我们将时间窗口进行划分,如上图我们把滑动窗口划分为6格,所以每一格代表10秒,每超过10秒,我们的时间窗口就会向右滑动一格,每一格都有自己独立的计数器,例如:一个请求在0:35到达, 那么0:30到0:39的计数器会+1,那么滑动窗口是怎么解决临界点的问题呢?如上图,0:59到达的100个请求会在灰色区域格子中,而1:00到达的请求会在红色格子中,窗口会向右滑动一格,那么此时间窗口内的总请求数共200个,超过了限定的100,所以此时能够检测出来触发了限流。回头看看计数器算法,会发现,其实计数器算法就是窗口滑动算法,只不过计数器算法没有对时间窗口进行划分,所以是一格。
由此可见,当滑动窗口的格子划分越多,限流的统计就会越精确。
算法的思路就是水(请求)先进入到漏桶里面,漏桶以恒定的速度流出,当水流的速度过大就会直接溢出,可以看出漏桶算法能强行限制数据的传输速率。如下图所示。
漏桶算法不支持突发流量。
从上图中可以看出,令牌算法有点复杂,桶里存放着令牌token。桶一开始是空的,token以固定的速率r往桶里面填充,直到达到桶的容量,多余的token会被丢弃。每当一个请求过来时,就会尝试着移除一个token,如果没有token,请求无法通过。
令牌桶算法支持突发流量。
Guava框架提供了令牌桶算法的实现,可直接使用这个框架的RateLimiter类创建一个令牌桶限流器,比如:每秒放置的令牌桶的数量为5,那么RateLimiter对象可以保证1秒内不会放入超过5个令牌,并且以固定速率进行放置令牌,达到平滑输出的效果。
平滑流量示例
这里,我写了一个使用Guava框架实现令牌桶算法的示例,如下所示。
package io.binghe.limit.guava;
import com.google.common.util.concurrent.RateLimiter;
/**
* @author binghe
* @version 1.0.0
* @description 令牌桶算法
*/
public class TokenBucketLimiter {
public static void main(String[] args){
//每秒钟生成5个令牌
RateLimiter limiter = RateLimiter.create(5);
//返回值表示从令牌桶中获取一个令牌所花费的时间,单位是秒
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
}
}
代码的实现非常简单,就是使用Guava框架的RateLimiter类生成了一个每秒向桶中放入5个令牌的对象,然后不断从桶中获取令牌。我们先来运行下这段代码,输出的结果信息如下所示。
0.0
0.197294
0.191278
0.19997
0.199305
0.200472
0.200184
0.199417
0.200111
0.199759
从输出结果可以看出:第一次从桶中获取令牌时,返回的时间为0.0,也就是没耗费时间。之后每次从桶中获取令牌时,都会耗费一定的时间,这是为什么呢?按理说,向桶中放入了5个令牌后,再从桶中获取令牌也应该和第一次一样并不会花费时间啊!
因为在Guava的实现是这样的:我们使用RateLimiter.create(5)
创建令牌桶对象时,表示每秒新增5个令牌,1秒等于1000毫秒,也就是每隔200毫秒向桶中放入一个令牌。
当我们运行程序时,程序运行到RateLimiter limiter = RateLimiter.create(5);
时,就会向桶中放入一个令牌,当程序运行到第一个System.out.println(limiter.acquire(1));
时,由于桶中已经存在一个令牌,直接获取这个令牌,并没有花费时间。然而程序继续向下执行时,由于程序会每隔200毫秒向桶中放入一个令牌,所以,获取令牌时,花费的时间几乎都是200毫秒左右。
突发流量示例
我们再来看一个突发流量的示例,代码示例如下所示。
package io.binghe.limit.guava;
import com.google.common.util.concurrent.RateLimiter;
/**
* @author binghe
* @version 1.0.0
* @description 令牌桶算法
*/
public class TokenBucketLimiter {
public static void main(String[] args){
//每秒钟生成5个令牌
RateLimiter limiter = RateLimiter.create(5);
//返回值表示从令牌桶中获取一个令牌所花费的时间,单位是秒
System.out.println(limiter.acquire(50));
System.out.println(limiter.acquire(5));
System.out.println(limiter.acquire(5));
System.out.println(limiter.acquire(5));
System.out.println(limiter.acquire(5));
}
}
上述代码表示的含义为:每秒向桶中放入5个令牌,第一次从桶中获取50个令牌,也就是我们说的突发流量,后续每次从桶中获取5个令牌。接下来,我们运行上述代码看下效果。
0.0
9.998409
0.99109
1.000148
0.999752
运行代码时,会发现当命令行打印出0.0后,会等很久才会打印出后面的输出结果。
程序每秒钟向桶中放入5个令牌,当程序运行到 RateLimiter limiter = RateLimiter.create(5);
时,就会向桶中放入令牌。当运行到 System.out.println(limiter.acquire(50));
时,发现很快就会获取到令牌,花费了0.0秒。接下来,运行到第一个System.out.println(limiter.acquire(5));
时,花费了9.998409秒。小伙们可以思考下,为什么这里会花费10秒中的时间呢?
这是因为我们使用RateLimiter limiter = RateLimiter.create(5);
代码向桶中放入令牌时,一秒钟放入5个,而System.out.println(limiter.acquire(50));
需要获取50个令牌,也就是获取50个令牌需要花费10秒钟时间,这是因为程序向桶中放入50个令牌需要10秒钟。程序第一次从桶中获取令牌时,很快就获取到了。而第二次获取令牌时,花费了将近10秒的时间。
Guava框架支持突发流量,但是在突发流量之后再次请求时,会被限速,也就是说:在突发流量之后,再次请求时,会弥补处理突发请求所花费的时间。所以,我们的突发示例程序中,在一次从桶中获取50个令牌后,再次从桶中获取令牌,则会花费10秒左右的时间。