限流器算法
目前常用限流器算法為兩種：令牌桶算法和漏桶算法，主要區(qū)別在于：漏桶算法能夠強(qiáng)行限制請(qǐng)求速率，平滑突發(fā)請(qǐng)求，而令牌桶算法在限定平均速率的情況下，允許一定量的突發(fā)請(qǐng)求
下面是從網(wǎng)上找到的兩張算法圖示，就很容易區(qū)分這兩種算法的特性了
漏桶算法
令牌桶算法
針對(duì)接口來(lái)說(shuō)，一般會(huì)允許處理一定量突發(fā)請(qǐng)求，只要求限制平均速率，所以令牌桶算法更加常見(jiàn)。
令牌桶算法工具ratelimiter
目前本人常用的令牌桶算法實(shí)現(xiàn)類當(dāng)屬google guava的ratelimiter，guava不僅實(shí)現(xiàn)了令牌桶算法，還有緩存、新的集合類、并發(fā)工具類、字符串處理類等等。是一個(gè)強(qiáng)大的工具集
ratelimiter api可以查看并發(fā)編程網(wǎng)guava ratelimiter的介紹
ratelimiter源碼分析
ratelimiter默認(rèn)情況下，最核心的屬性有兩個(gè)nextfreeticketmicros，下次可獲取令牌時(shí)間，storedpermits桶內(nèi)令牌數(shù)。
判斷是否可獲取令牌:
每次獲取令牌的時(shí)候，根據(jù)桶內(nèi)令牌數(shù)計(jì)算最快下次能獲取令牌的時(shí)間nextfreeticketmicros，判斷是否可以獲取資源時(shí)，只要比較nextfreeticketmicros和當(dāng)前時(shí)間就可以了，so easy
獲取令牌操作：
對(duì)于獲取令牌，根據(jù)nextfreeticketmicros和當(dāng)前時(shí)間計(jì)算出新增的令牌數(shù)，寫入當(dāng)前令牌桶令牌數(shù)，重新計(jì)算nextfreeticketmicros，桶內(nèi)還有令牌，則寫入當(dāng)前時(shí)間，并減少本次請(qǐng)求獲取的令牌數(shù)。
如同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) { //嘗試獲取資源最多等待時(shí)間 long timeoutmicros = max(unit.tomicros(timeout), 0); //檢查獲取資源數(shù)目是否正確 checkpermits(permits); long microstowait; //加鎖 synchronized (mutex()) { //當(dāng)前時(shí)間 long nowmicros = stopwatch.readmicros(); //判斷是否可以在timeout時(shí)間內(nèi)獲取資源 if (!canacquire(nowmicros, timeoutmicros)) { return false; } else { //可獲取資源，對(duì)資源進(jìn)行重新計(jì)算，并返回當(dāng)前線程需要休眠時(shí)間 microstowait = reserveandgetwaitlength(permits, nowmicros); } } //休眠 stopwatch.sleepmicrosuninterruptibly(microstowait); return true;} |
判斷是否可獲取令牌:
|
1
2
3
4
|
private boolean canacquire(long nowmicros, long timeoutmicros) { //最早可獲取資源時(shí)間-等待時(shí)間<=當(dāng)前時(shí)間 方可獲取資源 return queryearliestavailable(nowmicros) - timeoutmicros <= nowmicros;} |
ratelimiter默認(rèn)實(shí)現(xiàn)類的queryearliestavailable是取成員變量nextfreeticketmicros
獲取令牌并計(jì)算需要等待時(shí)間操作：
|
1
2
3
4
5
6
|
final long reserveandgetwaitlength(int permits, long nowmicros) { //獲取下次可獲取時(shí)間 long momentavailable = reserveearliestavailable(permits, nowmicros); //計(jì)算當(dāng)前線程需要休眠時(shí)間 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) { //重新計(jì)算桶內(nèi)令牌數(shù)storedpermits resync(nowmicros); long returnvalue = nextfreeticketmicros; //本次消耗的令牌數(shù) double storedpermitstospend = min(requiredpermits, this.storedpermits); //重新計(jì)算下次可獲取時(shí)間nextfreeticketmicros double freshpermits = requiredpermits - storedpermitstospend; long waitmicros = storedpermitstowaittime(this.storedpermits, storedpermitstospend) + (long) (freshpermits * stableintervalmicros); this.nextfreeticketmicros = longmath.saturatedadd(nextfreeticketmicros, waitmicros); //減少桶內(nèi)令牌數(shù) this.storedpermits -= storedpermitstospend; return returnvalue;} |
實(shí)現(xiàn)簡(jiǎn)單的spring mvc限流攔截器
實(shí)現(xiàn)一個(gè)handlerinterceptor，在構(gòu)造方法中創(chuàng)建一個(gè)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調(diào)用限流器的tryacquire方法，判斷是否已經(jīng)超過(guò)限制速率
|
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()+"請(qǐng)求超過(guò)限流器速率"); 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> |
復(fù)雜版本的spring mvc限流攔截器
使用properties傳入攔截的url表達(dá)式->速率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> |
為每個(gè)url表達(dá)式創(chuàng)建一個(gè)對(duì)應(yīng)的ratelimiter限流器。url表達(dá)式則封裝為org.springframework.web.servlet.mvc.condition.patternsrequestcondition。patternsrequestcondition是springmvc 的dispatcherservlet中用來(lái)匹配請(qǐng)求和controller的類，可以判斷請(qǐng)求是否符合這些url表達(dá)式。
在攔截器prehandle方法中
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
//當(dāng)前請(qǐng)求路徑string lookuppath = urlpathhelper.getlookuppathforrequest(request);//迭代所有url表達(dá)式對(duì)應(yīng)的patternsrequestconditionfor (patternsrequestcondition patternsrequestcondition : urlratemap.keyset()) { //進(jìn)行匹配 list<string> matches = patternsrequestcondition.getmatchingpatterns(lookuppath); if (!matches.isempty()) { //匹配成功的則獲取對(duì)應(yīng)限流器的令牌 if (urlratemap.get(patternsrequestcondition).tryacquire()) { loggerutil.log(lookuppath + " 請(qǐng)求匹配到" + joiner.on(",").join(patternsrequestcondition.getpatterns()) + "限流器"); } else { //獲取令牌失敗 loggerutil.log(lookuppath + " 請(qǐng)求超過(guò)" + joiner.on(",").join(patternsrequestcondition.getpatterns()) + "限流器速率"); return false; } }} |
具體的實(shí)現(xiàn)類
請(qǐng)見(jiàn)github
以上就是本文的全部?jī)?nèi)容，希望對(duì)大家的學(xué)習(xí)有所幫助，也希望大家多多支持服務(wù)器之家。
原文鏈接：http://blog.csdn.net/valleychen1111/article/details/78038366
