原子快照 | Codeboy's Blog

形式陈述

固定 $n$ 个异步进程 $p_0,\ldots,p_{n-1}$ ，每个进程一次只执行一个操作。快照对象保存向量 $(v_0,\ldots,v_{n-1})$ ，提供两个接口：update_i(v) 只由 $p_i$ 调用，替换第 $i$ 项；scan() 由任意参与进程调用，返回整个向量。目标是使这两类操作共同线性一致，并且wait-free。

采用单写多读atomic 寄存器数组 $A$ 。每个槽整体原子地保存记录 (seq, value, view)：无界递增整数序号、当前值，以及一个长为 $n$ 的快照。初值为 A[i] = (0, v_i^0, initialValues)。写者有私有计数器 seq_i = 0；本页把整个记录的一次读写算作一个基础操作，尚不计算记录的位宽与拷贝成本。

collect() 按固定顺序各读一次 $A[0],\ldots,A[n-1]$ ，返回记录数组。它本身不保证快照一致。下面使用 Aspnes 讲义 Algorithm 20.1 的复用相邻 collect 版本：

text

scan():
    initial = collect()
    previous = initial
    loop:
        current = collect()
        if current == previous:
            return values(current)
        if some j satisfies current[j].seq >= initial[j].seq + 2:
            return current[j].view
        previous = current

update_i(v):
    s = scan()
    seq_i = seq_i + 1
    A[i].write((seq_i, v, s))

数组相等指逐槽记录相等；序号不回绕使“写过又写回相同值”仍可被识别。内部 scan 与外部扫描使用同一算法；本进程执行它期间不会同时更新自己的槽。更新先扫描，再把新值、序号和扫描结果作为一个完整记录发布。

直觉

两次相同收集是一张“中间有过稳定状态”的证据，但只靠等待稳定可能永远重试。算法让每个更新者先交出一份完整视图：若它快到足以反复干扰别人，扫描者就借用它已经算好的答案。这是帮助机制的一种形式，帮助发生在信息共享上，不必由某个 helper 替别人执行同一段代码。

关键不是任意旧视图都可用，而是要证明被借用视图的采集发生在本次扫描区间内。序号至少增加二，正是定位这段时间包含关系的证据。

例子与边界

一次 collect 可以读到从未存在的向量

取三个进程： $p_0$ 只更新槽 $x$ ， $p_1$ 只更新槽 $y$ ， $p_2$ 扫描； $p_2$ 自己的槽始终固定，下面省略该分量。两个变化槽初值为 $(x,y)=(0,0)$ 。扫描者先读 $x=0$ ；随后 $p_0$ 发布 $x=1$ ，再由 $p_1$ 发布 $y=1$ ；扫描者最后读 $y=1$ 。它返回的对应分量为 $(0,1)$ ，但真实数组只经历 $(0,0)\to(1,0)\to(1,1)$ ，没有出现 $(0,1)$ 。每个槽始终只有自己的写者，各次基础读写也都原子，错误仍然成立。

被持续更新时怎样借用答案

令 $n=3$ ，值向量初始为 $(0,0,0)$ ， $p_0$ 扫描， $p_1$ 更新， $p_2$ 静止。下表中的序号向量只摘录每个记录的 seq 字段，完整 collect 仍读取全部记录。

步骤	$p_0$ 观察或 $p_1$ 发布	推理
首次 collect	序号 $(0,0,0)$	保存为 `initial` 与 `previous`。
$p_1$ 第一次更新	`(1, 10, (0,0,0))`	内部扫描先取得初始值，然后发布值 $10$ 。
第二次 collect	序号 $(0,1,0)$	两次不等，增量仅一，还不能借用。
$p_1$ 第二次更新	`(2, 20, (0,10,0))`	它先取得包含旧值 $10$ 的视图，再发布值 $20$ 。
第三次 collect	序号 $(0,2,0)$	达到初始序号加二，返回存储视图 $(0,10,0)$ 。

扫描者观察到同一写者两次递增后，借用第二次更新之前完成的内部扫描 — p0 的三次 collect 观察序号零、一、二；第二次更新携带的视图零、十、零在 p0 的调用区间内取得。

最后返回的不是最新值向量 $(0,20,0)$ ，但它确实出现在调用期间：第一次发布之后、第二次发布之前。线性一致快照要求区间内有一个合法位置，不要求返回时仍是最新。

正确性与步数界

若相邻两次 collect 相等，对每个槽，从第一次读该槽到第二次读该槽之间都没有发布：否则无界序号必变。所有这些区间共同覆盖“第一次 collect 结束到第二次 collect 开始”的间隙。因此该间隙内数组恰等于返回向量，可把扫描线性化在那里。

若某槽序号从初次观察的 $k$ 增至至少 $k+2$ ，当前记录携带的内部扫描必在发布 $k+1$ 或更晚记录之后才开始；那次发布又在外层扫描初次读到 $k$ 之后。内部扫描在当前记录发布前结束，而当前记录又在外层读到它之前发布。因此内部扫描的整个区间嵌在外层扫描内。借用它的线性化位置即可。若内部扫描本身也借用了他人的视图，就沿已经完成且更早返回的扫描追溯；有限执行前缀不容许无限倒退，最终到达相邻 collect 相等的直接扫描。每次 update 则在线性发布记录时生效。

终止计数使用本进程的槽不会变化这一前提。每次未返回的相邻比较，至少有一个其他槽发生序号变化；同一个槽相对初次观察累计变化两次，就会触发借用。因此至多有 $n-1$ 次失败比较，下一次比较必返回，总 collect 数至多 $n+1$ 。本页每次完整读取 $n$ 槽，所以 scan 至多执行 $n(n+1)$ 次基础读，update 再加一次基础写，均为 $O(n^2)$ 。若缓存本进程的槽，可省去每轮一次读；不要把优化后的计数与这里的伪代码混用。

只有相等检测而没有借用分支时，对手可在每次收集之间插入更新，让扫描永久失败。有限位宽序号若直接回绕，也会让记录变化被相等比较掩盖；有界寄存器快照需要额外构造。宽记录包含整份视图，因而基础操作数不是机器字操作数，更不是传输位数。

推论与应用

原子快照把逐槽原子性提升到整个向量的读接口，可为共享状态监测和其他并发算法提供一个共同观察点。但它只更新调用者自己的分量，并不提供任意多项同时修改的事务。

Chandy–Lamport 分布式快照记录因果一致的进程与通道状态，目标是消息传递执行中的一致切片；本页则要求扫描与更新有共同线性化，并返回扫描区间内的寄存器向量。二者都叫快照，规格与模型却需分别检验。

自测：在上表第二次 collect 后，让 $p_1$ 停止，其他进程也不更新。下一次 scan 比较应走哪一分支，返回什么？答案是两次记录相等，直接返回 $(0,10,0)$ 。再说明为什么只观察到序号加一时不能立即借用：第一次更新的内部扫描可能在外层调用开始前就已完成，随后写者暂停到外层调用中才发布。

参考资料

James Aspnes, Notes on Theory of Distributed Systems, 2026-04-25 版，§20.2 “Snapshots using double collects with helping”，Algorithm 20.1，印刷页 193–196；本页采用相邻 collect 复用形式。
Yehuda Afek, Hagit Attiya, Danny Dolev, Eli Gafni, Michael Merritt, and Nir Shavit, “Atomic Snapshots of Shared Memory”, Journal of the ACM 40(4), 1993, pp. 873–890，§3 与 Figure 3。原文使用 double collect 组织扫描，不能将它的循环次数直接视为本页单次 collect 的次数。

形式陈述 ​

一次 collect 可以读到从未存在的向量 ​

被持续更新时怎样借用答案 ​

正确性与步数界 ​

反向链接

形式陈述

一次 collect 可以读到从未存在的向量

被持续更新时怎样借用答案

正确性与步数界