什么是限流

是指系統(tǒng)在高并發(fā)截亦，大量請求的情況下宴胧，限制新的流量對系統(tǒng)的訪問融涣，從而保證系統(tǒng)服務的安全性童番。

為什么會限制限流？

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

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

限流算法

計數(shù)限流算法

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

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

非常的簡單粗暴性雄，計數(shù)器的值要是存內存中就算單機限流算法没卸。存中心存儲里，例如 Redis 中秒旋，集群機器訪問就算分布式限流算法约计。

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

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

固定窗口限流算法

首先維護一個計數(shù)器蜘犁，將單位時間段當作一個“窗口”，計數(shù)器只記錄 這個 “窗口”接受到的請求

• 當次數(shù)小于限流閾值止邮，就允許訪問这橙，并且計算器+1
• 當次數(shù)大于限流閾值，就拒絕訪問
• 當“窗口”時間過去之后导披，計算器清零

假設單位時間是1秒屈扎，限流閥值為3。在單位時間1秒內撩匕，每來一個請求,計數(shù)器就加1助隧，如果計數(shù)器累加的次數(shù)超過限流閥值3，后續(xù)的請求全部拒絕滑沧。等到1s結束后并村，計數(shù)器清0，重新開始計數(shù)滓技。

限流1.png

期望的流量 - 實際流量

限流2.png

問題：

1. 一段時間內（不超過時間窗口）系統(tǒng)服務不可用哩牍。比如窗口大小為1s，限流大小為100令漂，然后恰好在某個窗口的第1ms來了100個請求膝昆，然后第2ms-999ms的請求就都會被拒絕丸边，這段時間用戶會感覺系統(tǒng)服務不可用。
2. 窗口切換時可能會產生兩倍的閾值流量請求假設限流閥值為5個請求荚孵，單位時間窗口是1s,如果我們在單位時間內的前0.8-1s和1-1.2s妹窖，分別并發(fā)5個請求。雖然都沒有超過閥值收叶，但是如果算0.8-1.2s,則并發(fā)數(shù)高達10骄呼，已經超過單位時間1s不超過5閥值的定義啦，通過的請求達到了閾值的兩倍判没。
   
   限流4.png

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

滑動窗口限流

滑動窗口為了限流解決固定窗口臨界值的問題蜓萄，可以保證在任意時間窗口內都不會超過閾值。

限流5.png

相對于固定窗口嫉沽，滑動窗口除了需要引入計數(shù)器之外還需要記錄時間窗口內每個請求到達的時間點绸硕，因此對內存的占用會比較多。
規(guī)則如下，假設時間窗口為 1 秒：

• 記錄每次請求的時間
• 統(tǒng)計每次請求的時間 至 往前推1秒這個時間窗口內請求數(shù)，并且 1 秒前的數(shù)據(jù)可以刪除甚脉。
• 統(tǒng)計的請求數(shù)小于閾值就記錄這個請求的時間，并允許通過猴凹，反之拒絕。

[圖片上傳失敗...(image-f7c9ba-1668061853226)]

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

問題：

1. 滑動窗口和固定窗口都無法解決短時間之內集中流量的突擊曾雕。
   們所想的限流場景，例如每秒限制 100 個請求助被。希望請求每 10ms 來一個，這樣我們的流量處理就很平滑揩环，但是真實場景很難控制請求的頻率搔弄。因此可能存在 5ms 內就打滿了閾值的情況。

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

漏桶算法

漏桶算法面對限流炫刷，就更加的柔性，不存在直接的粗暴拒絕郁妈。
它的原理很簡單柬唯，可以認為就是注水漏水的過程。往漏桶中以任意速率流入水圃庭，以固定的速率流出水锄奢。當水超過桶的容量時失晴，會被溢出，也就是被丟棄拘央。因為桶容量是不變的涂屁，保證了整體的速率。

• 流入的水滴灰伟，可以看作是訪問系統(tǒng)的請求拆又，這個流入速率是不確定的。
• 桶的容量一般表示系統(tǒng)所能處理的請求數(shù)栏账。
• 如果桶的容量滿了帖族，就達到限流的閥值，就會丟棄水滴（拒絕請求）

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

  
  
  限流6.png

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

問題：

1. 面對突發(fā)請求兑障，服務的處理速度和往常一樣的，這其實不是我想要的蕉汪；我想要可以定制化去改變處理速度旺垒。

令牌桶算法能夠在一定程度上解決流量突發(fā)的問題。

令牌同算法

• 有一個令牌管理員肤无，根據(jù)限流大小先蒋，定速往令牌桶里放令牌。
• 如果令牌數(shù)量滿了宛渐，超過令牌桶容量的限制竞漾，那就丟棄。
• 系統(tǒng)在接受到一個用戶請求時窥翩，都會先去令牌桶要一個令牌业岁。如果拿到令牌，那么就處理這個請求的業(yè)務邏輯寇蚊；
• 如果拿不到令牌笔时，就直接拒絕這個請求。

限流7.png

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

限流結論

• 固定窗口算法實現(xiàn)簡單业稼，性能高，但是會有臨界突發(fā)流量問題蚂蕴，瞬時流量最大可以達到閾值的2倍低散。
• 為了解決臨界突發(fā)流量，可以將窗口劃分為多個更細粒度的單元骡楼，每次窗口向右移動一個單元熔号，于是便有了滑動窗口算法。
• 滑動窗口當流量到達閾值時會瞬間掐斷流量鸟整，所以導致流量不夠平滑引镊。
• 想要達到限流的目的，又不會掐斷流量吃嘿，使得流量更加平滑祠乃？可以考慮漏桶算法梦重！需要注意的是兑燥，漏桶算法通常配置一個FIFO的隊列使用以達到允許限流的作用。
• 由于速率固定琴拧，即使在某個時刻下游處理能力過剩降瞳，也不能得到很好的利用，這是漏桶算法的一個短板蚓胸。
• 限流和瞬時流量其實并不矛盾挣饥，在大多數(shù)場景中，短時間突發(fā)流量系統(tǒng)是完全可以接受的沛膳。令牌桶算法就是不二之選了扔枫，令牌桶以固定的速率v產生令牌放入一個固定容量為n的桶中，當請求到達時嘗試從桶中獲取令牌锹安。
• 當桶滿時短荐，允許最大瞬時流量為n；當桶中沒有剩余流量時則限流速率最低叹哭，為令牌生成的速率v忍宋。
• 如何實現(xiàn)更加靈活的多級限流呢？滑動日志限流算法了解一下风罩！這里的日志則是請求的時間戳糠排，通過計算制定時間段內請求總數(shù)來實現(xiàn)靈活的限流。
• 當然超升，由于需要存儲時間戳信息入宦，其占用的存儲空間要比其他限流算法要大得多哺徊。
  不管黑貓白貓，能抓到老鼠的就是好貓云石。限流算法并沒有絕對的好劣之分唉工，如何選擇合適的限流算法呢？不妨從性能汹忠，是否允許超出閾值淋硝，落地成本，流量平滑度宽菜，是否允許突發(fā)流量以及系統(tǒng)資源大小限制多方面考慮谣膳。

當然，市面上也有比較成熟的限流工具和框架铅乡。如Google出品的Guava中基于令牌桶實現(xiàn)的限流組件继谚，拿來即用；以及alibaba開源的面向分布式服務架構的流量控制框架Sentinel更會讓你愛不釋手阵幸，它是基于滑動窗口實現(xiàn)的花履。

具體的實現(xiàn)限流的方式

1）Tomcat 使用 maxThreads 來實現(xiàn)限流。

2）Nginx 的 limit_req_zone 和 burst 來實現(xiàn)速率限流挚赊。

3）Nginx 的 limit_conn_zone 和 limit_conn 兩個指令控制并發(fā)連接的總數(shù)诡壁。

4）時間窗口算法借助 Redis 的有序集合可以實現(xiàn)。

5）漏桶算法可以使用 Redis-Cell 來實現(xiàn)荠割。

6）令牌算法可以解決Google的guava包來實現(xiàn)妹卿。

限流按照規(guī)模來分類：

1）單節(jié)點限流：限流的方案僅適用于單節(jié)點規(guī)模，在大規(guī)模集群下不適用

2）分布式系統(tǒng)限流：適用于大規(guī)模集群限流蔑鹦，當然單節(jié)點也支持夺克，例如：redis、zookeeper嚎朽、Sentinel

需要注意的是借助Redis實現(xiàn)的限流方案可用于分布式系統(tǒng)铺纽，而guava實現(xiàn)的限流只能應用于單機環(huán)境。

參考資料：

https://blog.csdn.net/budongfengqing/article/details/124437962

https://blog.csdn.net/u013735734/article/details/123494680

https://blog.csdn.net/sshduanzhijun/article/details/115019205