一、限流的作用
由于api接口無法控制調用方的行為，是以當遇到瞬時請求量激增時，會導緻接口占用過多伺服器資源，使得其他請求響應速度降低或是逾時，更有甚者可能導緻伺服器當機。
限流(rate limiting)指對應用服務的請求進行限制，例如某一接口的請求限制為100個每秒,對超過限制的請求則進行快速失敗或丢棄。
限流可以應對：
熱點業務帶來的突發請求；
調用方bug導緻的突發請求；
惡意攻擊請求。
是以，對于公開的接口最好采取限流措施。
二、為什麼要分布式限流
當應用為單點應用時，隻要應用進行了限流，那麼應用所依賴的各種服務也都得到了保護。
但線上業務出于各種原因考慮，多是分布式系統，單節點的限流僅能保護自身節點，但無法保護應用依賴的各種服務，并且在進行節點擴容、縮容時也無法準确控制整個服務的請求限制。
而如果實作了分布式限流，那麼就可以友善地控制整個服務叢集的請求限制，且由于整個叢集的請求數量得到了限制，是以服務依賴的各種資源也得到了限流的保護。
三、限流的算法
實作限流有很多辦法，在程式中時通常是根據每秒處理的事務數(transaction per second)來衡量接口的流量。
本文介紹幾種最常用的限流算法：
固定視窗計數器；
滑動視窗計數器；
漏桶；
令牌桶。
1、固定視窗計數器算法
固定視窗計數器算法概念如下：
将時間劃分為多個視窗；
在每個視窗内每有一次請求就将計數器加一；
如果計數器超過了限制數量，則本視窗内所有的請求都被丢棄當時間到達下一個視窗時，計數器重置。
固定視窗計數器是最為簡單的算法，但這個算法有時會讓通過請求量允許為限制的兩倍。考慮如下情況：限制1秒内最多通過5個請求，在第一個視窗的最後半秒内通過了5個請求，第二個視窗的前半秒内又通過了5個請求。這樣看來就是在1秒内通過了10個請求。
2、滑動視窗計數器算法
滑動視窗計數器算法概念如下：
将時間劃分為多個區間；
在每個區間内每有一次請求就将計數器加一維持一個時間視窗，占據多個區間；
每經過一個區間的時間，則抛棄最老的一個區間，并納入最新的一個區間；
如果目前視窗内區間的請求計數總和超過了限制數量，則本視窗内所有的請求都被丢棄。
滑動視窗計數器是通過将視窗再細分，并且按照時間"滑動"，這種算法避免了固定視窗計數器帶來的雙倍突發請求，但時間區間的精度越高，算法所需的空間容量就越大。
3、漏桶算法
漏桶算法概念如下：
将每個請求視作"水滴"放入"漏桶"進行存儲；
"漏桶"以固定速率向外"漏"出請求來執行如果"漏桶"空了則停止"漏水"；
如果"漏桶"滿了則多餘的"水滴"會被直接丢棄。
漏桶算法多使用隊列實作，服務的請求會存到隊列中，服務的提供方則按照固定的速率從隊列中取出請求并執行，過多的請求則放在隊列中排隊或直接拒絕。
漏桶算法的缺陷也很明顯，當短時間内有大量的突發請求時，即便此時伺服器沒有任何負載，每個請求也都得在隊列中等待一段時間才能被響應。
4、令牌桶算法
令牌桶算法概念如下：
令牌以固定速率生成；
生成的令牌放入令牌桶中存放，如果令牌桶滿了則多餘的令牌會直接丢棄，當請求到達時，會嘗試從令牌桶中取令牌，取到了令牌的請求可以執行；
如果桶空了，那麼嘗試取令牌的請求會被直接丢棄。
令牌桶算法既能夠将所有的請求平均分布到時間區間内，又能接受伺服器能夠承受範圍内的突發請求，是以是目前使用較為廣泛的一種限流算法。
四、代碼實作
作為如此重要的功能，在java中自然有很多實作限流的類庫，例如google的開源項目guava提供了ratelimiter類，實作了單點的令牌桶限流。
而分布式限流常用的則有hystrix、resilience4j、sentinel等架構，但這些架構都需引入第三方的類庫，對于國企等一些保守的企業，引入外部類庫都需要經過層層審批，較為麻煩。
分布式限流本質上是一個叢集并發問題，而redis作為一個應用廣泛的中間件，又擁有單程序單線程的特性，天然可以解決分布式叢集的并發問題。本文簡單介紹一個通過redis實作單次請求判斷限流的功能。
1、腳本編寫
經過上面的對比，最适合的限流算法就是令牌桶算法。而為實作限流算法，需要反複調用redis查詢與計算，一次限流判斷需要多次請求較為耗時。是以我們采用編寫lua腳本運作的方式，将運算過程放在redis端，使得對redis進行一次請求就能完成限流的判斷。
令牌桶算法需要在redis中存儲桶的大小、目前令牌數量，并且實作每隔一段時間添加新的令牌。最簡單的辦法當然是每隔一段時間請求一次redis，将存儲的令牌數量遞增。
但實際上我們可以通過對限流兩次請求之間的時間和令牌添加速度來計算得出上次請求之後到本次請求時，令牌桶應添加的令牌數量。是以我們在redis中隻需要存儲上次請求的時間和令牌桶中的令牌數量，而桶的大小和令牌的添加速度可以通過參數傳入實作動态修改。
由于第一次運作腳本時預設令牌桶是滿的，是以可以将資料的過期時間設定為令牌桶恢複到滿所需的時間，及時釋放資源。
編寫完成的lua腳本如下：
local ratelimit_info = redis.pcall('hmget',keys[1],'last_time','current_token')
local last_time = ratelimit_info[1]
local current_token = tonumber(ratelimit_info[2])
local max_token = tonumber(argv[1])
local token_rate = tonumber(argv[2])
local current_time = tonumber(argv[3])
local reverse_time = 1000/token_rate
if current_token == nil then
current_token = max_token
last_time = current_time
else
local past_time = current_time-last_time
local reverse_token = math.floor(past_time/reverse_time)
current_token = current_token+reverse_token
last_time = reverse_time*reverse_token+last_time
if current_token>max_token then
current_token = max_token
end
end
local result = 0
if(current_token>0) then
result = 1
current_token = current_token-1
end
redis.call('hmset',keys[1],'last_time',last_time,'current_token',current_token)
redis.call('pexpire',keys[1],math.ceil(reverse_time*(max_token-current_token)+(current_time-last_time)))
return result
2、執行限流
這裡使用spring data redis來進行redis腳本的調用。
編寫redis腳本類:
public class redisretelimitscript implements redisscript<string> {
private static final string script =
"local ratelimit_info = redis.pcall('hmget',keys[1],'last_time','current_token') local last_time = ratelimit_info[1] local current_token = tonumber(ratelimit_info[2]) local max_token = tonumber(argv[1]) local token_rate = tonumber(argv[2]) local current_time = tonumber(argv[3]) local reverse_time = 1000/token_rate if current_token == nil then current_token = max_token last_time = current_time else local past_time = current_time-last_time; local reverse_token = math.floor(past_time/reverse_time) current_token = current_token+reverse_token; last_time = reverse_time*reverse_token+last_time if current_token>max_token then current_token = max_token end end local result = '0' if(current_token>0) then result = '1' current_token = current_token-1 end redis.call('hmset',keys[1],'last_time',last_time,'current_token',current_toke redis.call('pexpire',keys[1],math.ceil(reverse_time*(max_tokencurrent_token)+(current_time-last_time))) return result";
@override public string getsha1() {
return digestutils.sha1hex(script);
}
@override public class<string> getresulttype() { return string.class;
@override public string getscriptasstring() { return script;
}
通過redistemplate對象執行腳本：
public boolean ratelimit(string key, int max, int rate) {
list<string> keylist = new arraylist<>(1);
keylist.add(key);
return "1".equals(stringredistemplate
.execute(new redisretelimitscript(), keylist, integer.tostring(max), integer.tostring(rate),
long.tostring(system.currenttimemillis())));
ratelimit方法傳入的key為限流接口的id，max為令牌桶的最大大小，rate為每秒鐘恢複的令牌數量，傳回的boolean即為此次請求是否通過了限流。為了測試redis腳本限流是否可以正常工作，我們編寫一個單元測試進行測試看看。
@autowired
private redismanager redismanager;
@test
public void ratelimittest() throws interruptedexception {
string key = "test_ratelimit_key";
int max = 10; //令牌桶大小
int rate = 10; //令牌每秒恢複速度
atomicinteger successcount = new atomicinteger(0);
executor executor = executors.newfixedthreadpool(10);
countdownlatch countdownlatch = new countdownlatch(30);
for (int i = 0; i < 30; i++) {
executor.execute(() -> {
boolean isallow = redismanager.ratelimit(key, max, rate);
if (isallow) {
successcount.addandget(1);
}
log.info(boolean.tostring(isallow));
countdownlatch.countdown();
});
}
countdownlatch.await();
log.info("請求成功{}次", successcount.get());
}
設定令牌桶大小為10，令牌桶每秒恢複10個，啟動10個線程在短時間内進行30次請求，并輸出每次限流查詢的結果。日志輸出：
[19:12:50,283]true
[19:12:50,284]true
[19:12:50,291]true
[19:12:50,297]true
[19:12:50,298]true
[19:12:50,305]true
[19:12:50,305]false
[19:12:50,312]false
[19:12:50,319]false
[19:12:50,325]false
[19:12:50,326]false
[19:12:50,380]false
[19:12:50,387]false
[19:12:50,392]false
[19:12:50,393]請求成功11次
可以看到，在0.1秒内請求的30次請求中，除了初始的10個令牌以及随時間恢複的1個令牌外，剩下19個沒有取得令牌的請求均傳回了false，限流腳本正确的将超過限制的請求給判斷出來了，業務中此時就可以直接傳回系統繁忙或接口請求太過頻繁等提示。
3、開發中遇到的問題
1）lua變量格式
lua中的string和number需要通過tonumber()和tostring()進行轉換。
2）redis入參
redis的pexpire等指令不支援小數，但lua的number類型可以存放小數，是以number類型傳遞給 redis時最好通過math.ceil()等方式轉換以避免存在小數導緻指令失敗。
3）time指令
由于redis在叢集下是通過複制腳本及參數到所有節點上，是以無法在具有不确定性的指令後面執行寫入指令，是以隻能請求時傳入時間而無法使用redis的time指令擷取時間。
3.2版本之後的redis腳本支援redis.replicate_commands()，可以改為使用time指令擷取目前時間。
4）潛在的隐患
由于此lua腳本是通過請求時傳入的時間做計算，是以務必保證分布式節點上擷取的時間同步，如果時間不同步會導緻限流無法正常運作。
作者：段然，甜橙金融創新中心開發工程師，目前負責公司平台化建設及媒介能力聚合。
想知道更多？掃描下面的二維碼關注我