常見的限流算法
計數器（固定窗口）算法
在指定周期內累加訪問次數引谜，當訪問次數達到設定的閾值時牍陌，觸發(fā)限流策略，當進入下一個時間周期時進行訪問次數的清零员咽。
限定每一分鐘能夠處理的總的請求數為100毒涧，在第一個一分鐘內，一共請求了60次贝室。接著到第二個一分鐘契讲，counter又從0開始計數仿吞，在一分半鐘時，已經達到了最大限流的閾值怀泊，這個時候后續(xù)的所有請求都會被拒絕茫藏。這種算法可以用在短信發(fā)送的頻次限制上，比如限制同一個用戶一分鐘之內觸發(fā)短信發(fā)送的次數霹琼。
臨界問題
這種算法存在一個臨界問題务傲，這種算法針對的是固定周期的累加訪問次數，但是如果服務器需要做到的是限制每個一分鐘內的訪問量枣申，這種算法顯然就不適用了售葡，因為計數器算法無法限制每隔一段時間內的訪問量均不超過閾值。
在第一分鐘的0：58和第二分鐘的1：02這個時間段內忠藤，分別出現了100個請求挟伙，整體來看就會出現4秒內總的請求量達到200，超出了設置的閾值模孩。
滑動窗口算法
滑動窗口算法是將時間周期分為N個小周期（窗口）尖阔，分別記錄每個小周期內訪問次數，然后根據時間將窗口往前滑動并刪除過期的小時間窗口榨咐。最終只需要統(tǒng)計滑動窗口范圍內的所有小時間窗口總的計數即可介却。
將一分鐘拆分為4個小時間窗口，每個小時間窗口最多能夠處理25個請求块茁。并且通過虛線框表示滑動窗口的大谐菘馈（當前窗口的大小是2，也就是在這個窗口內最多能夠處理50個請求）数焊。同時滑動窗口會隨著時間往前移動永淌，比如前面15s結束之后，窗口會滑動到15s～45s這個范圍佩耳，然后在新的窗口中重新統(tǒng)計數據遂蛀。
由此可見，當滑動窗口的格子劃分的越多干厚，那么滑動窗口的滾動就越平滑李滴，限流的統(tǒng)計就會越精確。此算法可以很好的解決固定窗口算法的臨界問題萍诱。
令牌桶限流算法
令牌桶是網絡流量整形（Traffic Shaping）和速率限制（Rate Limiting）中最常使用的一種算法悬嗓。對于每一個請求，都需要從令牌桶中獲得一個令牌裕坊，如果沒有獲得令牌包竹，則需要觸發(fā)限流策略。
系統(tǒng)會以一個恒定速度（r tokens/sec）往固定容量的令牌桶中放入令牌，如果此時有客戶端請求過來周瞎，則需要先從令牌桶中拿到令牌以獲得訪問資格苗缩。
限流場景
假設令牌生成速度是每秒10個，也就等同于QPS=10声诸，此時在請求獲取令牌的時候酱讶，會存在三種情況：
? 請求速度大于令牌生成速度：那么令牌會很快被取完，后續(xù)再進來的請求會被限流彼乌。
? 請求速度等于令牌生成速度：此時流量處于平穩(wěn)狀態(tài)泻肯。
? 請求速度小于令牌生成速度：說明此時系統(tǒng)的并發(fā)數并不高，請求能被正常處理慰照。
由于令牌桶有固定的大小灶挟，當請求速度小于令牌生成速度時，令牌桶會被填滿毒租。所以令牌桶能夠處理突發(fā)流量稚铣，也就是在短時間內新增的流量系統(tǒng)能夠正常處理，這是令牌桶的特性墅垮。
漏桶限流算法
漏桶限流算法的主要作用是控制數據注入網絡的速度惕医，平滑網絡上的突發(fā)流量。
在漏桶算法內部同樣維護一個容器算色，這個容器會以恒定速度出水抬伺，不管上面的水流速度多快剃允，漏桶水滴的流出速度始終保持不變斥废。訪問請求到達時直接放入漏桶，如當前容量已達到上限（限流值）统锤，則進行丟棄（觸發(fā)限流策略）。漏桶以固定的速率進行釋放訪問請求（即請求通過）逾雄，直到漏桶為空银锻。實際上消息中間件就使用了漏桶限流的思想做鹰，不管生產者的請求量有多大更振，消息的處理能力取決于消費者。
限流場景
在漏桶限流算法中乎芳，存在以下幾種可能的情況：
? 請求速度大于漏桶流出水滴的速度：也就是請求數超出當前服務所能處理的極限，將會觸發(fā)限流策略。
? 請求速度小于或者等于漏桶流出水滴的速度原在，也就是服務端的處理能力正好滿足客戶端的請求量秽浇，將正常執(zhí)行审残。
漏桶限流算法和令牌桶限流算法的實現原理相差不大，最大的區(qū)別是漏桶無法處理短時間內的突發(fā)流量没宾，漏桶限流算法是一種恒定速度的限流算法褐澎。
四種算法比較
