阿Q技术站

深浅色

第 3 章 Pregel/BSP 计算模型 ​

3.1 历史背景 ​

Pregel 是 Google 于 2010 年发表的大规模图计算框架论文《Pregel: A System for Large-Scale Graph Processing》，其底层采用 BSP（Bulk Synchronous Parallel，整体同步并行）计算模型。BSP 由 Leslie Valiant 于 1990 年提出，目标是为并行算法提供一个不依赖具体硬件拓扑的桥接模型：一次计算被切分为若干个超步（Superstep），每个超步包含本地计算、通信、屏障同步三个阶段，所有并行单元在屏障处对齐后才进入下一个超步。

LangGraph 将该模型从大规模离线图计算迁移到 Agent 运行时：每个节点（Node）类比为 Pregel 中的顶点（Vertex），Channel 类比为顶点之间传递消息的边与信箱，超步对应运行时的一轮调度，Checkpoint 对应超步结束时的全局快照。这种映射使 LangGraph 天然具备确定性执行、可快照、可中断恢复的特性。

3.2 BSP 三阶段 ​

每个 Superstep 严格按以下顺序执行：

  1. 本地计算（Local Computation）：每个被调度的顶点/节点基于上一个超步结束后的全局状态执行自身逻辑，产生要发送给其他顶点的消息/写入。在 LangGraph 中，该阶段对应节点函数执行，返回一个增量字典。
  2. 通信（Communication）：节点产生的写入被放入一个待提交缓冲区（pending writes），按 Channel 的路由规则进入目标通道的暂存区。此阶段写入对其他正在同一超步执行的节点不可见。
  3. 屏障同步（Barrier Synchronization）：运行时等待所有本轮被调度节点执行完毕，随后按 Channel 规则将待提交缓冲区合并到真实状态，生成新的全局状态版本；若配置了 Checkpointer，则写入快照；最后根据更新后的状态与边规则计算下一个超步要调度的节点集合。

关键点：本 Superstep 的写入对本轮其他节点不可见，必须等屏障同步后才在下一超步可见。这是 BSP 模型与函数嵌套调用模型最本质的差异。

3.3 LangGraph 对 BSP 的映射 ​

Pregel/BSP 概念LangGraph 对应
Vertex（顶点）Node（通过 add_node 注册的可调用对象）
Message（消息）Channel（State 的字段，承载节点间数据流）
Superstep（超步）一轮执行（tick/atick），从 Plan 到 Update 完成
Barrier（屏障）Update 阶段的同步点，等待所有并发节点完成
Vertex Value（顶点值）Channel 当前值（State 字段的当前值）
Outgoing Message（出边消息）节点返回的增量字典中的字段值
Checkpoint（检查点）超步末写入 Checkpointer 的状态快照

LangGraph 运行时将三阶段具体化为 Plan → Execute → Update：

  • Plan 阶段：读取上轮结束后的 Channel 状态，沿普通边前进，在条件边处调用 path 函数根据已更新状态做路由决策，得出本轮要执行的节点集合；
  • Execute 阶段：基于 asyncio 并发执行本轮选中的所有节点。每个节点接收的 state 都是上一轮结束后的只读快照；节点返回的增量写入 pending writes 缓冲区，不修改真实 State；
  • Update 阶段：所有节点完成后，对每个 Channel 分别执行合并：LastValue 通道取唯一写入，BinaryOperatorAggregate 通道使用 reducer 将旧值与新写入做聚合，Topic 通道将消息追加到订阅列表。合并完成后将新状态写入 Checkpointer（若有），并进入下一个超步的 Plan。

3.4 双缓冲与可见性 ​

LangGraph 使用**双缓冲（Double Buffering）**机制：状态分为"当前版本"（供节点读取）和"待提交版本"（本轮写入的暂存区）。Execute 阶段所有节点读取的都是上一个超步冻结的当前版本，因此同一超步内两个并发节点 A、B 之间互相看不到对方的返回值，完全消除了"先写入者影响后读取者"的竞态条件。屏障同步点才将待提交版本原子切换为新的当前版本。

该机制有三个直接推论：

  1. interrupt 只能发生在超步边界。节点函数一旦进入 Execute 阶段就会运行到返回（或抛异常），中途无法被运行时暂停。若在节点内部调用 interrupt()，实际抛出的是一个特殊的 GraphInterrupt 异常，它会沿着执行栈冒泡到超步边界，由 Update 阶段捕获并保存快照，等待 resume。
  2. 循环不会导致栈溢出。在 while 循环或递归函数里反复调用自身会压栈，但 LangGraph 的循环是"一个超步结束 → 下一个超步重新调度目标节点"，每一轮都是新的调度帧，与函数调用栈解耦。默认 recursion_limit 为 25 超步，超限抛出 GraphRecursionError，而非递归栈溢出。
  3. 状态变更延迟一个 Superstep 可见。节点 A 在本超步写入字段 x，本超步内与 A 并行的节点 B 读到的 x 仍是旧值；若需要 B 基于新 x 执行，必须通过边把 B 放到下一个超步。

3.5 与 LCEL/DAG 执行模型对比 ​

LCEL（LangChain Expression Language）采用的是函数调用栈模型：a | b | c 编译为 c(b(a.invoke(input))) 的嵌套调用，执行路径是深度优先的函数栈。该模型结构简单、延迟低，但无法表达回环，无法在中间任意节点做快照与恢复，流式输出只能沿调用栈向上传递。

LangGraph 采用的是迭代式 Superstep 推进模型：每一轮由调度器决定要执行哪些节点，节点之间通过 Channel 通信，每一轮末都有一个明确的"状态版本号"，Checkpoint 按版本号落盘。该模型支持循环、支持任意超步中断/恢复、支持同超步内节点并发，代价是每轮存在屏障同步开销，长尾节点会拖慢整轮。

text
时间轴 →
Superstep 0         Superstep 1           Superstep 2
┌─────────────┐    ┌─────────────┐       ┌─────────────┐
│ Plan: {A,B} │    │ Plan: {C}   │       │ Plan: {D}   │
├─────────────┤    ├─────────────┤       ├─────────────┤
│ Execute:    │    │ Execute:    │       │ Execute:    │
│  A ──┐      │    │  C reads    │       │  D reads    │
│      ├─►buf │    │  state_v1 ──┼─►buf  │  state_v2   │
│  B ──┘      │    │             │       │             │
├─────────────┤    ├─────────────┤       ├─────────────┤
│ Update:     │    │ Update:     │       │ Update:     │
│  buf → v1   │    │  buf → v2   │       │  buf → v3   │
│  ckpt[v1]   │    │  ckpt[v2]   │       │  ckpt[v3]   │
└─────────────┘    └─────────────┘       └─────────────┘
      │                  │                     │
      ▼                  ▼                     ▼
    可见性边界          可见性边界             可见性边界

源码入口：Pregel 运行时实现在 langgraph/pregel/ 目录下，对外的核心调度方法为 Pregel.atick（异步）与 Pregel.tick（同步），每次调用对应一个 Superstep 的完整 Plan-Execute-Update 流程。

3.6 BSP 的代价 ​

BSP 模型的工程代价需要明确：

  • 屏障同步长尾等待：同一超步内若一个节点是慢节点（如外部 API 耗时 10 秒），其余节点即便毫秒级完成也要等慢节点，影响整轮延迟；
  • 状态延迟可见：节点写入无法被同轮其他节点读取，对"边写边读"的细粒度协作需要拆分为多个超步，增加调度轮次；
  • 不适合极低延迟场景：在微秒-毫秒级的在线推理链路中，每轮固定的调度与合并开销占比过高，这类场景更适合纯函数链。

本章小结 ​

LangGraph 的执行模型直接继承自 Pregel/BSP：一次图执行由若干个三阶段（本地计算→通信→屏障同步）超步构成，节点在 Execute 阶段基于上一轮只读快照并发执行，写入经待提交缓冲区在 Update 阶段原子合并并快照。双缓冲消除了同轮竞态，也带来了 interrupt 必须在超步边界、循环不走调用栈、状态变更延迟一轮可见等特性。

常见错误 ​

  1. 误认为同一 Superstep 内节点之间可以互相看到写入。现象：节点 A 写入 x=1 后，并行节点 B 读到的 x 仍是旧值。原因：BSP 双缓冲机制保证同轮隔离。修复：将 B 放到下一个超步（通过边让 B 的前驱是 A），或把需要基于新值计算的逻辑合并到同一节点。
  2. 误认为 interrupt() 能立即暂停当前节点。现象：在节点函数中调用 interrupt 后，后续代码似乎仍在执行或异常栈混乱。原因：interrupt 是抛出特殊异常冒泡到超步边界，并非暂停当前函数的协程。修复：将中断点设计在节点边界——即节点返回后、下一轮 Plan 之前挂起，不在节点中间等待。
  3. 误认为循环会栈溢出。现象：看到循环边担心深度递归。原因：把图上的环等同于函数递归。修复：理解超步调度模型，循环由递归深度由 recursion_limit 参数控制（默认 25）而非 Python 调用栈。

生产建议 ​

  • 将外部调用（模型、HTTP、数据库）都实现为 async 节点，避免在 Execute 阶段阻塞事件循环，减少屏障长尾；
  • 对耗时长的节点做粒度拆分，让同一超步内节点的耗时尽量相近，缓解长尾等待；
  • recursion_limit 按业务显式设置，对明确知道只需 3–5 轮的图（如重试型循环）设得更小，异常情况尽早失败；
  • 重要业务流程在每轮 Update 后落 Checkpoint（使用 Postgres 后端），故障恢复时从最近一个版本号 resume，避免重跑已完成步骤；
  • 阅读 langgraph/pregel/ 源码时从 atick 方法入手，沿 Plan→Execute→Update 三个私有方法追踪，可快速建立对运行时的整体心智模型。