摘要：固定窗口算法将时间划分为固定大小的窗口（如1min），在每个窗口内允许一定数量的请求。每当请求到达时，系统会检查当前窗口内的请求数量，如果未超过限制，则允许请求；否则，拒绝请求。
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 lock(mtx_); auto now = std::chrono::steady_clock::now; // 如果当前时间在窗口内 if (now - window_start_time_优点
实现简单，非常容易理解。适用于请求速率相对稳定的场景。缺点
在短时间流量突发时，将会有大量失败，无法平滑流量。有窗口边际效应：在窗口切换时，可能会出现短时间内请求激增的情况，导致系统过载。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 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 (now - last_bucket_time_); int buckets_to_update = static_cast(elapsed / bucket_size_); if (buckets_to_update > 0) { for (int i = 0; i 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 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 > 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 lock(mtx_); Leak; if (current_water_ + task.GetLoad (now - last_leak_time_); int leaked_water = static_cast(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 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(now - last_refill_time_); current_tokens_ = std::min(capacity_, current_tokens_ + static_cast(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
总结
每种限流算法都有其适用的场景和优缺点。在选择限流算法时，需要根据具体的业务需求和系统特性进行权衡。通过合理选择和组合这些算法，可以有效地保护系统免受过载的影响。
来源：散文随风想一点号
免责声明：本站系转载，并不代表本网赞同其观点和对其真实性负责。如涉及作品内容、版权和其它问题，请在30日内与本站联系，我们将在第一时间删除内容!
