限流算法：漏桶與令牌桶

在大量併發訪問的場景裡，系統很容易由於過多的請求而崩潰。在系統被拆分成多個微服務之後，每個微服務具有獨立性，有責任保護好自己。為了避免因為負載過高導致服務崩潰，可以使用限流。

一、漏桶

漏桶算法原理示意圖

請求在到達服務器後，首先會被放到一個“桶”裡面。系統會以恆定的速率從“桶”裡面取請求進行處理。“桶”是有大小限制的，當“桶”滿了的時候，再收到的請求是無法放到桶裡面的，會做拋棄處理，可以向客戶端返回稍後重試的錯誤。這個“桶”可以用隊列來實現。為了解決競爭問題，可以使用阻塞隊列。為了儘量減少多線程訪問的衝突，可以使用無鎖隊列（對於無鎖隊列會在以後的文章中進行講解）。

二、令牌桶

令牌桶算法原理示意圖

請求到達服務器後，會申請令牌，如果能夠拿到令牌則服務器進行處理，拿不到，則做拋棄處理。對於一次申請令牌的數量，可以每個請求一個或者按著請求的數據量進行分配，具體要根據場景來設定。服務器會定期的向“桶”內添加令牌，如果令牌基本沒怎麼消耗，超過了令牌“桶”的大小，則待添加的令牌會被丟棄，不會放入令牌桶。令牌桶算法常用Guava的RateLimiter來實現或者Semphore來實現。

三、二者比較

個人認為漏桶更適合異步請求，可以對突發的高併發請求進行削峰。但是這樣帶來的後果就是，在高併發時，請求的處理時間被變長。因為在超過處理能力之後，請求會被積壓到“桶”裡面，待前面的請求處理完後才會被處理。當用戶請求是異步請求時，對用戶體驗較好，也能提供吞吐量。而令牌桶則適合同步請求，對於突發的請求能夠以提高處理速率的方式消化請求。在當前的互聯網下，請求響應的速度要快。令牌桶算法能夠保證在處理能力範圍內的請求都能夠快速被處理。

總之，兩個算法是從不同的方面處理高併發，漏桶是增加緩存，將1秒內到來的請求5秒處理完，使每秒的壓力減小。令牌桶則是在處理能力範圍內，加快處理速度，1s到來的請求1秒消化完。至於選擇哪種算法，需要根據具體的業務場景，二者的區別已經在上面講了，權衡利弊做出選擇。