Part 01

什么是限流？ 

業(yè)務(wù)系統(tǒng)限流是指系統(tǒng)在面臨高并發(fā)或者大流量請(qǐng)求的情況下，限制新的請(qǐng)求對(duì)系統(tǒng)的訪問(wèn)，從而保證系統(tǒng)的穩(wěn)定性和安全性。

Part 02

為什么要限流？  

系統(tǒng)資源和處理能力都是有限的，如果一個(gè)系統(tǒng)不限制流量，比如在秒殺活動(dòng)、大促銷等場(chǎng)景下，瞬時(shí)間大量的流量訪問(wèn)將超出系統(tǒng)的負(fù)載，最終會(huì)導(dǎo)致服務(wù)異常、機(jī)器宕機(jī)。

Part 03

常用的限流算法 

常用的限流算法有固定窗口算法、滑動(dòng)窗口算法、漏桶算法和令牌桶算法，下面將對(duì)這幾種算法分別進(jìn)行介紹，這也是所有限流框架實(shí)現(xiàn)限流的基礎(chǔ)。

Part 04

固定窗口算法 

固定窗口限流算法是最基礎(chǔ)的一種限流算法。原理是將一段固定時(shí)間當(dāng)做一個(gè)窗口，通過(guò)計(jì)數(shù)器記錄這個(gè)窗口接收到的請(qǐng)求次數(shù)。當(dāng)請(qǐng)求次數(shù)大于限流閾值，就拒絕訪問(wèn)；反之就允許訪問(wèn)，并將計(jì)數(shù)器加1。當(dāng)時(shí)間窗口結(jié)束后將計(jì)數(shù)器重置為0。

該算法易于理解，實(shí)現(xiàn)也簡(jiǎn)單。但是缺點(diǎn)也很明顯，會(huì)產(chǎn)生突刺現(xiàn)象和臨界問(wèn)題：

• 突刺現(xiàn)象是指窗口一段時(shí)間內(nèi)服務(wù)不可用，導(dǎo)致流程曲線不夠平滑。假如窗口大小為1分鐘，限流閾值為10，然后窗口的第1秒恰好進(jìn)來(lái)10個(gè)請(qǐng)求，導(dǎo)致以后59秒的請(qǐng)求都被拒絕。
• 臨界問(wèn)題是指窗口切換時(shí)產(chǎn)生兩倍閾值流量的請(qǐng)求。假如窗口大小還是1分鐘，限流閾值還是10，然后第一個(gè)窗口前期沒(méi)有請(qǐng)求，恰好在第59秒進(jìn)來(lái)10個(gè)請(qǐng)求，此時(shí)這10個(gè)請(qǐng)求都會(huì)放行。下一個(gè)窗口的第1秒恰好又來(lái)了10個(gè)請(qǐng)求，也全部放行了，相當(dāng)于2秒之內(nèi)通過(guò)了20個(gè)請(qǐng)求，而系統(tǒng)設(shè)定的閾值是10。惡意用戶有可能通過(guò)算法的這個(gè)漏洞，在時(shí)間窗口的重置節(jié)點(diǎn)處突發(fā)請(qǐng)求，瞬間壓垮業(yè)務(wù)系統(tǒng)。

Part 05

滑動(dòng)窗口算法 

為了解決固定窗口算法中的臨界問(wèn)題，讓流量限制更加平滑，產(chǎn)生了滑動(dòng)窗口算法。該算法將固定窗口中分割出多個(gè)小窗口，分別記錄每個(gè)小窗口內(nèi)的訪問(wèn)次數(shù)，然后根據(jù)時(shí)間將窗口往前滑動(dòng)并刪除過(guò)期的小窗口。

假設(shè)窗口時(shí)間還是1分鐘，滑動(dòng)窗口算法把它劃分為6個(gè)小周期，每個(gè)小周期是10秒，對(duì)應(yīng)滑動(dòng)窗口被劃分為6個(gè)小格子。每隔10秒時(shí)間窗口就會(huì)往右滑動(dòng)一格，每個(gè)小窗口都有獨(dú)立的計(jì)數(shù)器，如果請(qǐng)求是43秒到達(dá)的，40秒到50秒小窗口對(duì)應(yīng)的計(jì)數(shù)器就會(huì)加1。

我們看下滑動(dòng)窗口是如何解決臨界問(wèn)題的，假設(shè)1分鐘內(nèi)的限流閥值還是10，50秒到60秒內(nèi)（比如58秒的時(shí)候）來(lái)了10個(gè)請(qǐng)求，落在綠色格子里。時(shí)間過(guò)了60秒這個(gè)點(diǎn)之后又來(lái)10個(gè)請(qǐng)求，落在紅色格子里。滑動(dòng)窗口過(guò)了60秒這個(gè)點(diǎn)后會(huì)右移一個(gè)小格，當(dāng)前的窗口時(shí)間段是10秒到70秒，這個(gè)區(qū)域的請(qǐng)求已經(jīng)超過(guò)限定的10了，所以紅色格子的請(qǐng)求都會(huì)被拒絕。

滑動(dòng)窗口算法雖然解決了臨界問(wèn)題，但是一旦到達(dá)限流閾值后，請(qǐng)求都會(huì)被直接拒絕。在實(shí)際應(yīng)用中我們要的限流效果不是把流量一下子掐斷，而是讓流量平滑地進(jìn)入系統(tǒng)當(dāng)中。

Part 06

漏桶算法 

如何更加平滑的限流，我們來(lái)看看漏桶算法。漏桶算法的限流原理可以認(rèn)為就是進(jìn)水漏水的過(guò)程。請(qǐng)求像水一樣以任意速率注入漏桶，而漏桶會(huì)按照固定的速率將水漏掉；當(dāng)進(jìn)水速度超過(guò)漏水速度時(shí)，漏桶會(huì)裝滿，此后進(jìn)入的水會(huì)溢出，也就是請(qǐng)求被丟棄。

漏桶算法主要目的是將網(wǎng)絡(luò)中的突發(fā)流量整合成平滑穩(wěn)定的流量，不過(guò)由于漏桶對(duì)流量的控制過(guò)于嚴(yán)格，導(dǎo)致部分場(chǎng)景下不能充分利用系統(tǒng)資源。因?yàn)槁┩暗穆┧俾适枪潭ǖ?，即使在某一時(shí)刻下游系統(tǒng)處理能力富余，漏桶也不會(huì)允許突發(fā)流量通過(guò)。流量突發(fā)時(shí)我們希望系統(tǒng)在穩(wěn)定的同時(shí)，能盡可能快的處理用戶請(qǐng)求，接下來(lái)介紹的令牌桶算法能夠在一定程度上解決流量突發(fā)的問(wèn)題。

Part 07

令牌桶算法 

令牌桶算法是對(duì)漏桶算法的一種改進(jìn)，除了能夠限流外，還允許一定程度的流量突發(fā)。其原理是設(shè)置一個(gè)令牌桶，以恒定速率向令牌桶放入令牌，請(qǐng)求到達(dá)時(shí)嘗試從令牌桶中拿令牌，只有拿到令牌才能夠放行，否則請(qǐng)求將會(huì)被拒絕。

令牌桶具有以下特點(diǎn)：

• 根據(jù)限流大小定速往令牌桶里放令牌。
• 如果令牌數(shù)量超過(guò)令牌桶容量的限制就丟棄令牌。
• 每一個(gè)請(qǐng)求首先去令牌桶拿令牌，拿到令牌就處理請(qǐng)求，拿不到令牌就直接拒絕。

Part 08

 小結(jié)  

最后我們對(duì)上述四種限流算法進(jìn)行一下簡(jiǎn)單的總結(jié)。

固定窗口算法實(shí)現(xiàn)簡(jiǎn)單，但是流量曲線不夠平滑有突刺現(xiàn)象，在窗口切換時(shí)可能會(huì)產(chǎn)生兩倍閾值流量的臨界問(wèn)題?；瑒?dòng)窗口算法作為固定窗口算法的一種改進(jìn)，有效解決了窗口切換時(shí)的臨界問(wèn)題。阿里開(kāi)源的流量控制框架Sentinel就是基于滑動(dòng)窗口實(shí)現(xiàn)的。

漏桶算法能夠?qū)α髁科鸬狡交鞯淖饔?，讓隨機(jī)不確定的流量以固定的速率流出，但是不能解決流量突發(fā)問(wèn)題。令牌桶算法能夠在限制數(shù)據(jù)的平均傳輸速率的同時(shí)還允許某種程度的突發(fā)傳輸。Guava的RateLimiter限流組件，就是基于令牌桶算法實(shí)現(xiàn)的。