千呼萬喚，高并發(fā)限流算法之漏桶&令牌桶來了！

等啊等，盼啊盼，6月份終于來了，在618，你可以清空掉所有的預(yù)售訂單，還有購買商家所推出的限時折扣如前十五分鐘購買5折等，買的人很開心，商家也很開心。然而程序員們不開心了，提供應(yīng)用服務(wù)的團(tuán)隊、提供監(jiān)控服務(wù)的團(tuán)隊、提供基礎(chǔ)設(shè)施服務(wù)的團(tuán)隊都繃著一根神經(jīng)，生怕是自己這一環(huán)掛了，導(dǎo)致整個服務(wù)鏈路崩塌，最后被老板祭天了。

而今天我們給大家?guī)砹艘粍┝妓?，那便?span style="font-synthesis: style; font-weight: 600;">針對高并發(fā)的解決方案。所謂高并發(fā)指的是請求突然大量的襲來，比如雙十一整點搶購這種，服務(wù)器正常情況下的流量請求是50000個，雙十一來了500000個，這叫人服務(wù)器咋扛得住嘛。而應(yīng)對高并發(fā)，我們也有三大法寶：緩存、降級、限流。所謂緩存就是把用戶最常訪問的數(shù)據(jù)放起來，用戶請求來時，先訪問緩存中的數(shù)據(jù)，如果緩存沒有命中，再訪問后端數(shù)據(jù)，一定程度緩解了高并發(fā)。所謂降級就是非核心服務(wù)不讓訪問了、核心服務(wù)返回上一級頁面，用戶請求來時，最重要的頁面就是支付，其余的積分啥的都不重要，因此集中資源給到支付模塊使用。所謂限流就是限制流量，原來可以支撐50000個請求，突然來了500000個請求，限制只有60000個請求可以正常訪問，其余的都暫時先訪問不了。

在限流中，常用的算法有兩個：漏桶算法、令牌桶算法。漏桶算法就像是一個漏掉的水桶一樣，水桶底部是空的，無論上面倒多少水下來，漏出去的水都是固定的。漏桶算法如下所示，在流量場景中，BurstyFlow代表流量，在0-2秒內(nèi)突然來了12Mbps的突發(fā)流量，中間2-7秒沒有流量過來，7-10秒是平穩(wěn)的流量，可以看到數(shù)據(jù)不是平穩(wěn)的，通過漏桶可以將數(shù)據(jù)變得平穩(wěn)，每秒出去的流量是3Mbps。

它的偽代碼實現(xiàn)如下，我們定義了一個漏桶的demo，定義了桶容量、水流出速度、當(dāng)前水量、時間，通過水量與容量的差來看看是否繼續(xù)加水（也就是流量是否還可以繼續(xù)進(jìn)來），如果小于總?cè)萘?，則請求可以繼續(xù)進(jìn)來，如果大于則請求無法進(jìn)來了。

另一個限流算法是令牌桶算法，它與漏桶算法的區(qū)別在于允許流量一定程度的改變，不像漏桶算法始終是固定的流量。那么什么是令牌桶算法呢？

令牌桶算法就是在桶里面有一定令牌，我們可以往桶里不斷的去添加令牌，請求到來時拿到令牌就可以進(jìn)入下一階段去處理了，拿不到令牌的請求就會處于等待狀態(tài)。

它的偽代碼實現(xiàn)如下，我們定義了令牌桶的大小，令牌放入的速度，當(dāng)前的令牌量，執(zhí)行算法不斷的去添加令牌，如果大于桶容量則停止增加，反之則繼續(xù)增加令牌，如果當(dāng)前令牌數(shù)小于1，則不發(fā)放令牌，拒絕請求，如果大于1則發(fā)放令牌，處理請求。

講完了兩個限流算法后，我們看看在業(yè)務(wù)中是如何去實現(xiàn)限流。在微服務(wù)架構(gòu)下，我們把一個大的應(yīng)用分為多個微服務(wù)，服務(wù)與服務(wù)之間通過遠(yuǎn)程調(diào)用進(jìn)行通信，服務(wù)與數(shù)據(jù)庫之間通過數(shù)據(jù)庫連接池進(jìn)行連接，服務(wù)內(nèi)部則通過接口相互調(diào)用來實現(xiàn)功能。因此整個限流的層次也包含應(yīng)用層級限制、資源層級限制、接口層級限制。

在應(yīng)用層級的限制，主要是總并發(fā)數(shù)的限制，如果超過了閾值則不響應(yīng)用戶請求，比如tomcat自帶的設(shè)置，如MaxConnector設(shè)置最大連接數(shù)、MaxThreads設(shè)置最大線程數(shù)。在資源層級的限制，可以使用數(shù)據(jù)庫連接池、線程池等技術(shù)，超過線程池數(shù)則不能連接數(shù)據(jù)庫，無法響應(yīng)服務(wù)。在接口層級可以對核心接口的調(diào)用進(jìn)行限制，單位時間內(nèi)（如每秒/每分鐘/每小時）最大允許調(diào)用量，超過之后則調(diào)用失敗。表層的限制策略都是依托于深層的算法，而這算法可以是漏桶或者令牌桶算法。

無論是漏桶算法還是令牌桶算法，都只是工具，最終要服務(wù)于業(yè)務(wù)，通過原理與偽代碼的結(jié)合，你明白如何做實現(xiàn)了嘛？趕緊在你的業(yè)務(wù)中碼起來吧。無論是直接面對用戶的業(yè)務(wù)部門，還是服務(wù)于業(yè)務(wù)的基礎(chǔ)設(shè)施部門，都必須要對高并發(fā)謹(jǐn)慎起來，做好緩存降級限流措施。