引言
在開(kāi)發(fā)高并發(fā)系統(tǒng)時(shí)有三把利器用來(lái)保護(hù)系統(tǒng)：緩存荷憋、降級(jí)和限流蜀涨。今天我們要聊的就是限流（Rate Limit）鹦赎，限流的目的很簡(jiǎn)單，就是為了保護(hù)系統(tǒng)不被瞬時(shí)大流量沖垮猾瘸，
限流這個(gè)概念我其實(shí)很早之前就有去了解過(guò)界赔，不過(guò)無(wú)奈之前工作所接觸業(yè)務(wù)的并發(fā)量實(shí)在是談不上限流。目前公司大促峰值QPS在2w往上牵触，自然而然需要用到限流淮悼，特別是類(lèi)似秒殺這種瞬時(shí)流量非常大但實(shí)際成單率低的業(yè)務(wù)場(chǎng)景。
目前比較常用的限流算法有三種
計(jì)數(shù)器固定窗口算法
計(jì)數(shù)器滑動(dòng)窗口算法
漏桶算法
令牌桶算法
計(jì)數(shù)器固定窗口算法
計(jì)數(shù)器固定窗口算法是最簡(jiǎn)單的限流算法揽思，實(shí)現(xiàn)方式也比較簡(jiǎn)單袜腥。就是通過(guò)維護(hù)一個(gè)單位時(shí)間內(nèi)的計(jì)數(shù)值，每當(dāng)一個(gè)請(qǐng)求通過(guò)時(shí)钉汗，就將計(jì)數(shù)值加1羹令，當(dāng)計(jì)數(shù)值超過(guò)預(yù)先設(shè)定的閾值時(shí)，就拒絕單位時(shí)間內(nèi)的其他請(qǐng)求损痰。如果單位時(shí)間已經(jīng)結(jié)束福侈，則將計(jì)數(shù)器清零，開(kāi)啟下一輪的計(jì)數(shù)卢未。
但是這種實(shí)現(xiàn)會(huì)有一個(gè)問(wèn)題肪凛，舉個(gè)例子:
假設(shè)我們?cè)O(shè)定1秒內(nèi)允許通過(guò)的請(qǐng)求閾值是200，如果有用戶(hù)在時(shí)間窗口的最后幾毫秒發(fā)送了200個(gè)請(qǐng)求辽社，緊接著又在下一個(gè)時(shí)間窗口開(kāi)始時(shí)發(fā)送了200個(gè)請(qǐng)求伟墙，那么這個(gè)用戶(hù)其實(shí)在一秒內(nèi)成功請(qǐng)求了400次，顯然超過(guò)了閾值但并不會(huì)被限流滴铅。其實(shí)這就是臨界值問(wèn)題戳葵，那么臨界值問(wèn)題要怎么解決呢？
- 代碼實(shí)現(xiàn) -- CounterRateLimit.java
計(jì)數(shù)器滑動(dòng)窗口算法
計(jì)數(shù)器滑動(dòng)窗口法就是為了解決上述固定窗口計(jì)數(shù)存在的問(wèn)題而誕生汉匙，學(xué)過(guò)TCP協(xié)議的同學(xué)應(yīng)該對(duì)滑動(dòng)窗口不陌生拱烁，其實(shí)還是不太一樣的生蚁，下文我們要說(shuō)的滑動(dòng)窗口是基于時(shí)間來(lái)劃分窗口的。而TCP的滑動(dòng)窗口指的是能夠接受的字節(jié)數(shù)邻梆，并且大小是可變的（擁塞控制）
滑動(dòng)窗口是怎么做的守伸？
前面說(shuō)了固定窗口存在臨界值問(wèn)題绎秒，要解決這種臨界值問(wèn)題浦妄，顯然只用一個(gè)窗口是解決不了問(wèn)題的。假設(shè)我們?nèi)匀辉O(shè)定1秒內(nèi)允許通過(guò)的請(qǐng)求是200個(gè)见芹，但是在這里我們需要把1秒的時(shí)間分成多格剂娄，假設(shè)分成5格（格數(shù)越多，流量過(guò)渡越平滑）玄呛，每格窗口的時(shí)間大小是200毫秒阅懦，每過(guò)200毫秒，就將窗口向前移動(dòng)一格徘铝。為了便于理解耳胎，可以看下圖
圖中將窗口劃為5份，每個(gè)小窗口中的數(shù)字表示在這個(gè)窗口中請(qǐng)求數(shù)惕它，所以通過(guò)觀察上圖怕午，可知在當(dāng)前時(shí)間快（200毫秒）允許通過(guò)的請(qǐng)求數(shù)應(yīng)該是20而不是200（只要超過(guò)20就會(huì)被限流），因?yàn)槲覀冏罱K統(tǒng)計(jì)請(qǐng)求數(shù)時(shí)是需要把當(dāng)前窗口的值進(jìn)行累加淹魄，進(jìn)而得到當(dāng)前請(qǐng)求數(shù)來(lái)判斷是不是需要進(jìn)行限流郁惜。
那么滑動(dòng)窗口限流法是完美的嗎？
細(xì)心觀察的我們應(yīng)該能馬上發(fā)現(xiàn)問(wèn)題甲锡，滑動(dòng)窗口限流法其實(shí)就是計(jì)數(shù)器固定窗口算法的一個(gè)變種兆蕉。流量的過(guò)渡是否平滑依賴(lài)于我們?cè)O(shè)置的窗口格數(shù)也就是統(tǒng)計(jì)時(shí)間間隔，格數(shù)越多缤沦，統(tǒng)計(jì)越精確虎韵，但是具體要分多少格我們也說(shuō)不上來(lái)呀...
- 代碼實(shí)現(xiàn) -- SlidingWindowRateLimit.java
漏桶算法
上面所介紹的兩種算法都不能非常平滑的過(guò)渡，下面就是漏桶算法登場(chǎng)了
什么是漏桶算法缸废？
漏桶算法以一個(gè)常量限制了出口流量速率劝术，因此漏桶算法可以平滑突發(fā)的流量。其中漏桶作為流量容器我們可以看做一個(gè)FIFO的隊(duì)列呆奕，當(dāng)入口流量速率大于出口流量速率時(shí)养晋，因?yàn)榱髁咳萜魇怯邢薜模?dāng)超出流量容器大小時(shí)梁钾，超出的流量會(huì)被丟棄绳泉。
下圖比較形象的說(shuō)明了漏桶算法的原理，其中水龍頭是入口流量姆泻，漏桶是流量容器零酪，勻速流出的水是出口流量冒嫡。
漏桶算法的特點(diǎn)
漏桶具有固定容量，出口流量速率是固定常量（流出請(qǐng)求）
入口流量可以以任意速率流入到漏桶中（流入請(qǐng)求）
如果入口流量超出了桶的容量四苇，則流入流量會(huì)溢出（新請(qǐng)求被拒絕）
代碼實(shí)現(xiàn) -- LeakyBucketRateLimit.java
不過(guò)因?yàn)槁┩八惴ㄏ拗屏肆鞒鏊俾适且粋€(gè)固定常量值孝凌，所以漏桶算法不支持出現(xiàn)突發(fā)流出流量。但是在實(shí)際情況下月腋，流量往往是突發(fā)的蟀架。
令牌桶算法
令牌桶算法是漏桶算法的改進(jìn)版，可以支持突發(fā)流量榆骚。不過(guò)與漏桶算法不同的是片拍，令牌桶算法的漏桶中存放的是令牌而不是流量。
那么令牌桶算法是怎么突發(fā)流量的呢妓肢？
最開(kāi)始捌省，令牌桶是空的，我們以恒定速率往令牌桶里加入令牌碉钠，令牌桶被裝滿(mǎn)時(shí)纲缓，多余的令牌會(huì)被丟棄。當(dāng)請(qǐng)求到來(lái)時(shí)喊废，會(huì)先嘗試從令牌桶獲取令牌（相當(dāng)于從令牌桶移除一個(gè)令牌）祝高，獲取成功則請(qǐng)求被放行，獲取失敗則阻塞活拒絕請(qǐng)求操禀。
令牌桶算法的特點(diǎn)
最多可以存發(fā)b個(gè)令牌褂策。如果令牌到達(dá)時(shí)令牌桶已經(jīng)滿(mǎn)了，那么這個(gè)令牌會(huì)被丟棄
請(qǐng)求到來(lái)時(shí)颓屑，如果令牌桶中少于n個(gè)令牌斤寂，那么不會(huì)刪除令牌。該請(qǐng)求會(huì)被限流（阻塞活拒絕）
算法允許最大b(令牌桶大小)個(gè)請(qǐng)求的突發(fā)
令牌桶算法限制的是平均流量揪惦，因此其允許突發(fā)流量（只要令牌桶中有令牌遍搞，就不會(huì)被限流）
- 代碼實(shí)現(xiàn) -- TokenBucketRateLimit.java
總結(jié)
至此，基本把以上4種限流算法的原理都解釋清楚了器腋。每種限流算法都有其固定特點(diǎn)溪猿，及各自適用的場(chǎng)景，其中計(jì)數(shù)器算法是其中最簡(jiǎn)單的纫塌，相當(dāng)于滑動(dòng)窗口算法的簡(jiǎn)化版诊县，令牌桶算法相比漏桶算法對(duì)資源的利用率更高（允許突發(fā)流量）
