滑动窗口限流器

Throttle Sliding Window

专题: Systems & Architecture / 系统与架构
难度: L2
来源: MyntBit

个人笔记

题目详情

在高频交易系统中，交易所网关实施严格的速率限制。滑动窗口速率限制器提供精确机制，在固定时间窗口内强制消息数量限制。

任务：实现滑动窗口速率限制器类，使用滑动时间窗口跟踪消息发送频率。支持配置窗口大小和最大消息数，提供检查当前请求是否在限制内的方法。

英文原题

In high-frequency trading systems, exchange gateways impose strict rate limits to prevent malicious or runaway algorithms from overwhelming the matching engine. A sliding window rate limiter provides a precise mechanism to enforce message limits over a rolling time window, ensuring compliance with exchange rules.
Task
Implement a RateLimiter class to enforce a sliding window rate limit. The class must include the following methods:

RateLimiter(int window_size_ms, int max_requests): Initialize

解析

问题分析

滑动窗口限流器精确控制时间窗口内的最大请求数。与固定窗口不同，滑动窗口消除了窗口边界处的突发流量问题。使用双端队列存储每个请求的时间戳。

解法

class SlidingWindowThrottle {
    std::deque<std::chrono::steady_clock::time_point> timestamps_;
    const int max_requests_;
    const std::chrono::milliseconds window_;
public:
    bool allow() {
        auto now = std::chrono::steady_clock::now();
        auto cutoff = now - window_;
        while (!timestamps_.empty() && timestamps_.front() < cutoff) timestamps_.pop_front();
        if ((int)timestamps_.size() >= max_requests_) return false;
        timestamps_.push_back(now); return true;
    }
};

复杂度与边界

时间复杂度：allow O(1) 均摊（每个时间戳最多入队出队一次）
边界条件：(1) max_requests=0 拒绝所有 (2) 长时间无请求后队列为空 (3) 时钟回拨可能导致异常

英文解析

Analysis

Sliding window rate limiters precisely control the maximum number of requests within a time window. Unlike fixed windows, sliding windows eliminate burst traffic at window boundaries. A deque stores timestamps for each request.

Solution

class SlidingWindowThrottle {
    std::deque<std::chrono::steady_clock::time_point> timestamps_;
    const int max_requests_;
    const std::chrono::milliseconds window_;
public:
    bool allow() {
        auto now = std::chrono::steady_clock::now();
        auto cutoff = now - window_;
        while (!timestamps_.empty() && timestamps_.front() < cutoff) timestamps_.pop_front();
        if ((int)timestamps_.size() >= max_requests_) return false;
        timestamps_.push_back(now); return true;
    }
};

Complexity & Edge Cases

Time complexity: allow O(1) amortized (each timestamp enters/exits queue at most once)
Edge cases: (1) max_requests=0 rejects all (2) Queue empty after long idle period (3) Clock rollback may cause anomalies

Key Considerations

Window granularity: Sliding window with 1ms resolution provides smooth rate limiting; coarse granularity (1s) creates burst-then-wait pattern
Memory overhead: Counting events in sliding window requires storing per-event timestamps; optimize with circular buffer or bucketed approximation
Rate adjustment: Throttle rate must be configurable per venue; different exchanges enforce different rate limits (e.g., 20 msg/sec vs 100 msg/sec)
Backpressure propagation: When throttle rejects a message, upstream must be notified to queue or drop; silent rejection causes message loss without visibility