限流器算法
目前常用限流器算法為兩種：令牌桶算法和漏桶算法，主要區別在於：漏桶算法能夠強行限制請求速率，平滑突發請求，而令牌桶算法在限定平均速率的情況下，允許一定量的突發請求
下面是兩張算法圖示，就很容易區分這兩種算法的特性了
漏桶算法
令牌桶算法
針對接口來說，一般會允許處理一定量突發請求，只要求限制平均速率，所以令牌桶算法更加常見。
令牌桶算法工具RateLimiter
目前本人常用的令牌桶算法實現類當屬google guava的RateLimiter，guava不僅實現了令牌桶算法，還有緩存、新的集合類、併發工具類、字符串處理類等等。是一個強大的工具集
RateLimiter api可以查看併發編程網guava RateLimiter的介紹
RateLimiter源碼分析
RateLimiter默認情況下，最核心的屬性有兩個nextFreeTicketMicros，下次可獲取令牌時間，storedPermits桶內令牌數。
判斷是否可獲取令牌:
每次獲取令牌的時候，根據桶內令牌數計算最快下次能獲取令牌的時間nextFreeTicketMicros，判斷是否可以獲取資源時，只要比較nextFreeTicketMicros和當前時間就可以了，so easy
獲取令牌操作：
對於獲取令牌，根據nextFreeTicketMicros和當前時間計算出新增的令牌數，寫入當前令牌桶令牌數，重新計算nextFreeTicketMicros，桶內還有令牌，則寫入當前時間，並減少本次請求獲取的令牌數。
如同java的AQS類一樣，RateLimiter的核心在tryAcquire方法
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;
判斷是否可獲取令牌:
private boolean canAcquire(long nowMicros, long timeoutMicros) {
//最早可獲取資源時間-等待時間<=當前時間 方可獲取資源
return queryEarliestAvailable(nowMicros) - timeoutMicros <= nowMicros;
RateLimiter默認實現類的queryEarliestAvailable是取成員變量nextFreeTicketMicros
獲取令牌並計算需要等待時間操作：
final long reserveAndGetWaitLength(int permits, long nowMicros) {
//獲取下次可獲取時間
long momentAvailable = reserveEarliestAvailable(permits, nowMicros);
//計算當前線程需要休眠時間
return max(momentAvailable - nowMicros, 0);
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限流器
public SimpleRateLimitInterceptor(int rate) {
if (rate > 0)
globalRateLimiter = RateLimiter.create(rate);
else
throw new RuntimeException("rate must greater than zero");
在preHandle調用限流器的tryAcquire方法，判斷是否已經超過限制速率
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中配置限流攔截器
<interceptors>
<interceptor>
<mapping>
<bean>
<constructor-arg>
複雜版本的spring mvc限流攔截器
使用Properties傳入攔截的url表達式->速率rate
<interceptor>
<mapping>
<bean>
<property>
<props>
<prop>1/<prop>
<prop>2/<prop>
為每個url表達式創建一個對應的RateLimiter限流器。url表達式則封裝為org.springframework.web.servlet.mvc.condition.PatternsRequestCondition。PatternsRequestCondition是springmvc 的DispatcherServlet中用來匹配請求和Controller的類，可以判斷請求是否符合這些url表達式。
在攔截器preHandle方法中
//當前請求路徑
String lookupPath = urlPathHelper.getLookupPathForRequest(request);
//迭代所有url表達式對應的PatternsRequestCondition
for (PatternsRequestCondition patternsRequestCondition : urlRateMap.keySet()) {
//進行匹配
List<string> matches = patternsRequestCondition.getMatchingPatterns(lookupPath);/<string>
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;
}
}
}
具體的實現類
為大家更好的理解高併發流量控制策略
為大家準備了視頻講解
視頻內容：
1.什麼是高併發？
2.高併發帶來的問題
3.高併發系統架構圖
4.高併發的優化方案
5.為什麼要限流
6.如何限流
7.限流算法
8.固定窗口
9.滑動窗口
10.漏桶算法
11.令牌桶算法
12.令牌桶算法限流實戰
13.自定義註解和AOP
14.分佈式場景下限流方案實戰
15.高併發的優化方案和技術
16.互聯網架構樹
資料獲取方式
關注+轉發後，私信關鍵詞 【架構】即可獲取！
重要的事情說三遍，轉發、轉發、轉發後再發私信，才可以拿到!
閱讀更多 Java邵先生 的文章
