大家好我是小白，最近在牛客熱榜中，小馬哥持續(xù)霸榜，關(guān)于怎么設(shè)計(jì)一個(gè)秒殺系統(tǒng)：直達(dá)帖子 ，我也來蹭一蹭小馬哥熱度。秒殺系統(tǒng)近兩年來，后端開發(fā)的同學(xué)簡歷中幾乎人手一個(gè)，但是當(dāng)面試官深挖秒殺系統(tǒng)的時(shí)候，你真的能hold住嘛？今天小白補(bǔ)充一個(gè)秒殺系統(tǒng)中的細(xì)節(jié)——限流算法.

熱榜

限流算法是我們秒殺系統(tǒng)中繞不開的一個(gè)關(guān)鍵性算法，在高并發(fā)的場景下它能有效在入口為我們降低90%以上的流量，有效保護(hù)我們的下游系統(tǒng)。我們可能相對(duì)熟悉的是漏桶算法和令牌桶算法，這也是我們秒殺系統(tǒng)中常用的兩個(gè)算法。如果在面試過程中被問到限流算法，有時(shí)候如果我們?cè)诿嬖囘^程中 “不小心” 給面試官側(cè)漏一下這些算法的實(shí)習(xí)原理，有時(shí)候會(huì)達(dá)到眼前一亮的效果。（難道非要我去學(xué)電焊，才能亮瞎面試官）

讓人眼前一亮的男人

下面小白帶大家深入介紹這四個(gè)限流算法老大哥，首先是一哥計(jì)數(shù)器算法。

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

一哥頭腦簡單四肢發(fā)達(dá)，毫無技巧性統(tǒng)計(jì)固定的時(shí)間窗口的流量，比如我設(shè)置一個(gè)一分鐘的時(shí)間窗口，每次從第0s開始統(tǒng)計(jì)，第60s結(jié)束統(tǒng)計(jì)流量。如果從第0s到第60s中間有累計(jì)有超過1w個(gè)請(qǐng)求，一哥就給它掐斷接下來的請(qǐng)求，第二分鐘重新歸零統(tǒng)計(jì)。顯然，這種設(shè)計(jì)會(huì)有一個(gè)非常大的漏洞，比如我在第一分鐘的第59s突然來了9999個(gè)請(qǐng)求，然后在第二分鐘的第1s來了9999個(gè)請(qǐng)求，然而 “聰明” 的一哥會(huì)覺得很正常，它認(rèn)為你第一分鐘的流量，跟我第二分鐘有個(gè)毛線關(guān)系，反正兩個(gè)時(shí)間窗口都沒超過1w。但是實(shí)際上短短兩秒內(nèi)就有19998個(gè)請(qǐng)求進(jìn)來了，違背了我們的限流原則，存在臨界值的問題，有可能導(dǎo)致下游系統(tǒng)崩了。

滑動(dòng)時(shí)間窗口限流算法

二哥滑動(dòng)時(shí)間窗口限流算法看著一哥的限流方式，覺得它應(yīng)該有什么大病，跟一哥這樣的蟲豸為伍怎么可能限好流，它汲取了TCP滑動(dòng)窗口的靈感，設(shè)計(jì)出時(shí)間滑動(dòng)窗口。經(jīng)常刷算法題的同學(xué)應(yīng)該還是比較清楚滑動(dòng)窗口，總結(jié)來說，就是維持時(shí)間滑動(dòng)窗口內(nèi)的請(qǐng)求數(shù)<=閾值，當(dāng)請(qǐng)求數(shù)超過閾值的時(shí)候，時(shí)間窗口后面的所有請(qǐng)求都會(huì)拋棄。所謂的滑動(dòng)時(shí)間窗口，當(dāng)你滑動(dòng)到最新的時(shí)間片段，就會(huì)把最前面的時(shí)間片段給拋棄，它就像一個(gè)固定長度的隊(duì)列一樣，假設(shè)長度為一分鐘，我們把這一分鐘分為60個(gè)時(shí)間片段，也就是每個(gè)時(shí)間片段1s，窗口往前滑動(dòng)一個(gè)時(shí)間片段，就會(huì)拋棄最后面那個(gè)時(shí)間片段。類似于隊(duì)頭入隊(duì)一個(gè)元素，隊(duì)尾就要出隊(duì)一個(gè)元素，始終維持這個(gè)窗口大小不變。同時(shí)在滑動(dòng)的過程中統(tǒng)計(jì)時(shí)間片段的請(qǐng)求數(shù)。其實(shí)我們可以發(fā)現(xiàn)，其實(shí)我們?cè)O(shè)置時(shí)間片段的大小確實(shí)會(huì)影響滑動(dòng)時(shí)間窗口算法的精確性，我們時(shí)間片段越小，每次向前滑動(dòng)的步子越小，限流的統(tǒng)計(jì)就會(huì)越精確。我們微服務(wù)體系中的sentinel框架就是基于這種限流算法來實(shí)現(xiàn)的，

二哥雖然解決了一哥存在的臨界值問題，但是它真的是完美的嗎？滑動(dòng)時(shí)間窗口限流算***記錄每次合法請(qǐng)求的時(shí)刻日志，然后靠當(dāng)前請(qǐng)求時(shí)間與時(shí)間窗口大小做一個(gè)范圍查詢數(shù)據(jù)并求和，來判斷是否超過閾值。在較高閾值和小時(shí)間片段的情況下，其實(shí)通過窗口累積求和的方式是不夠高效的，特別是我們處于高并發(fā)這種場景下，對(duì)效率的要求更高?；诖?，我們的三哥和四哥出現(xiàn)了。

漏桶算法

三哥漏桶算法其實(shí)非常好理解，所謂的漏桶就是一個(gè)底部漏水的桶，我們的請(qǐng)求可以類比成桶里的水，桶的大小是固定的，請(qǐng)求進(jìn)桶的速度是不固定的，只有漏桶底部放出去的請(qǐng)求速度是固定的

漏桶

額，不好意思是下面這張圖：

漏桶算法

令牌桶算法

四哥它和三哥不同的是，它是以恒定的速度在木桶中加入令牌，木桶滿了則不再加入令牌。每個(gè)請(qǐng)求過來都嘗試從木桶中取出一個(gè)令牌，請(qǐng)求拿著令牌去繼續(xù)執(zhí)行后續(xù)的業(yè)務(wù)邏輯。沒有拿到令牌的請(qǐng)求直接就會(huì)被丟棄，不繼續(xù)執(zhí)行后續(xù)的業(yè)務(wù)邏輯。上面的秒殺場景中，在秒殺之前我令牌桶有一滿桶的令牌等著你用，秒殺時(shí)一瞬間大量的請(qǐng)求跑進(jìn)來，此時(shí)我令牌桶中的令牌可以瞬間被取出，立馬就可以應(yīng)付大量的請(qǐng)求并且反饋給用戶。之后的請(qǐng)求等我令牌桶慢慢放入令牌才能處理?？梢杂行幚頍狳c(diǎn)場景的突發(fā)流量。

令牌桶算法

總結(jié)：限流算法沒有優(yōu)秀之分，它們適用的場景不一樣。在面試的過程中，如果涉及到你的項(xiàng)目中用到的限流的算法，如果能把原理和面試官抽絲剝繭講清楚，也能給面試官印象分拉滿。讓面試官知道你不僅僅停留在會(huì)用這個(gè)階段。

我是小白，今天的分享到此結(jié)束了，如果帖子中寫的有什么錯(cuò)誤，歡迎大家在評(píng)論區(qū)指正，大家一起學(xué)習(xí)一起進(jìn)步。碼字這么久了，大家給個(gè)一鍵三連吧，后續(xù)我會(huì)繼續(xù)更新怎么吃透一個(gè)項(xiàng)目系列，希望大家能追更哦，你的點(diǎn)贊和收藏是我更新的動(dòng)力。

一鍵三連