手写并发调度器与LRU缓存深度解析：Map 一个 API 省掉 50 行双向链表

一句话概括

并发调度器和 LRU 缓存表面上是两道独立的手写题，背地里共享同一道「有限资源的最优分配」母题——调度器管理请求并发数，LRU 管理缓存容量，两者都要面对空状态/满状态/临界区竞争这些边界条件。

核心知识点

1. 并发调度器：Promise 队列 + 流量整形

class Scheduler {
  constructor(limit = 2) {
    this.limit = limit
    this.queue = []
    this.running = 0
  }

  add(task) {
    // task 是 () => Promise 的工厂函数，不是 Promise 本身！
    return new Promise((resolve, reject) => {
      this.queue.push({ task, resolve, reject })
      this._run()
    })
  }

  _run() {
    while (this.running < this.limit && this.queue.length) {
      const { task, resolve, reject } = this.queue.shift()
      this.running++
      task()
        .then(resolve, reject)
        .finally(() => { this.running--; this._run() })
    }
  }
}

// 使用：同时最多 2 个请求
const s = new Scheduler(2)
const delay = (ms, name) => () =>
  new Promise(r => setTimeout(() => { console.log(name, 'done'); r() }, ms))

s.add(delay(1000, 'A'))
s.add(delay(500, 'B'))
s.add(delay(300, 'C'))
// 输出顺序：B done → C done → A done  （B先完成，释放槽位给C）

核心要点：

• task 必须是工厂函数（() => Promise），不是 Promise。Promise 一旦创建就开始执行了
• _run() 在 .finally() 中被递归调用，形成自驱的流水线
• 返回 Promise 让调用方可以 await 每个 add 的结果

2. LRU 缓存：Map 天然有序，一行 get 就是「移至最新」

class LRUCache {
  #map = new Map()
  #cap = 0

  constructor(cap) { this.#cap = cap }

  get(key) {
    if (!this.#map.has(key)) return -1
    const val = this.#map.get(key)
    this.#map.delete(key)              // 删旧位置
    this.#map.set(key, val)            // 插到 Map 末尾 = 标记为「最近使用」
    return val
  }

  put(key, val) {
    if (this.#map.has(key)) this.#map.delete(key)
    if (this.#map.size >= this.#cap) {
      // Map.keys().next() 返回最先插入的 = 最久未使用
      this.#map.delete(this.#map.keys().next().value)
    }
    this.#map.set(key, val)
  }
}

为什么 Map 就够了，不需要双向链表？ ES6 Map 保证按插入顺序迭代。delete + set = 将 key 移到末尾（最近使用）；keys().next() 取最早插入的（最久未使用）。所有操作 O(1)，代码量省 70%。

3. 调度器进阶：去重 + 超时 + 优先级

class AdvancedScheduler {
  #limit, #queue = [], #running = 0, #pending = new Map()

  constructor(limit = 3) { this.#limit = limit }

  add(task, key, { priority = 0, timeout = 0 } = {}) {
    // 请求去重：相同 key 的在途请求，直接复用
    if (key && this.#pending.has(key)) return this.#pending.get(key)

    const p = new Promise((resolve, reject) => {
      this.#queue.push({ task, resolve, reject, timeout, priority })
      this.#queue.sort((a, b) => b.priority - a.priority)
      this.#run()
    })
    if (key) {
      this.#pending.set(key, p)
      p.finally(() => this.#pending.delete(key))
    }
    return p
  }

  #run() {
    while (this.#running < this.#limit && this.#queue.length) {
      const { task, resolve, reject, timeout } = this.#queue.shift()
      this.#running++
      const p = timeout > 0
        ? Promise.race([task(), new Promise((_, rj) => setTimeout(() => rj(new Error('timeout')), timeout))])
        : task()
      p.then(resolve, reject).finally(() => { this.#running--; this.#run() })
    }
  }
}

4. LRU 进阶：带 TTL 过期的版本

class LRUWithTTL extends LRUCache {
  #ttl = 0
  constructor(cap, ttl = 0) { super(cap); this.#ttl = ttl }

  get(key) {
    const entry = super.get(key)
    if (entry === -1) return -1
    if (entry.expire && Date.now() > entry.expire) {
      this.#map.delete(key)
      return -1
    }
    return entry.val
  }

  put(key, val) {
    super.put(key, { val, expire: this.#ttl ? Date.now() + this.#ttl : 0 })
  }
}

其实你每天都在用

• 浏览器并发请求 — 浏览器对同域名下请求限制 6 个并发。你同时请求 20 张图片，只有 6 个同时在发，其余排队——浏览器内置了类似调度器的东西
• 文件分片上传 — 上传 10GB 文件，切成 1000 个分片，Scheduler(5) 控制同时上传 5 片
• localStorage 缓存淘汰 — 存了太多 token/配置/localCache，写个 LRU 限制最多 50 条，多余的自动删
• 接口数据缓存 — 首页热数据存 LRU Cache，30 秒 TTL，不同页面跳转不用重复请求
• Node.js 的 maxSockets — http.Agent 的 maxSockets 参数就是并发调度器在 HTTP 层的应用

常见误解（FAQ）

❌ 误区：「调度器的 task 可以直接传 Promise」

绝对不行。Promise 创建时就开始执行了，传 Promise 等于所有任务同时启动。必须传工厂函数 () => Promise，由调度器决定何时执行。

❌ 误区：「LRU 一定需要双向链表才能 O(1)」

JavaScript 的 Map 就是 O(1) 的插入/删除/访问，且保证插入顺序。双向链表版本只有在考试要求「纯数据结构实现」时才需要。

❌ 误区：「调度器的并发数就是同时发多少个请求」

对 CPU/内存密集任务用 navigator.hardwareConcurrency 做上限；对 I/O 密集（网络请求）可以用更大值。但要考虑浏览器同一域名的并发限制（Chrome 默认 6 个 TCP 连接）。

❌ 误区：「LRU 适合所有缓存场景」

LRU 假设「最近访问的数据将来更可能被访问」。但如果访问模式是周期性扫描（如定时全量同步），LRU 会把所有数据都淘汰一遍，命中率为零。这种场景应该用 LFU 或 TTL。

一句话总结

并发调度和 LRU 缓存本质上都是在做「限流」——前者的资源是带宽/连接，后者的资源是内存，而它们共同的设计心法是：用队列/链表把「谁先谁后」这个时空问题显式管理起来，而不是依赖操作系统的随机调度。