返回题库

漏桶限流器

Leaky Bucket Limiter

专题
General / 综合
难度
L2
来源
MyntBit

题目详情

漏桶算法是流量控制的经典方法。请求以任意速率到达，但以固定速率"漏出"（处理）。如果桶满，新请求被拒绝。在量化交易中，漏桶限流器用于保护交易所网关和订单入口不被过载。

任务：实现一个线程安全的漏桶限流器类，支持可配置的速率和容量。

英文原题

Rate limiting is a critical component in algorithmic trading systems and exchange gateways, preventing infrastructure from being overwhelmed by unexpected bursts of traffic such as misconfigured algorithms submitting excessive orders. The Leaky Bucket algorithm acts as a strict meter that smooths out these bursts by processing requests at a constant, continuous rate.
Task
Implement a LeakyBucket class that rate limits incoming requests.

  • LeakyBucket(double capacity, double leak_rate): Initial
解析

问题分析

漏桶算法是流量控制的经典方法。请求以任意速率到达，但以固定速率"漏出"（处理）。如果桶满，新请求被拒绝。相比令牌桶，漏桶保证绝对平滑的输出速率，适合交易所网关的硬限流场景。

实现

class LeakyBucket {
    const double rate_;       // 每秒允许通过的请求数
    const double capacity_;   // 桶的最大容量
    double water_ = 0.0;      // 当前水量
    std::chrono::steady_clock::time_point last_check_;
    std::mutex mtx_;
public:
    LeakyBucket(double rate, double capacity) 
        : rate_(rate), capacity_(capacity), 
          last_check_(std::chrono::steady_clock::now()) {}
    
    bool tryConsume(double amount = 1.0) {
        std::lock_guard lk(mtx_);
        auto now = std::chrono::steady_clock::now();
        double elapsed = std::chrono::duration<double>(now - last_check_).count();
        water_ = std::max(0.0, water_ - elapsed * rate_);
        last_check_ = now;
        if (water_ + amount <= capacity_) {
            water_ += amount;
            return true;
        }
        return false;
    }
};

复杂度与边界

  • 时间复杂度：tryConsume 为 O(1)，无需遍历或排序
  • 空间复杂度：O(1)，仅存储几个标量
  • 边界条件：(1) rate=0 时应拒绝所有请求 (2) amount > capacity 时直接拒绝 (3) 长时间间隔后桶应为空 (4) 并发调用需互斥锁保护

英文解析

Analysis

The leaky bucket algorithm is a classic rate-limiting method. Requests arrive at arbitrary rates but "leak out" (are processed) at a fixed rate. If the bucket is full, new requests are rejected. Compared to the token bucket, the leaky bucket guarantees an absolutely smooth output rate, suitable for hard rate-limiting scenarios at exchange gateways.

Solution

class LeakyBucket {
    const double rate_;       // requests per second allowed
    const double capacity_;   // maximum bucket capacity
    double water_ = 0.0;      // current water level
    std::chrono::steady_clock::time_point last_check_;
    std::mutex mtx_;
public:
    LeakyBucket(double rate, double capacity) 
        : rate_(rate), capacity_(capacity), 
          last_check_(std::chrono::steady_clock::now()) {}
    
    bool tryConsume(double amount = 1.0) {
        std::lock_guard lk(mtx_);
        auto now = std::chrono::steady_clock::now();
        double elapsed = std::chrono::duration<double>(now - last_check_).count();
        water_ = std::max(0.0, water_ - elapsed * rate_);
        last_check_ = now;
        if (water_ + amount <= capacity_) {
            water_ += amount;
            return true;
        }
        return false;
    }
};

Complexity & Edge Cases

  • Time complexity: tryConsume O(1), no traversal or sorting required
  • Space complexity: O(1), only a few scalar values stored
  • Edge cases: (1) rate=0 should reject all requests (2) amount > capacity rejected immediately (3) bucket should be empty after long idle intervals (4) concurrent calls require mutex protection

Key Considerations

  1. Token vs request granularity: Leaky bucket controls average rate, not instantaneous bursts — a burst within capacity still passes immediately
  2. Clock skew tolerance: Distributed systems must account for clock drift when comparing timestamps across nodes
  3. Memoryless property: Each check recomputes from current state; no need to persist bucket level between calls
  4. Production tuning: Capacity should exceed expected burst by 2x; drain rate set to long-term average throughput target