百度面試：如何用Redis實(shí)現(xiàn)限流？
高并發(fā)系統(tǒng)有三大特征：限流、緩存和熔斷，所以限流已經(jīng)成為當(dāng)下系統(tǒng)開發(fā)中必備的功能了。那么，什么是限流？如何實(shí)現(xiàn)限流？使用 Redis 能不能實(shí)現(xiàn)限流？接下來(lái)我們一起來(lái)看。
1.什么是限流？
限流是指在各種應(yīng)用場(chǎng)景中，通過(guò)技術(shù)和策略手段對(duì)數(shù)據(jù)流量、請(qǐng)求頻率或資源消耗進(jìn)行有計(jì)劃的限制，以避免系統(tǒng)負(fù)載過(guò)高、性能下降甚至崩潰的情況發(fā)生。限流的目標(biāo)在于維護(hù)系統(tǒng)的穩(wěn)定性和可用性，并確保服務(wù)質(zhì)量。
使用限流有以下幾個(gè)好處：
- 保護(hù)系統(tǒng)穩(wěn)定性：過(guò)多的并發(fā)請(qǐng)求可能導(dǎo)致服務(wù)器內(nèi)存耗盡、CPU 使用率飽和，從而引發(fā)系統(tǒng)響應(yīng)慢、無(wú)法正常服務(wù)的問(wèn)題。
- 防止資源濫用：確保有限的服務(wù)資源被合理公平地分配給所有用戶，防止個(gè)別用戶或惡意程序過(guò)度消耗資源。
- 優(yōu)化用戶體驗(yàn)：對(duì)于網(wǎng)站和應(yīng)用程序而言，如果任由高并發(fā)導(dǎo)致響應(yīng)速度變慢，會(huì)影響所有用戶的正常使用體驗(yàn)。
- 保障安全：在網(wǎng)絡(luò)層面，限流有助于防范 DoS/DDoS 攻擊，降低系統(tǒng)遭受惡意攻擊的風(fēng)險(xiǎn)。
- 運(yùn)維成本控制：合理的限流措施可以幫助企業(yè)減少不必要的硬件投入，節(jié)省運(yùn)營(yíng)成本。
2.限流常見算法
限流的常見實(shí)現(xiàn)算法有以下幾個(gè)：
- 計(jì)數(shù)器算法：將時(shí)間周期劃分為固定大小的窗口（如每分鐘、每小時(shí)），并在每個(gè)窗口內(nèi)統(tǒng)計(jì)請(qǐng)求的數(shù)量。當(dāng)窗口內(nèi)的請(qǐng)求數(shù)達(dá)到預(yù)設(shè)的閾值時(shí)，后續(xù)請(qǐng)求將被限制。時(shí)間窗口結(jié)束后，計(jì)數(shù)器清零。
- 優(yōu)點(diǎn)：實(shí)現(xiàn)簡(jiǎn)單，易于理解。
- 缺點(diǎn)：在窗口切換時(shí)刻可能會(huì)有突刺流量問(wèn)題，即在窗口結(jié)束時(shí)會(huì)有短暫的大量請(qǐng)求被允許通過(guò)。
- 滑動(dòng)窗口算法：改進(jìn)了計(jì)算器算法（固定窗口算法）的突刺問(wèn)題，將時(shí)間窗口劃分為多個(gè)小的時(shí)間段（桶），每個(gè)小時(shí)間段有自己的計(jì)數(shù)器。隨著時(shí)間流逝，窗口像滑塊一樣平移，過(guò)期的小時(shí)間段的計(jì)數(shù)會(huì)被丟棄，新時(shí)間段加入計(jì)數(shù)。所有小時(shí)間段的計(jì)數(shù)之和不能超過(guò)設(shè)定的閾值。
優(yōu)點(diǎn)：更平滑地處理流量，避免了突刺問(wèn)題。
缺點(diǎn)：實(shí)現(xiàn)相對(duì)復(fù)雜，需要維護(hù)多個(gè)計(jì)數(shù)器。
漏桶算法：想象一個(gè)固定容量的桶，水（請(qǐng)求）以恒定速率流入桶中，同時(shí)桶底部有小孔讓水以恒定速率流出。當(dāng)桶滿時(shí)，新來(lái)的水（請(qǐng)求）會(huì)被丟棄。此算法主要用來(lái)平滑網(wǎng)絡(luò)流量，防止瞬時(shí)流量過(guò)大。
優(yōu)點(diǎn)：可以平滑突發(fā)流量，保證下游系統(tǒng)的穩(wěn)定。
缺點(diǎn)：無(wú)法處理突發(fā)流量高峰，多余的請(qǐng)求會(huì)被直接丟棄。
令牌桶算法：與漏桶相反，有一個(gè)固定速率填充令牌的桶，令牌代表請(qǐng)求許可。當(dāng)請(qǐng)求到達(dá)時(shí)，需要從桶中取出一個(gè)令牌，如果桶中有令牌則允許請(qǐng)求通過(guò)，否則拒絕。桶的容量是有限的，多余的令牌會(huì)被丟棄。
優(yōu)點(diǎn)：既能平滑流量，又能處理一定程度的突發(fā)流量（因?yàn)榱钆瓶梢岳鄯e）。
缺點(diǎn)：需要精確控制令牌生成速度，實(shí)現(xiàn)較漏桶復(fù)雜。
3.使用Redis實(shí)現(xiàn)限流
使用 Redis 也可以實(shí)現(xiàn)簡(jiǎn)單的限流，它的常見限流方法有以下幾種實(shí)現(xiàn)：
- 基于計(jì)數(shù)器和過(guò)期時(shí)間實(shí)現(xiàn)的計(jì)數(shù)器算法：使用一個(gè)計(jì)數(shù)器存儲(chǔ)當(dāng)前請(qǐng)求量（每次使用 incr 方法相加），并設(shè)置一個(gè)過(guò)期時(shí)間，計(jì)數(shù)器在一定時(shí)間內(nèi)自動(dòng)清零。計(jì)數(shù)器未到達(dá)限流值就可以繼續(xù)運(yùn)行，反之則不能繼續(xù)運(yùn)行。
- 基于有序集合（ZSet）實(shí)現(xiàn)的滑動(dòng)窗口算法：將請(qǐng)求都存入到 ZSet 集合中，在分?jǐn)?shù)（score）中存儲(chǔ)當(dāng)前請(qǐng)求時(shí)間。然后再使用 ZSet 提供的 range 方法輕易的獲取到 2 個(gè)時(shí)間戳內(nèi)的所有請(qǐng)求，通過(guò)獲取的請(qǐng)求數(shù)和限流數(shù)進(jìn)行比較并判斷，從而實(shí)現(xiàn)限流。
- 基于列表（List）實(shí)現(xiàn)的令牌桶算法：在程序中使用定時(shí)任務(wù)給 Redis 中的 List 添加令牌，程序通過(guò) List 提供的 leftPop 來(lái)獲取令牌，得到令牌繼續(xù)執(zhí)行，否則就是限流不能繼續(xù)運(yùn)行。
了解了以上概念后，接下來(lái)我們來(lái)看具體的實(shí)現(xiàn)。
3.1 計(jì)數(shù)器算法
此方法的實(shí)現(xiàn)思路是：使用一個(gè)計(jì)數(shù)器存儲(chǔ)當(dāng)前請(qǐng)求量（每次使用 incr 方法相加），并設(shè)置一個(gè)過(guò)期時(shí)間，計(jì)數(shù)器在一定時(shí)間內(nèi)自動(dòng)清零，從而實(shí)現(xiàn)限流。
它的具體操作步驟如下：
- 使用 Redis 的計(jì)數(shù)器保存當(dāng)前請(qǐng)求的數(shù)量。
- 設(shè)置一個(gè)過(guò)期時(shí)間，使得計(jì)數(shù)器在一定時(shí)間內(nèi)自動(dòng)清零。
- 每次收到請(qǐng)求時(shí)，檢查計(jì)數(shù)器當(dāng)前值，如果未達(dá)到限流閾值，則增加計(jì)數(shù)器的值，否則拒絕請(qǐng)求。
具體實(shí)現(xiàn)代碼如下：
import redis.clients.jedis.Jedis;
public class RedisRateLimiter {
private static final String REDIS_KEY = "request_counter";
private static final int REQUEST_LIMIT = 100; // 限流閾值
private static final int EXPIRE_TIME = 60; // 過(guò)期時(shí)間（秒）
public boolean allowRequest() {
Jedis jedis = new Jedis("localhost");
try {
Long counter = jedis.incr(REDIS_KEY);
if (counter == 1) {
// 第一次設(shè)置過(guò)期時(shí)間
jedis.expire(REDIS_KEY, EXPIRE_TIME);
}
if (counter <= REQUEST_LIMIT) {
return true; // 允許請(qǐng)求通過(guò)
} else {
return false; // 請(qǐng)求達(dá)到限流閾值，拒絕請(qǐng)求
}
} finally {
jedis.close();
}
}
public static void main(String[] args) {
RedisRateLimiter rateLimiter = new RedisRateLimiter();
for (int i = 0; i < 110; i++) {
if (rateLimiter.allowRequest()) {
System.out.println("Request Allowed");
} else {
System.out.println("Request Denied (Rate Limited)");
}
}
}
}在上述代碼中，每次請(qǐng)求會(huì)通過(guò) allowRequest() 方法判斷是否達(dá)到限流閾值，如果未達(dá)到則允許通過(guò)，并遞增計(jì)數(shù)器的值，否則拒絕請(qǐng)求。同時(shí)，第一次設(shè)置計(jì)數(shù)器的過(guò)期時(shí)間，使得計(jì)數(shù)器在指定的時(shí)間內(nèi)自動(dòng)清零。
PS：以上是一個(gè)簡(jiǎn)單的示例，實(shí)際應(yīng)用中需要根據(jù)具體場(chǎng)景實(shí)現(xiàn)更復(fù)雜的限流邏輯，并考慮并發(fā)情況下的線程安全性等問(wèn)題。
因?yàn)橛?jì)算器算法有突刺問(wèn)題，因此我們需要使用升級(jí)版的滑動(dòng)窗口算法或其他限流算法來(lái)解決此問(wèn)題。
3.2 滑動(dòng)窗口算法
此方法的實(shí)現(xiàn)思路是：將請(qǐng)求都存入到 ZSet 集合中，在分?jǐn)?shù)（score）中存儲(chǔ)當(dāng)前請(qǐng)求時(shí)間。然后再使用 ZSet 提供的 range 方法輕易的獲取到 2 個(gè)時(shí)間戳內(nèi)的所有請(qǐng)求，通過(guò)獲取的請(qǐng)求數(shù)和限流數(shù)進(jìn)行比較并判斷，從而實(shí)現(xiàn)限流。
它的具體操作步驟如下：
- 使用有序集合（ZSet）來(lái)存儲(chǔ)每個(gè)時(shí)間窗口內(nèi)的請(qǐng)求時(shí)間戳，成員（member）表示請(qǐng)求的唯一標(biāo)識(shí)，分?jǐn)?shù)（score）表示請(qǐng)求的時(shí)間戳。
- 每次收到請(qǐng)求時(shí)，將請(qǐng)求的時(shí)間戳作為成員，當(dāng)前時(shí)間戳作為分?jǐn)?shù)加入到有序集合中。
- 根據(jù)有序集合的時(shí)間范圍和滑動(dòng)窗口的設(shè)置，判斷當(dāng)前時(shí)間窗口內(nèi)的請(qǐng)求數(shù)量是否超過(guò)限流閾值。
具體實(shí)現(xiàn)代碼如下：
import redis.clients.jedis.Jedis;
import redis.clients.jedis.Tuple;
import java.util.Set;
public class RedisSlidingWindowRateLimiter {
private static final String ZSET_KEY = "request_timestamps";
private static final int WINDOW_SIZE = 60; // 時(shí)間窗口大小（單位：秒）
private static final int REQUEST_LIMIT = 100; // 限流閾值
public boolean allowRequest() {
Jedis jedis = new Jedis("localhost");
long currentTimestamp = System.currentTimeMillis() / 1000;
// 添加當(dāng)前請(qǐng)求的時(shí)間戳到有序集合
jedis.zadd(ZSET_KEY, currentTimestamp, String.valueOf(currentTimestamp));
// 移除過(guò)期的請(qǐng)求時(shí)間戳，保持時(shí)間窗口內(nèi)的請(qǐng)求
long start = currentTimestamp - WINDOW_SIZE;
long end = currentTimestamp;
jedis.zremrangeByScore(ZSET_KEY, 0, start);
// 查詢當(dāng)前時(shí)間窗口內(nèi)的請(qǐng)求數(shù)量
Set<Tuple> requestTimestamps = jedis.zrangeByScoreWithScores(ZSET_KEY, start, end);
long requestCount = requestTimestamps.size();
jedis.close();
// 判斷請(qǐng)求數(shù)量是否超過(guò)限流閾值
return requestCount <= REQUEST_LIMIT;
}
public static void main(String[] args) {
RedisSlidingWindowRateLimiter rateLimiter = new RedisSlidingWindowRateLimiter();
for (int i = 0; i < 110; i++) {
if (rateLimiter.allowRequest()) {
System.out.println("Request Allowed");
} else {
System.out.println("Request Denied (Rate Limited)");
}
}
}
}在上述代碼中，每次收到請(qǐng)求時(shí)，將當(dāng)前請(qǐng)求的時(shí)間戳加入到有序集合中，并移除過(guò)期的請(qǐng)求時(shí)間戳，然后查詢當(dāng)前時(shí)間窗口內(nèi)的請(qǐng)求數(shù)量，判斷是否達(dá)到限流閾值。這樣基于 Redis 的滑動(dòng)窗口限流算法可以有效控制單位時(shí)間內(nèi)的請(qǐng)求流量，避免系統(tǒng)被過(guò)多請(qǐng)求壓垮。
3.3 令牌桶算法
此方法的實(shí)現(xiàn)思路是：在程序中使用定時(shí)任務(wù)給 Redis 中的 List 添加令牌，程序通過(guò) List 提供的 leftPop 來(lái)獲取令牌，得到令牌繼續(xù)執(zhí)行，否則就是限流不能繼續(xù)運(yùn)行。
① 添加令牌
在 Spring Boot 項(xiàng)目中，通過(guò)定時(shí)任務(wù)給 Redis 中的 List 每秒中添加一個(gè)令牌（當(dāng)然也可以通過(guò)修改定時(shí)任務(wù)的執(zhí)行時(shí)間來(lái)控制令牌的發(fā)放速度），具體實(shí)現(xiàn)代碼如下：
@Configuration // 1.注入到 IoC 中，啟動(dòng)程序時(shí)加載
@EnableScheduling // 2.開啟定時(shí)任務(wù)
public class SaticScheduleTask {
@Autowired
private RedisTemplate redisTemplate;
// 3.添加定時(shí)任務(wù)
@Scheduled(fixedRate = 1000)
private void configureTasks() {
redisTemplate.opsForList().rightPush("limit_list",UUID.randomUUID().toString());
}
}② 獲取令牌
令牌的獲取代碼如下：
public boolean allowRequest(){
Object result = redisTemplate.opsForList().leftPop("limit_list");
if(result == null){
return false;
}
return true;
}在上述代碼中，我們每次訪問(wèn) allowRequest() 方法時(shí)，會(huì)嘗試從 Redis 中獲取一個(gè)令牌，如果拿到令牌了，那就說(shuō)明沒超出限制，可以繼續(xù)執(zhí)行，反之則不能執(zhí)行。
