目錄

前言

限流的作用

4種常見(jiàn)限流算法

固定窗口限流

基本原理

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

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

滑動(dòng)窗口限流

基本原理

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

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

漏桶限流

基本原理

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

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

令牌桶限流

基本原理

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

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

算法比較與選擇

---

前言

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

限流的作用

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

4種常見(jiàn)限流算法

固定窗口限流

基本原理

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

簡(jiǎn)單實(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      請(qǐng)求限制數(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è)請(qǐng)求，初始化窗口并設(shè)置過(guò)期時(shí)間if (count == 1) {// 窗口時(shí)長(zhǎng)設(shè)置為1秒counter.expire(windowSize, TimeUnit.SECONDS);}// 如果請(qǐng)求數(shù)量超過(guò)限制，觸發(fā)限流if (count > limit) {// 觸發(fā)限流的不記在請(qǐng)求數(shù)量中counter.decrementAndGet();// 執(zhí)行限流邏輯}// 請(qǐng)求通過(guò)，繼續(xù)處理業(yè)務(wù)邏輯} finally {rLock.unlock();}}
}

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

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

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

滑動(dòng)窗口限流

基本原理

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

簡(jiǎn)單實(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      請(qǐng)求限制數(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;// 移除窗口外的請(qǐng)求（即移除時(shí)間小于窗口起始時(shí)間的請(qǐng)求）counter.removeRangeByScore(0, true, windowStartTimestamp, false);// 將當(dāng)前時(shí)間戳作為score和member存入有序集合中counter.add(currentTimestamp, currentTimestamp);// 獲取當(dāng)前窗口內(nèi)的請(qǐng)求數(shù)量long count = counter.size();// 判斷是否超過(guò)限流閾值if (count > limit) {// 執(zhí)行限流邏輯}// 請(qǐng)求通過(guò)，繼續(xù)處理業(yè)務(wù)邏輯} finally {rLock.unlock();}}
}

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

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

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

缺點(diǎn)：

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

漏桶限流

基本原理

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

簡(jiǎn)單實(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)前請(qǐng)求的水位桶RBucket<Long> bucket = redissonClient.getBucket(KEY_PREFIX + key);// 獲取最后一次漏出請(qǐng)求的時(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ì)算自上次漏出以來(lái)經(jīng)過(guò)的時(shí)間long timeElapsed = currentTime - lastLeakTime;// 計(jì)算漏出的請(qǐng)求數(shù)量long leakedAmount = timeElapsed / leakRate;// 更新水位if (leakedAmount > 0) {// 更新水位，確保不為負(fù)currentWaterLevel = Math.max(0, currentWaterLevel - leakedAmount);// 更新最后漏出時(shí)間lastLeakTimeBucket.set(currentTime);}// 檢查是否可以接受新的請(qǐng)求if (currentWaterLevel < bucketSize) {// 接受請(qǐng)求，水位加一bucket.set(currentWaterLevel + 1);// 請(qǐng)求通過(guò)，繼續(xù)處理業(yè)務(wù)邏輯} // 觸發(fā)限流邏輯} finally {lock.unlock();}}
}

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

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

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

缺點(diǎn)：

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

令牌桶限流

基本原理

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

簡(jiǎn)單實(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è)置令牌桶限流器的限流效果：如限流的類(lèi)型、每個(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í)行失敗后的操作....}// 請(qǐng)求通過(guò)，繼續(xù)處理業(yè)務(wù)邏輯}
}

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

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

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

缺點(diǎn)：

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

算法比較與選擇

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

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

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

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