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

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

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

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

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

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

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

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

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

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

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