系列导航：上一篇 18 消息队列接入与积压恢复 ｜ 本篇 19 ｜ 下一篇 20 发号服务的唯一性与失败模式

“三十分钟后关闭未支付的预约”“两小时后提醒参会者”，这类需求都可以写成一句话：到了某个时刻之后，执行一次某个动作。真正实现起来，这句话里的“到了”“执行”和“一次”都要重新定义。到期时刻由谁的时钟判断？多个执行者同时扫描时，谁拿到任务？执行者拿到任务后被杀死或被暂停，任务何时由别人接手？原执行者恢复后又提交结果，系统听谁的？取消请求与到期同时到达，返回给调用方的“已取消”究竟保证了什么？

本篇用 PostgreSQL 保存任务，多个独立 JVM 进程担任执行者，用真实的 kill -9 和 SIGSTOP 制造执行者失联，逐一回答这些问题。结论先写在契约里：系统允许同一任务有多次执行尝试，“一次”只落在副作用上，并且要靠唯一约束或幂等键来保证。代码在 examples/19-delayed-tasks/，输出在 evidence/19/output.txt。

需求契约

调用方可以做两件事：安排一个任务（类型、载荷、延迟、最大尝试次数），以及取消一个任务。执行者可以做四件事：领取到期任务、续租、报告完成、报告失败。系统对这些操作承诺：

  • 任务不会在 due_at 之前被领取，due_at 与租约期限都以数据库时钟为准。
  • 任务的同一次尝试只被一个执行者领取。每次领取都使 attempt 加一，这个值同时是本次尝试的栅栏令牌。
  • 只有持有当前 attempt 且租约未被收回的执行者能把任务改成完成或失败。迟到的提交被拒绝，不改变状态，也不写副作用。
  • 本地副作用与“完成”在同一事务中写入，每个任务最多一行。
  • 终态 DONE、CANCELLED、DEAD 不会再改变。
  • 取消的返回值准确描述取消时任务所处的阶段，调用方据此知道还可能发生什么。

系统不承诺任务在到期的那一刻准时执行，延迟取决于轮询间隔和执行者负载；也不承诺执行恰好一次，执行者崩溃后，任务会被再次领取。外部系统上已经发生的效果无法撤回。

规模假设全部是教学取值：3 个执行者进程；租约 1–2 秒，执行期间续租；轮询间隔 10–500 毫秒；索引实验中有 4 万行任务，其中 2 万行尚未到期。这些参数用于让故障在几秒内显现，不是推荐配置。

数据模型与状态机

任务表的关键字段是 state、due_at、attempt、lease_owner、lease_until 和 cancel_requested。表上有一条检查约束：状态为 CLAIMED 当且仅当两个租约字段非空，使“执行中却没有租约”这类不一致在写入时就被拒绝。两条部分索引分别只覆盖等待中和执行中的任务：

1
2
create index task_due_idx   on task (due_at)      where state = 'SCHEDULED';
create index task_lease_idx on task (lease_until) where state = 'CLAIMED';

PostgreSQL 的部分索引只覆盖谓词选中的行（PostgreSQL 16 §11.8）。已完成的历史任务不进入到期索引，索引大小与历史量无关。

图 19-1：任务状态机（前置条件写在迁移上，拒绝路径见注释）

stateDiagram-v2
    [*] --> SCHEDULED: schedule
    SCHEDULED --> CLAIMED: claim（due_at ≤ now()，SKIP LOCKED，attempt+1，写租约）
    SCHEDULED --> CANCELLED: cancel → 返回 CANCELLED
    CLAIMED --> DONE: complete（attempt 匹配且未请求取消）+ 同事务写 effect
    CLAIMED --> CLAIMED: cancel → 置 cancel_requested，返回 REQUESTED
    CLAIMED --> CANCELLED: complete / fail / 租约过期，且 cancel_requested
    CLAIMED --> SCHEDULED: fail 未用尽（退避后到期）/ 租约过期回收
    CLAIMED --> DEAD: fail 或租约过期，且尝试用尽
    DONE --> [*]
    CANCELLED --> [*]
    DEAD --> [*]
    note right of CLAIMED
      attempt 不匹配的 complete / fail / extend：
      REJECTED_STALE 或 false，状态与副作用不变
      对终态 cancel：TOO_LATE 或 ALREADY_CANCELLED
    end note

原子领取

领取要在一条语句里完成四件事：找出到期任务，跳过别的执行者已经锁住的行，把状态改为 CLAIMED 并写入租约，令 attempt 加一。

1
2
3
4
5
6
7
8
9
10
update task t
   set state = 'CLAIMED', attempt = t.attempt + 1, lease_owner = ?,
       lease_until = clock_timestamp() + ? * interval '1 millisecond'
 where t.id in (select id from task
                 where state = 'SCHEDULED' and due_at <= now()
                 order by due_at
                 for update skip locked
                 limit ?)
   and t.state = 'SCHEDULED'
returning t.id, t.kind, t.payload, t.attempt, t.due_at

PostgreSQL 文档说明，SKIP LOCKED 会跳过不能立即加锁的行，由此得到的数据视图不一致，因此不适合一般用途，但适合多个消费者访问队列类表的场景（PostgreSQL 16 SELECT，锁定子句）。同一页还指出，在 READ COMMITTED 下，带 ORDER BY 和锁定子句的 SELECT 可能返回乱序的行。所以 order by due_at 只让较早到期的任务大致先被领取，不构成严格的到期顺序保证，契约里也没有承诺顺序。外层的 t.state = 'SCHEDULED' 是第二道检查：并发更新提交后，READ COMMITTED 下的 UPDATE 会对新版本重新评估 WHERE 条件（PostgreSQL 16 §13.2.1），已被别人改走的行不会被再改一次。

到期条件用 now() 而不用 clock_timestamp()，这是有意的选择。now() 返回当前事务的开始时刻（PostgreSQL 16 §9.9.5），属于 STABLE 函数，可以作为索引扫描条件；clock_timestamp() 是 VOLATILE，文档说明这类函数不能用作索引扫描的比较值（PostgreSQL 16 §38.7）。boundary_partial_due_index 在 4 万行任务、其中 2 万行未到期的表上比较两种写法的执行计划：

1
2
3
now()            → Index Scan using task_due_idx … Index Cond: (due_at <= now())  Buffers: shared hit=2
clock_timestamp()→ Index Scan using task_due_idx … Filter: (… due_at <= clock_timestamp())
                   Rows Removed by Filter: 20000  Buffers: shared hit=304

没有到期任务时，前者读 2 个缓冲块；后者把 2 万行未到期任务逐行过滤一遍，读 304 个缓冲块。执行者每隔几十毫秒空轮询一次，这个差别会乘以轮询频率。领取在自动提交下单语句执行，now() 就等于语句开始时刻，不会因为长事务而停留在过去。

对照：先查询，再更新

另一种直观写法分两步：先 SELECT 出到期任务的 id，再按 id 执行 UPDATE，第二步不带状态条件，也不加行锁。negative_naive_select_then_update 让 3 个进程用这种写法处理 300 个任务：

1
2
CASE negative_naive_select_then_update  PASS expectDuplicate tasks=300 claims=408 tasksClaimedMoreThanOnce=83 byMultipleWorkers=83 effects=408 duplicateEffects=108
CASE control_skip_locked_same_load      PASS tasks=300 claims=300 tasksClaimedMoreThanOnce=0 byMultipleWorkers=0 effects=300 duplicateEffects=0

83 个任务被不止一个进程领取，副作用多出 108 条（这个对照写入的是没有唯一约束的副作用表，以便把重复暴露出来）。同样负载下改用原子领取，300 个任务恰好对应 300 次领取。两步之间的窗口里，多个进程读到同一批“仍在等待”的行，各自都认为自己领到了。

正常路径 normal_three_workers 中，3 个进程处理 300 个任务，完成 300、副作用 300、领取 300，重复领取 0，最小延迟 0.5ms，即没有任务早于 due_at 被领取。同一行还给出了本机这次运行的延迟分位，p50 为 37.0ms，p99 为 143.3ms。它们只描述这一次运行，当时机器上还有其他章节的实验，不能拿来外推。

租约与栅栏

执行者领取任务后可能崩溃，也可能只是停住：垃圾回收暂停、进程被挂起、所在主机过载。数据库无法区分这两种情况，它只知道租约到期了。租约到期后，回收语句把任务改回 SCHEDULED（或在尝试用尽时改为 DEAD），任务可以被再次领取。

租约最早作为分布式缓存一致性机制提出。Gray 与 Cheriton 在 SOSP 1989 的论文中写道，非拜占庭故障只影响性能而不影响正确性，同时也指出租约依赖行为良好的时钟。本实现让到期与租约都只使用数据库时钟，执行者本地只用 System.nanoTime 安排续租节奏；Java 文档说明，该值只能用来测量经过的时间，与墙钟无关（Java SE 21 System）。

租约只回答“何时允许别人接手”，回答不了“旧执行者恢复后怎么办”。被挂起的进程恢复时，并不知道自己的租约已被收回，它会继续执行，然后提交。阻止这次提交的是栅栏令牌：完成语句只在 attempt 与领取时拿到的值一致、状态仍是 CLAIMED 时才生效，副作用的插入放在同一事务中，并且只在更新命中一行后执行。

1
2
3
4
5
// TaskStore.complete（同一事务）
update task set state = 'DONE', result = ?, lease_owner = null, lease_until = null
 where id = ? and attempt = ? and state = 'CLAIMED' and not cancel_requested;
// 命中 1 行 → insert into effect(task_id, attempt, worker) → commit → DONE
// 命中 0 行 → 若本次尝试被请求取消则转 CANCELLED，否则 REJECTED_STALE

用单调递增的代号让资源一侧拒绝旧持有者，这个思路在锁服务的文献中也有讨论（例如 Burrows 关于 Chubby 的 OSDI 2006 论文中的 sequencer）。该论文原文在本环境无法访问，这里只借用这个通用概念。本实现中，资源就是任务行本身，因此栅栏由同一条 UPDATE 的条件执行，不需要额外协调。

图 19-2：执行者被挂起超过租约后的时序（确认点为数据库提交）

sequenceDiagram
    participant A as 执行者 A（attempt=1）
    participant DB as PostgreSQL task 行
    participant B as 执行者 B
    A->>DB: claim → attempt=1，lease_until=t+1s
    Note over A: SIGSTOP，续租停止
    Note over DB: lease_until 过期
    B->>DB: reclaimExpired → SCHEDULED
    B->>DB: claim → attempt=2
    B->>DB: complete(attempt=2) + effect，提交 → DONE
    Note over A: SIGCONT
    A->>DB: extend(attempt=1) → 0 行（租约已失）
    A->>DB: complete(attempt=1) → 0 行
    DB-->>A: REJECTED_STALE，结果与 effect 不变

两个故障用例的输出：

1
2
3
CASE crash_kill9_lease_retry        PASS exitA=137 stolenWhileAliveAndRenewing=0 killToReclaimMs=753 task=[DONE,2] claims=[1,kA | 2,kB] effect=[2,kB]
CASE sigstop_late_commit_rejected   PASS afterB=[DONE,2,by sB attempt 2] final=[DONE,2,by sB attempt 2] oldWorker=[COMMIT task=1 attempt=1 outcome=REJECTED_STALE leaseLostSeen=true] effect=[2,sB]
CASE negative_unfenced_late_commit  PASS expectOverwriteAndDuplicate afterB=[DONE,2,by sB attempt 2] final=[DONE,2,by sA attempt 1] effectsNoUnique=2 oldWorker=[COMMIT task=1 attempt=1 outcome=DONE leaseLostSeen=true]

kill -9 用例里，A 存活并续租期间，B 一次也没有领到（stolenWhileAliveAndRenewing=0）。A 被杀后 753ms，任务被回收（租约 1 秒），由 B 以 attempt=2 完成，副作用只有 attempt=2 的一行。挂起用例中，A 恢复后自己发现了租约丢失，但仍按代码路径尝试提交，结果被拒绝，任务结果仍署名 B。去掉栅栏的对照里，同样的时序让旧执行者把结果覆盖成 attempt 1 的值，副作用写了两条。注意 leaseLostSeen=true 在对照中同样出现：执行者自己察觉租约丢失并不能保护数据，必须由数据库一侧拒绝。

取消

取消只有一条 UPDATE：等待中的任务直接变为 CANCELLED；执行中的任务只置 cancel_requested，状态保持 CLAIMED；更新不到任何行时，再读一次终态来区分“已完成”“已取消”和“不存在”。返回值是契约的一部分：

返回值 取消时的阶段 调用方能依赖的结论
CANCELLED 等待中 任务不会再执行，不会有副作用
REQUESTED 执行中 本地副作用不会提交，最终状态为 CANCELLED；执行者已经发出的外部调用无法收回
TOO_LATE 已 DONE 或 DEAD 取消无效，副作用（如有）已经发生
ALREADY_CANCELLED / NOT_FOUND — 幂等重复 / 任务不存在

执行者续租时检查 not cancel_requested，续租失败就停止；即使执行者没有及时察觉，完成语句同样带着这个条件，命中 0 行后把任务转为 CANCELLED。cancel_semantics 逐一检查了上表：等待中取消返回 CANCELLED，再次取消返回 ALREADY_CANCELLED，执行中取消返回 REQUESTED，之后续租返回 false、提交得到 CANCELLED_BEFORE_COMMIT，最终状态 CANCELLED，副作用 0 条。

到期与取消同时发生时，结果必须落在允许的集合里。race_due_vs_cancel 运行 200 轮，每轮让取消请求在任务到期附近发出：

1
CASE race_due_vs_cancel  PASS rounds=200 violations=0 outcomes={CANCELLED/CANCELLED/effects=0=96, REQUESTED/CANCELLED/effects=0=77, TOO_LATE/DONE/effects=1=27}

三种组合分别是：领取前取消；执行中取消，本地副作用未提交；完成后取消，取消返回太晚、副作用一条。“返回已取消却产生了副作用”或“返回太晚却没有副作用”的组合一次也没有出现。三类结果的比例随调度变化，断言只检查违例数为 0。

副作用的去重边界

本地副作用写在同一个数据库里，靠“完成”事务和 effect.task_id 主键保证每个任务至多一行。外部副作用（调用另一个服务、发送一条通知）不在这个事务里，执行者只能把幂等键交给外部服务，由对方去重。键的取法决定了重复执行时会发生什么：

1
2
3
CASE ext_key_per_task_dedup        PASS crashedWorkers=1 task=[DONE,2] localEffects=1 externalApplied=1 keysSeen=[task-1]
CASE ext_key_per_attempt_duplicates PASS expectDuplicate crashedWorkers=1 task=[DONE,2] localEffects=1 externalApplied=2 keysSeen=[task-1-a1, task-1-a2]
CASE cancel_after_external_call    PASS cancel=REQUESTED final=CANCELLED localEffects=0 externalApplied=1

两组用例都让第一次尝试在调用外部服务之后、提交之前崩溃。键取任务 id 时，第二次尝试带着同一个键，外部只生效一次。键取“任务 + 尝试”时，两次尝试的键不同，外部生效两次，尽管本地副作用仍只有一行。第三个用例说明取消的边界：外部调用已经发出后再取消，返回 REQUESTED，本地不提交，而外部效果已经发生。按任务取键的前提是外部服务真的持久地按键去重，实验中的假服务把去重表放在内存里，重启即丢失，这一点只用来演示键的取法，不代表外部服务的持久性。

失败与重试

执行者报告失败时，同样受栅栏约束。尝试未用尽时，任务回到 SCHEDULED，due_at 推迟 backoff × 2^(attempt−1)；用尽时转为 DEAD；已请求取消时转为 CANCELLED。retry_backoff_then_done 让前两次尝试注入失败，退避基数为 200ms，任务在第 3 次完成；相邻两次领取的间隔为 274ms 和 423ms，分别不短于 200ms 和 400ms 的退避值，副作用 1 条。retry_exhausted_dead 让每次尝试都失败，第 3 次后进入 DEAD，副作用 0 条。

到期发现：轮询与时间轮

执行者发现到期任务的方式决定了延迟与数据库负载之间的权衡。数据库轮询最简单：每隔固定间隔执行一次领取语句。poll_interval_tradeoff 在本机比较了两个间隔：

1
2
poll=50ms  {p50=17.2 p99=57.4 max=74.7 claimQueries=134}
poll=500ms {p50=274.4 p99=501.6 max=503.6 claimQueries=20}

间隔放大 10 倍，领取查询次数（含空轮询）从 134 降到 20，最大延迟从约 75ms 升到约 504ms，上界大致等于轮询间隔。数字只描述这一次本机运行，但形状是确定的：轮询方案的延迟上界由间隔决定，空轮询的开销与间隔成反比，有了部分索引之后每次空轮询只读少量缓冲块。

另一种方案是进程内分层时间轮。Varghese 与 Lauck 在 SOSP 1987 提出时间轮（扩展版发表于 IEEE/ACM Transactions on Networking 1997）：在轮的覆盖范围内，启动和停止定时器都是常数时间；分层结构用多层不同粒度的轮覆盖更大的时间范围。本章实现了一个 3 层、每层 64 槽的模型，用受控时钟检验（输出标注 model=in-process-wheel）：

1
2
3
CASE wheel_fire_exact_tick          PASS model=in-process-wheel timers=20000 cancelled=4026 fired=15974 wrongTick=0 missed=0 dup=0 cascades=31430 remaining=0
CASE wheel_horizon_rejected         PASS model=in-process-wheel scheduleAtSpan=[beyond wheel horizon: delta=262144] scheduleAtSpanMinus1=accepted
CASE wheel_restart_needs_durable    PASS model=in-process-wheel tasks=2000 crashAtTick=274489 inWheelAtCrash=649 notYetLoaded=647 afterRebuild{never=0 executedTwice=5 moreThanTwice=0}

2 万个定时器在推进中被取消约两成，其余每个都恰好在到期 tick 触发，没有遗漏和重复。超出视界 64³ tick 的定时器被拒绝。第三个用例说明时间轮不能单独成为事实来源：崩溃时轮中有 649 个定时器，另有 647 个尚未装入，它们只存在于持久层；只有从持久层按“视界内到期”重新装入，才没有任务永远不执行（never=0），而崩溃前已触发但尚未落盘完成的 5 个任务会再执行一次。

两种方案因此不是二选一。时间轮可以降低到期发现的延迟和空轮询，但它的内容是持久层的缓存，崩溃后必须重建，重建后的重复执行仍然要靠本章的栅栏和副作用去重处理。本章没有实现“时间轮 + 数据库”的混合调度，只用模型说明了它需要满足的条件。

用例与证据

用例 类型 观察值（evidence/19/output.txt）
normal_three_workers 正常，多进程 300 任务，领取 300、副作用 300、重复 0
boundary_not_before_due / boundary_claim_limit 边界 到期前领取 0 次；批量上限 10,10,5,0
boundary_partial_due_index 边界，执行计划 now() 读 2 块，clock_timestamp() 读 304 块
cancel_semantics / race_due_vs_cancel 取消 返回值逐项符合；200 轮违例 0
retry_backoff_then_done / retry_exhausted_dead 失败重试 第 3 次完成；用尽后 DEAD
crash_kill9_lease_retry 崩溃恢复 被杀后 753ms 回收，attempt=2 完成
sigstop_late_commit_rejected 迟到提交 REJECTED_STALE，结果未被覆盖
negative_unfenced_late_commit 负向对照 结果被旧执行者覆盖，副作用 2 条
negative_naive_select_then_update / 对照 负向对照 83 个任务重复领取；原子领取 0
ext_key_* / cancel_after_external_call 外部副作用 按任务取键生效 1 次，按尝试取键 2 次
poll_interval_tradeoff 方案对比 见上文
wheel_* 模型 精确触发；超视界拒绝；重建后不丢、5 个重复

入口为 examples/19-delayed-tasks/run.sh，环境见 evidence/19/env.txt。kill -9、SIGSTOP 两个用例依赖 1 秒租约和 0.3–1.5 秒的等待，机器负载过高时可能需要放宽等待时间，但断言本身不需要放宽。

结论边界

实验支持以下结论：在单个 PostgreSQL 实例上，原子领取保证同一次尝试只被一个执行者领取；attempt 栅栏使崩溃或挂起后迟到的提交无法改写结果或重复写入本地副作用；取消的四种返回值与最终状态、副作用一致；外部副作用的重复与否取决于幂等键是否跨尝试保持不变。

实验没有覆盖数据库主备切换、网络分区和执行者与数据库之间的半开连接，也没有在多台机器上检验时钟偏差。由于到期与租约都只使用数据库时钟，执行者的本地时钟只影响续租节奏；数据库切换到另一台时钟有偏差的主机时会发生什么，不在本章证据之内。文中的延迟数字都不应外推。

本章的栅栏令牌依赖一个单调递增的整数。下一篇 20 发号服务的唯一性与失败模式 讨论更一般的问题：在多进程、进程重启和时钟回退下，怎样产生不重复的标识，以及“不重复”的范围到底有多大。