首先我們先來看看什么是限流？

限流是指在系統(tǒng)面臨高并發(fā)、大流量請求的情況下，限制新的流量對系統(tǒng)的訪問，從而保證系統(tǒng)服務的安全性。

另一種解釋：在計算機網(wǎng)絡中，限流就是控制網(wǎng)絡接口發(fā)送或接收請求的速率，它可防止DoS攻擊和限制Web爬蟲。

那么我們?yōu)槭裁磿蘖鳎?/p>

日常的業(yè)務上有類似秒殺活動、雙十一大促或者突發(fā)新聞等場景，用戶的流量突增，后端服務的處理能力是有限的，如果不能處理好突發(fā)流量，后端服務很容易就被打垮，導致整個系統(tǒng)崩潰！

亦或是爬蟲等不正常流量，我們對外暴露的服務都要以最大惡意去防備我們的調(diào)用者。我們不清楚調(diào)用者會如何調(diào)用我們的服務。假設某個調(diào)用者開幾十個線程一天二十四小時瘋狂調(diào)用你的服務，不做啥處理咱服務也算完了。更勝的還有DDos攻擊。

接下來一起來看看有哪些限流算法

計數(shù)限流

最簡單的限流算法就是計數(shù)限流了，例如系統(tǒng)能同時處理100個請求，保存一個計數(shù)器，處理了一個請求，計數(shù)器加一，一個請求處理完畢之后計數(shù)器減一。

每次請求來的時候看看計數(shù)器的值，如果超過閾值要么拒絕。

非常的簡單粗暴，計數(shù)器的值要是存內(nèi)存中就算單機限流算法。存中心存儲里，例如 Redis 中，集群機器訪問就算分布式限流算法。

優(yōu)點就是：簡單粗暴，單機在 Java 中可用 Atomic 等原子類、分布式就 Redis incr。

缺點就是：假設我們允許的閾值是1萬，此時計數(shù)器的值為0， 當1萬個請求在前1秒內(nèi)一股腦兒的都涌進來，這突發(fā)的流量可是頂不住的。緩緩的增加處理和一下子涌入對于程序來說是不一樣的。

固定窗口限流算法

首先維護一個計數(shù)器，將單位時間段當做一個窗口，計數(shù)器記錄這個窗口接收請求的次數(shù)。

當次數(shù)少于限流閥值，就允許訪問，并且計數(shù)器+1

當次數(shù)大于限流閥值，就拒絕訪問。

當前的時間窗口過去之后，計數(shù)器清零。

假設單位時間是1秒，限流閥值為3。在單位時間1秒內(nèi)，每來一個請求,計數(shù)器就加1，如果計數(shù)器累加的次數(shù)超過限流閥值3，后續(xù)的請求全部拒絕。等到1s結(jié)束后，計數(shù)器清0，重新開始計數(shù)。

如下圖：

這個時候看起來沒有什么問題，但事實總是殘酷的！

一段時間內(nèi)（不超過時間窗口）系統(tǒng)服務不可用。比如窗口大小為1s，限流大小為100，然后恰好在某個窗口的第1ms來了100個請求，然后第2ms-999ms的請求就都會被拒絕，這段時間用戶會感覺系統(tǒng)服務不可用。

窗口切換時可能會產(chǎn)生兩倍于閾值流量的請求。假設限流閥值為5個請求，單位時間窗口是1s,如果我們在單位時間內(nèi)的前0.8-1s和1-1.2s，分別并發(fā)5個請求。雖然都沒有超過閥值，但是如果算0.8-1.2s,則并發(fā)數(shù)高達10，已經(jīng)超過單位時間1s不超過5閥值的定義啦，通過的請求達到了閾值的兩倍。

為了解決這個問題引入了滑動窗口限流。

滑動窗口限流

滑動窗口限流解決固定窗口臨界值的問題，可以保證在任意時間窗口內(nèi)都不會超過閾值。

相對于固定窗口，滑動窗口除了需要引入計數(shù)器之外還需要記錄時間窗口內(nèi)每個請求到達的時間點，因此對內(nèi)存的占用會比較多。

規(guī)則如下，假設時間窗口為 1 秒：

記錄每次請求的時間

統(tǒng)計每次請求的時間 至 往前推1秒這個時間窗口內(nèi)請求數(shù)，并且 1 秒前的數(shù)據(jù)可以刪除。

統(tǒng)計的請求數(shù)小于閾值就記錄這個請求的時間，并允許通過，反之拒絕。

從圖中不難看出，滑動窗口算法就是固定窗口的升級版。將計時窗口劃分成一個小窗口，滑動窗口算法就退化成了固定窗口算法。而滑動窗口算法其實就是對請求數(shù)進行了更細粒度的限流，窗口劃分的越多，則限流越精準。

但是滑動窗口和固定窗口都無法解決短時間之內(nèi)集中流量的突擊。

我們所想的限流場景，例如每秒限制 100 個請求。希望請求每 10ms 來一個，這樣我們的流量處理就很平滑，但是真實場景很難控制請求的頻率。因此可能存在 5ms 內(nèi)就打滿了閾值的情況。

當然對于這種情況還是有變型處理的，例如設置多條限流規(guī)則。不僅限制每秒 100 個請求，再設置每 10ms 不超過 2 個。

接下來再說說漏桶，它可以解決時間窗口類的痛點，使得流量更加的平滑。

漏桶算法

漏桶算法面對限流，就更加的柔性，不存在直接的粗暴拒絕。

它的原理很簡單，可以認為就是注水漏水的過程。往漏桶中以任意速率流入水，以固定的速率流出水。當水超過桶的容量時，會被溢出，也就是被丟棄。因為桶容量是不變的，保證了整體的速率。

流入的水滴，可以看作是訪問系統(tǒng)的請求，這個流入速率是不確定的。

桶的容量一般表示系統(tǒng)所能處理的請求數(shù)。

如果桶的容量滿了，就達到限流的閥值，就會丟棄水滴（拒絕請求）

流出的水滴，是恒定過濾的，對應服務按照固定的速率處理請求。

看到這想到啥，是不是和消息隊列思想有點像，削峰填谷。經(jīng)過漏洞這么一過濾，請求就能平滑的流出，看起來很像很挺完美的？實際上它的優(yōu)點也即缺點。

面對突發(fā)請求，服務的處理速度和平時是一樣的，這其實不是我們想要的，在面對突發(fā)流量我們希望在系統(tǒng)平穩(wěn)的同時，提升用戶體驗即能更快的處理請求，而不是和正常流量一樣，循規(guī)蹈矩的處理（看看，之前滑動窗口說流量不夠平滑，現(xiàn)在太平滑了又不行，難搞?。?。

而接下來我們要談的令牌桶算法能夠在一定程度上解決流量突發(fā)的問題。

令牌桶算法

令牌桶算法是對漏斗算法的一種改進，除了能夠起到限流的作用外，還允許一定程度的流量突發(fā)。

令牌桶算法原理：

有一個令牌管理員，根據(jù)限流大小，定速往令牌桶里放令牌。

如果令牌數(shù)量滿了，超過令牌桶容量的限制，那就丟棄。

系統(tǒng)在接受到一個用戶請求時，都會先去令牌桶要一個令牌。如果拿到令牌，那么就處理這個請求的業(yè)務邏輯；

如果拿不到令牌，就直接拒絕這個請求。

可以看出令牌桶在應對突發(fā)流量的時候，桶內(nèi)假如有 100 個令牌，那么這 100 個令牌可以馬上被取走，而不像漏桶那樣勻速的消費。所以在應對突發(fā)流量的時候令牌桶表現(xiàn)的更佳。

限流結(jié)論

固定窗口算法實現(xiàn)簡單，性能高，但是會有臨界突發(fā)流量問題，瞬時流量最大可以達到閾值的2倍。

為了解決臨界突發(fā)流量，可以將窗口劃分為多個更細粒度的單元，每次窗口向右移動一個單元，于是便有了滑動窗口算法。

滑動窗口當流量到達閾值時會瞬間掐斷流量，所以導致流量不夠平滑。

想要達到限流的目的，又不會掐斷流量，使得流量更加平滑？可以考慮漏桶算法！需要注意的是，漏桶算法通常配置一個FIFO的隊列使用以達到允許限流的作用。

由于速率固定，即使在某個時刻下游處理能力過剩，也不能得到很好的利用，這是漏桶算法的一個短板。

限流和瞬時流量其實并不矛盾，在大多數(shù)場景中，短時間突發(fā)流量系統(tǒng)是完全可以接受的。令牌桶算法就是不二之選了，令牌桶以固定的速率v產(chǎn)生令牌放入一個固定容量為n的桶中，當請求到達時嘗試從桶中獲取令牌。

當桶滿時，允許最大瞬時流量為n；當桶中沒有剩余流量時則限流速率最低，為令牌生成的速率v。

如何實現(xiàn)更加靈活的多級限流呢？滑動日志限流算法了解一下！這里的日志則是請求的時間戳，通過計算制定時間段內(nèi)請求總數(shù)來實現(xiàn)靈活的限流。

當然，由于需要存儲時間戳信息，其占用的存儲空間要比其他限流算法要大得多。