保障服務穩定的三大利器：熔斷降級、服務限流和故障模擬。今天和大家談談限流算法的幾種實現方式，本文所說的限流並非是Nginx層面的限流，而是業務代碼中的邏輯限流。
為什麼需要限流
按照服務的調用方，可以分為以下幾種類型服務
1、與用戶打交道的服務
比如web服務、對外API，這種類型的服務有以下幾種可能導致機器被拖垮：
- 用戶增長過快（這是好事）
- 因為某個熱點事件（微博熱搜）
- 競爭對象爬蟲
- 惡意的刷單
這些情況都是無法預知的，不知道什麼時候會有10倍甚至20倍的流量打進來，如果真碰上這種情況，擴容是根本來不及的（彈性擴容都是虛談，一秒鐘你給我擴一下試試）
2、對內的RPC服務
一個服務A的接口可能被BCDE多個服務進行調用，在B服務發生突發流量時，直接把A服務給調用掛了，導致A服務對CDE也無法提供服務。 這種情況時有發生，解決方案有兩種： 1、每個調用方採用線程池進行資源隔離 2、使用限流手段對每個調用方進行限流
限流算法實現
常見的限流算法有：計數器、令牌桶、漏桶。
1、計數器算法
採用計數器實現限流有點簡單粗暴，一般我們會限制一秒鐘的能夠通過的請求數，比如限流qps為100，算法的實現思路就是從第一個請求進來開始計時，在接下去的1s內，每來一個請求，就把計數加1，如果累加的數字達到了100，那麼後續的請求就會被全部拒絕。等到1s結束後，把計數恢復成0，重新開始計數。
具體的實現可以是這樣的：對於每次服務調用，可以通過 AtomicLong#incrementAndGet()方法來給計數器加1並返回最新值，通過這個最新值和閾值進行比較。
這種實現方式，相信大家都知道有一個弊端：如果我在單位時間1s內的前10ms，已經通過了100個請求，那後面的990ms，只能眼巴巴的把請求拒絕，我們把這種現象稱為“突刺現象”
2、漏桶算法
為了消除"突刺現象"，可以採用漏桶算法實現限流，漏桶算法這個名字就很形象，算法內部有一個容器，類似生活用到的漏斗，當請求進來時，相當於水倒入漏斗，然後從下端小口慢慢勻速的流出。不管上面流量多大，下面流出的速度始終保持不變。
不管服務調用方多麼不穩定，通過漏桶算法進行限流，每10毫秒處理一次請求。因為處理的速度是固定的，請求進來的速度是未知的，可能突然進來很多請求，沒來得及處理的請求就先放在桶裡，既然是個桶，肯定是有容量上限，如果桶滿了，那麼新進來的請求就丟棄。
在算法實現方面，可以準備一個隊列，用來保存請求，另外通過一個線程池定期從隊列中獲取請求並執行，可以一次性獲取多個併發執行。
這種算法，在使用過後也存在弊端：無法應對短時間的突發流量。
3、令牌桶算法
從某種意義上講，令牌桶算法是對漏桶算法的一種改進，桶算法能夠限制請求調用的速率，而令牌桶算法能夠在限制調用的平均速率的同時還允許一定程度的突發調用。
在令牌桶算法中，存在一個桶，用來存放固定數量的令牌。算法中存在一種機制，以一定的速率往桶中放令牌。每次請求調用需要先獲取令牌，只有拿到令牌，才有機會繼續執行，否則選擇選擇等待可用的令牌、或者直接拒絕。
放令牌這個動作是持續不斷的進行，如果桶中令牌數達到上限，就丟棄令牌，所以就存在這種情況，桶中一直有大量的可用令牌，這時進來的請求就可以直接拿到令牌執行，比如設置qps為100，那麼限流器初始化完成一秒後，桶中就已經有100個令牌了，這時服務還沒完全啟動好，等啟動完成對外提供服務時，該限流器可以抵擋瞬時的100個請求。所以，只有桶中沒有令牌時，請求才會進行等待，最後相當於以一定的速率執行。
實現思路：可以準備一個隊列，用來保存令牌，另外通過一個線程池定期生成令牌放到隊列中，每來一個請求，就從隊列中獲取一個令牌，並繼續執行。
幸運的是，通過Google開源的guava包，我們可以很輕鬆的創建一個令牌桶算法的限流器。
com.google.guava guava 18.0
通過RateLimiter類的create方法，創建限流器。
其實Guava提供了多種create方法，方便創建適合各種需求的限流器。在上述例子中，創建了一個每秒生成10個令牌的限流器，即100ms生成一個，並最多保存10個令牌，多餘的會被丟棄。
rateLimiter提供了acquire()和tryAcquire()接口
- 使用acquire()方法，如果沒有可用令牌，會一直阻塞直到有足夠的令牌。
- 使用tryAcquire()方法，如果沒有可用令牌，就直接返回false。
- 使用tryAcquire()帶超時時間的方法，如果沒有可用令牌，就會判斷在超時時間內是否可以等到令牌，如果不能，就返回false，如果可以，就阻塞等待。
集群限流
前面討論的幾種算法都屬於單機限流的範疇，但是業務需求五花八門，簡單的單機限流，根本無法滿足他們。
比如為了限制某個資源被每個用戶或者商戶的訪問次數，5s只能訪問2次，或者一天只能調用1000次，這種需求，單機限流是無法實現的，這時就需要通過集群限流進行實現。
如何實現？為了控制訪問次數，肯定需要一個計數器，而且這個計數器只能保存在第三方服務，比如redis。
大概思路：每次有相關操作的時
候，就向redis服務器發送一個incr命令，比如需要限制某個用戶訪問/index接口的次數，只需要拼接用戶id和接口名生成redis的key，每次該用戶訪問此接口時，只需要對這個key執行incr命令，在這個key帶上過期時間，就可以實現指定時間的訪問頻率。
