编码母题 / P1 / 异步编程 / 05

令牌桶限流器

先读清题意与边界，独立尝试，再展开思路并对照可运行的参考代码。

重要程度高价值难度困难预计完成45–60 分钟

难度按 LeetCode 简单／中等／困难三档估计；工程题并非 LeetCode 官方题目。用时指独立编码并检查主要边界的参考时间，因经验而异。

题目是什么

实现具有容量和补充速率的令牌桶。tryRemove 立即返回，remove 在令牌不足时排队等待；允许容量内突发且请求不得越过队头。

输入输出示例

容量 2、当前 0 个令牌时，等待 2 个令牌的请求排在等待 1 个令牌的请求之前。

练习起手式与验证

复制代码后补全空方法，再运行下方三组验证；复杂题所需的辅助类型与输入准备一并放在代码块中。

/*
 * 题目：令牌桶限流器
 * 要求：实现具有容量和补充速率的令牌桶。tryRemove 立即返回，remove
 * 在令牌不足时排队等待；允许容量内突发且请求不得越过队头。
 * 示例：容量 2、当前 0 个令牌时，等待 2 个令牌的请求排在等待 1 个令牌的请求之前。
 */
class TokenBucket {
  constructor({ capacity, refillPerSecond }) {}
  refill() {}
  tryRemove(count = 1) {}
  remove(count = 1) {}
  validateCount(count) {}
  drain() {}
}

(async () => {
  const bucket = new TokenBucket({ capacity: 2, refillPerSecond: 100 });
  console.log(bucket.tryRemove()); // 预期：true
  console.log(bucket.tryRemove()); // 预期：true
  console.log(bucket.tryRemove()); // 预期：false
})().catch(console.error);

解题思路

展开思路、不变量与常见边界

关键切入点：按经过时间惰性补充令牌，只为队头设置唤醒计时器并保持 FIFO。

核心模型：不创建持续 setInterval，而是在每次操作时按经过时间惰性补充。 tokens = min(capacity, tokens + elapsed * rate)。异步等待采用 FIFO 队列，单个定时器唤醒队头，避免轮询和定时器风暴。不变量：0 <= tokens <= capacity；队列非空时新请求不能越过队头；每个等待项只完成一次。count 大于 capacity 永远无法满足，必须立即拒绝。迁移：第三方 API、模型接口、Tool 调用和多租户配额。生产实现还需处理取消、分布式共享配额和时钟回拨。

参考代码与验证

“关键机制”注释用于解释实现，下载链接提供未经页面注释修改的原始 JS 文件。

// 关键机制：按经过时间惰性补充令牌，只为队头设置唤醒计时器并保持 FIFO。
class TokenBucket {
  constructor({ capacity, refillPerSecond }) {
    if (!(capacity > 0) || !(refillPerSecond > 0))
      throw new RangeError("capacity and rate must be > 0");
    this.capacity = capacity;
    this.ratePerMs = refillPerSecond / 1000;
    this.tokens = capacity;
    this.updatedAt = Date.now();
    this.queue = [];
    this.head = 0;
    this.timer = null;
  }

  refill() {
    const now = Date.now();
    const elapsed = Math.max(0, now - this.updatedAt);
    this.tokens = Math.min(
      this.capacity,
      this.tokens + elapsed * this.ratePerMs,
    );
    this.updatedAt = now;
  }

  tryRemove(count = 1) {
    this.validateCount(count);
    this.refill();
    if (this.head < this.queue.length || this.tokens < count) return false;
    this.tokens -= count;
    return true;
  }

  remove(count = 1) {
    this.validateCount(count);
    return new Promise((resolve) => {
      this.queue.push({ count, resolve });
      this.drain();
    });
  }

  validateCount(count) {
    if (!(count > 0) || count > this.capacity)
      throw new RangeError("count must be in (0, capacity]");
  }

  drain() {
    if (this.timer) {
      clearTimeout(this.timer);
      this.timer = null;
    }
    this.refill();
    while (this.head < this.queue.length && this.tokens >= this.queue[this.head].count) {
      const item = this.queue[this.head++];
      this.tokens -= item.count;
      item.resolve();
      this.refill();
    }
    if (this.head === this.queue.length) {
      this.queue = [];
      this.head = 0;
      return;
    }
    // 已消费前缀超过一半时压缩；避免 shift 的逐次搬移和长期保留已完成请求。
    if (this.head * 2 >= this.queue.length) {
      this.queue = this.queue.slice(this.head);
      this.head = 0;
    }
    const missing = this.queue[this.head].count - this.tokens;
    const waitMs = Math.max(1, Math.ceil(missing / this.ratePerMs));
    this.timer = setTimeout(() => {
      this.timer = null;
      this.drain();
    }, waitMs);
  }
}

// 三组以上可直接运行的验证；异步题使用独立执行块。
(async () => {
  const bucket = new TokenBucket({ capacity: 2, refillPerSecond: 100 });
  console.log(bucket.tryRemove()); // 预期：true
  console.log(bucket.tryRemove()); // 预期：true
  console.log(bucket.tryRemove()); // 预期：false
  const start = Date.now();
  await bucket.remove();
  console.log(Date.now() - start >= 7); // 预期：true
  console.log((() => { try { (() => bucket.tryRemove(3))(); return false; } catch { return true; } })()); // 预期：true（抛出异常）


})().catch(console.error);

复杂度分析

时间复杂度：均摊 O(1)／队列操作。队头索引避免 shift 搬移；偶发前缀压缩由此前已出队次数分摊。

空间复杂度：O(q)。队列保存 q 个待处理请求，计时器始终只有一个。

下载原始 JS 文件