5 大常見高併發限流算法選型淺析

在現代高併發系統中，隨着用戶訪問量的激增和業務需求的不斷擴展，限流作爲一種至關重要的保護機制，被廣泛應用於防止系統過載，確保系統的穩定性和可用性。
本文將深入剖析幾種常見的限流算法，探討它們的原理、優缺點並給出代碼實例，幫助讀者更好地理解和應用這些算法，從而在實際項目中構建更加高效、穩定的系統。

01 固定窗口算法（Fixed Window Algorithm）

固定窗口算法將時間劃分爲固定大小的窗口（如 1min），在每個窗口內允許一定數量的請求。每當請求到達時，系統會檢查當前窗口內的請求數量，如果未超過限制，則允許請求；否則，拒絕請求。

class FixedWindowRateLimiter {
public:
    FixedWindowRateLimiter(int max_requests_per_win, std::chrono::seconds window_size)
        : max_requests_per_win_(max_requests_per_win), window_size_(window_size), request_count_(0) {
        window_start_time_ = std::chrono::steady_clock::now();
    }
    bool TryAcquire(int request_size) {
        std::lock_guard<std::mutex> lock(mtx_);
        auto now = std::chrono::steady_clock::now();
        // 如果當前時間在窗口內
        if (now - window_start_time_ < window_size_) {
            // 檢查請求數量是否超過限制
            if (request_count_ + request_size <= max_requests_per_win_) {
                request_count_ += request_size; // 增加請求計數
                return true; // 允許請求
            } else {
                return false; // 超過最大請求數
            }
        } else {
            // 重置窗口
            window_start_time_ = now;
            request_count_ = request_size; // 重置請求計數爲當前請求數量
            return true; // 允許請求
        }
    }
private:
    int max_requests_per_win_; // 最大請求數
    std::chrono::seconds window_size_; // 窗口大小
    int request_count_; // 當前請求計數
    std::chrono::steady_clock::time_point window_start_time_; // 窗口開始時間
    std::mutex mtx_; // 互斥鎖
};

優點

• 實現簡單，非常容易理解。

• 適用於請求速率相對穩定的場景。

缺點

• 在短時間流量突發時，將會有大量失敗，無法平滑流量。

• 有窗口邊際效應：在窗口切換時，可能會出現短時間內請求激增的情況，導致系統過載。

02 滑動窗口算法（Sliding Window Algorithm）

滑動窗口算法是對固定窗口算法的改進，它將時間窗口劃分爲多個小桶，併爲每個小桶維護一個獨立的請求計數器。當請求到達時，算法會根據請求的時間戳將其放入相應的小桶中，並檢查整個滑動窗口內的請求總數是否超過限制。隨着時間的推移，滑動窗口會不斷向右滑動，丟棄最舊的小桶並添加新的小桶。

class SlidingWindowRateLimiter {
public:
    SlidingWindowRateLimiter(int max_requests_per_win, std::chrono::seconds bucket_size, int num_buckets)
        : max_requests_per_win_(max_requests_per_win), bucket_size_(bucket_size), num_buckets_(num_buckets) {
        request_counts_.resize(num_buckets, 0);
        last_bucket_time_ = std::chrono::steady_clock::now();
    }
    bool TryAcquire(int request_size) {
        std::lock_guard<std::mutex> lock(mtx_);
        auto now = std::chrono::steady_clock::now();
        UpdateBuckets_(now);
        int total_requests = 0;
        for (int count : request_counts_) {
            total_requests += count;
        }
        if (total_requests + request_size <= max_requests_per_win_) {
            request_counts_[current_bucket_index_] += request_size; // 增加當前桶的請求計數
            return true; // 允許請求
        } else {
            return false; // 超過最大請求數
        }
    }
private:
    void UpdateBuckets_(std::chrono::steady_clock::time_point now) {
        auto elapsed = std::chrono::duration_cast<std::chrono::seconds>(now - last_bucket_time_);
        int buckets_to_update = static_cast<int>(elapsed / bucket_size_);
        if (buckets_to_update > 0) {
            for (int i = 0; i < std::min(num_buckets_, buckets_to_update); ++i) {
                auto next_bucket_index = (current_bucket_index_ + 1) % num_buckets_;
                request_counts_[next_bucket_index] = 0; // 移除最舊的桶
                current_bucket_index_ = next_bucket_index; // 移動到下一個桶
            }
            last_bucket_time_ += buckets_to_update * bucket_size_; // 更新最後桶的時間
        }
    }
    int max_requests_per_win_; // 最大請求數
    std::chrono::seconds bucket_size_; // 每個小桶的大小
    int num_buckets_; // 小桶的數量
    std::vector<int> request_counts_; // 每個小桶的請求計數
    std::mutex mtx_; // 互斥鎖
    std::chrono::steady_clock::time_point last_bucket_time_; // 上一個桶的時間
    int current_bucket_index_ = 0; // 當前桶的索引
};

優點

• 相比固定窗口算法可以更細粒度地控制流量。

• 減緩了固定窗口算法中的窗口邊際效應。

缺點

• 在短時間流量突發時，將會有大量失敗，無法平滑流量。

03 滑動日誌算法（Sliding Log Algorithm）

滑動日誌算法通過記錄每個請求的時間戳來控制請求速率。當一個請求到達時，系統會檢查最近一段時間內的請求記錄，計算請求速率是否超過限制。如果超過，則拒絕請求；否則，處理請求並記錄當前請求的時間戳。

class SlidingLogRateLimiter {
public:
    SlidingLogRateLimiter(int max_requests_per_win, std::chrono::seconds window_size)
        : max_requests_per_win_(max_requests_per_win), window_size_(window_size) {}
    bool TryAcquire(int request_size) {
        std::lock_guard<std::mutex> lock(mtx_);
        auto now = std::chrono::steady_clock::now();
        CleanUp_(now);
        int total_requests = 0;
        for (const auto& timestamp : request_log_) {
            total_requests += timestamp.second;
        }
        if (total_requests + request_size <= max_requests_per_win_) {
            request_log_.emplace_back(now, request_size); // 記錄當前請求
            return true; // 允許請求
        } else {
            return false; // 超過最大請求數
        }
    }
private:
    void CleanUp_(std::chrono::steady_clock::time_point now) {
        auto expiration_time = now - window_size_;
        while (!request_log_.empty() && request_log_.front().first < expiration_time) {
            request_log_.pop_front(); // 移除過期的請求記錄
        }
    }
    int max_requests_per_win_; // 最大請求數
    std::chrono::seconds window_size_; // 窗口大小
    std::deque<std::pair<std::chrono::steady_clock::time_point, int>> request_log_; // 請求日誌
    std::mutex mtx_; // 互斥鎖
};

優點

• 可以非常精確地控制請求速率。

缺點

• 在短時間流量突發時，將會有大量失敗，無法平滑流量。

• 由於每一次成功請求都要被記錄，所以會有較大額外的內存開銷。

04 漏桶算法（Leaky Bucket Algorithm）

漏桶算法將請求看作水滴，將請求處理過程看作水從漏桶底部中流出。系統以恆定速率處理請求（即漏桶的漏水速率），當一個請求到達時，如果漏桶未滿，則請求被放入漏桶中等待處理；如果漏桶已滿，則請求被拒絕。

class Task {
public:
    virtual int GetLoad() = 0;
    virtual void Run() = 0;
}
class LeakyBucketRateLimiter {
public:
    LeakyBucketRateLimiter(int capacity, int leak_rate)
        : capacity_(capacity), leak_rate_(leak_rate), current_water_(0) {
        last_leak_time_ = std::chrono::steady_clock::now();
    }
    bool TryRun(const TaskPtr& task) {
        std::lock_guard<std::mutex> lock(mtx_);
        Leak();
        if (current_water_ + task.GetLoad() <= capacity_) {
            current_water_ += task.GetLoad(); // 將請求放入漏桶
            heap_timer_.Schedule(task, current_water_ / leak_rate); // 定時器在該任務的水漏完後將會執行task的Run方法
            return true; // 允許請求
        } else {
            return false; // 漏桶已滿，請求被拒絕
        }
    }
private:
    void Leak() {
        auto now = std::chrono::steady_clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::seconds>(now - last_leak_time_);
        int leaked_water = static_cast<int>(elapsed.count()) * leak_rate_;
        if (leaked_water > 0) {
            current_water_ = std::max(0, current_water_ - leaked_water); // 減少水量
            last_leak_time_ = now; // 更新最後漏水時間
        }
    }
    int capacity_; // 漏桶的容量
    int leak_rate_; // 漏水速率（每秒漏掉的水量）
    int current_water_; // 當前水量
    HeapTimer heap_timer_; // 一個任務執行的定時器
    std::mutex mtx_; // 互斥鎖
    std::chrono::steady_clock::time_point last_leak_time_; // 上次漏水的時間
};

優點

• 能提供非常平穩的流量。

• 削峯填谷，有一定的應對流量突發能力（桶的大小）。

缺點

• 控制比較刻板，彈性能力較弱。

• 在併發時候會產生額外的延遲等待開銷（比如限制流量爲 1qps，兩個請求同時到達，必然有其中一個請求需要等 1s 後才能服務）。

05 令牌桶算法（Token Bucket Algorithm）

令牌桶算法使用一個桶來存儲令牌，以固定速率向桶中添加令牌。每當請求到達時，會先檢查桶中是否有令牌，如果有，則允許請求並消耗相應令牌；如果沒有，則拒絕請求。

class TokenBucketRateLimiter {
public:
    TokenBucketRateLimiter(int capacity, int refill_rate)
        : capacity_(capacity), refill_rate_(refill_rate), current_tokens_(0) {
        last_refill_time_ = std::chrono::steady_clock::now();
    }
    bool TryAcquire(int request_size) {
        std::lock_guard<std::mutex> lock(mtx_);
        Refill_();
        if (current_tokens_ >= request_size) {
            current_tokens_ -= request_size; // 消耗令牌
            return true; // 允許請求
        } else {
            return false; // 令牌不足，請求被拒絕
        }
    }
private:
    void Refill_() {
        auto now = std::chrono::steady_clock::now();
        auto elapsed = std::chrono::duration_cast<std::chrono::seconds>(now - last_refill_time_);
        current_tokens_ = std::min(capacity_, current_tokens_ + static_cast<int>(elapsed.count()) * refill_rate_); // 更新令牌數量
        last_refill_time_ = now; // 更新最後補充時間
    }
    int capacity_; // 令牌桶的容量
    int refill_rate_; // 令牌補充速率（每秒補充的令牌數量）
    int current_tokens_; // 當前令牌數量
    std::mutex mtx_; // 互斥鎖
    std::chrono::steady_clock::time_point last_refill_time_; // 上次補充令牌的時間
};

優點

• 能夠處理突發流量，避免系統瞬間過載。

• 靈活性高，可以通過調整令牌生成速率和桶容量來控制流量。

缺點

• 實現相對複雜。

06 總結

每種限流算法都有其適用的場景和優缺點。在選擇限流算法時，需要根據具體的業務需求和系統特性進行權衡。通過合理選擇和組合這些算法，可以有效地保護系統免受過載的影響。

原創作者｜林思捷

本文由 Readfog 進行 AMP 轉碼，版權歸原作者所有。
來源：https://mp.weixin.qq.com/s/93QNjdAuATTHp_axkgrblg