??：在開發(fā)高并發(fā)系統(tǒng)時(shí)，有三把利器用來保護(hù)系統(tǒng)：緩存、降級和限流。

限流在很多場景中用來限制并發(fā)和請求量，比如說秒殺搶購，保護(hù)自身系統(tǒng)和下游系統(tǒng)不被巨型流量沖垮等。你要開發(fā)一個(gè)限流的框架，那么必不可少的就是要選擇一種合適的限流算法。限流算法很多，常見的有幾類分別是：計(jì)數(shù)器算法、滑動(dòng)窗口算法、漏桶算法、令牌桶算法，具體視業(yè)務(wù)場景，統(tǒng)計(jì)的精準(zhǔn)度，限流維度而定。下面逐一講解。

1、計(jì)數(shù)器算法

計(jì)數(shù)器算法是限流算法里最簡單也是最容易實(shí)現(xiàn)的一種算法。主要用來限制一定時(shí)間內(nèi)的總并發(fā)數(shù)，計(jì)數(shù)器限流只要一定時(shí)間內(nèi)的總請求數(shù)超過設(shè)定的閥值則進(jìn)行限流，是一種簡單粗暴的總數(shù)量限流，而不是平均速率限流。比如數(shù)據(jù)庫連接池、線程池、秒殺的并發(fā)數(shù)；

優(yōu)點(diǎn)：簡單粗暴，單機(jī)在Java中可用Atomic等原子類或Semaphore，分布式就用Redis incr。

eg:我們規(guī)定，對于A接口來說，我們1分鐘的訪問次數(shù)不能超過100個(gè)。那么在一開始的時(shí)候，我們可以設(shè)置一個(gè)計(jì)數(shù)器counter，每當(dāng)一個(gè)請求過來的時(shí)候，counter就加1，如果counter的值大于100并且該請求與第一個(gè)請求的間隔時(shí)間還在1分鐘之內(nèi)，那么說明請求數(shù)過多，限流；如果該請求與第一個(gè)請求的間隔時(shí)間大于1分鐘，且counter的值還在限流范圍內(nèi)，那么就重置 counter

缺點(diǎn)：有一個(gè)十分致命的問題，那就是臨界問題。

eg:假設(shè)第1分鐘中的第59秒的時(shí)候，來了100個(gè)請求，這個(gè)時(shí)候是沒有超過100的限制。然后第2分鐘的第1秒來了100個(gè)請求，相隔幾毫秒，一下子進(jìn)來200個(gè)請求，明顯大于我們的限流閾值100。也就是說在時(shí)間窗口的重置節(jié)點(diǎn)處突發(fā)請求，可以瞬間超過我們的速率限制。用戶有可能通過算法的這個(gè)漏洞，瞬間壓垮我們的應(yīng)用。所以這個(gè)算法不夠完美是不是？

為了解決這個(gè)臨界區(qū)問題，我們引入了滑動(dòng)窗口算法。

2、滑動(dòng)窗口算法

滑動(dòng)窗口，又稱rolling window。上邊提到的計(jì)數(shù)器算法中，比如限制1分鐘內(nèi)的訪問次數(shù)，那么這個(gè)1分鐘就是一個(gè)固定的時(shí)間窗口，而滑動(dòng)窗口是將固定窗口再進(jìn)行細(xì)分成多個(gè)窗口。

eg:比如將1分鐘的固定窗口細(xì)分成6個(gè)窗口，那么每個(gè)窗口的時(shí)間就是10秒。如圖整個(gè)紅色的矩形框表示一個(gè)時(shí)間窗口，窗口是一直滑動(dòng)的，每過10秒，我們的時(shí)間窗口就會往右滑動(dòng)一格。按照上邊我們的假設(shè)：假設(shè)第1分鐘中的第59秒的時(shí)候，來了100個(gè)請求，落到灰色格子里，而第2分鐘的1:00到達(dá)的100個(gè)請求會落在橘黃色的格子中，而這時(shí)我們的時(shí)間窗剛好檢測到整個(gè)1分鐘內(nèi)（紅色框），總請求數(shù)量一共是200個(gè)，超過了限定的100個(gè)，所以此時(shí)能夠檢測出來觸發(fā)了限流。

Spring Cloud 中的熔斷框架 Hystrix，以及 Spring Cloud Alibaba 中的Sentinel 都采用滑動(dòng)窗口來做數(shù)據(jù)統(tǒng)計(jì)。

優(yōu)點(diǎn)：減少了臨界值帶來的并發(fā)超過閾值的問題。

由此可見，當(dāng)滑動(dòng)窗口的格子劃分的越多，那么滑動(dòng)窗口的滾動(dòng)就越平滑，限流的統(tǒng)計(jì)就會越精確。

3、漏桶算法（漏斗算法）

漏桶算法相對前面的計(jì)數(shù)算法更加柔性，它的原理也很簡單，它是一種恒定速率的限流算法，不管請求量是多少，服務(wù)端的處理效率是恒定的。漏桶限制的是請求的流出速率。漏桶中裝的是請求。

優(yōu)點(diǎn)：是能夠以固定的速率去控制流量，穩(wěn)定性比較好。

可以認(rèn)為就是我們常用的漏斗注水漏水的過程。漏桶接受以任意速率流入的水，并且以固定速率將水流出。當(dāng)水超過桶的容量時(shí)，會被溢出，也就相當(dāng)于被丟棄。

漏桶算法原理與消息隊(duì)列思想有些類似，都是進(jìn)行削峰填谷，經(jīng)過漏桶后請求就能勻速平滑的流出。它是一種恒定速率的限流算法，不管請求量是多少，服務(wù)端的處理效率是恒定的?；?MQ 來實(shí)現(xiàn)的生產(chǎn)者消費(fèi)者模型，其實(shí)算是一種漏桶限流算法。

缺點(diǎn)：就是無法應(yīng)對突發(fā)流量的來襲，以及處理請求會有延遲

eg：假設(shè)你的漏桶出口固定了每秒鐘只能通過100個(gè)請求，如果此時(shí)有150個(gè)請求，無論你后方的系統(tǒng)能不能抗住這150個(gè)請求，通過漏桶算法都會將另外50個(gè)請求進(jìn)行攔截，只能等前面的100個(gè)請求結(jié)束后才能繼續(xù)放行剩下的50個(gè)請求，無法應(yīng)對突發(fā)流量的來襲。

面對突發(fā)請求，服務(wù)的處理速度和平常一樣，這其實(shí)不是我們想要的。我們更想要的是面對突發(fā)流量時(shí)，在系統(tǒng)平穩(wěn)運(yùn)行的同時(shí)又能更快的處理請求，而不是一直按照統(tǒng)一的速率來處理。漏桶算法，可能更多的用來保護(hù)別人的接口。另外，漏桶中由于請求是暫存在桶中的，所以請求什么時(shí)候能被處理，則是有延時(shí)的，這并不符合互聯(lián)網(wǎng)業(yè)務(wù)低延時(shí)的要求。

4、令牌桶算法

令牌桶是一個(gè)存放固定容量令牌的桶，按照固定速率往桶里添加令牌，填滿了就丟棄令牌，請求是否被處理要看桶中令牌是否足夠，當(dāng)令牌數(shù)減為零時(shí)則拒絕新的請求。在流量低峰的時(shí)候，令牌桶會出現(xiàn)堆積，因此當(dāng)出現(xiàn)瞬時(shí)高峰的時(shí)候，有足夠多的令牌可以獲取，令牌桶允許一定程度突發(fā)流量，只要有令牌就可以處理，支持一次拿多個(gè)令牌。令牌桶中裝的是令牌。

網(wǎng)關(guān)層面的限流、或者接口調(diào)用的限流，都可以使用令牌桶算法，像 Google 的Guava，和 Redisson 的限流，都用到了令牌桶算法。

優(yōu)點(diǎn)：令牌桶算法是對漏斗算法的一種改進(jìn)，除了能夠起到限流的作用外，還允許一定程度的流量突發(fā)。

與漏桶算法相比，有可能導(dǎo)致短時(shí)間內(nèi)的請求數(shù)上升（因?yàn)槟玫搅钆坪?，就可以訪問接口，存在一瞬間將所有令牌拿走的情況），但不會有計(jì)數(shù)算法那樣高的峰值（因?yàn)榱钆茢?shù)量是勻速增加的）。所以在應(yīng)對突發(fā)流量的時(shí)候令牌桶表現(xiàn)的更佳。

一般自己調(diào)用自己的接口，接口會有一定的伸縮性，令牌桶算法，主要用來保護(hù)自己的服務(wù)器接口。

缺點(diǎn)：例如令牌桶，假如系統(tǒng)上線時(shí)沒有預(yù)熱，那么可能會出現(xiàn)由于此時(shí)桶中還沒有令牌，而導(dǎo)致請求被誤殺的情況；

5、限流算法總結(jié)

上面我們已經(jīng)了解了每個(gè)限流算法的的特點(diǎn)，并且類比了一些應(yīng)用場景。綜上可知，雖然漏桶、令牌桶對比時(shí)間窗口類算法對流量的整形效果更好，但是它們也有各自的缺點(diǎn)。

令牌桶、漏桶算法更適合阻塞式限流的場景，即后臺任務(wù)類的限流。

而基于時(shí)間窗口的限流則更適合互聯(lián)網(wǎng)實(shí)施業(yè)務(wù)限流的場景，即能處理快速處理，不能處理及時(shí)響應(yīng)調(diào)用方，避免請求出現(xiàn)過長的等待時(shí)間。

6、限流組件

一般而言我們不需要自己實(shí)現(xiàn)限流算法來達(dá)到限流的目的，不管是接入層限流還是細(xì)粒度的接口限流其實(shí)都有現(xiàn)成的輪子使用，其實(shí)現(xiàn)也是用了上述我們所說的限流算法。

比如Google Guava 提供的限流工具類 RateLimiter，是基于令牌桶實(shí)現(xiàn)的，并且擴(kuò)展了算法，支持預(yù)熱功能。

阿里開源的限流框架Sentinel 中的勻速排隊(duì)限流策略，就采用了漏桶算法。

Nginx 中的限流模塊 limit_req_zone，采用了漏桶算法，還有 OpenResty 中的 resty.limit.req庫等等。