沒有哪種算法是最好的或者是最差的，具體要根據(jù)實際業(yè)務場景決定使用哪種實現(xiàn)方式，本質(zhì)都是提高功能的性價比，利用盡可能小的開發(fā)成本，產(chǎn)生盡可能大的收益。今天主要介紹的是目前比較常見的限流算法：
-
固定窗口（計算器法） -
滑動窗口 -
漏桶算法 -
令牌桶算法
一、固定窗口算法（計算器算法）
計數(shù)器算法是使用計數(shù)器在周期內(nèi)累加訪問次數(shù)，當達到設定的限流值時，觸發(fā)限流策略。下一個周期開始時，進行清零，重新計數(shù)。
此算法在單機還是分布式環(huán)境下實現(xiàn)都非常簡單，使用redis的incr原子自增性和線程安全即可輕松實現(xiàn)。
這個算法通常用于QPS限流和統(tǒng)計總訪問量，對于秒級以上的時間周期來說，會存在一個非常嚴重的問題，那就是臨界問題，如下圖：
假設1min內(nèi)服務器的負載能力為100，因此一個周期的訪問量限制在100，然而在第一個周期的最后5秒和下一個周期的開始5秒時間段內(nèi)，分別涌入100的訪問量，雖然沒有超過每個周期的限制量，但是整體上10秒內(nèi)已達到200的訪問量，已遠遠超過服務器的負載能力，由此可見，計數(shù)器算法方式限流對于周期比較長的限流，存在很大的弊端。
二、滑動窗口算法
滑動窗口算法是將時間周期分為N個小周期，分別記錄每個小周期內(nèi)訪問次數(shù)，并且根據(jù)時間滑動刪除過期的小周期。
如下圖，假設時間周期為1min，將1min再分為2個小周期，統(tǒng)計每個小周期的訪問數(shù)量，則可以看到，第一個時間周期內(nèi)，訪問數(shù)量為75，第二個時間周期內(nèi)，訪問數(shù)量為100，超過100的訪問則被限流掉了
由此可見，當滑動窗口的格子劃分地越多，那么滑動窗口的滾動就越平滑，限流的統(tǒng)計就會越精確。
此算法可以很好地解決固定窗口算法的臨界問題。
三、漏桶算法
漏桶算法是訪問請求到達時直接放入漏桶，如當前容量已達到上限（限流值），則進行丟棄（觸發(fā)限流策略）。漏桶以固定的速率進行釋放訪問請求（即請求通過），直到漏桶為空。
四、令牌桶算法
令牌桶算法是程序以r（r=時間周期/限流值）的速度向令牌桶中增加令牌，直到令牌桶滿，請求到達時向令牌桶請求令牌，如獲取到令牌則通過請求，否則觸發(fā)限流策略。
總結(jié)：
-
所有的請求在處理之前都需要拿到一個可用的令牌才會被處理；
-
根據(jù)限流大小，設置按照一定的速率往桶里添加令牌；
-
桶設置最大的放置令牌限制，當桶滿時、新添加的令牌就被丟棄或者拒絕；
-
請求達到后首先要獲取令牌桶中的令牌，拿著令牌才可以進行其他的業(yè)務邏輯，處理完業(yè)務邏輯之后，將令牌直接刪除；
-
令牌桶有最低限額，當桶中的令牌達到最低限額的時候，請求處理完之后將不會刪除令牌，以此保證足夠的限流。
