TikTok Scheduler：动态任务依赖、Worker Polling 与失败重试

题意与假设

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

• 训练采用task从DRAFT到SEALED后执行，依赖只可在DRAFT编辑；若要求运行中动态改依赖，必须规定撤销/重跑合同。
• 一个任务所有前置成功才READY；失败前置阻断后继，允许retry budget，取消/补偿需业务规定。
• worker至少一次尝试执行，外部业务副作用必须幂等或被fencing保护；不宣称单靠队列实现任意副作用exactly once。

解题路线

1. schema拆Task(id,version,state,remaining,attempt,lease_until)、Dependency(parent,child)唯一边、Attempt(id,worker,token,result)。把图编辑版本和执行attempt分开，一个任务重试不是新增另一个依赖节点。
2. 持续新增依赖有关键race：若任务已执行才加前置，过去执行不再满足新图。先声明SEALED冻结依赖，seal时验环并计算未完成前置；若动态编辑不可冻结则需要显式取消当前lease或重新构建版本，不靠一句“加锁”解决语义。
3. worker poll时原子把READY→RUNNING并分配lease/token，同时返回attempt ID。长任务heartbeat续租；worker失联到期可重试，旧worker恢复后不能凭旧token提交覆盖新attempt结果。
4. 完成提交按(task,attempt)去重，只有当前有效attempt可RUNNING→SUCCEEDED。每条(parent,child)完成传播也需幂等记账，重发成功通知不能把remaining减两次导致后继提前执行。
5. 可用任务成功outbox异步传播，依赖数量极多时分批更新并检查进度。Task成功ACK不要求一次RPC同步扫描百万后继，但最终传播必须可重放；剩余计数只是优化，可靠依据是依赖完成记录。
6. 调度只扫READY索引/队列，不每次poll全表检查所有前置。高入度任务可分组聚合完成状态，避免所有parent完成都争同一个计数行；最后一次变READY需CAS保证只入队一次。
7. 失败政策影响图：永久失败后继blocked，有限retry时先等最终判定，取消可能传播cancelled；不能把失败也减少“未成功前置”直到零。批量重跑需新version/attempt与下游失效合同。
8. 验收网络ACK丢失、重复poll、worker跑完但lease过期、重复成功、依赖编辑与seal并发、传播中宕机。容量拆任务写入率、READY吞吐、依赖边传播率和热点计数争用，队列长度本身不反映全部负载。

手动走一遍

A/B是C前置。A成功通知重复两次，C.remaining只能从2变1；B失败不能变0。A的旧worker token7迟到时，若任务已由token8重试完成，token7必须被拒。完成task的状态与向全部后继传播是不同阶段，outbox会补齐遗漏。

规模与取舍

存储O(V+E+attempt历史)，每条成功依赖传播期望常数事务但热点有争用；全图首次验环O(V+E)。总工作包含重试和传播，动态局部图编辑不默认常量时间。

易错点与追问

容易失分的边界

• 运行后加依赖却不定义重跑。
• 重复完成减计数两次。
• 失败前置被当成功。
• 租约到期认为旧worker已经停止。
• poll每次扫描全部图。

继续深挖

• 何时允许删除依赖？
• 如何返回最短环见证？
• 百万前置怎样避免单行热点？
• 业务写入成功但task完成提交失败怎么办？