目錄

前言

限流的作用

4種常見限流算法

固定窗口限流

基本原理

簡單實(shí)現(xiàn)

優(yōu)點(diǎn)和缺點(diǎn)

滑動(dòng)窗口限流

基本原理

簡單實(shí)現(xiàn)

優(yōu)點(diǎn)和缺點(diǎn)

漏桶限流

基本原理

簡單實(shí)現(xiàn)

優(yōu)點(diǎn)和缺點(diǎn)

令牌桶限流

基本原理

簡單實(shí)現(xiàn)

優(yōu)點(diǎn)和缺點(diǎn)

算法比較與選擇

---

前言

在現(xiàn)代分布式系統(tǒng)和高并發(fā)場景下，限流已成為保障系統(tǒng)穩(wěn)定性和可用性的重要手段。隨著互聯(lián)網(wǎng)應(yīng)用規(guī)模的不斷擴(kuò)大，系統(tǒng)經(jīng)常會(huì)面對海量請求和突發(fā)流量，如何有效控制和管理這些請求流量成為一項(xiàng)關(guān)鍵挑戰(zhàn)。限流算法作為流量控制的重要工具，能夠幫助系統(tǒng)平衡資源分配、抵御惡意攻擊，并在高峰期維持服務(wù)的連續(xù)性與可靠性。本文將深入探討幾種常見的限流算法及其應(yīng)用場景，幫助讀者更好地理解限流機(jī)制的工作原理與優(yōu)化策略。

限流的作用

限流的作用在于防止系統(tǒng)過載、保障服務(wù)的可用性、優(yōu)化資源利用、平滑高峰流量，并確保服務(wù)質(zhì)量和用戶體驗(yàn)。通過控制請求的頻率，限流機(jī)制能夠在高并發(fā)或突發(fā)流量的情況下保護(hù)系統(tǒng)資源，提升其整體性能和響應(yīng)能力，從而避免系統(tǒng)崩潰或服務(wù)中斷。

4種常見限流算法

固定窗口限流

基本原理

計(jì)數(shù)器算法是在一定的時(shí)間間隔里，記錄請求次數(shù)，當(dāng)請求次數(shù)超過間隔內(nèi)的最大次數(shù)時(shí)，觸發(fā)限流策略。當(dāng)進(jìn)入下一個(gè)時(shí)間窗口時(shí)進(jìn)行訪問次數(shù)的清零。例如，如果設(shè)置了1秒鐘內(nèi)最多允許100個(gè)請求的上限，那么系統(tǒng)會(huì)統(tǒng)計(jì)當(dāng)前窗口內(nèi)的請求數(shù)量，當(dāng)請求數(shù)量未達(dá)到上限時(shí)，允許請求通過，一旦達(dá)到上限，則拒絕剩余的請求，直到進(jìn)入下一個(gè)時(shí)間窗口為止，在新的時(shí)間窗口開始時(shí)，計(jì)數(shù)器會(huì)被重置，重新統(tǒng)計(jì)請求數(shù)量。如下圖所示：

簡單實(shí)現(xiàn)

import org.redisson.api.*;
import org.springframework.stereotype.Service;import javax.annotation.Resource;
import java.util.concurrent.TimeUnit;@Service
public class RedisLimiterManager {@ResourceRedissonClient redissonClient;/*** 限流操作** @param key        限流鍵* @param limit      請求限制數(shù)量* @param windowSize 窗口大小*/public void doRateLimit(String key, Long limit, Long windowSize) {// 加分布式鎖RLock rLock = redissonClient.getLock(key);try {// 加鎖rLock.lock(100, TimeUnit.MILLISECONDS);// 獲取原子計(jì)數(shù)器RAtomicLong counter = redissonClient.getAtomicLong(key);// 計(jì)數(shù)long count = counter.incrementAndGet();// 如果是第一個(gè)請求，初始化窗口并設(shè)置過期時(shí)間if (count == 1) {// 窗口時(shí)長設(shè)置為1秒counter.expire(windowSize, TimeUnit.SECONDS);}// 如果請求數(shù)量超過限制，觸發(fā)限流if (count > limit) {// 觸發(fā)限流的不記在請求數(shù)量中counter.decrementAndGet();// 執(zhí)行限流邏輯}// 請求通過，繼續(xù)處理業(yè)務(wù)邏輯} finally {rLock.unlock();}}
}

優(yōu)點(diǎn)和缺點(diǎn)

優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，易于理解。

缺點(diǎn)：存在明顯的臨界問題，比如: 假設(shè)限流閥值為5個(gè)請求，單位時(shí)間窗口是1s,如果我們在單位時(shí)間內(nèi)的前0.8-1s和1-1.2s，分別并發(fā)5個(gè)請求。雖然都沒有超過閥值，但是如果算0.8-1.2s,則并發(fā)數(shù)高達(dá)10，已經(jīng)超過單位時(shí)間1s不超過5閥值的定義啦。

滑動(dòng)窗口限流

基本原理

滑動(dòng)窗口顧名思義，就是持續(xù)的滑動(dòng)，它的窗口大小是固定的，但是起止時(shí)間是動(dòng)態(tài)的，窗口大小被分割成大小相等的若干子窗口，每次滑動(dòng)，都會(huì)滑過一個(gè)子窗口，同時(shí)每個(gè)子窗口單獨(dú)計(jì)數(shù)，并且所有子窗口的計(jì)數(shù)求和不應(yīng)大于整體窗口的閾值。這樣的話，當(dāng)新請求的時(shí)間點(diǎn)大于時(shí)間窗口右邊界時(shí)，窗口右移一個(gè)子窗口，最左邊的子窗口的計(jì)數(shù)值舍棄。 例如，如果設(shè)定的限流策略是“每秒鐘最多允許100個(gè)請求”，那么系統(tǒng)會(huì)不斷滑動(dòng)地統(tǒng)計(jì)過去1秒內(nèi)的請求次數(shù)。如果請求次數(shù)未達(dá)到上限，允許請求通過；否則拒絕請求。如下圖所示：

簡單實(shí)現(xiàn)

import org.redisson.api.*;
import org.springframework.stereotype.Service;import javax.annotation.Resource;
import java.util.concurrent.TimeUnit;@Service
public class RedisLimiterManager {@ResourceRedissonClient redissonClient;/*** 限流操作** @param key        限流鍵* @param limit      請求限制數(shù)量* @param windowSize 窗口大小*/public void doRateLimit(String key, Long limit, Long windowSize) {// 獲取計(jì)數(shù)的有序集合RScoredSortedSet<Long> counter = redissonClient.getScoredSortedSet(key);// 使用分布式鎖RLock rLock = redissonClient.getLock(key);try {// 加鎖rLock.lock(200, TimeUnit.MILLISECONDS);// 當(dāng)前時(shí)間戳long currentTimestamp = System.currentTimeMillis();// 窗口起始時(shí)間戳long windowStartTimestamp = currentTimestamp - windowSize * 1000;// 移除窗口外的請求（即移除時(shí)間小于窗口起始時(shí)間的請求）counter.removeRangeByScore(0, true, windowStartTimestamp, false);// 將當(dāng)前時(shí)間戳作為score和member存入有序集合中counter.add(currentTimestamp, currentTimestamp);// 獲取當(dāng)前窗口內(nèi)的請求數(shù)量long count = counter.size();// 判斷是否超過限流閾值if (count > limit) {// 執(zhí)行限流邏輯}// 請求通過，繼續(xù)處理業(yè)務(wù)邏輯} finally {rLock.unlock();}}
}

優(yōu)點(diǎn)和缺點(diǎn)

優(yōu)點(diǎn)：

• 簡單易懂，精度較高，也解決了固定窗口的臨界時(shí)間處理問題。

缺點(diǎn)：

• 突發(fā)流量無法處理，一旦到達(dá)限流后，請求都會(huì)直接暴力被拒絕，影響用戶的體驗(yàn)。

漏桶限流

基本原理

漏桶算法可以形象地理解為一個(gè)固定容量的水桶，水以不規(guī)則的速度流入桶中，但以固定的速率從桶底漏出。假設(shè)水桶的容量是固定的，如果水流入的速度超過了漏出的速度，且水桶已滿，多余的水（請求）將被丟棄。如下圖所示：

簡單實(shí)現(xiàn)

import org.redisson.api.*;
import org.springframework.stereotype.Service;import javax.annotation.Resource;
import java.util.concurrent.TimeUnit;@Service
public class RedisLimiterManager {private static final String KEY_PREFIX = "leakyBucketRateLimiter:";@ResourceRedissonClient redissonClient;/*** 限流操作** @param key        限流鍵* @param leakRate   漏出速率* @param bucketSize 桶的容量*/public void doRateLimit(String key, Long leakRate, Long bucketSize) {// 獲取當(dāng)前請求的水位桶RBucket<Long> bucket = redissonClient.getBucket(KEY_PREFIX + key);// 獲取最后一次漏出請求的時(shí)間RBucket<Long> lastLeakTimeBucket = redissonClient.getBucket(KEY_PREFIX + key + ":lastLeakTime");// 創(chuàng)建分布式鎖RLock lock = redissonClient.getLock(KEY_PREFIX + "LOCK:" + key);try {// 嘗試獲取鎖lock.lock(100, TimeUnit.MILLISECONDS);// 當(dāng)前時(shí)間戳long currentTime = System.currentTimeMillis();// 當(dāng)前水位Long currentWaterLevel = bucket.get();// 上次漏出時(shí)間Long lastLeakTime = lastLeakTimeBucket.get();// 初始化水位和漏出時(shí)間if (currentWaterLevel == null) {currentWaterLevel = 0L;}if (lastLeakTime == null) {lastLeakTime = currentTime;}// 計(jì)算自上次漏出以來經(jīng)過的時(shí)間long timeElapsed = currentTime - lastLeakTime;// 計(jì)算漏出的請求數(shù)量long leakedAmount = timeElapsed / leakRate;// 更新水位if (leakedAmount > 0) {// 更新水位，確保不為負(fù)currentWaterLevel = Math.max(0, currentWaterLevel - leakedAmount);// 更新最后漏出時(shí)間lastLeakTimeBucket.set(currentTime);}// 檢查是否可以接受新的請求if (currentWaterLevel < bucketSize) {// 接受請求，水位加一bucket.set(currentWaterLevel + 1);// 請求通過，繼續(xù)處理業(yè)務(wù)邏輯} // 觸發(fā)限流邏輯} finally {lock.unlock();}}
}

優(yōu)點(diǎn)和缺點(diǎn)

優(yōu)點(diǎn)：

• 既能夠限流，還能夠平滑控制處理速度。

缺點(diǎn)：

• 需要對請求進(jìn)行緩存，會(huì)增加服務(wù)器的內(nèi)存消耗。
• 無法應(yīng)對突然激增的流量，因?yàn)橹荒芤怨潭ǖ乃俾侍幚碚埱?#xff0c;對系統(tǒng)資源利用不夠友好。
• 桶流入水（發(fā)請求）的速率如果一直大于桶流出水（處理請求）的速率的話，那么桶會(huì)一直是滿的，一部分新的請求會(huì)被丟棄，導(dǎo)致服務(wù)質(zhì)量下降。

令牌桶限流

基本原理

令牌桶算法以恒定的速率生成令牌并放入桶中，令牌數(shù)不會(huì)超過桶容量，當(dāng)有請求到來時(shí)，會(huì)嘗試申請一塊令牌，如果沒有令牌則會(huì)拒絕請求，有足夠的令牌則會(huì)處理請求，并且減少桶內(nèi)令牌數(shù)。如下圖所示：

簡單實(shí)現(xiàn)

import org.redisson.api.*;
import org.springframework.stereotype.Service;import javax.annotation.Resource;@Service
public class RedisLimiterManager {@ResourceRedissonClient redissonClient;/*** 限流操作** @param key 限流鍵*/public void doRateLimit(String key) {RRateLimiter rRateLimiter = redissonClient.getRateLimiter(key);// 設(shè)置令牌桶限流器的限流效果：如限流的類型、每個(gè)限流時(shí)間窗口內(nèi)生成的令牌數(shù)量、速率的時(shí)間間隔和時(shí)間間隔的單位。rRateLimiter.trySetRate(RateType.OVERALL, 2, 1, RateIntervalUnit.SECONDS);// 嘗試獲取 1 個(gè)令牌boolean canOp = rRateLimiter.tryAcquire(1);if (!canOp) {// 獲取令牌失敗// 執(zhí)行失敗后的操作....}// 請求通過，繼續(xù)處理業(yè)務(wù)邏輯}
}

優(yōu)點(diǎn)和缺點(diǎn)

優(yōu)點(diǎn)：

• 面對突發(fā)流量，可以在短時(shí)間內(nèi)提供更多的處理能力，以處理突發(fā)流量。
• 與漏桶算法相比，令牌桶算法提供了更大的靈活性，可以動(dòng)態(tài)調(diào)整生成令牌的速率。

缺點(diǎn)：

• 如果令牌產(chǎn)生速率和桶的容量設(shè)置不合理，可能會(huì)出現(xiàn)問題比如大量的請求被丟棄、系統(tǒng)過載。

算法比較與選擇

固定窗口算法：業(yè)務(wù)簡單，對突發(fā)流量要求不高的場景。

滑動(dòng)窗口算法：需要精確控制請求速率，平滑限流時(shí)使用。

漏桶算法：適合對流量有嚴(yán)格平穩(wěn)要求的場景，尤其是在處理突發(fā)請求能力有限、系統(tǒng)必須穩(wěn)定輸出流量的情況下。

令牌桶算法：對突發(fā)流量有要求，對穩(wěn)定性和精度要求較高的場景。