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_; // 互斥锁
};

算法简介：通过设定固定的时间窗口，在窗口内计算请求的数量，如果超出限制，则拒绝请求。每当时间窗口到期，计数器重置。
适用场景：适用于请求速率较稳定、对时间窗口的要求不高的场景。
案例：某银行的API接口，每秒钟限制5次请求，超过5次即拒绝。当一个时间窗口（如1秒）结束时，计数器会重置。

优点

实现简单，非常容易理解。
适用于请求速率相对稳定的场景。

缺点

在短时间流量突发时，将会有大量失败，无法平滑流量。
有窗口边际效应：在窗口切换时，可能会出现短时间内请求激增的情况，导致系统过载。

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; // 当前桶的索引
};

算法简介：滑动窗口计数器算法是对固定窗口计数器算法的改进。它将时间窗口滑动分段，每个小段都进行计数，精确度更高。相比固定窗口，它更加平滑，不会出现突如其来的拒绝。
适用场景：适用于对请求的实时性和稳定性要求较高的场景。
案例：某社交平台在API访问上使用了滑动窗口算法，可以避免短时间内请求量突然增大时的系统压力，使请求处理更加平稳。

优点

相比固定窗口算法可以更细粒度地控制流量。
减缓了固定窗口算法中的窗口边际效应。

缺点

在短时间流量突发时，将会有大量失败，无法平滑流量。

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_; // 上次补充令牌的时间
};