面試官:限流算法有哪些?
限流的實現(xiàn)算法有很多,但常見的限流算法有三種:計數(shù)器算法、漏桶算法和令牌桶算法。
1、計數(shù)器算法
計數(shù)器算法是在一定的時間間隔里,記錄請求次數(shù),當請求次數(shù)超過該時間限制時,就把計數(shù)器清零,然后重新計算。當請求次數(shù)超過間隔內(nèi)的最大次數(shù)時,拒絕訪問。
計數(shù)器算法的實現(xiàn)比較簡單,但存在“突刺現(xiàn)象”。
突刺現(xiàn)象是指,比如限流 QPS(每秒查詢率)為 100,算法的實現(xiàn)思路就是從第一個請求進來開始計時,在接下來的 1 秒內(nèi),每來一個請求,就把計數(shù)加 1,如果累加的數(shù)字達到了 100,后續(xù)的請求就會被全部拒絕。等到 1 秒結(jié)束后,把計數(shù)恢復成 0,重新開始計數(shù)。如果在單位時間 1 秒內(nèi)的前 10 毫秒處理了 100 個請求,那么后面的 990 毫秒會請求拒絕所有的請求,我們把這種現(xiàn)象稱為“突刺現(xiàn)象”。
計數(shù)器算法的簡單實現(xiàn)代碼如下:
2、漏桶算法
漏桶算法的實現(xiàn)思路是,有一個固定容量的漏桶,水流(請求)可以按照任意速率先進入到漏桶里,但漏桶總是以固定的速率勻速流出,當流入量過大的時候(超過桶的容量),則多余水流(請求)直接溢出。如下圖所示:
漏桶算法提供了一種機制,通過它可以讓突發(fā)流量被整形,以便為系統(tǒng)提供穩(wěn)定的請求,比如 Sentinel 中流量整形(勻速排隊功能)就是此算法實現(xiàn)的,如下圖所示:
更多 Sentinel 內(nèi)容詳見:https://mp.weixin.qq.com/s/nF5f18BP8hscqIEmIFRN8Q。
3、令牌桶算法
令牌按固定的速率被放入令牌桶中,桶中最多存放 N 個令牌(Token),當桶裝滿時,新添加的令牌被丟棄或拒絕。當請求到達時,將從桶中刪除 1 個令牌。令牌桶中的令牌不僅可以被移除,還可以往里添加,所以為了保證接口隨時有數(shù)據(jù)通過,必須不停地往桶里加令牌。由此可見,往桶里加令牌的速度就決定了數(shù)據(jù)通過接口的速度。我們通過控制往令牌桶里加令牌的速度從而控制接口的流量。令牌桶的實現(xiàn)原理如下圖所示:
4、漏桶算法 VS 令牌桶算法
漏桶算法是按照常量固定速率流出請求的,流入請求速率任意,當流入的請求數(shù)累積到漏桶容量時,新流入的請求被拒絕。令牌桶算法是按照固定速率往桶中添加令牌的,請求是否被處理需要看桶中的令牌是否足夠,當令牌數(shù)減為零時,拒絕新的請求。令牌桶算法允許突發(fā)請求,只要有令牌就可以處理,允許一定程度的突發(fā)流量。漏桶算法限制的是常量流出速率,從而使突發(fā)流入速率平滑。
比如服務器空閑時,理論上使用漏桶算法服務器可以直接處理一次洪峰(一次洪水過程的最大流量),但是漏桶算法處理請求的速率是恒定的,因此,前期服務器資源只能根據(jù)恒定的漏水速度逐步處理請求,無法直接處理這次洪峰。而使用令牌桶算法就不存在這個問題,因為它可以先把令牌桶一次性裝滿,處理一次洪峰之后再走限流。
總結(jié)
限流的常見算法有以下 3 種:
- 計數(shù)器算法:實現(xiàn)簡單,但有突刺現(xiàn)象;
- 漏桶算法:固定速率處理請求,處理任意流量更加平滑,可以實現(xiàn)流量整形;
- 令牌桶算法:通過控制桶中的令牌實現(xiàn)限流,可以處理一定的突發(fā)流量,比如處理一次洪峰。
參考 & 鳴謝
《分布式微服務架構(gòu)》
https://blog.csdn.net/chengqiuming/article/details/122385943。