题干与适用场景
请实现一个单机 Scheduler，支持 schedule(taskId, runAt, priority, fn)、cancel(taskId) 和 next()。调度规则是先选择最早 runAt，相同时选择更高 priority，仍相同时按提交序号；同一 taskId 只能有一个有效版本。取消后任务不得被执行，next() 在没有到期任务时返回等待信息或空值。请说明如何处理惰性删除、并发 worker、时钟和关闭竞态。
公开面试资料把任务调度器列为结合优先队列、线程池、取消和失败处理的综合题。它比单独实现一个优先队列多出生命周期和并发契约，适合考察候选人能否把数据结构不变量落实到可运行接口。
面试官考察点
- 能否定义任务状态：
pending、running、cancelled、completed，并禁止非法状态回退。 - 能否使用
(runAt, -priority, sequence)建立确定性排序，避免任务对象不可比较。 - 能否用版本号或惰性删除处理重复调度与取消，保证旧堆条目不会泄漏执行。
- 能否把“取消已排队任务”和“中止正在运行函数”区分开。
- 能否证明 worker 数量、关闭顺序和时钟选择不会破坏边界。
回答前需要澄清的问题
runAt使用单调时钟的相对时间，还是可被校准的墙上时间？默认使用单调时钟计算等待时长。fn是否接收取消信号？默认接收AbortSignal，但只能合作式停止。schedule遇到重复taskId是更新还是报错？本题采用更新旧版本并使旧条目失效。cancel是否保证正在运行的函数立即停止？不保证；只阻止尚未开始的执行，并向运行中函数发出信号。close是否等待已运行任务？默认停止接收新任务，等待 worker 收尾后再结束。
30 秒回答框架
我会用最小堆保存 (runAt, -priority, sequence, taskId, version)，再用字典保存每个任务 ID 的当前版本。更新或取消只修改字典状态并让旧堆项失效；next() 弹出堆顶时反复校验版本和状态，只有当前且到期的任务才能进入 running。调度线程用单调时钟计算距堆顶的等待时间，worker 通过固定并发上限执行函数。取消排队任务是强保证，取消运行中函数是合作式语义；关闭时先拒绝新任务，再唤醒调度线程并等待收尾。
分步骤深入解答
第一步：固定排序键和状态不变量
堆元素的排序键是 (runAt, -priority, sequence)；sequence 单调递增，保证完全相同的时间和优先级仍有确定顺序。字典 current[taskId] 只保存最新版本。堆中可以暂时保留旧版本，但旧版本永远不能从 pending 转为 running。
第二步：实现 schedule 的更新语义
每次 schedule 生成新版本并写入字典，再压入一个新堆项。若已有旧版本，不必在线性数组中删除；只要让字典指向新版本，弹出时比较版本即可。这样插入是 O(log n)，重复 ID 不会出现两个有效执行。
schedule(id, runAt, priority, fn):
version = nextVersion(id)
current[id] = {version, state: pending, fn, runAt, priority}
heappush(heap, (runAt, -priority, nextSequence(), id, version))第三步：实现 cancel 和堆顶清理
取消时从字典读取当前任务；若仍为 pending，标记为 cancelled 并触发唤醒。next() 弹出堆顶后检查字典是否仍指向同一版本，以及状态是否为 pending。失效项、已取消项和旧版本都直接丢弃。惰性删除避免 O(n) 扫描，但必须统计失效比例并在阈值达到时重建堆。
第四步：处理到期与 worker 上限
调度线程不能把未来任务立即交给 worker。它读取堆顶的 runAt，用单调时钟计算等待时长；到期后原子地把任务从 pending 改成 running，再投递到固定大小的 worker 队列。并发上限由 worker 数或信号量保证，不能只依赖调用方自觉。
第五步：区分取消与函数中止
排队任务在状态转换前被取消时，不会调用 fn。已经进入 running 的任务只能收到 AbortSignal；函数必须主动检查信号或把信号传递给可取消的 I/O。调度器记录 cancelRequested，但不把未确认的函数退出误报为已完成。
第六步：设计 close 的竞态顺序
close 先把调度器置为 closing，拒绝新的 schedule，再取消等待计时器并唤醒调度线程。调度线程停止领取新任务，worker 继续处理已领取任务；所有 worker 结束后状态变成 closed。如果需求是立即丢弃排队任务，应显式遍历当前字典标记取消，不能只清空堆而遗漏状态和指标。
第七步：证明复杂度与空间边界
正常 schedule 为 O(log n)，cancel 为 O(1) 标记，next 的堆操作为 O(log n)。每个失效堆项最多被弹出一次，因此清理成本可以摊销到产生它的更新或取消操作。长期只更新不消费会增加空间；当堆长度超过有效任务数的固定倍数时，用字典中的当前项线性重建，避免垃圾无界增长。
第八步：测试关键交错
测试相同时间和优先级的稳定顺序、重复 ID 更新后旧版本不执行、取消恰好发生在领取前后、未来任务等待被新早期任务打断、worker 达到上限、函数抛错、关闭期间提交以及单调时钟跳变。用一个排序列表模型对拍 next() 结果，并记录最大活动 worker 数。
高质量示范回答
我会把状态和堆分开维护：字典保存每个 taskId 的最新版本，最小堆保存 (runAt, -priority, sequence, taskId, version)。调度更新采用新版本覆盖，取消采用状态标记；两者都不直接修改堆数组。调度线程只在任务到期后原子领取，并把任务放入固定大小的 worker 队列。领取前的版本校验保证取消和旧版本不会执行，运行后的取消则通过 AbortSignal 合作式处理。关闭流程先拒绝新提交，再停止领取、唤醒等待者并等待已运行任务收尾。监控有效项与堆长度，按失效比例触发重建。
常见错误
- 只按优先级排序，忽略未来
runAt，导致任务提前执行。 - 更新时直接改堆内元素，破坏堆不变量。
- 取消只从字典删除，弹出旧堆项时仍然调用函数。
- 把
cancel()返回成功等同于正在运行的函数已经停止。 - 用墙上时间计算超时，系统校时后出现负等待或长时间饥饿。
close()只清空队列，留下调度线程、计时器或 worker 未结束。- 没有限制 worker 数，压力上来后把堆变成无界并发启动器。
追问及应对
如果高优先级任务持续到来，如何避免低优先级饥饿？
先说明题目默认严格优先级，低优先级可能等待很久。需要公平性时，可让有效等待时间逐步提升有效优先级，或使用分层配额的加权公平队列；这会改变排序键和可证明的延迟边界，必须补充监控和测试。
如何支持重复任务而不发生重叠执行？
在任务状态中加入 running 锁或每个 ID 的 generation。下一次触发若仍为 running，按契约选择跳过、合并一次待执行标记或排队一个新版本；不能无条件再次提交，否则同一资源可能并发执行。
进程崩溃后怎样恢复任务？
内存堆只能保证进程存活期间的调度。持久化版本、状态和下一次运行时间后，重启时从存储重建堆；领取需要条件更新或租约，函数还应幂等，因为恢复通常只能提供至少一次执行。
如何把单机实现扩展到多节点？
把堆替换为带时间索引的持久队列，并用租约或条件写入确保一个任务只有一个 owner。节点故障时让租约过期后重试；取消和更新都携带版本号，消费者拒绝过期版本。跨节点时钟应以存储端时间或明确的容忍窗口校验。