聊聊高并發(fā)系統(tǒng)限流特技-1來自開濤的博客
在開發(fā)高并發(fā)系統(tǒng)時有三把利器用來保護系統(tǒng)：緩存哼丈、降級和限流梧田。緩存的目的是提升系統(tǒng)訪問速度和增大系統(tǒng)能處理的容量江解，可謂是抗高并發(fā)流量的銀彈义屏；而降級是當(dāng)服務(wù)出問題或者影響到核心流程的性能則需要暫時屏蔽掉士修，待高峰或者問題解決后再打開凛忿；而有些場景并不能用緩存和降級來解決澈灼，比如稀缺資源（秒殺、搶購）店溢、寫服務(wù)（如評論叁熔、下單）、頻繁的復(fù)雜查詢（評論的最后幾頁）床牧，因此需有一種手段來限制這些場景的并發(fā)/請求量荣回，即限流。
限流的目的是通過對并發(fā)訪問/請求進行限速或者一個時間窗口內(nèi)的的請求進行限速來保護系統(tǒng)戈咳，一旦達到限制速率則可以拒絕服務(wù)（定向到錯誤頁或告知資源沒有了）心软、排隊或等待（比如秒殺、評論著蛙、下單）删铃、降級（返回托底數(shù)據(jù)或默認(rèn)數(shù)據(jù)，如商品詳情頁庫存默認(rèn)有貨）踏堡。
一般開發(fā)高并發(fā)系統(tǒng)常見的限流有：限制總并發(fā)數(shù)（比如數(shù)據(jù)庫連接池猎唁、線程池）、限制瞬時并發(fā)數(shù)（如nginx的limit_conn模塊顷蟆，用來限制瞬時并發(fā)連接數(shù)）诫隅、限制時間窗口內(nèi)的平均速率（如Guava的RateLimiter、nginx的limit_req模塊帐偎，限制每秒的平均速率）逐纬；其他還有如限制遠程接口調(diào)用速率、限制MQ的消費速率削樊。另外還可以根據(jù)網(wǎng)絡(luò)連接數(shù)豁生、網(wǎng)絡(luò)流量、CPU或內(nèi)存負(fù)載等來限流。
先有緩存這個銀彈沛硅，后有限流來應(yīng)對618眼刃、雙十一高并發(fā)流量，在處理高并發(fā)問題上可以說是如虎添翼摇肌，不用擔(dān)心瞬間流量導(dǎo)致系統(tǒng)掛掉或雪崩擂红，最終做到有損服務(wù)而不是不服務(wù)；限流需要評估好围小，不可亂用昵骤，否則會正常流量出現(xiàn)一些奇怪的問題而導(dǎo)致用戶抱怨。
因在實際工作中遇到過許多人來問如何進行限流肯适，因此本文會詳細介紹各種限流手段变秦。那么接下來我們從限流算法、應(yīng)用級限流框舔、分布式限流蹦玫、接入層限流來詳細學(xué)習(xí)下限流技術(shù)手段。
限流算法
常見的限流算法有：令牌桶刘绣、漏桶樱溉。計數(shù)器也可以進行粗暴限流實現(xiàn)。
令牌桶算法
令牌桶算法是一個存放固定容量令牌的桶纬凤，按照固定速率往桶里添加令牌福贞。令牌桶算法的描述如下：
假設(shè)限制2r/s，則按照500毫秒的固定速率往桶中添加令牌停士；
桶中最多存放b個令牌挖帘，當(dāng)桶滿時，新添加的令牌被丟棄或拒絕恋技；
當(dāng)一個n個字節(jié)大小的數(shù)據(jù)包到達拇舀，將從桶中刪除n個令牌，接著數(shù)據(jù)包被發(fā)送到網(wǎng)絡(luò)上蜻底；
如果桶中的令牌不足n個骄崩，則不會刪除令牌，且該數(shù)據(jù)包將被限流（要么丟棄朱躺，要么緩沖區(qū)等待）刁赖。
漏桶算法
漏桶作為計量工具（The Leaky Bucket Algorithm as a Meter）時搁痛，可以用于流量整形（Traffic Shaping）和流量控制（TrafficPolicing）长搀，漏桶算法的描述如下：
一個固定容量的漏桶，按照常量固定速率流出水滴鸡典；
如果桶是空的源请，則不需流出水滴；
可以以任意速率流入水滴到漏桶；
如果流入水滴超出了桶的容量谁尸，則流入的水滴溢出了（被丟棄）舅踪，而漏桶容量是不變的。
令牌桶和漏桶對比：
令牌桶是按照固定速率往桶中添加令牌良蛮，請求是否被處理需要看桶中令牌是否足夠抽碌，當(dāng)令牌數(shù)減為零時則拒絕新的請求；
漏桶則是按照常量固定速率流出請求决瞳，流入請求速率任意货徙，當(dāng)流入的請求數(shù)累積到漏桶容量時，則新流入的請求被拒絕皮胡；
令牌桶限制的是平均流入速率（允許突發(fā)請求痴颊，只要有令牌就可以處理，支持一次拿3個令牌屡贺，4個令牌）蠢棱，并允許一定程度突發(fā)流量；
漏桶限制的是常量流出速率（即流出速率是一個固定常量值甩栈，比如都是1的速率流出泻仙，而不能一次是1，下次又是2）谤职，從而平滑突發(fā)流入速率饰豺；
令牌桶允許一定程度的突發(fā)，而漏桶主要目的是平滑流入速率允蜈；
兩個算法實現(xiàn)可以一樣冤吨，但是方向是相反的，對于相同的參數(shù)得到的限流效果是一樣的饶套。
另外有時候我們還使用計數(shù)器來進行限流漩蟆，主要用來限制總并發(fā)數(shù)，比如數(shù)據(jù)庫連接池妓蛮、線程池怠李、秒殺的并發(fā)數(shù)；只要全局總請求數(shù)或者一定時間段的總請求數(shù)設(shè)定的閥值則進行限流蛤克，是簡單粗暴的總數(shù)量限流捺癞，而不是平均速率限流。
到此基本的算法就介紹完了构挤，接下來我們首先看看應(yīng)用級限流髓介。
應(yīng)用級限流
限流總并發(fā)/連接/請求數(shù)
對于一個應(yīng)用系統(tǒng)來說一定會有極限并發(fā)/請求數(shù)，即總有一個TPS/QPS閥值筋现，如果超了閥值則系統(tǒng)就會不響應(yīng)用戶請求或響應(yīng)的非常慢唐础，因此我們最好進行過載保護箱歧，防止大量請求涌入擊垮系統(tǒng)。
如果你使用過Tomcat一膨，其Connector其中一種配置有如下幾個參數(shù)：
acceptCount：如果Tomcat的線程都忙于響應(yīng)呀邢，新來的連接會進入隊列排隊，如果超出排隊大小豹绪，則拒絕連接价淌；
maxConnections：瞬時最大連接數(shù)，超出的會排隊等待瞒津；
maxThreads：Tomcat能啟動用來處理請求的最大線程數(shù)输钩，如果請求處理量一直遠遠大于最大線程數(shù)則可能會僵死。
詳細的配置請參考官方文檔仲智。另外如Mysql（如max_connections）买乃、Redis（如tcp-backlog）都會有類似的限制連接數(shù)的配置。
限流總資源數(shù)
如果有的資源是稀缺資源（如數(shù)據(jù)庫連接钓辆、線程）剪验，而且可能有多個系統(tǒng)都會去使用它，那么需要限制應(yīng)用前联；可以使用池化技術(shù)來限制總資源數(shù)：連接池功戚、線程池。比如分配給每個應(yīng)用的數(shù)據(jù)庫連接是100似嗤，那么本應(yīng)用最多可以使用100個資源啸臀，超出了可以等待或者拋異常。
限流某個接口的總并發(fā)/請求數(shù)
如果接口可能會有突發(fā)訪問情況烁落，但又擔(dān)心訪問量太大造成崩潰乘粒，如搶購業(yè)務(wù)；這個時候就需要限制這個接口的總并發(fā)/請求數(shù)總請求數(shù)了伤塌；因為粒度比較細灯萍，可以為每個接口都設(shè)置相應(yīng)的閥值∶看希可以使用Java中的AtomicLong進行限流：
================================
try{
if(atomic.incrementAndGet() > 限流數(shù)) {
//拒絕請求
}
//處理請求
}finally{
atomic.decrementAndGet();
}
=========================================
適合對業(yè)務(wù)無損的服務(wù)或者需要過載保護的服務(wù)進行限流旦棉，如搶購業(yè)務(wù)，超出了大小要么讓用戶排隊药薯，要么告訴用戶沒貨了绑洛，對用戶來說是可以接受的。而一些開放平臺也會限制用戶調(diào)用某個接口的試用請求量童本，也可以用這種計數(shù)器方式實現(xiàn)真屯。這種方式也是簡單粗暴的限流，沒有平滑處理巾陕，需要根據(jù)實際情況選擇使用讨跟；
限流某個接口的時間窗請求數(shù)
即一個時間窗口內(nèi)的請求數(shù)，如想限制某個接口/服務(wù)每秒/每分鐘/每天的請求數(shù)/調(diào)用量鄙煤。如一些基礎(chǔ)服務(wù)會被很多其他系統(tǒng)調(diào)用晾匠，比如商品詳情頁服務(wù)會調(diào)用基礎(chǔ)商品服務(wù)調(diào)用，但是怕因為更新量比較大將基礎(chǔ)服務(wù)打掛梯刚，這時我們要對每秒/每分鐘的調(diào)用量進行限速凉馆；一種實現(xiàn)方式如下所示：
================================
LoadingCache counter =
CacheBuilder.newBuilder()
.expireAfterWrite(2, TimeUnit.SECONDS)
.build(newCacheLoader() {
@Override
publicAtomicLong load(Long seconds)throwsException {
return newAtomicLong(0);
}
});
longlimit =1000;
while(true) {
//得到當(dāng)前秒longcurrentSeconds = System.currentTimeMillis() /1000;
if(counter.get(currentSeconds).incrementAndGet() > limit) {
System.out.println("限流了:"+ currentSeconds);
continue;
}
//業(yè)務(wù)處理
}
================================
我們使用Guava的Cache來存儲計數(shù)器，過期時間設(shè)置為2秒（保證1秒內(nèi)的計數(shù)器是有的）亡资，然后我們獲取當(dāng)前時間戳然后取秒數(shù)來作為KEY進行計數(shù)統(tǒng)計和限流澜共，這種方式也是簡單粗暴，剛才說的場景夠用了锥腻。
平滑限流某個接口的請求數(shù)
之前的限流方式都不能很好地應(yīng)對突發(fā)請求嗦董，即瞬間請求可能都被允許從而導(dǎo)致一些問題；因此在一些場景中需要對突發(fā)請求進行整形瘦黑，整形為平均速率請求處理（比如5r/s京革，則每隔200毫秒處理一個請求，平滑了速率）幸斥。這個時候有兩種算法滿足我們的場景：令牌桶和漏桶算法匹摇。Guava框架提供了令牌桶算法實現(xiàn)，可直接拿來使用甲葬。
Guava RateLimiter提供了令牌桶算法實現(xiàn)：平滑突發(fā)限流(SmoothBursty)和平滑預(yù)熱限流(SmoothWarmingUp)實現(xiàn)廊勃。
SmoothBursty
================================
RateLimiter limiter = RateLimiter.create(5);
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
將得到類似如下的輸出：
0.0
0.198239
0.196083
0.200609
0.199599
0.19961
================================
1、RateLimiter.create(5)表示桶容量為5且每秒新增5個令牌经窖，即每隔200毫秒新增一個令牌坡垫；
2、limiter.acquire()表示消費一個令牌画侣，如果當(dāng)前桶中有足夠令牌則成功（返回值為0）葛虐，如果桶中沒有令牌則暫停一段時間，比如發(fā)令牌間隔是200毫秒棉钧，則等待200毫秒后再去消費令牌（如上測試用例返回的為0.198239屿脐，差不多等待了200毫秒桶中才有令牌可用），這種實現(xiàn)將突發(fā)請求速率平均為了固定請求速率宪卿。
再看一個突發(fā)示例：
================================
RateLimiter limiter = RateLimiter.create(5);
System.out.println(limiter.acquire(5));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1))
將得到類似如下的輸出：
0.0
0.98745
0.183553
0.199909
================================
limiter.acquire(5)表示桶的容量為5且每秒新增5個令牌的诵，令牌桶算法允許一定程度的突發(fā)，所以可以一次性消費5個令牌佑钾，但接下來的limiter.acquire(1)將等待差不多1秒桶中才能有令牌西疤，且接下來的請求也整形為固定速率了。
================================
RateLimiter limiter = RateLimiter.create(5);
System.out.println(limiter.acquire(10));
System.out.println(limiter.acquire(1));
System.out.println(limiter.acquire(1));
將得到類似如下的輸出：
0.0
1.997428
0.192273
0.200616
================================
同上邊的例子類似休溶，第一秒突發(fā)了10個請求代赁，令牌桶算法也允許了這種突發(fā)（允許消費未來的令牌）扰她，但接下來的limiter.acquire(1)將等待差不多2秒桶中才能有令牌，且接下來的請求也整形為固定速率了芭碍。
接下來再看一個突發(fā)的例子：
================================
RateLimiter limiter = RateLimiter.create(2);
System.out.println(limiter.acquire());
Thread.sleep(2000L);
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
System.out.println(limiter.acquire());
將得到類似如下的輸出：
0.0
0.0
0.0
0.0
0.499876
0.495799
================================
1徒役、創(chuàng)建了一個桶容量為2且每秒新增2個令牌；
2窖壕、首先調(diào)用limiter.acquire()消費一個令牌忧勿，此時令牌桶可以滿足（返回值為0）；
3瞻讽、然后線程暫停2秒鸳吸，接下來的兩個limiter.acquire()都能消費到令牌，第三個limiter.acquire()也同樣消費到了令牌速勇，到第四個時就需要等待500毫秒了晌砾。
此處可以看到我們設(shè)置的桶容量為2（即允許的突發(fā)量），這是因為SmoothBursty中有一個參數(shù)：最大突發(fā)秒數(shù)（maxBurstSeconds）默認(rèn)值是1s烦磁，突發(fā)量/桶容量=速率*maxBurstSeconds贡羔，所以本示例桶容量/突發(fā)量為2，例子中前兩個是消費了之前積攢的突發(fā)量个初，而第三個開始就是正常計算的了乖寒。令牌桶算法允許將一段時間內(nèi)沒有消費的令牌暫存到令牌桶中，留待未來使用院溺，并允許未來請求的這種突發(fā)楣嘁。
SmoothBursty通過平均速率和最后一次新增令牌的時間計算出下次新增令牌的時間的，另外需要一個桶暫存一段時間內(nèi)沒有使用的令牌（即可以突發(fā)的令牌數(shù)）珍逸。另外RateLimiter還提供了tryAcquire方法來進行無阻塞或可超時的令牌消費逐虚。
因為SmoothBursty允許一定程度的突發(fā)，會有人擔(dān)心如果允許這種突發(fā)谆膳，假設(shè)突然間來了很大的流量叭爱，那么系統(tǒng)很可能扛不住這種突發(fā)。因此需要一種平滑速率的限流工具漱病，從而系統(tǒng)冷啟動后慢慢的趨于平均固定速率（即剛開始速率小一些买雾，然后慢慢趨于我們設(shè)置的固定速率）。Guava也提供了SmoothWarmingUp來實現(xiàn)這種需求杨帽，其可以認(rèn)為是漏桶算法漓穿，但是在某些特殊場景又不太一樣。
SmoothWarmingUp創(chuàng)建方式：RateLimiter.create(doublepermitsPerSecond, long warmupPeriod, TimeUnit unit)
permitsPerSecond表示每秒新增的令牌數(shù)注盈，warmupPeriod表示在從冷啟動速率過渡到平均速率的時間間隔晃危。
示例如下：
================================
RateLimiter limiter = RateLimiter.create(5,1000, TimeUnit.MILLISECONDS);
for(inti =1; i <5;i++) {
System.out.println(limiter.acquire());
}
Thread.sleep(1000L);
for(inti =1; i <5;i++) {
System.out.println(limiter.acquire());
}
將得到類似如下的輸出：
0.0
0.51767
0.357814
0.219992
0.199984
0.0
0.360826
0.220166
0.199723
0.199555
================================
速率是梯形上升速率的，也就是說冷啟動時會以一個比較大的速率慢慢到平均速率老客；然后趨于平均速率（梯形下降到平均速率）僚饭≌鸲＃可以通過調(diào)節(jié)warmupPeriod參數(shù)實現(xiàn)一開始就是平滑固定速率。
到此應(yīng)用級限流的一些方法就介紹完了鳍鸵。假設(shè)將應(yīng)用部署到多臺機器苇瓣，應(yīng)用級限流方式只是單應(yīng)用內(nèi)的請求限流，不能進行全局限流权纤。因此我們需要分布式限流和接入層限流來解決這個問題。
分布式限流
分布式限流最關(guān)鍵的是要將限流服務(wù)做成原子化乌妒，而解決方案可以使使用redis+lua或者nginx+lua技術(shù)進行實現(xiàn)汹想，通過這兩種技術(shù)可以實現(xiàn)的高并發(fā)和高性能。
首先我們來使用redis+lua實現(xiàn)時間窗內(nèi)某個接口的請求數(shù)限流撤蚊，實現(xiàn)了該功能后可以改造為限流總并發(fā)/請求數(shù)和限制總資源數(shù)古掏。Lua本身就是一種編程語言，也可以使用它實現(xiàn)復(fù)雜的令牌桶或漏桶算法侦啸。
redis+lua實現(xiàn)中的lua腳本：
================================
local key = KEYS[1] --限流KEY（一秒一個）
local limit = tonumber(ARGV[1])??????? --限流大小
local current = tonumber(redis.call("INCRBY", key, "1")) --請求數(shù)+1
if current > limit then --如果超出限流大小
return 0
elseif current == 1 then? --只有第一次訪問需要設(shè)置2秒的過期時間
redis.call("expire", key,"2")
end
return 1
================================
如上操作因是在一個lua腳本中槽唾，又因Redis是單線程模型，因此是線程安全的光涂。如上方式有一個缺點就是當(dāng)達到限流大小后還是會遞增的庞萍，可以改造成如下方式實現(xiàn)：
================================
local key = KEYS[1] --限流KEY（一秒一個）
local limit = tonumber(ARGV[1])??????? --限流大小
local current = tonumber(redis.call('get', key) or "0")
if current + 1 > limit then --如果超出限流大小
return 0
else? --請求數(shù)+1，并設(shè)置2秒過期
redis.call("INCRBY", key,"1")
redis.call("expire", key,"2")
return 1
end
================================
如下是Java中判斷是否需要限流的代碼：
================================
public static booleanacquire()throwsException {
String luaScript = Files.toString(newFile("limit.lua"), Charset.defaultCharset());
Jedis jedis =newJedis("192.168.147.52",6379);
String key ="ip:"+ System.currentTimeMillis()/1000;//此處將當(dāng)前時間戳取秒數(shù)Stringlimit ="3";//限流大小return(Long)jedis.eval(luaScript,Lists.newArrayList(key), Lists.newArrayList(limit)) ==1;
}
================================
因為Redis的限制（Lua中有寫操作不能使用帶隨機性質(zhì)的讀操作忘闻，如TIME）不能在Redis Lua中使用TIME獲取時間戳钝计，因此只好從應(yīng)用獲取然后傳入，在某些極端情況下（機器時鐘不準(zhǔn)的情況下）齐佳，限流會存在一些小問題私恬。
使用Nginx+Lua實現(xiàn)的Lua腳本：
================================
local locks = require "resty.lock"
local function acquire()
local lock =locks:new("locks")
local elapsed, err =lock:lock("limit_key") --互斥鎖
local limit_counter =ngx.shared.limit_counter --計數(shù)器
local key = "ip:" ..os.time()
local limit = 5 --限流大小
local current =limit_counter:get(key)
if current ~= nil and current + 1> limit then --如果超出限流大小
lock:unlock()
return 0
end
if current == nil then
limit_counter:set(key, 1, 1) --第一次需要設(shè)置過期時間，設(shè)置key的值為1炼吴，過期時間為1秒
else
limit_counter:incr(key, 1) --第二次開始加1即可
end
lock:unlock()
return 1
end
ngx.print(acquire())
================================
實現(xiàn)中我們需要使用lua-resty-lock互斥鎖模塊來解決原子性問題(在實際工程中使用時請考慮獲取鎖的超時問題)本鸣，并使用ngx.shared.DICT共享字典來實現(xiàn)計數(shù)器。如果需要限流則返回0，否則返回1殃姓。使用時需要先定義兩個共享字典（分別用來存放鎖和計數(shù)器數(shù)據(jù)）：
================================
http {
……
lua_shared_dictlocks 10m;
lua_shared_dictlimit_counter 10m;
}
================================
有人會糾結(jié)如果應(yīng)用并發(fā)量非常大那么redis或者nginx是不是能抗得最砣弧；不過這個問題要從多方面考慮：你的流量是不是真的有這么大命爬，是不是可以通過一致性哈希將分布式限流進行分片，是不是可以當(dāng)并發(fā)量太大降級為應(yīng)用級限流辐脖；對策非常多饲宛，可以根據(jù)實際情況調(diào)節(jié)；像在京東使用Redis+Lua來限流搶購流量嗜价，一般流量是沒有問題的艇抠。
對于分布式限流目前遇到的場景是業(yè)務(wù)上的限流幕庐，而不是流量入口的限流；流量入口限流應(yīng)該在接入層完成家淤，而接入層筆者一般使用Nginx异剥。
參考資料
https://en.wikipedia.org/wiki/Token_bucket
https://en.wikipedia.org/wiki/Leaky_bucket
http://redis.io/commands/incr
http://nginx.org/en/docs/http/ngx_http_limit_req_module.html
http://nginx.org/en/docs/http/ngx_http_limit_conn_module.html
https://github.com/openresty/lua-resty-limit-traffic
