限流器算法
目前常用限流器算法为两种：令牌桶算法和漏桶算法，主要区别在于：漏桶算法能够强行限制请求速率，平滑突发请求，而令牌桶算法在限定平均速率的情况下，允许一定量的突发请求
下面是从网上找到的两张算法图示，就很容易区分这两种算法的特性了
漏桶算法
令牌桶算法
针对接口来说，一般会允许处理一定量突发请求，只要求限制平均速率，所以令牌桶算法更加常见。
令牌桶算法工具ratelimiter
目前本人常用的令牌桶算法实现类当属google guava的ratelimiter，guava不仅实现了令牌桶算法，还有缓存、新的集合类、并发工具类、字符串处理类等等。是一个强大的工具集
ratelimiter api可以查看并发编程网guava ratelimiter的介绍
ratelimiter源码分析
ratelimiter默认情况下，最核心的属性有两个nextfreeticketmicros，下次可获取令牌时间，storedpermits桶内令牌数。
判断是否可获取令牌:
每次获取令牌的时候，根据桶内令牌数计算最快下次能获取令牌的时间nextfreeticketmicros，判断是否可以获取资源时，只要比较nextfreeticketmicros和当前时间就可以了，so easy
获取令牌操作：
对于获取令牌，根据nextfreeticketmicros和当前时间计算出新增的令牌数，写入当前令牌桶令牌数，重新计算nextfreeticketmicros，桶内还有令牌，则写入当前时间，并减少本次请求获取的令牌数。
如同java的aqs类一样，ratelimiter的核心在tryacquire方法
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
|
public boolean tryacquire(int permits, long timeout, timeunit unit) {
//尝试获取资源最多等待时间
long timeoutmicros = max(unit.tomicros(timeout), 0);
//检查获取资源数目是否正确
checkpermits(permits);
long microstowait;
//加锁
synchronized (mutex()) {
//当前时间
long nowmicros = stopwatch.readmicros();
//判断是否可以在timeout时间内获取资源
if (!canacquire(nowmicros, timeoutmicros)) {
return false;
} else {
//可获取资源，对资源进行重新计算，并返回当前线程需要休眠时间
microstowait = reserveandgetwaitlength(permits, nowmicros);
}
}
//休眠
stopwatch.sleepmicrosuninterruptibly(microstowait);
return true;
}
|
判断是否可获取令牌:
|
1
2
3
4
|
private boolean canacquire(long nowmicros, long timeoutmicros) {
//最早可获取资源时间-等待时间<=当前时间 方可获取资源
return queryearliestavailable(nowmicros) - timeoutmicros <= nowmicros;
}
|
ratelimiter默认实现类的queryearliestavailable是取成员变量nextfreeticketmicros
获取令牌并计算需要等待时间操作：
|
1
2
3
4
5
6
|
final long reserveandgetwaitlength(int permits, long nowmicros) {
//获取下次可获取时间
long momentavailable = reserveearliestavailable(permits, nowmicros);
//计算当前线程需要休眠时间
return max(momentavailable - nowmicros, 0);
}
|
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
|
final long reserveearliestavailable(int requiredpermits, long nowmicros) {
//重新计算桶内令牌数storedpermits
resync(nowmicros);
long returnvalue = nextfreeticketmicros;
//本次消耗的令牌数
double storedpermitstospend = min(requiredpermits, this.storedpermits);
//重新计算下次可获取时间nextfreeticketmicros
double freshpermits = requiredpermits - storedpermitstospend;
long waitmicros =
storedpermitstowaittime(this.storedpermits, storedpermitstospend)
+ (long) (freshpermits * stableintervalmicros);
this.nextfreeticketmicros = longmath.saturatedadd(nextfreeticketmicros, waitmicros);
//减少桶内令牌数
this.storedpermits -= storedpermitstospend;
return returnvalue;
}
|
实现简单的spring mvc限流拦截器
实现一个handlerinterceptor，在构造方法中创建一个ratelimiter限流器
|
1
2
3
4
5
6
|
public simpleratelimitinterceptor(int rate) {
if (rate > 0)
globalratelimiter = ratelimiter.create(rate);
else
throw new runtimeexception("rate must greater than zero");
}
|
在prehandle调用限流器的tryacquire方法，判断是否已经超过限制速率
|
1
2
3
4
5
6
7
|
public boolean prehandle(httpservletrequest request, httpservletresponse response, object handler) throws exception {
if (!globalratelimiter.tryacquire()) {
loggerutil.log(request.getrequesturi()+"请求超过限流器速率");
return false;
}
return true;
}
|
在dispatcher-servlet.xml中配置限流拦截器
|
1
2
3
4
5
6
7
8
9
|
<mvc:interceptors>
<!--限流拦截器-->
<mvc:interceptor>
<mvc:mapping path="/**"/>
<bean class="limit.simpleratelimitinterceptor">
<constructor-arg index="0" value="${totalrate}"/>
</bean>
</mvc:interceptor>
</mvc:interceptors>
|
复杂版本的spring mvc限流拦截器
使用properties传入拦截的url表达式->速率rate
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
<mvc:interceptor>
<mvc:mapping path="/**"/>
<bean class="limit.ratelimitinterceptor">
<!--单url限流-->
<property name="urlproperties">
<props>
<prop key="/get/{id}">1</prop>
<prop key="/post">2</prop>
</props>
</property>
</bean>
</mvc:interceptor>
|
为每个url表达式创建一个对应的ratelimiter限流器。url表达式则封装为org.springframework.web.servlet.mvc.condition.patternsrequestcondition。patternsrequestcondition是springmvc 的dispatcherservlet中用来匹配请求和controller的类，可以判断请求是否符合这些url表达式。
在拦截器prehandle方法中
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//当前请求路径
string lookuppath = urlpathhelper.getlookuppathforrequest(request);
//迭代所有url表达式对应的patternsrequestcondition
for (patternsrequestcondition patternsrequestcondition : urlratemap.keyset()) {
//进行匹配
list<string> matches = patternsrequestcondition.getmatchingpatterns(lookuppath);
if (!matches.isempty()) {
//匹配成功的则获取对应限流器的令牌
if (urlratemap.get(patternsrequestcondition).tryacquire()) {
loggerutil.log(lookuppath + " 请求匹配到" + joiner.on(",").join(patternsrequestcondition.getpatterns()) + "限流器");
} else {
//获取令牌失败
loggerutil.log(lookuppath + " 请求超过" + joiner.on(",").join(patternsrequestcondition.getpatterns()) + "限流器速率");
return false;
}
}
}
|
具体的实现类
请见github
以上就是本文的全部内容，希望对大家的学习有所帮助，也希望大家多多支持服务器之家。
原文链接：http://blog.csdn.net/valleychen1111/article/details/78038366