前言

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

考察點(diǎn)

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

回答  

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

1. （如圖）計(jì)數(shù)器限流，一般用在單一維度的訪問頻率限制上，比如短信驗(yàn)證碼每隔60s 只能發(fā)送一次，或者接口調(diào)用次數(shù)等。它的實(shí)現(xià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)簡單，但是存在臨界問題。如果在一個(gè)時(shí)間窗口內(nèi)的最后一次調(diào)用正好在時(shí)間窗口結(jié)束的瞬間，那么這個(gè)請求會(huì)被拒絕，因?yàn)橛?jì)數(shù)器已經(jīng)歸零。為了解決這個(gè)問題，可以采用滑動(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)請求被拒絕的情況。

圖片

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

圖片

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

圖片

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

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