服務治理之常用限流算法總結(jié)
一、為什么會有限流
限流，看字面意思，限制流動。
為什么要限制流動？
比如高速公路出現(xiàn)了事故，交警會對高速路車輛的進入進行指揮和限制。
發(fā)生了一些意外情況，才可能要限制流動。等恢復正常情況后，就解除限制。不可能無緣無故地限制流動，畢竟限制會影響正常系統(tǒng)運行。
再舉一個例子：
足球館看足球比賽，足球館的場地大小是固定的，座位數(shù)是固定的，能容納看球人數(shù)總量是有限的。如果超過足球館容量最大承載，會導致場內(nèi)擁擠，這樣會發(fā)生2個問題：一個是導致大家行動不便，一個可能會發(fā)生意想不到的事故。
那怎么辦？球票。
一個足球場出售的球票是有限制的，一共賣多少張票是有一定數(shù)量額度。
系統(tǒng)容量有限，如果超過了系統(tǒng)的負荷，那么就需要做一些限制措施，避免系統(tǒng)運行時出現(xiàn)異常情況。
那在計算機系統(tǒng)中，為什么要限流？
同理，訪問計算機系統(tǒng)時或者是計算機系統(tǒng)本身出現(xiàn)了一些異常情況。比如流量過大，系統(tǒng)處理不過來。比如系統(tǒng)升級等等情況。
計算機系統(tǒng)容量是有限的，內(nèi)存大小，CPU 處理數(shù)據(jù)的速度，都是有限的，不可能無限大。如果超過了一定的閾值，系統(tǒng)就會出現(xiàn)異常，甚至宕機。
現(xiàn)在微服務架構(gòu)比較流行，各種服務比較多，服務之間調(diào)用頻繁。
如果訪問一個 API 服務時，超過了這個服務能提供的最大訪問能力，服務會崩潰，那就要對這個服務進行保護，避免服務因訪問過大導致服務不可用，不僅影響自己服務，也可能影響其它相關服務。
采用什么方法保護服務呢？限流就是保護方法之一。
在 IT 高并發(fā)系統(tǒng)中，出于對系統(tǒng)的保護，需要對系統(tǒng)進行限流。
二、IT 系統(tǒng)中的限流
上面已經(jīng)介紹了 IT 系統(tǒng)中的一些限流問題。
下面來看看對使用限流的一些具體情況描述。
在互聯(lián)網(wǎng)世界里，一根一根的網(wǎng)線把整個世界連接起來，那么網(wǎng)絡里面?zhèn)鬏數(shù)臄?shù)據(jù)
流動起來就形成了網(wǎng)絡流。TCP 里就有限制流量的算法-滑動窗口算法。
在微服務系統(tǒng)里的 API 接口中，對接口做限制，保護接口安全，保證系統(tǒng)穩(wěn)定。
對接口訪問請求，怎么描述接口請求情況？
一般用每秒請求數(shù)（request per second），并發(fā)請求數(shù)等，來描述對接口的請求情況。所以限制也是對每秒請求數(shù)進行限制。
還有平常使用的連接池技術(shù)，也可以理解為限流思想的一種，把連接數(shù)限制在一個數(shù)量上。把固定數(shù)量的連接放入“池子”中，很形象的說法。當然也是復用減少損耗。
三、常用限流算法
常用的限流算法，一般有 4 種：
計數(shù)器
滑動窗口
漏桶
令牌桶
計數(shù)器算法
計數(shù)器算法：
在固定窗口內(nèi)對請求進行計數(shù)，然后與設置的最大請求數(shù)進行比較，如果超過了最大值，就進行限流。到達了一個固定時間窗口終點，將計數(shù)器清零，重新開始計數(shù)。
計數(shù)器算法又叫?固定窗口算法-Fixed Window。
舉個例子，比如在微服務中有一個接口，限制調(diào)用次數(shù)：1 分鐘內(nèi)最大調(diào)用次數(shù)為 30。
根據(jù)描述，這個算法為：
設置最大請求數(shù) MaxRequest = 30，窗口時間 WindowTime = 60 秒，
還有一個計時開始時間 BeginTime , 請求計數(shù) Counter。
算法優(yōu)點：實現(xiàn)簡單
算法缺點：
1.計數(shù)器算法有一個”臨界時間點“問題。
比如限制 1 分鐘內(nèi)最大請求為 30 個。在 21:30:59 秒到達 30 個，然后 21:31:01 秒（臨界時間）又瞬間到達 30 個，雖然兩個時間窗內(nèi)請求都符合限流要求，但在兩個窗口臨界時間 2 秒內(nèi)集中了 60 次請求，超過了規(guī)定值 30。全局從速率來看 30/60s=0.5，而現(xiàn)在 60/2s =30，遠超 0.5，這對系統(tǒng)來說可能就無法承受了。在這個 2 秒內(nèi)不做限流，就可能會把我們的應用搞崩潰。
它無法應對兩個時間窗口臨界時間內(nèi)的突發(fā)流量。
2.如果請求速度太快，會丟掉一些請求。
怎么解決“臨界時間點”問題，看下面滑動窗口算法。
滑動窗口算法
滑動窗口算法（Sliding Window）部分解決了計數(shù)器算法（固定時間窗口算法）“時間臨界點” 的問題。
有的人還會把滑動窗口算法細分：滑動窗口日志(sliding window log)?和?滑動窗口計數(shù)（sliding window counter）。
滑動窗口計數(shù)
滑動窗口算法：
在計數(shù)器算法中，把大時間窗口再進一步劃分為更細小的時間窗口格子，隨著時間向前移動，大時間窗每次向前移動一個小格子，而不是大時間窗向前移動。每個小格子都有自己獨立計數(shù)器，小格子會記錄每個請求到達的時間點。
最終統(tǒng)計比較：
比較小格子內(nèi)請求數(shù)：(大時間窗口內(nèi)規(guī)定最大請求數(shù) / N個小格子) > 小格子時間窗內(nèi)總請求數(shù)
舉個例子：
把 1 分鐘時間窗再劃分為 6 個小格子時間窗，每個小格子 10 秒。每過 10 秒鐘，時間窗口向右滑動一小格。每一個小格
都有自己獨立的計數(shù)器 counter。下面圖1到圖2：
滑動窗口算法是怎么解決“臨界時間點”問題？
還是用上面計數(shù)器的例子：比如限制 1 分鐘內(nèi)最大請求為 30 個。
在 21:30:59 秒到達 30 個請求，它落在上圖2中灰色小格子中，然后 21:31:01 秒又瞬間到達 30 個，它會落在圖2橘色小格子中。而當時間到達 21:31:01 時，時間窗要向右移動一小格（如上圖2箭頭所示），此時大時間窗內(nèi)的總請求數(shù)為 60，超過了規(guī)定的最大請求數(shù) 30 個，這時就能檢測出超過了請求闕值從而觸發(fā)限流。
為什么說是部分解決“臨界時間點”，或者說它的缺點？
這個看劃分小格子的時間大小了。比如說上面例子小格子時間是 10 秒，如果瞬間流量是微秒呢？可能又會超過限制。那劃分更細時間單位。理論上流量到達時間也可以更細。
這個又咋辦？
多層次限流，同一個接口設置多條限流規(guī)則。比如 1 分鐘 30 個，100ms 2 個。
與計數(shù)器算法（固定時間窗口算法）區(qū)別：
計數(shù)器其實是一個固定時間窗口，它只有一格，比較大的一格時間，計數(shù)器算法是按照一大格時間窗向前移動?；瑒哟翱谒惴ㄊ前凑找恍「駮r間向前移動。固定窗口可以說是滑動窗口的一種特殊情況。
滑動時間窗口小格子劃分的時間越細，向前移動就越平滑。
漏桶算法
先看下面一張圖：
這個圖很形象的把漏桶算法表示出來了：
(a)圖：有一個控制開關的水龍頭，下面有一個桶用來裝水，桶下面有一個放水的洞。把請求比作水，水來了就先放到桶里，然后按照一定
的速率放出水。水龍頭放水過快，桶里的水滿了就會溢出。表現(xiàn)為請求就是多出的請求丟掉。(b)圖：把 (a) 圖再進一步算法化，把漏桶算法形象表示出來。
流入的請求速率是不確定，請求可以是任意速率流入桶中，流出的請求則是按照固定速率流出。把流入桶中的請求計數(shù)(桶的當前水位)，當請求超過桶的容量(最高水位)時，桶溢出丟棄這部分請求。
有的人形象把它叫作流量“整形”，因為不管你流入有多快，流出都是固定速率。
缺點：
這個漏桶算法能保護系統(tǒng)，但是有大量請求時還是會丟棄很多請求，導致請求失敗數(shù)高。
令牌桶算法
上面漏桶算法流入速度不穩(wěn)定，流出速度是穩(wěn)定的。
漏桶算法是直接把請求放入到桶里，令牌桶算法，一看名字，放入桶中的是令牌，然后請求獲取令牌成功才能往下執(zhí)行，否則丟棄請求。
令牌總數(shù)超過桶容量，就丟棄。令牌我們可以勻速生產(chǎn)，所以流入桶中令牌是穩(wěn)定的。
因為令牌是自己生產(chǎn)的，所以生產(chǎn)令牌的快慢可以控制，那是不是接受對應的請求可以快也可以慢，這樣就能夠應對突發(fā)流量。流量大，生產(chǎn)令牌就快點。能不能應對無限大突發(fā)流量？當然不行，資源是有限，對桶的最大流量也要進行限制。
令牌桶算法如下圖所示：
總結(jié)下令牌桶算法幾個關鍵參數(shù)：
1.令牌桶的容量
2.令牌生產(chǎn)的速率，比如每秒生產(chǎn)多少個令牌
3.最大限流量，最大請求的容量，這個關系到令牌桶里的令牌總數(shù)
桶中是可以存儲令牌的，這就使得令牌桶算法支持一定程度突發(fā)大流量。這一點來說，對用戶訪問比較友好。
作者：九卷出處：https://www.cnblogs.com/jiujuan/p/16264022.html
記得點「贊」和「在看」↓
愛你們