它是什么
调度器在未来的某个时间运行任务：10 分钟后发这封邮件、午夜运行这份报表、明天重试这笔支付。核心问题看起来很简单：在数十亿个待处理的任务里，系统怎么知道此刻哪些到期了，而不必全部扫描？答案决定了系统能不能扩展，而它是一个数据结构的选择：数据库索引、有序集合，或时间轮（timing wheel）。
Important
核心要点： Tick 机制把调度器从”带定时器的数据库”变成了一个可扩展的系统：它决定了你每秒是扫描所有任务，还是只扫描到期的任务。把找到到期任务（trigger，由时间驱动）与运行它们（dispatch，由 worker 容量驱动）分开，并让 worker 拉取。
何时需要它
“设计一个任务调度器”和”设计一个延迟队列”都落在这里，还有它们的追问：午夜有几百万个任务同时到期怎么办、worker 在任务中途死了怎么办、怎么大规模运行 cron？
Note
面试信号： 从数据库轮询走到有序集合再走到时间轮，并说明每一种在十亿个任务时为什么失败，就是正确的做法。接着点出时钟对齐时刻（午夜）的惊群，并对这些桶预先分片，这才是区分级别的地方。
找到到期的任务
| 方式 | 做法 | 为什么失败或胜出 |
|---|---|---|
| 数据库轮询 | 每 N 毫秒执行 SELECT ... WHERE due_time <= now() AND status = 'pending' LIMIT n | 简单，小规模没问题。在十亿个任务时，这个查询会碰到太多行，尤其是在惊群窗口里 |
| 有序集合（例如 Redis） | 以到期时间为分数的任务 id；取出到期的区间 | 每次操作 O(log N)，但一个集合装不下十亿条目，而时钟对齐的尖峰会让当前时间的分片成为热点 |
| 时间轮 | 把时间划分成槽；每个槽只保存在该槽到期的任务；指针每个 tick 前进一个槽 | 找到期的槽是 O(1)，处理它是 O(桶大小)；可以按时间分片 |
时间轮是怎么工作的。 想象一个有 3,600 个槽的钟面，每个槽对应一小时中的一秒。每个槽是一个桶，装着在那一秒到期的任务 id，指针每秒前进一个槽。当它落在某个槽上时，那个桶里的一切都变为就绪。
分层时间轮处理更远的任务：秒轮（60 个槽）、分钟轮（60）、小时轮（24）、天轮。一个在 3 小时 25 分 40 秒后到期的任务，被放进小时轮的 +3 槽。当那个小时槽到来时，任务级联进入分钟轮的 +25 槽；当那个槽到来时，它级联进入秒轮的 +40 槽，然后触发。每个任务被触碰几次，而不是被持续扫描。
算例。 每天十亿个任务均匀分布，大约是每秒 11,600 个，所以每一秒的桶里大约有 12,000 个任务。一个时钟对齐的尖峰，比如午夜，可能在一个桶里放 300,000 个，这仍然是有界的、并且事先已知，所以你可以查看未来的桶，并预热 dispatch 管道。
为什么在这个问题上选时间轮而不是有序集合：
- 有界的扫描成本。 桶是预先分好区的：查找当前槽是 O(1)，而不是对到期区间做线性扫描。
- 按时间而不是按 key 分片。 节点 A 处理第 0 到 29 秒，节点 B 处理第 30 到 59 秒；集合的分片是按 key 的哈希，对不上时间边界。
- 预先缓解惊群。 你可以提前查看一个热点桶；用有序集合时，你是在它触发的那一刻才发现尖峰。
Trigger、dispatch 与状态机
- 任务到达。 任务服务计算到期时间（立即、延迟，或下一个 cron 实例），并把 id 插入合适的桶。
- 时间轮 tick。 每秒钟，trigger 引擎前进并读取当前的桶；这些 id 就是到期的。
- 送入就绪队列，按优先级和 worker 类型分区。这是 trigger 与 dispatch 之间的缓冲，能吸收惊群。
- Worker 拉取就绪队列，并用在版本列上做 compare-and-swap 的方式原子地认领一个任务（pending 到 running）。
- 租约与心跳。 被认领的任务有一个租约（例如 60 秒）；worker 必须在租约内发送心跳，否则 dispatcher 就认为它死了，把任务重新入队。
- 完成。 Worker 报告成功或失败；状态变为
succeeded或failed，周期性任务则安排它的下一个实例。
CREATED -> PENDING -> READY -> RUNNING -> SUCCEEDED
-> FAILED -> PENDING (重试)
-> TIMED_OUT -> PENDING (重新入队)每次状态转换都是一次条件更新，UPDATE task SET status='running', version=version+1 WHERE task_id=? AND version=?。如果 compare-and-swap 失败，说明别的 worker 已经认领了它，落败者就退让。这样**不需要分布式锁**就做到了至多一个活跃的执行。
Caution
常见错误： 基于推送的 dispatch，即调度器把任务推给 worker。在惊群期间，dispatcher 会用超出 worker 承受能力的任务压垮慢的 worker。拉取是自我调节的：worker 只在有容量时才取活，这也是就绪队列是缓冲而不是瓶颈的原因。
Warning
生产实践： 当 300,000 个任务同时就绪时，即使是 compare-and-swap 也会产生争用。在这个规模下，要对任务表和就绪队列做分区，让每个分片处理突发的一个切片，并且让任务处理函数幂等：租约过期可能让一个任务运行两次。
周期性任务（cron）
不要存储一个周期性任务的所有未来实例。存储 cron 表达式，并且只生成下一个实例：
- 用户提交一个 cron 表达式（
0 0 * * *，每天午夜）。 - cron 解析器计算下一个到期时间，并把那一个实例插入时间轮。
- 当它触发并完成之后，解析器计算再下一个实例并插入。
这让存储与调度的数量成正比，而不是与它们向前运行多远成正比。对于错过的运行（调度器在午夜宕机），要有显式的策略：补跑一次、补跑每个错过的实例，或者跳过。
延迟队列与 DAG
延迟队列是同一个时间轮换了一个前端：任务的”到期时间”是现在加上延迟，到期时它被投递到一个队列，而不是 worker 集群。任务的依赖图则是一个只在上游任务成功后才触发某个任务的调度器：为每个任务记录未满足的依赖数，上游完成时递减，当计数到零时把任务放入时间轮或就绪队列。
如何选择
| 情形 | 选择 | 原因 |
|---|---|---|
| 量不大，一个数据库 | 带索引的轮询 | 最简单 |
| 数百万个延迟项，不想要协调开销 | 有序集合 | O(log N)，容易 |
| 数十亿个任务、时钟对齐的尖峰 | 按时间分片的分层时间轮 | 有界的扫描，可预先分片 |
| 分发给 worker | 带租约地从就绪队列拉取 | 自我调节；能处理 worker 死亡 |
| 同一时刻恰好一次执行 | 在版本列上做 compare-and-swap | 不需要分布式锁 |
| 周期性任务 | 存 cron 表达式；物化下一个实例 | 存储保持很小 |
相关
- 演练：设计分布式任务调度器 — 这个 tick 机制所驱动的完整调度器设计。
- 演练：设计通知系统 — 通过延迟队列做定时和延迟发送。
- 参考：分布式锁与 Fencing Token — 当旧 worker 只是暂停时，租约过期意味着什么。