限流器算法
目前常用限流器算法為兩種：令牌桶算法和漏桶算法，主要區別在于：漏桶算法能夠強行限制請求速率，平滑突發請求，而令牌桶算法在限定平均速率的情況下，允許一定量的突發請求
下面是從網上找到的兩張算法圖示，就很容易區分這兩種算法的特性了
漏桶算法
令牌桶算法
針對接口來說，一般會允許處理一定量突發請求，只要求限制平均速率，所以令牌桶算法更加常見。
令牌桶算法工具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表達式對應的patternsrequestconditionfor (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
