前言

今天來(lái)分享一道比較好的面試題，“常見(jiàn)的限流算法有哪些？”對(duì)于這個(gè)問(wèn)題，我們一起看看考察點(diǎn)和比較好的回答吧！

考察點(diǎn)

限流算法是一種用于限制流量請(qǐng)求的頻率或速率的算法，其目的是在高并發(fā)或大流量請(qǐng)求的情況下，保護(hù)系統(tǒng)服務(wù)的安全性和可用性。限流算法可以應(yīng)對(duì)熱點(diǎn)業(yè)務(wù)帶來(lái)的突發(fā)請(qǐng)求、調(diào)用方bug導(dǎo)致的突發(fā)請(qǐng)求以及惡意攻擊請(qǐng)求等情況。這個(gè)問(wèn)題就是面試官想考察我們是不是平日里善于積累，仔細(xì)思考這方面的知識(shí)！

回答  

首先，限流算法是一種系統(tǒng)保護(hù)策略，主要是避免在流量高峰導(dǎo)致系統(tǒng)被壓垮，造成系統(tǒng)不可用的問(wèn)題。常考的算法有以下幾種。

1. （如圖）計(jì)數(shù)器限流，一般用在單一維度的訪問(wèn)頻率限制上，比如短信驗(yàn)證碼每隔60s 只能發(fā)送一次，或者接口調(diào)用次數(shù)等。它的實(shí)現(xiàn)方法很簡(jiǎn)單，每調(diào)用一次就加 1，處理結(jié)束以后減一。

 計(jì)數(shù)器限流算法的實(shí)現(xiàn)原理是在一個(gè)時(shí)間窗口內(nèi)，每調(diào)用一次就增加計(jì)數(shù)器，當(dāng)時(shí)間窗口到達(dá)設(shè)定的時(shí)間后，計(jì)數(shù)器歸零。如果在時(shí)間窗口內(nèi)再次調(diào)用，則計(jì)數(shù)器再次增加。這種算法的優(yōu)點(diǎn)是實(shí)現(xiàn)簡(jiǎn)單，但是存在臨界問(wèn)題。如果在一個(gè)時(shí)間窗口內(nèi)的最后一次調(diào)用正好在時(shí)間窗口結(jié)束的瞬間，那么這個(gè)請(qǐng)求會(huì)被拒絕，因?yàn)橛?jì)數(shù)器已經(jīng)歸零。為了解決這個(gè)問(wèn)題，可以采用滑動(dòng)窗口限流算法。該算法將時(shí)間窗口劃分為多個(gè)小的時(shí)間段，每個(gè)時(shí)間段都有一個(gè)獨(dú)立的計(jì)數(shù)器。當(dāng)一個(gè)時(shí)間段結(jié)束時(shí)，該時(shí)間段的計(jì)數(shù)器歸零，而其他時(shí)間段的計(jì)數(shù)器保持不變。這樣就可以避免在時(shí)間窗口結(jié)束的瞬間出現(xiàn)請(qǐng)求被拒絕的情況。

圖片

2. （如圖）滑動(dòng)窗口限流，本質(zhì)上也是一種計(jì)數(shù)器，只是通過(guò)以時(shí)間為維度的可滑動(dòng)窗口設(shè)計(jì)，來(lái)減少了臨界值帶來(lái)的并發(fā)超過(guò)閾值的問(wèn)題。每次進(jìn)行數(shù)據(jù)統(tǒng)計(jì)的時(shí)候，只需要統(tǒng)計(jì)這個(gè)窗口內(nèi)每個(gè)時(shí)間刻度的訪問(wèn)量就可以了。Spring Cloud里面的熔斷框架Hystrix ，以及Spring Cloud Alibaba里面的Sentinel都采用了滑動(dòng)窗口來(lái)做數(shù)據(jù)統(tǒng)計(jì)。

圖片

3. （如圖)漏桶算法，它是一種恒定速率的限流算法，不管請(qǐng)求量是多少，服務(wù)端的處理效率是恒定的。基于 MQ 來(lái)實(shí)現(xiàn)的生產(chǎn)者消費(fèi)者模型，其實(shí)算是一種漏桶限流算法。

圖片

4. （如圖）令牌桶算法，相對(duì)漏桶算法來(lái)說(shuō)，它可以處理突發(fā)流量的問(wèn)題。它的核心思想是，令牌桶以恒定速率去生成令牌保存到令牌桶里面，桶的大小是固定的，令牌桶滿了以后就不再生成令牌。每個(gè)客戶端請(qǐng)求進(jìn)來(lái)的時(shí)候，必須要從令牌桶獲得一個(gè)令牌才能訪問(wèn)，否則排隊(duì)等待。在流量低峰的時(shí)候，令牌桶會(huì)出現(xiàn)堆積，因此當(dāng)出現(xiàn)瞬時(shí)高峰的時(shí)候，有足夠多的令牌可以獲取，因此令牌桶能夠允許瞬時(shí)流量的處理。網(wǎng)關(guān)層面的限流、或者接口調(diào)用的限流，都可以使用令牌桶算法，像 Google 的 Guava，和 Redisson 的限流，都用到了令牌桶算法在我看來(lái)，限流的本質(zhì)是實(shí)現(xiàn)系統(tǒng)保護(hù)，最終選擇什么樣的算法，一方面取決于統(tǒng)計(jì)的精準(zhǔn)度，另一方面考慮限流維度和場(chǎng)景的需求。

以上就是我對(duì)于這個(gè)問(wèn)題的理解。