令牌桶VS漏桶：誰才是流量控制的“最優(yōu)解”？
大家好，我是小富～
面試被問到限流算法，很多面試官會(huì)讓直接手寫令牌桶和漏桶的實(shí)現(xiàn)。雖然平時(shí)用過Redis、Guava等現(xiàn)成的限流工具，但真要手寫還是有點(diǎn)慌。今天就來聊聊這兩種經(jīng)典限流算法的區(qū)別，并用Java手寫實(shí)現(xiàn)。
很多的限流工具底層都應(yīng)用了它們
一、令牌桶 vs 漏桶：核心區(qū)別
令牌桶
令牌桶的核心思想：固定容量的桶，以固定速率往桶里放令牌，請求來了就從桶拿令牌，沒令牌就拒絕。
有點(diǎn)像買票進(jìn)站，想去坐火車就先去售票窗口買票，買到票了就憑票進(jìn)入，買不到等待，因?yàn)榇翱跁?huì)定時(shí)的放票，再去搶。
下圖是用Ai生成的，大致能體現(xiàn)出這么個(gè)意思
令牌桶特點(diǎn)：
1、可以處理突發(fā)流量（桶里有令牌就能用），因?yàn)椴⒉皇且恢闭埱蠖己芏啵珪?huì)一直以固定速率向桶里添加令牌，請求少時(shí)桶內(nèi)令牌滿了，請求激增可以滿桶拿令牌頂一陣
2、原理和實(shí)現(xiàn)上相對簡單
3、內(nèi)存占用小
漏桶適用場景：
接口限流：保護(hù)業(yè)務(wù)系統(tǒng)或者敏感接口
防止惡意攻擊：抵御Dos或DDos攻擊
……
它的優(yōu)勢在于能夠限制平均速率，同時(shí)允許一定的突發(fā)流量
漏桶
漏桶的核心思想比令牌桶早更簡單：請求像水一樣流入桶中，桶以固定速率“漏水”處理請求，超出桶容量的請求被丟棄或排隊(duì)。
漏桶的特點(diǎn)：
1、輸出非常平滑穩(wěn)定
2、能有效保護(hù)下游系統(tǒng)（流量平滑）
3、? 無法處理突發(fā)流量
4、? 可能造成請求延遲
漏桶適用場景：
數(shù)據(jù)庫連接池：保護(hù)數(shù)據(jù)庫不被過載
消息隊(duì)列消費(fèi)：控制消費(fèi)速率
支付系統(tǒng)：確保支付處理穩(wěn)定性
二、手寫實(shí)現(xiàn)
令牌桶實(shí)現(xiàn)
public class TokenBucket {
// 桶容量（最大令牌數(shù)）
privatefinallong capacity;
// 令牌填充速率（令牌/秒）
privatefinallong refillRate;
// 當(dāng)前令牌數(shù)量
private AtomicLong tokens;
// 上次填充時(shí)間戳（納秒）
privatelong lastRefillTime;
public TokenBucket(long capacity, long refillRate) {
this.capacity = capacity;
this.refillRate = refillRate;
this.tokens = new AtomicLong(capacity);
this.lastRefillTime = System.nanoTime();
}
// 示例使用
public static void main(String[] args) throws InterruptedException {
// 創(chuàng)建桶：容量10令牌，每秒填充5令牌
TokenBucket bucket = new TokenBucket(10, 2);
// 模擬請求
for (int i = 1; i <= 50; i++) {
if (bucket.tryAcquire()) {
System.out.println("請求" + i + ": 通過");
} else {
System.out.println("請求" + i + ": 限流");
}
Thread.sleep(100); // 100ms請求一次
}
}
/**
* 嘗試獲取令牌
*
* @return true-獲取成功，false-被限流
*/
public synchronized boolean tryAcquire() {
refillTokens();
if (tokens.get() > 0) {
tokens.decrementAndGet();
returntrue;
}
returnfalse;
}
/**
* 嘗試獲取多個(gè)令牌
*
* @param numTokens 請求令牌數(shù)
*/
public synchronized boolean tryAcquire(int numTokens) {
refillTokens();
if (tokens.get() >= numTokens) {
tokens.addAndGet(-numTokens);
returntrue;
}
returnfalse;
}
// 根據(jù)時(shí)間差補(bǔ)充令牌
private void refillTokens() {
long now = System.nanoTime();
// 計(jì)算時(shí)間差（秒）
double elapsedSec = (now - lastRefillTime) * 1e-9;
// 計(jì)算應(yīng)補(bǔ)充的令牌數(shù)
long tokensToAdd = (long) (elapsedSec * refillRate);
if (tokensToAdd > 0) {
tokens.set(Math.min(capacity, tokens.get() + tokensToAdd));
lastRefillTime = now;
}
}
}
-
使用 AtomicLong 保證線程安全。
-
通過時(shí)間差動(dòng)態(tài)計(jì)算補(bǔ)充的令牌數(shù)。
-
桶容量限制突發(fā)流量的最大值。
漏桶實(shí)現(xiàn)
import java.util.concurrent.atomic.AtomicLong;
publicclass LeakyBucket {
// 桶容量（最大請求數(shù)）
privatefinallong capacity;
// 漏水速率（請求/秒）
privatefinallong leakRate;
// 當(dāng)前水量（待處理請求數(shù)）
private AtomicLong water;
// 上次漏水時(shí)間戳（毫秒）
privatelong lastLeakTime;
public LeakyBucket(long capacity, long leakRate) {
this.capacity = capacity;
this.leakRate = leakRate;
this.water = new AtomicLong(0);
this.lastLeakTime = System.currentTimeMillis();
}
// 示例使用
public static void main(String[] args) throws InterruptedException {
// 創(chuàng)建桶：容量5請求，每秒處理2請求
LeakyBucket bucket = new LeakyBucket(5, 1);
// 模擬請求
for (int i = 1; i <= 15; i++) {
if (bucket.tryPass()) {
System.out.println("請求" + i + ": 通過 (當(dāng)前水位: " + bucket.water.get() + ")");
} else {
System.out.println("請求" + i + ": 限流 (水位溢出)");
}
Thread.sleep(200); // 200ms請求一次
}
}
/**
* 嘗試通過漏桶
*
* @return true-允許通過，false-被限流
*/
public synchronized boolean tryPass() {
leakWater();
if (water.get() < capacity) {
water.incrementAndGet();
returntrue;
}
returnfalse;
}
// 根據(jù)時(shí)間差漏水
private void leakWater() {
long now = System.currentTimeMillis();
// 計(jì)算時(shí)間差（秒）
long elapsedMs = now - lastLeakTime;
if (elapsedMs > 0) {
// 計(jì)算漏水量
long leaked = (long) (elapsedMs * leakRate / 1000.0);
if (leaked > 0) {
water.updateAndGet(cur -> Math.max(0, cur - leaked));
lastLeakTime = now;
}
}
}
}
-
漏出速率固定，確保請求處理平滑。
-
水量超過容量時(shí)直接拒絕請求。
三、測試對比
public class RateLimiterTest {
public static void main(String[] args) throws InterruptedException {
// 測試令牌桶：容量10，每秒填充5個(gè)令牌
TokenBucket tokenBucket = new TokenBucket(10, 5);
// 測試漏桶：容量10，每秒漏出5個(gè)請求
LeakyBucket leakyBucket = new LeakyBucket(10, 5);
System.out.println("=== 令牌桶測試（支持突發(fā)） ===");
testTokenBucket(tokenBucket);
Thread.sleep(1000);
System.out.println("\n=== 漏桶測試（平滑輸出） ===");
testLeakyBucket(leakyBucket);
}
private static void testTokenBucket(TokenBucket bucket) {
// 模擬突發(fā)請求
for (int i = 0; i < 15; i++) {
boolean success = bucket.tryConsume(1);
System.out.printf("請求%d: %s (當(dāng)前令牌: %.1f)%n",
i + 1, success ? "通過" : "拒絕", bucket.getCurrentTokens());
}
}
private static void testLeakyBucket(LeakyBucket bucket) {
// 模擬突發(fā)請求
for (int i = 0; i < 15; i++) {
boolean success = bucket.tryConsume();
System.out.printf("請求%d: %s (當(dāng)前水量: %.1f)%n",
i + 1, success ? "通過" : "拒絕", bucket.getCurrentWater());
}
}
}
四、面試要點(diǎn)總結(jié)
面試官可能會(huì)問的問題：
Q: 兩種算法的核心區(qū)別是什么？
A: 令牌桶允許突發(fā)，漏桶強(qiáng)制平滑輸出
Q: 什么場景用令牌桶，什么場景用漏桶？
A: 需要處理突發(fā)用令牌桶，需要保護(hù)下游用漏桶
Q: 如何選擇桶的容量和速率？
A: 根據(jù)業(yè)務(wù)峰值、系統(tǒng)承載能力、用戶體驗(yàn)綜合考慮
Q: 分布式環(huán)境下如何實(shí)現(xiàn)？
A: 可以用Redis實(shí)現(xiàn)，或者用一致性哈希分片
說在后邊
手寫限流算法是一般在高級別的面試中不太會(huì)出現(xiàn)，但它們的基礎(chǔ)概念要掌握，在考場景題時(shí)它們都是不錯(cuò)的方案。
簡單記：令牌桶像ATM機(jī)，有錢就能取；漏桶像水龍頭，固定流速出水。
完活！
浙公網(wǎng)安備 33010602011771號