SWE · System Design / 设计追问

一个物理Timer实现多个逻辑Timer:堆、重设与过期回调

物理set会覆盖旧任务,最早逻辑到期驱动下一次唤醒。

题目重点:物理set会覆盖旧任务,最早逻辑到期驱动下一次唤醒。

题意与假设

这道练习题保留了面经中值得训练的核心约束,并将需要澄清的条件单独列出。现场拿到变体时,先和面试官确认这些条件。

  • 训练合同:物理timer可设置一个绝对单调时间deadline,重设覆盖旧注册;已投递callback可能仍到达。
  • 逻辑事件有唯一id、deadline与callback;cancel及相同deadline顺序按注册序号约定,串行事件循环执行。

解题路线

  1. 最小堆存(deadline,seq,id,version),map保存逻辑状态。新最早deadline入堆时重设物理timer;删除用lazy无效项并在读取堆头时清理。
  2. 每次物理重设递增generation;回调携带捕获generation,旧回调到达时发现不匹配即忽略。否则弹出全部deadline≤now的有效事件,先改变状态为FIRED再调用用户逻辑。
  3. 用户callback可能注册新timer或抛异常,不能持锁执行。每个callback独立捕获异常,处理完重新读堆头并arm,避免新最早任务遗漏。周期timer要约定fixed-rate还是fixed-delay及漏周期处理。

手动走一遍

注册A=100,后注册B=50,物理timer改为50;旧100回调已排队不会误触发第二次A,generation判定阻止旧唤醒。B回调中取消A并注册C=60;重设前重新检查有效堆头,下一次60而不是沿用缓存100。

规模与取舍

add/cancel更新map期望O(1),堆push/pop O(logn);lazy取消可让堆大于活跃n,需按比例压缩。一次唤醒k到期事件O(klogn)加用户callback成本。

易错点与追问

容易失分的边界

  • 墙钟校准可能跳变,延时任务应以monotonic时钟调度。
  • 恰好一次callback不能仅靠timer保证,进程崩溃恢复还要持久状态与幂等业务。

继续深挖

  • 多个线程add/cancel时,generation和arm需要怎样同步?
  • 机器休眠恢复时积压大量到期timer如何分批且保持顺序?
✓已复制微信号!