Unison 分布式垃圾回收（DGC）设计解析：基于弱引用表与 Keepalive 协议的远程 Box 生命周期管理

导读

Unison 的分布式编程模型允许计算在多节点之间自由迁移（Remote.transfer）、在远程节点写入可变箱（Box）并异步调度任务（Remote.fork）。当对象引用跨越节点边界之后，"谁负责回收、何时回收"就成为正确性与内存安全的关键问题。本文以仓库中的设计文档 docs/distributed-garbage-collection.markdown 为主体，完整讲解 Unison 提出的分布式垃圾回收（Distributed Garbage Collection, DGC）方案：如何用一张弱引用 B 表追踪本地 Box、一张弱引用 C 集合追踪本地对象所引用的远程 Box，并通过带"已访问集合"的 Keepalive 消息在节点间递归传播存活信息。读完本文，你将掌握该方案的完整算法流程、b_subs 索引缓存机制、传输窗口期的竞态处理，以及针对循环引用图的回收策略验证方法。

需要提前说明的是：这是一份设计文档（RFC/提案）。从当前仓库源码检索来看，keepalive、BoxId、WeakMap 等符号仅出现在 docs/ 下的设计文档中，在 unison-runtime/src/Unison/Runtime 的运行时实现代码里尚未发现对应实现；它描述的是与 分布式编程 RFC 相配套的分布式能力设计目标，读者应将其作为架构蓝图来理解。

分布式模型背景：Box 与 Remote

在进入 GC 算法之前，需要先建立分布式编程模型的最小上下文。根据 docs/distributed-programming-rfc.markdown，Unison 计算可以跨节点迁移、失败、异步 fork 并被监督：

-- 当前计算正在执行的节点
Remote.here : Remote Node

-- 将剩余计算的执行控制权转移到目标节点
Remote.transfer : Node -> Remote Unit

-- 异步启动一个远程计算，返回可监督的 Task
Remote.fork : ∀ a . Remote a -> Remote Task

-- 创建当前节点上的临时 Box；运行时只是一个 (GUID, Node)
Box.empty : ∀ a . Remote (Box a)

-- 向 Box 写入值；若 Box 已满则等待 Box.take 清空
Box.put : ∀ a . a -> Box a -> Remote Unit

-- 取出并返回 Box 中的值；若 Box 为空则等待 Box.put 填充
Box.take : ∀ a . Box a -> Remote a

-- 类似 Box.take，但值保留在 Box 内
Box.read : ∀ a . Box a -> Remote a

正是这套 API 使"一个节点的堆与 Box 可以引用另一个节点上的 Box"成为可能，也由此产生了跨节点的引用追踪需求。设计文档开篇即点明：分布式 GC 的核心问题，是让一个节点能安全地持有对远程 Box 的引用，同时又不让这些远程 Box 因本地已不再引用而泄漏在远端。

核心数据结构：弱引用 B 表与 C 集合

方案围绕两个以"弱引用"（weak reference）为基础的数据结构展开。所谓弱引用，指的是"键本身不阻止被 GC 回收"——一旦本地堆/Box 不再引用某个对象，对应条目就会因为弱映射的语义被自动移除，无需显式删除：

-- 追踪本地所有 Box 的弱映射：
-- 键是 BoxId，值是包裹了 Box 内容的 MVar Value
-- 一旦本地堆/Box 不再引用某个 Box，该条目自动消失
B_map :: WeakMap BoxId (MVar Value)

-- 追踪"被本地堆/Box 引用的所有远程 Box"的弱集合
type RemoteBox = (BoxId, Node)
C_set :: WeakMap RemoteBox

两者的分工非常清晰：

• B_map 回答"本节点上还有哪些 Box 活着"。由于是弱映射，条目随着本地引用消失而自动清理，天然避免了传统 GC 中"标记-清除"带来的引用表维护负担；
• C_set 回答"本节点正在引用哪些远程 Box"。每个远程 Box 用 (BoxId, Node) 二元组唯一标识，其中 Node 是该 Box 的归属节点（owner）。

每个本地 Box b 还携带一个关联值，以及该值内容所引用的全部 Box 集合 b_subs（即 b 的"被引用子集"，包含本地与远程两种 Box）。b_subs 是整个 keepalive 传播算法的输入。

Keepalive 消息与传播算法

消息结构

节点间依靠 Keepalive 消息维持远程 Box 的存活。消息携带两个关键信息：目标 Box 的 BoxId，以及一个 visited 集合，用于记录"这条 keepalive 已经由谁传播过"，从而避免消息在图中的环上无限循环：

let keepaliveDuration = 20.seconds -- 或任意合适的时长
type Keepalive = Keepalive { b :: BoxId, visited :: Set RemoteBox }

keepaliveDuration 是接收方为 Box 建立强引用的固定时长。设计文档给出的示例值为 20 秒，并注明"或任意合适的时长"——实际取值应在网络延迟、消息丢失容忍度与回收及时性之间权衡。

接收 Keepalive 的处理流程

当节点 n 收到针对 BoxId b 的 keepalive 消息时，按以下优先级处理：

1. 若 n 不拥有 b，直接忽略——正常情况下不应发生，属于防御性检查；
2. 若 (b,n) ∈ visited，直接忽略——说明该 keepalive 是环路上的正常重复，不需要再次处理；
3. 否则，进入正式处理流程：
   • 为 b 建立为期 keepaliveDuration 的强引用，确保在下一个 keepalive 到来前 b 不会被回收；
   • 令 b_subs 为 b 所引用的全部 Box（本地与远程）集合：
     • 若 b_subs 尚未被缓存、且当前没有进程正在索引 b，则启动索引并将结果缓存下来；
     • 若索引在限时内未完成，不要中断索引，而是退而求其次，用 C_set 作为 b_subs 的近似值来处理本次 keepalive 消息——这是保证协议在慢速/大对象场景下仍能及时响应的关键妥协；
   • 对每个 b_i ∈ b_subs 逐一分发：
     • 若 b_i 是远程 Box，向 b_i 的归属节点发送 (Keepalive b_i (Set.insert (b,n) visited))；
     • 若 b_i 是本地 Box，在本节点内递归处理 (Keepalive b_i (Set.insert (b,n) visited))。文档特别注明：无论是否真正走网络，递归传播本地 Box 的 keepalive 都是必需的，因为本地 Box 之间可能相互引用，必须让整条引用链都获得刷新。

注意 visited 集合的作用：每次向子 Box 传播时，都把 (b, n) 插入 visited。这样当消息沿引用环绕回已被访问过的 (b, n) 时，第二步的判断就会将其忽略，使算法在环上至多执行一轮，杜绝了 keepalive 风暴。

传播的终止性与近似性

值得强调的是第 3.2 步的容错设计：b_subs 的完整索引可能耗时较长（涉及深层扫描），而 keepalive 必须在 keepaliveDuration 量级内尽快扩散。因此协议允许"用 C_set 近似代替 b_subs"。C_set 可能比 b_subs 大（包含历史引用过的远程 Box），但这种近似只会导致"多发一些 keepalive"，而不会导致"漏发 keepalive"——漏发才会造成远程 Box 被误回收，多发只是轻微浪费，方向上是安全的。

b_subs 的索引与缓存：Optional [BoxId]

计算 b_subs（即 b 内部值所传递引用的 Box 集合）是 keepalive 传播的数据基础，设计文档给出了三点实现要点：

1. 每个运行时值 v 维护一个可变缓存 Optional [BoxId]，记录 v 传递引用的 Box。Optional 语义很讲究：None 表示"尚未计算"，Just subs 表示"已计算完成"，从而可以区分未索引与索引完毕两种状态；
2. 对 v 做一次深度扫描（deep scan）以递归填满各层缓存。由于索引是从值出发的递归过程，子树的值也会顺带获得各自的缓存；
3. 避免重访已有缓存的子树。当深扫遇到一个已经带有 Just [...] 缓存的子值时，直接复用其缓存，不再下钻。

这套"带缓存的可变深度扫描"本质上是一种增量式引用图遍历：首次访问时全量索引，后续访问只付出缓存命中的成本。它既服务于 keepalive 的 b_subs 计算，也可复用于传输前的依赖打包。

传输窗口期：续延与 Box 更新到达时的竞态保护

接收方的动作

当续延（continuation）c 从节点 x 传输到节点 y，或值 c 通过 Box.put 从 x 写入 y 时，节点 y 会把 c 引用的非本地 Box 加入 C_set。文档建议这项索引可以作为网络反序列化过程的一部分完成——即"边收边索引"，值一落地，引用关系就已登记，无需二次遍历。

竞态窗口与双重 keepalive

这是整个方案中最微妙的部分。设想如下时序：

1. 节点 x 持有对某远程 Box 的引用，并依赖它维持 keepalive；
2. x 把包含该引用的续延传输给 y；
3. 若 x 在传输完成后立即认为"引用已转移，我不再需要续 keepalive"，而 y 的 keepalive 尚未发出，两者之间就存在一个空档期——被引用的远程 Box 可能在这个空档内被其归属节点回收。

设计文档给出的约束是：

• 节点 x 在传输过程中必须对 c 引用的所有 Box 发送 keepalive（文档注明"这应该无需特殊处理就会发生"——因为正常情况下 x 本来就在为其引用维持 keepalive）；
• 传输完成之后至少再补发一次 keepalive，以覆盖 y 接手 keepalive 之前的竞态窗口；
• 为满足上述要求，节点 x 和 y 在 c 被传输期间可能都需要索引 c：x 需要知道该发哪些 keepalive，y 需要知道该登记哪些远程引用。

这一设计体现了分布式 GC 的通用原则：存活信息的交接必须存在重叠期（overlap），绝不允许出现"旧持有者已放手、新持有者未接手"的真空。

FAQ：设计自洽性的论证

设计文档用两个已解答问题 + 两个开放问题来检验方案的自洽性。

Q：C_set 会包含本地 Box 引用的全部远程 Box 吗？

A：会。 论证的关键在于"远程 Box 引用只能从哪里来"。要把值存入 b，该值必然是在某个续延内构造的（Box.put 与 Remote.transfer 都发生在续延中）。因此：

• 远程 Box 引用要么来自从远程节点传输过来的续延，
• 要么来自从远程节点 Box.put 过来的值。

而这两种情况在"接收续延或 Box 更新"的处理流程中，都会把其中的远程引用索引进 C_set。于是可以归纳证明：任何进入本地堆/Box 的远程引用，都必然经过一次被索引进 C_set 的入口。这是该方案正确性的核心归纳不变量。

Q：能否说 durable 值不维持 Box 存活？durable 值是否不应期待其引用的 Box 中保留特定值？

A：……（设计文档未给出结论）。这是一个开放问题：Durable 值是持久化存储中的不可变数据，若 durable 值内部引用了远程 Box，那么"durable 的持久性"与"Box 的临时性"之间如何协调，文档留待后续设计讨论。

Q：如果远程节点已经算出了某个运行时值的 Optional [BoxId]，它是否应该把缓存一并传输给我？

A：……（设计文档未给出结论）。这是第二个开放问题，涉及缓存的传输带宽成本与接收方重算成本的权衡，同样留待后续决定。

两个未决问题均以省略号占位，说明这份文档当时处于设计讨论的中期阶段，尚未收敛到最终决议。

优化：延迟到首次传输才分配 Box

设计文档提出了一项明确的优化措施：

在首次传输之前，避免把 Box 分配进 B-map 和 C-set。首次传输前，Box 只是栈上的普通 MVar。

其动机很直观：本地 Box 若从不跨节点，就完全没有分布式 GC 的记账开销。只有 Box 真正开始跨节点流动（被传输或写入远程引用）时，才把它登记进弱映射/弱集合。这让单节点场景的 Box 操作保持与普通 MVar 一致的轻量性能，而把 DGC 的固定成本只施加给确实需要分布式语义的 Box。

示例：循环引用图的回收验证

设计文档用一段伪 Unison 代码构造了一个跨越两个节点的循环引用图，用于检验 keepalive 算法在环上的表现：

type Foo = Ref (Box Foo) | No_Ref

do Remote
  Remote.transfer x
  q := Box.make
  r := Box.make
  Remote.transfer y
  s := Box.make
  t := Box.make
  Remote.fork <| do Remote
    sleep-random-duration
    Box.take t
  Box.put q (Ref s)
  Box.put s (Ref r)
  Box.put r (Ref t)
  Box.put t (Ref q)
  Box.put t No_Ref -- maintains cycle until Box.take t, then breaks cycle

对应的引用拓扑：

    x     y
   ┌─┐   ┌─┐
 ┌>│q│──>│s│
 │ ├─┤  /├─┤
 │ │ │ / │ │
 │ ├─┤└  ├─┤
 │ │r│──>│t│
 │ └─┘   └─┘
 └────────┘

这个例子的巧妙之处在于它同时检验了两类能力：

1. 跨节点循环：q → s → r → t → q 构成跨节点 x/y 的引用环。keepalive 携带 visited 集合沿环传播，会在绕回 (q, x) 时被第二步"(b,n) ∈ visited 则忽略"截停，从而在环上至多遍历一圈，验证了 visited 机制对环的终结能力；
2. 循环的主动断开：Box.put t No_Ref 把 t 的内容替换为无引用的构造子，使环在 t 处断开；而 Remote.fork 中异步执行的 Box.take t 会在随机延迟后取走 t 的值。整个例子演示了"远端异步消费者 + 主动断环"场景下，DGC 必须正确区分"环仍被外部引用"与"环已无人引用"两种状态——前者需持续 keepalive，后者允许各 Box 自然消亡。

方案定位与仓库证据

最后，明确一下该方案在仓库中的定位与可继续探索的资料：

• 设计文档本体：docs/distributed-garbage-collection.markdown（本文全部算法与代码示例的来源）；
• 配套 API 设计：docs/distributed-programming-rfc.markdown 定义了 Box、Remote.transfer、Remote.fork、Durable 等分布式原语，是本方案的语义基础；
• 早期讨论：docs/distributed-api-discussion-v1.md 记录了 v1 API 讨论，其中关于 Future.keepalive、僵尸任务清理、监督与 GC 的思考（如"5,000 个节点共享 Future 时 keepalive 泛滥"的应对思路）与本方案一脉相承；
• 运行时能力前提：unison-runtime/src/Unison/Runtime/docs.markdown 说明 Unison 运行时必须支持"对任意值（含循环）进行哈希、序列化、反序列化与依赖计算"，这正是续延跨节点传输、以及为 c 建立引用索引的前提；
• 实现状态：经检索，unison-runtime 的源码（如 Machine.hs、Builtin.hs）中未发现 WeakMap/BoxId/keepalive 的直接实现，说明本文所述为设计蓝图而非已落地代码。任何基于该方案的实施，都需要同时满足运行时对任意值索引/序列化能力的要求，并落实"传输重叠期双重 keepalive"的竞态保护。

结语

Unison 的这份分布式 GC 设计以两个弱引用结构（B_map、C_set）为骨架，以携带 visited 集合的 keepalive 消息为传播手段，以"可缓存、可近似"的 b_subs 索引为数据基础，构成了一套完整、自洽、容错的远程 Box 生命周期管理方案。其三个值得反复品味的设计决策是：弱引用自动清理降低了引用记账成本、visited 集合保证了环上的有界传播、索引超时时用 C_set 近似保证了协议在慢路径下的及时性。理解这套方案，也有助于把握 Unison 分布式原语（Remote.transfer、Box.put、Remote.fork）在引用安全层面的整体设计哲学。