百度面試：如何用Redis實(shí)現(xiàn)限流？

作者：磊哥 2024-06-11 10:03:56

我們每次訪問 allowRequest() 方法時(shí)，會嘗試從 Redis 中獲取一個令牌，如果拿到令牌了，那就說明沒超出限制，可以繼續(xù)執(zhí)行，反之則不能執(zhí)行。

高并發(fā)系統(tǒng)有三大特征：限流、緩存和熔斷，所以限流已經(jīng)成為當(dāng)下系統(tǒng)開發(fā)中必備的功能了。那么，什么是限流？如何實(shí)現(xiàn)限流？使用 Redis 能不能實(shí)現(xiàn)限流？接下來我們一起來看。

1.什么是限流？

限流是指在各種應(yīng)用場景中，通過技術(shù)和策略手段對數(shù)據(jù)流量、請求頻率或資源消耗進(jìn)行有計(jì)劃的限制，以避免系統(tǒng)負(fù)載過高、性能下降甚至崩潰的情況發(fā)生。限流的目標(biāo)在于維護(hù)系統(tǒng)的穩(wěn)定性和可用性，并確保服務(wù)質(zhì)量。

使用限流有以下幾個好處：

保護(hù)系統(tǒng)穩(wěn)定性：過多的并發(fā)請求可能導(dǎo)致服務(wù)器內(nèi)存耗盡、CPU 使用率飽和，從而引發(fā)系統(tǒng)響應(yīng)慢、無法正常服務(wù)的問題。
防止資源濫用：確保有限的服務(wù)資源被合理公平地分配給所有用戶，防止個別用戶或惡意程序過度消耗資源。
優(yōu)化用戶體驗(yàn)：對于網(wǎng)站和應(yīng)用程序而言，如果任由高并發(fā)導(dǎo)致響應(yīng)速度變慢，會影響所有用戶的正常使用體驗(yàn)。
保障安全：在網(wǎng)絡(luò)層面，限流有助于防范 DoS/DDoS 攻擊，降低系統(tǒng)遭受惡意攻擊的風(fēng)險(xiǎn)。
運(yùn)維成本控制：合理的限流措施可以幫助企業(yè)減少不必要的硬件投入，節(jié)省運(yùn)營成本。

2.限流常見算法

限流的常見實(shí)現(xiàn)算法有以下幾個：

計(jì)數(shù)器算法：將時(shí)間周期劃分為固定大小的窗口（如每分鐘、每小時(shí)），并在每個窗口內(nèi)統(tǒng)計(jì)請求的數(shù)量。當(dāng)窗口內(nèi)的請求數(shù)達(dá)到預(yù)設(shè)的閾值時(shí)，后續(xù)請求將被限制。時(shí)間窗口結(jié)束后，計(jì)數(shù)器清零。

優(yōu)點(diǎn)：實(shí)現(xiàn)簡單，易于理解。
缺點(diǎn)：在窗口切換時(shí)刻可能會有突刺流量問題，即在窗口結(jié)束時(shí)會有短暫的大量請求被允許通過。

滑動窗口算法：改進(jìn)了計(jì)算器算法（固定窗口算法）的突刺問題，將時(shí)間窗口劃分為多個小的時(shí)間段（桶），每個小時(shí)間段有自己的計(jì)數(shù)器。隨著時(shí)間流逝，窗口像滑塊一樣平移，過期的小時(shí)間段的計(jì)數(shù)會被丟棄，新時(shí)間段加入計(jì)數(shù)。所有小時(shí)間段的計(jì)數(shù)之和不能超過設(shè)定的閾值。

優(yōu)點(diǎn)：更平滑地處理流量，避免了突刺問題。
缺點(diǎn)：實(shí)現(xiàn)相對復(fù)雜，需要維護(hù)多個計(jì)數(shù)器。

漏桶算法：想象一個固定容量的桶，水（請求）以恒定速率流入桶中，同時(shí)桶底部有小孔讓水以恒定速率流出。當(dāng)桶滿時(shí)，新來的水（請求）會被丟棄。此算法主要用來平滑網(wǎng)絡(luò)流量，防止瞬時(shí)流量過大。

優(yōu)點(diǎn)：可以平滑突發(fā)流量，保證下游系統(tǒng)的穩(wěn)定。
缺點(diǎn)：無法處理突發(fā)流量高峰，多余的請求會被直接丟棄。

令牌桶算法：與漏桶相反，有一個固定速率填充令牌的桶，令牌代表請求許可。當(dāng)請求到達(dá)時(shí)，需要從桶中取出一個令牌，如果桶中有令牌則允許請求通過，否則拒絕。桶的容量是有限的，多余的令牌會被丟棄。

優(yōu)點(diǎn)：既能平滑流量，又能處理一定程度的突發(fā)流量（因?yàn)榱钆瓶梢岳鄯e）。
缺點(diǎn)：需要精確控制令牌生成速度，實(shí)現(xiàn)較漏桶復(fù)雜。

3.使用Redis實(shí)現(xiàn)限流

使用 Redis 也可以實(shí)現(xiàn)簡單的限流，它的常見限流方法有以下幾種實(shí)現(xiàn)：

基于計(jì)數(shù)器和過期時(shí)間實(shí)現(xiàn)的計(jì)數(shù)器算法：使用一個計(jì)數(shù)器存儲當(dāng)前請求量（每次使用 incr 方法相加），并設(shè)置一個過期時(shí)間，計(jì)數(shù)器在一定時(shí)間內(nèi)自動清零。計(jì)數(shù)器未到達(dá)限流值就可以繼續(xù)運(yùn)行，反之則不能繼續(xù)運(yùn)行。
基于有序集合（ZSet）實(shí)現(xiàn)的滑動窗口算法：將請求都存入到 ZSet 集合中，在分?jǐn)?shù)（score）中存儲當(dāng)前請求時(shí)間。然后再使用 ZSet 提供的 range 方法輕易的獲取到 2 個時(shí)間戳內(nèi)的所有請求，通過獲取的請求數(shù)和限流數(shù)進(jìn)行比較并判斷，從而實(shí)現(xiàn)限流。
基于列表（List）實(shí)現(xiàn)的令牌桶算法：在程序中使用定時(shí)任務(wù)給 Redis 中的 List 添加令牌，程序通過 List 提供的 leftPop 來獲取令牌，得到令牌繼續(xù)執(zhí)行，否則就是限流不能繼續(xù)運(yùn)行。

了解了以上概念后，接下來我們來看具體的實(shí)現(xiàn)。

3.1 計(jì)數(shù)器算法

此方法的實(shí)現(xiàn)思路是：使用一個計(jì)數(shù)器存儲當(dāng)前請求量（每次使用 incr 方法相加），并設(shè)置一個過期時(shí)間，計(jì)數(shù)器在一定時(shí)間內(nèi)自動清零，從而實(shí)現(xiàn)限流。

它的具體操作步驟如下：

使用 Redis 的計(jì)數(shù)器保存當(dāng)前請求的數(shù)量。
設(shè)置一個過期時(shí)間，使得計(jì)數(shù)器在一定時(shí)間內(nèi)自動清零。
每次收到請求時(shí)，檢查計(jì)數(shù)器當(dāng)前值，如果未達(dá)到限流閾值，則增加計(jì)數(shù)器的值，否則拒絕請求。

具體實(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; // 過期時(shí)間（秒）

    public boolean allowRequest() {
        Jedis jedis = new Jedis("localhost");
        
        try {
            Long counter = jedis.incr(REDIS_KEY);
            if (counter == 1) {
                // 第一次設(shè)置過期時(shí)間
                jedis.expire(REDIS_KEY, EXPIRE_TIME);
            }
            
            if (counter <= REQUEST_LIMIT) {
                return true; // 允許請求通過
            } else {
                return false; // 請求達(dá)到限流閾值，拒絕請求
            }
        } 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)");
            }
        }
    }
}

在上述代碼中，每次請求會通過 allowRequest() 方法判斷是否達(dá)到限流閾值，如果未達(dá)到則允許通過，并遞增計(jì)數(shù)器的值，否則拒絕請求。同時(shí)，第一次設(shè)置計(jì)數(shù)器的過期時(shí)間，使得計(jì)數(shù)器在指定的時(shí)間內(nèi)自動清零。

PS：以上是一個簡單的示例，實(shí)際應(yīng)用中需要根據(jù)具體場景實(shí)現(xiàn)更復(fù)雜的限流邏輯，并考慮并發(fā)情況下的線程安全性等問題。

因?yàn)橛?jì)算器算法有突刺問題，因此我們需要使用升級版的滑動窗口算法或其他限流算法來解決此問題。

3.2 滑動窗口算法

此方法的實(shí)現(xiàn)思路是：將請求都存入到 ZSet 集合中，在分?jǐn)?shù)（score）中存儲當(dāng)前請求時(shí)間。然后再使用 ZSet 提供的 range 方法輕易的獲取到 2 個時(shí)間戳內(nèi)的所有請求，通過獲取的請求數(shù)和限流數(shù)進(jìn)行比較并判斷，從而實(shí)現(xiàn)限流。

它的具體操作步驟如下：

使用有序集合（ZSet）來存儲每個時(shí)間窗口內(nèi)的請求時(shí)間戳，成員（member）表示請求的唯一標(biāo)識，分?jǐn)?shù)（score）表示請求的時(shí)間戳。
每次收到請求時(shí)，將請求的時(shí)間戳作為成員，當(dāng)前時(shí)間戳作為分?jǐn)?shù)加入到有序集合中。
根據(jù)有序集合的時(shí)間范圍和滑動窗口的設(shè)置，判斷當(dāng)前時(shí)間窗口內(nèi)的請求數(shù)量是否超過限流閾值。

具體實(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)前請求的時(shí)間戳到有序集合
        jedis.zadd(ZSET_KEY, currentTimestamp, String.valueOf(currentTimestamp));

        // 移除過期的請求時(shí)間戳，保持時(shí)間窗口內(nèi)的請求
        long start = currentTimestamp - WINDOW_SIZE;
        long end = currentTimestamp;
        jedis.zremrangeByScore(ZSET_KEY, 0, start);

        // 查詢當(dāng)前時(shí)間窗口內(nèi)的請求數(shù)量
        Set<Tuple> requestTimestamps = jedis.zrangeByScoreWithScores(ZSET_KEY, start, end);
        long requestCount = requestTimestamps.size();

        jedis.close();

        // 判斷請求數(shù)量是否超過限流閾值
        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)");
            }
        }
    }
}

在上述代碼中，每次收到請求時(shí)，將當(dāng)前請求的時(shí)間戳加入到有序集合中，并移除過期的請求時(shí)間戳，然后查詢當(dāng)前時(shí)間窗口內(nèi)的請求數(shù)量，判斷是否達(dá)到限流閾值。這樣基于 Redis 的滑動窗口限流算法可以有效控制單位時(shí)間內(nèi)的請求流量，避免系統(tǒng)被過多請求壓垮。

3.3 令牌桶算法

此方法的實(shí)現(xiàn)思路是：在程序中使用定時(shí)任務(wù)給 Redis 中的 List 添加令牌，程序通過 List 提供的 leftPop 來獲取令牌，得到令牌繼續(xù)執(zhí)行，否則就是限流不能繼續(xù)運(yùn)行。

① 添加令牌

在 Spring Boot 項(xiàng)目中，通過定時(shí)任務(wù)給 Redis 中的 List 每秒中添加一個令牌（當(dāng)然也可以通過修改定時(shí)任務(wù)的執(zhí)行時(shí)間來控制令牌的發(fā)放速度），具體實(shí)現(xiàn)代碼如下：

@Configuration      // 1.注入到 IoC 中，啟動程序時(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; 
}

在上述代碼中，我們每次訪問 allowRequest() 方法時(shí)，會嘗試從 Redis 中獲取一個令牌，如果拿到令牌了，那就說明沒超出限制，可以繼續(xù)執(zhí)行，反之則不能執(zhí)行。

責(zé)任編輯：武曉燕來源： Java中文社群