编码母题 / P1 / Agent 运行时 / 03

支持检查点的可恢复状态机

先读清题意与边界，独立尝试，再展开思路并对照可运行的参考代码。

重要程度高价值难度困难预计完成45–60 分钟

难度按 LeetCode 简单／中等／困难三档估计；工程题并非 LeetCode 官方题目。用时指独立编码并检查主要边界的参考时间，因经验而异。

题目是什么

实现可恢复的显式状态机。合法转移后保存检查点并递增版本；恢复不能让旧实例覆盖新版本，也不能让调用者修改存储内部对象。

输入输出示例

两个实例从同一版本恢复，先提交者成功，后提交者得到版本冲突。

练习起手式与验证

复制代码后补全空方法，再运行下方三组验证；复杂题所需的辅助类型与输入准备一并放在代码块中。

/*
 * 题目：支持检查点的可恢复状态机
 * 要求：实现可恢复的显式状态机。合法转移后保存检查点并递增版本；恢复不能让旧实例覆盖新版本，
 * 也不能让调用者修改存储内部对象。
 * 示例：两个实例从同一版本恢复，先提交者成功，后提交者得到版本冲突。
 */
const transitions = {
  pending: ["running", "cancelled"],
  running: ["waiting_approval", "completed", "failed", "cancelled"],
  waiting_approval: ["running", "failed", "cancelled"],
  completed: [],
  failed: [],
  cancelled: [],
};
const clone = (value) => structuredClone(value);
class MemoryCheckpointStore {
  constructor() {}
  save(checkpoint, expectedVersion) {}
  load(runId) {}
}
class RunStateMachine {
  constructor(store, checkpoint) {}
  static create(store, runId, data = {}) {}
  static restore(store, runId) {}
  transition(nextStatus, patch = {}) {}
  snapshot() {}
}

const store = new MemoryCheckpointStore();
const machine = RunStateMachine.create(store, "r1", { step: 0 });
machine.transition("running", { step: 1 });
machine.transition("waiting_approval");
const restored = RunStateMachine.restore(store, "r1");
console.log(restored.snapshot().status); // 预期："waiting_approval"
restored.transition("running");
restored.transition("completed");
console.log((() => { try { (() => restored.transition("running"))(); return false; } catch { return true; } })()); // 预期：true（抛出异常）
console.log((() => { try { (() => machine.transition("running"))(); return false; } catch { return true; } })()); // 预期：true（抛出异常）

解题思路

展开思路、不变量与常见边界

关键切入点：用状态转移表定义合法边，保存时 compare-and-set 校验期望版本。

核心模型：状态与副作用分离；Checkpoint 是可恢复事实，不是日志文本。不变量： version 单调递增；同一 runId 的版本不能倒退；恢复结果是深拷贝，调用方不能修改仓库内部数据。生产系统还需事务性 Outbox、Step 幂等和 Schema 版本迁移。

参考代码与验证

“关键机制”注释用于解释实现，下载链接提供未经页面注释修改的原始 JS 文件。

const transitions = {
  pending: ["running", "cancelled"],
  running: ["waiting_approval", "completed", "failed", "cancelled"],
  waiting_approval: ["running", "failed", "cancelled"],
  completed: [],
  failed: [],
  cancelled: [],
};
const clone = (value) => structuredClone(value);
// 关键机制：用状态转移表定义合法边，保存时 compare-and-set 校验期望版本。
class MemoryCheckpointStore {
  constructor() {
    this.data = new Map();
  }
  save(checkpoint, expectedVersion) {
    const current = this.data.get(checkpoint.runId);
    const actual = current?.version ?? 0;
    if (actual !== expectedVersion)
      throw new Error("checkpoint version conflict");
    this.data.set(checkpoint.runId, clone(checkpoint));
  }
  load(runId) {
    const value = this.data.get(runId);
    return value ? clone(value) : null;
  }
}
class RunStateMachine {
  constructor(store, checkpoint) {
    this.store = store;
    this.state = checkpoint;
  }
  static create(store, runId, data = {}) {
    return new RunStateMachine(store, {
      runId,
      status: "pending",
      version: 0,
      data: clone(data),
    });
  }
  static restore(store, runId) {
    const value = store.load(runId);
    if (!value) throw new Error("checkpoint not found");
    return new RunStateMachine(store, value);
  }
  transition(nextStatus, patch = {}) {
    if (!transitions[this.state.status].includes(nextStatus))
      throw new Error(
        `invalid transition: ${this.state.status} -> ${nextStatus}`,
      );
    const previousVersion = this.state.version;
    const next = {
      ...this.state,
      status: nextStatus,
      version: previousVersion + 1,
      data: { ...this.state.data, ...clone(patch) },
    };
    this.store.save(next, previousVersion);
    this.state = next;
    return this.snapshot();
  }
  snapshot() {
    return clone(this.state);
  }
}

// 三组以上可直接运行的验证。
const store = new MemoryCheckpointStore();
const machine = RunStateMachine.create(store, "r1", { step: 0 });
machine.transition("running", { step: 1 });
machine.transition("waiting_approval");
const restored = RunStateMachine.restore(store, "r1");
console.log(restored.snapshot().status); // 预期："waiting_approval"
restored.transition("running");
restored.transition("completed");
console.log((() => { try { (() => restored.transition("running"))(); return false; } catch { return true; } })()); // 预期：true（抛出异常）
console.log((() => { try { (() => machine.transition("running"))(); return false; } catch { return true; } })()); // 预期：true（抛出异常）

复杂度分析

时间复杂度：O(D)／转移。每次保存与返回快照都要克隆大小为 D 的状态数据。

空间复杂度：O(D)／检查点。仓库保存状态副本，递归或额外队列并不存在。

下载原始 JS 文件