前言

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

考察點

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

回答  

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

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

 計數器限流算法的實現原理是在一個時間窗口內，每調用一次就增加計數器，當時間窗口到達設定的時間后，計數器歸零。如果在時間窗口內再次調用，則計數器再次增加。這種算法的優(yōu)點是實現簡單，但是存在臨界問題。如果在一個時間窗口內的最后一次調用正好在時間窗口結束的瞬間，那么這個請求會被拒絕，因為計數器已經歸零。為了解決這個問題，可以采用滑動窗口限流算法。該算法將時間窗口劃分為多個小的時間段，每個時間段都有一個獨立的計數器。當一個時間段結束時，該時間段的計數器歸零，而其他時間段的計數器保持不變。這樣就可以避免在時間窗口結束的瞬間出現請求被拒絕的情況。

圖片

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

圖片

3. （如圖)漏桶算法，它是一種恒定速率的限流算法，不管請求量是多少，服務端的處理效率是恒定的。基于 MQ 來實現的生產者消費者模型，其實算是一種漏桶限流算法。

圖片

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

以上就是我對于這個問題的理解。