计算机系统工程-06：故障原子性

故障问题

转账需要完成两次修改：从付款账户扣钱，再给收款账户加钱。程序运行到一半时，机器可能突然断电。如果只保存了扣款，重启后就会少一笔钱。

本节讨论怎样把一组修改完整地保存，以及怎样在故障后恢复。先用单台服务器上的银行程序说明问题，再介绍临时副本、文件系统日志、重做日志、撤销日志和检查点。

这里采用停止故障（fail-stop）模型：故障发生时，参与操作的组件一起停止，内存中尚未持久保存的信息可能丢失。磁盘上已经完成的写入保留；故障时正在进行的写入，需要根据设备和日志格式提供的保证判断是否完整。多个节点只停一部分、剩余节点继续执行的情况，需要进一步讨论分布式协议。

为便于分析，前面的单次转账按串行执行理解。单台机器也可以同时处理多个线程的请求；这些请求仍需要锁或其他并发控制，才能协调共同访问的数据。

故障范围

故障模型规定哪些组件停止，以及哪些信息仍可用于恢复。机器突然断电时，内存中的页缓存、局部变量与执行进度可能丢失；可靠保存的磁盘记录则按设备提供的条件保留。

一个应用进程退出时，操作系统和其他进程可能仍在运行，内核缓存也可能继续回写。多机系统中，一台停止后，其他节点还可能继续接受操作。因此，分析或测试时要明确故障发生在哪个范围，再判断恢复能读取哪些记录。

下面按单机停止故障展开，并在重启后先完成恢复，再向应用提供账户结果。网络中的结果确认与跨节点提交，可以继续结合 RPC 和分布式协议理解。

分析步骤

读一张故障图时，可以先列出以下信息：

原状态与完整新状态，例如 10,10 和 0,20。
程序已经计算出的值，哪些只在局部变量中，哪些进入共享缓存。
磁盘实际保存了哪些数据，日志保存了哪些记录。
提交凭据是否完整有效，是否已经向用户确认。
故障后依据什么完成修改或恢复旧值。

程序执行、落盘、提交和回复各有自己的时刻。按这些阶段记录状态，再对照恢复规则，就能逐步判断中途失败的结果。

存储基础

文件保存一串字节，1 字节等于 8 bit。磁盘和 SSD 保存长期数据，内存保存程序正在使用的数据。断电后仍能保留的信息称为持久数据；把修改送到稳定存储并确认完成，通常称为落盘。

操作系统会把文件的一部分放在内存中的页缓存（page cache）里。页是内存管理的一种固定大小单位；缓存页被修改后，与磁盘内容不同，称为脏页。操作系统随后把脏页写回文件，这个过程称为回写。

mmap 把文件映射到进程的地址空间，程序可以通过访问内存来读取或修改文件。下面使用共享映射：修改会进入文件的页缓存，也可能被映射同一文件的其他进程看到，操作系统可以自动把它们回写到文件。

fsync 用于等待指定文件的修改按接口要求保存到存储设备。调用时传入已打开文件的描述符 fd，也就是操作系统交给进程的文件访问编号。它需要处理文件数据、相关管理信息和设备缓存的持久化，调用者还要检查返回结果。

程序修改页缓存后，后台回写可能先于显式 fsync 发生。因此，分析故障时需要看哪些内容已经落盘。fsync 可以确认持久化进度，涉及多个页的修改仍可能在执行过程中只完成一部分。mmap 手册、fsync 手册给出了相应接口含义。

图中的 memory 表示内存，disk 表示持久存储；time 箭头表示时间方向，闪电表示故障。实线方框通常表示已保存的内容，虚线或淡色方框表示尚未写入、已丢失或已删除的内容，具体状态结合图旁标注理解。

映射文件的地址范围可以大于当时可用的物理内存，操作系统按页调入并回写。重做方案将未提交新值保存在私有缓冲区，是为了避免它们提前进入银行数据文件；操作系统可能另行管理私有内存的换页，不能把两种落盘位置混为一谈。

转账过程

设账户 a、b 各有 10 元，从 a 向 b 转 10 元，完整结果应为 a=0,b=20。银行只做账户间转账时，所有账户余额之和应保持不变。这种每次正确操作都需要满足的条件称为不变量（invariant）。

下面是直接修改银行文件的简化过程。代码用于说明操作顺序，其中 map_shared 建立共享映射，sync_file 打开文件并完成同步、检查错误，notify_user 返回成功结果。

def transfer(bank_file, account_a, account_b, amount):
    """直接修改共享映射，再等待文件写入完成。"""
    records = map_shared(bank_file)

    # 两次赋值先修改页缓存中的账户记录。
    records[account_a] -= amount
    records[account_b] += amount

    # 同步成功后，才向用户报告完成。
    sync_file(bank_file)
    notify_user()

扣款页已经写入，收款页尚未写入时发生故障

从左到右看这张图：

磁盘中的 a、b 都为 10，总额为 20。
建立映射后，两个余额进入页缓存。
程序在内存中完成扣款和收款，页缓存变为 0,20，磁盘仍为 10,10。
操作系统先把 a 所在的页写回，磁盘变为 0,10。
b 所在的页还没写回，机器就停止了。内存里的 b=20 丢失，重启后只能读到总额为 10 的磁盘状态。

即使程序按顺序执行了两次赋值，设备也要分次写入不同位置。这里假定两个账户处于可以分别写回的页或存储单元中，从而展示部分落盘的情况。

检查转账时，还可以分别记录总额、余额限制、接受的请求数与每笔结果。总额保持不变和每笔请求只产生一次效果，各有自己的检查条件；后面的重复回放例子会用到这一点。

思考题：机器在转账过程中发生故障，余额可能是什么？在 fsync 之前和执行期间分别怎样分析？

解答：

原状态是 10,10，完整新状态是 0,20。如果两个修改都没落盘，重启后仍为 10,10；如果都落盘，则为 0,20。只落盘扣款会得到 0,10，只落盘收款会得到 10,20，两种结果都破坏了总额为 20 的不变量。

在 fsync 之前，后台回写也可能保存部分修改；执行期间，同步也可能只完成部分页。判断依据是实际持久化的内容。fsync 成功返回后，才能根据接口约定确认相关修改已保存。

原子性

全有或全无原子性（all-or-nothing atomicity）要求一组修改在恢复后具有完整结果：要么全部保留，要么全部撤销。

对于这次转账，恢复后可以保留 10,10，也可以保留 0,20。程序需要把 0,10 这样的中间状态修复好，再对外提供服务。

原子性描述一组修改怎样共同生效，持久性描述已经确认的结果怎样在故障后保留。向用户报告转账成功后，恢复过程必须能够保留这笔完整转账。尚未收到成功回复的操作，其结果还需要根据持久记录确认。

实现时，磁盘仍然可能短暂保存中间状态。系统保存额外的副本或日志，重启后根据这些信息恢复完整结果。

副本替换

临时副本（shadow copy）先保留原文件，把本次修改放到另一份文件里，体现写时复制（copy-on-write）的思路。这里先复制整份文件，再修改副本；新文件完整保存后，把正式文件名指向新版本。

def transfer_with_copy(bank_file, account_a, account_b, amount):
    """在临时文件中完成转账，然后发布新版本。"""
    temp_file = make_temp_name(bank_file)
    copy_file(bank_file, temp_file)
    records = map_shared(temp_file)

    # 中间状态只出现在临时文件中。
    records[account_a] -= amount
    records[account_b] += amount
    sync_file(temp_file)

    # 临时文件和正式文件位于同一文件系统。
    rename_file(temp_file, bank_file)
    sync_directory(parent_directory(bank_file))
    notify_user()

copy_file 对应复制文件的辅助过程，rename_file 对应改名接口。目录保存名称与文件的对应关系，sync_directory 用于持久保存改名后的目录项。上述代码暂按单个转账执行，实际实现还需要保证读取和替换期间没有冲突的并发修改。

复制、扣款、收款或同步临时文件时发生故障，正式的 bank 都保留完整旧版本。重启后可以清理未发布的临时文件，再重新处理这次请求。

文本编辑器也会保留恢复所需的文件。例如 Emacs 可以创建名称末尾带 ~ 的备份文件，并使用自动保存文件保存编辑过程中的内容。这些文件帮助找回旧内容或尚未正式保存的修改。具体编辑器的备份、自动保存和正式发布规则需要分别查看；本例采用“修改新副本，最后替换正式名称”的过程来说明原子更新。Emacs 备份文档

同一文件系统中的 rename 可以原子替换已有目标名称，运行中的路径查找会取得替换前或替换后的文件。已经打开旧文件的描述符可以继续访问旧对象。要让改名结果在故障后持久保留，还要同步有关目录，并由文件系统提供相应的恢复保证。rename 手册和 fsync 手册说明了这些条件。

思考题：复制或同步临时文件时发生故障，应该怎样恢复？为什么还要分析 rename？

解答：

正式文件仍是完整旧版本，可以删除未发布的临时文件，将这次转账按未完成处理。临时文件同步成功后，已经具备完整的新余额。

rename 会修改目录项和文件管理记录，这些信息分布在多个存储位置。故障恢复还要保证这些记录相互一致，才能可靠地使用旧版本或新版本。

改名过程

inode 是文件系统保存的一份文件管理记录，记录文件大小、权限和数据块位置等信息。目录项建立 文件名 → inode 号 的映射。一个 inode 可以有多个名称；硬链接计数记录有多少目录项指向它，图中用 refcount 或 rc 表示。

删除一个名称时，系统减少相应链接计数。链接计数为 0，且没有需要继续保留文件的打开引用时，文件系统可以回收它的空间。下面暂忽略打开引用，只看目录项与链接计数的关系。

改名涉及目录项以及两个 inode 的链接计数

初始状态中，bank → inode 12，bank_temp → inode 13，两个 inode 的链接计数均为 1。替换后应只保留 bank → inode 13，inode 13 的链接计数仍为 1；旧 inode 12 没有名称，链接计数为 0。

把这次替换拆成四个逻辑步骤：

步骤	目录项	inode 12 的计数	inode 13 的计数
初始	bank 指向 12，bank_temp 指向 13	1	1
① 修改目标名称	bank 和 bank_temp 都指向 13	1	1
② 增加新文件计数	两个名称都指向 13	1	2
③ 减少旧文件计数	两个名称都指向 13	0	2
④ 移除临时名称并减计数	只保留 bank 指向 13	0	1

这张图用简单步骤展示需要共同完成的管理信息修改。真实文件系统的内部顺序、锁和日志格式由实现决定。

改名故障

两个名称指向 inode 13，但链接计数仍为 1

步骤①之后，目录中的两个名称都指向 inode 13，计数却仍为 1。如果恢复后直接删除其中一个名称，计数会变为 0，文件可能被回收。剩下的名称还指向已回收的 inode，后续访问就会出错。

同时，inode 12 已失去目录项，计数还为 1。文件系统可能继续认为它被使用，从而无法回收这份空间。这称为空间泄漏；持续发生时，可用 inode 或磁盘空间会逐渐耗尽。

思考题：在哪些步骤之后发生故障，会留下不一致的管理信息？

解答：

①之后，inode 13 有两个名称、计数为 1；inode 12 没有名称、计数为 1，两处都不一致。

②之后，inode 13 的两个名称与计数 2 相符，inode 12 仍没有名称却保留计数 1，旧文件可能泄漏。

③之后，按图中“移除名称并减计数”作为一个逻辑步骤的简化模型，两个名称与计数 2 相符，旧文件计数为 0，管理关系已一致，但改名还没完成。真实实现还需处理步骤内部及回收过程的故障。

④完成并持久化后，只保留 bank 指向 inode 13，计数为 1，替换完成。

应用知道自己创建过 bank_temp，可以清理没有发布的临时文件。目录项、inode 和空间分配之间的一致性则需要文件系统自行恢复。应用可能长期不启动，也可能反复制造临时文件；文件系统必须能够独立完成管理记录的修复，避免空间持续泄漏。

应用负责转账总额等业务条件，文件系统负责名称、inode、数据块归属等管理条件。临时副本方案依赖改名具有相应原子性，其他涉及多处管理记录的文件接口也需要自己的故障恢复机制。

文件日志

文件系统日志（journal）在专用区域记录一组待完成的修改，包括要修改哪个块，以及这个块最终应保存什么。数据块在文件中的正常存储位置称为原位置，图中用 home 表示。

先写日志并提交，再修改原位置；故障时根据提交状态处理

一种便于理解的日志流程如下：

把本次修改写入 journal，并确认记录已持久保存。
写入并持久保存提交标记，表示这组记录完整且决定生效。
按日志修改原位置。
确认原位置的结果已持久保存后，回收对应日志空间。

故障发生在有效提交标记建立之前，恢复时丢弃这组未提交日志；在这段时间，协议保持原位置的旧内容。故障发生在有效提交之后，即使只改了部分原位置，也能根据日志补齐全部修改。

根据日志再次写入规定结果，称为重做（redo）。日志保存了恢复所需的新内容，因此原位置可以分多次写入。日志区域也要可靠保存，提交记录的完整性将在后面解释。

日志可以放在文件系统为它保留的块中，也可以使用专门的设备；“journal”表示这块区域的用途。每条修改至少需要让恢复程序知道目标位置及相应的新内容。同一事务可能影响目录块、inode 块和分配位图，日志通过一项共同提交决定把这些位置联系起来。

实现时，可以让底层块写入接口先收集修改，再统一保存日志。上层的改名或追加代码仍计算需要更新的块，日志层负责把这些更新组织为事务。它需要完整捕获受保护的修改，并在提交前阻止原位置提前保存未提交状态。这样，不同文件操作可以使用同一套恢复机制。

改名恢复

改名日志保存四项最终修改和 COMMITTED 标记

图中的磁盘从左到右包括 inode 位图、数据块位图、inode 区、数据块区和 journal。位图用每个 bit 记录相应对象是否已分配；dir 是保存目录项的数据块。

这次改名在 journal 中保存四项最终结果：

bank → inode 13；
删除 bank_temp 目录项；
将 inode 12 的链接计数设为 0；
将 inode 13 的链接计数设为 1。

日志描述每个管理位置完成后应保存的值。写入 COMMITTED 后，恢复过程就能够完成这四项修改。

目录项只修改了一部分，但已提交的日志保存了完整结果

故障时，原位置出现两个名称指向 inode 13、链接计数仍为 1 的状态。右侧 journal 保留全部最终值及提交标记。恢复时依次完成名称映射、临时名称删除和两个计数修改，最后得到 bank → 13,rc(12)=0,rc(13)=1。

思考题：只更新了目录项就发生故障，为什么有日志后仍能恢复？什么时候可以删除日志？

解答：

有效的 COMMITTED 标记确认这组修改需要完成；日志中的四项最终值提供了补齐修改所需的信息。恢复会把各项都设置为规定结果，即使其中一项已经写入，也可以再次设置为同一值。

需要等这些最终结果已保存到原位置后再删除日志。如果原位置仍缺少部分修改，提前删掉日志就会失去恢复依据。

文件追加

文件追加也会同时修改内容和管理信息。设 inode 13 已使用数据块 6、7、8，再追加一块新内容到块 9。

追加块 9 同时修改位图、数据、块指针和文件大小

日志里需要记录四项修改：

项目	修改	用途
数据块位图	`bit[9]:0→1`	把块 9 标为已分配，避免再分配给其他文件
数据块 9	保存追加内容	保留实际新增的字节
inode 块指针	`ptr[3]:null→9`	让文件的第 4 个数据块指向块 9
inode 大小	`size:3→4`	让读取能够覆盖新增内容

ptr[3] 从 0 开始编号，因此是第 4 个指针。图中的 size 按块数表示，真实 inode 通常用字节数记录文件长度。数据块大小固定时，增加一个块对应增加相应数量的字节。

只有位图更新，可能造成已分配空间缺少文件引用；只有指针更新，可能让文件指向仍被视为空闲的块；只有大小更新，读取可能遇到尚未建立的内容。因此这些管理记录要共同恢复为一致状态。

写入成本

把所有修改都写入 journal 后，还要写一次原位置。同一份受保护内容通常写两次，会增加磁盘或 SSD 的写入量。

231 GB 的游戏安装内容用于说明大量数据的写入成本

图中列出的《Call of Duty: Modern Warfare》安装内容为 231 GB。若一次写入这么多新数据，并让全部文件数据都经过完整日志，在忽略元数据等额外开销时，写入量约为：

$231\ \text{GB}+231\ \text{GB}=462\ \text{GB}$

这里按实际被修改的数据量计算。修改已有大文件中的一个块，只需要记录受影响的块；整个文件的容量用来说明大量内容写入时的成本。

元数据包括目录项、分配位图、块指针和文件大小。元数据损坏会影响文件定位、空间归属和回收，错误可能波及其他文件。文件内容损坏则会影响对应数据，应用可以通过校验和等方式发现部分错误。

元数据通常比文件内容小，文件系统只让元数据经过 journal，可以减少日志写入量。文件内容怎样保存、怎样与元数据排序，还要根据日志模式和应用要求安排。校验和用于检查内容是否符合预期，应用仍需要保存可用于恢复的副本或日志。

例如下载页面给出文件的预期哈希值。下载结束后重新计算哈希并比较，可以发现内容与预期不符；程序随后可以重新下载或读取可靠副本。检测到错误后仍需要恢复途径。元数据错误还可能让系统找错数据块或错误回收空间，因此文件系统需要维护这类结构自身的一致性。

日志模式

ext4 的 data=writeback、data=ordered、data=journal 规定文件数据怎样参与日志和写入排序。下面继续用追加块 9 的例子，图中蓝色方框表示三项元数据修改，绿色方框表示块 9 的内容，黄色方框表示提交标记。

回写模式

writeback 只记录元数据，块 9 的内容可以在其他时刻写入

data=writeback 把位图、块指针和大小写入 journal，文件内容直接写到原位置，数据写入与元数据提交之间缺少这里所需的先后保证。

假设元数据日志已提交，块 9 的新内容还没落盘就发生故障。恢复重做元数据后，文件有四个块、最后一个指针指向块 9，但块 9 仍可能保留分配前的旧内容。文件结构能够恢复，新增内容的持久化要由其他机制确认。

有序模式

ordered 在提交相关元数据之前先保存块 9 的新内容

data=ordered 仍只记录元数据，但要求与这次元数据修改相关的数据先写入原位置，再提交相应元数据日志。

图中绿色 block 9 data 位于黄色 COMMIT 之前。只要恢复确认本次元数据事务已提交，块 9 就已经保存新增内容。随后重做元数据，文件指针和大小把这块已写好的内容纳入文件。

这项排序保护了本例中新块与元数据的关联。任意覆盖已有文件多个页的修改，还需要应用自己的事务边界与恢复方案。

完整日志

journal 把三项元数据和块 9 内容一起记录，之后写回原位置

data=journal 把元数据和文件内容一起写入 journal。有效提交后，恢复可以同时重做位图、块指针、大小和块 9 的内容，让本次日志事务包含的追加完整恢复。

新增内容先写 journal、再写原位置，写入量较大。文件系统划分日志事务的范围与应用划分转账的范围还需要协调；一次银行操作如果涉及多次独立文件调用，仍需设计应用层事务。

模式	journal 保存的内容	块 9 与元数据提交的顺序	本例恢复后的新增块
writeback	三项元数据	不要求块 9 先写好	可能包含旧内容
ordered	三项元数据	块 9 先写好，随后提交元数据	已包含新内容
journal	三项元数据和块 9 内容	日志完整后提交，随后写原位置	可根据日志补齐新内容

三种模式的准确范围可查阅 ext4 文档与 journal 文档。

思考题：只记录元数据时，重要的文件内容怎样保护？ordered 或 journal 能保证整笔银行转账吗？

解答：

应用可以先同步新内容，再发布指向它的名称或管理记录；也可以为相关内容建立应用日志，保存副本并校验完整性。恢复所需的信息要在正式发布前持久保存。

ordered 保证相关数据与元数据的写入顺序，journal 可以恢复同一个日志事务中的数据和元数据。银行转账要求扣款、收款共同完成，应用还要让这两项修改处于受同一提交决定保护的事务中。

提交完整性

日志包含多条记录，它的提交标记也要写入设备。故障可能发生在提交标记写入时，因此恢复程序需要识别“完整且有效的提交”。

一种简化假设是设备对某个写入单位提供全有或全无保证，例如一个扇区写入会完整保存或保持原状。扇区是设备读写的基本单位之一，容量与设备有关。部分硬件通过断电保护电容等装置保留能量，完成已经开始的写入，具体保证需要看设备与存储接口的约定。

小的提交标记可以放进受保护的写入单位。日志内容可能跨多个扇区，常用长度、事务标识、校验和与提交标记共同识别记录边界和完整性。校验和由记录内容计算得到，恢复时重新计算并比较；CRC 是一种常见的错误检测方法。

持久化顺序还要单独保证：先确认相关记录已保存，再建立有效的提交标记。校验和帮助发现缺失或损坏的记录，写入同步负责确认它们已可靠保存。

文件系统块、内存页和设备保证的原子写入单位可能大小不同。假设文件系统按 4 KiB 块组织数据，而设备只承诺特定条件下 512 字节的原子写入，一整个块就跨越 8 个写入单位。提交标记即使能放进一个受保护单位，跨单位的日志仍需验证完整性，并按协议安排持久化。设备的断电保护、电源状态和缓存策略也应符合使用的保证。

思考题：写 COMMIT 时发生故障怎么办？一组记录超过一个扇区时，怎样判断是否完整？

解答：

如果设备对提交标记的写入单位提供原子性，恢复就按有效标记存在或不存在判断。记录跨多个扇区时，还要检查长度、校验和、事务标识及提交标记是否相互匹配。

标记完整且所需记录全部有效，恢复才把事务视为已提交。提交标记缺失或完整性检查失败时，按未提交处理。协议还必须保证有效提交之前，相关日志已经持久保存。

并发副本

现在加入两个客户端。初始 a=b=c=d=100，总额为 400。客户端 0 从 a 向 b 转 100，客户端 1 从 c 向 d 转 100。两笔转账涉及不同账户，但示例中的程序共同使用 bank 和 bank_temp。

客户端 1 把客户端 0 尚未完成的扣款一起发布到 bank

图中安排如下：

时刻	客户端动作	共享临时文件中的余额
初始	临时文件保存原银行数据	`100,100,100,100`
①	客户端 0 把 a 减为 0	`0,100,100,100`
②	客户端 0 被暂停，尚未给 b 加钱	`0,100,100,100`
③	客户端 1 把 c 减为 0、d 加为 200	`0,100,0,200`
④	客户端 1 同步并替换 bank	正式文件变为 `0,100,0,200`

客户端 1 同步的是共同使用的临时文件，它把客户端 0 的未完成扣款也保存并发布了。正式文件的总额成为 0+100+0+200=300，丢失了 100。

一次共享文件同步会保存文件中符合回写条件的修改。它需要配合事务和并发控制，才能区分哪些修改已经完成。

客户端 0 被暂停也可能仅仅是操作系统把 CPU 分配给其他线程。客户端 1 随后运行并完成自己的计算，仍可能与客户端 0 共用脏页。因此，问题会在正常调度中出现。若客户端 1 等客户端 0 完成后才发布共同文件，可以避免本图的半笔转账，但两笔独立转账的完成时间就被绑定在一起；还要处理客户端 0 最终失败时怎样清理中间值。

思考题：两笔转账的账户互不重叠，为什么仍会互相影响？给每个请求使用不同临时文件是否足够？

解答：

两个客户端共同修改一份临时文件及其页缓存，客户端 1 发布时包含了客户端 0 的中间值，因此总额从 400 变为 300。

独立临时文件可以隔离这个中间状态。若两个请求都从同一旧版本复制，并先后替换整个 bank，后发布的文件仍可能覆盖前一笔已完成转账，造成更新丢失。可以对“读旧版本、复制、修改、发布”整个过程加锁，或提交时检查版本，发现旧版本已变化后重新读取并计算。

副本局限

临时副本有三项主要成本：

并发操作需要额外协调。直接替换整份文件时，即使修改不同账户，也可能共享临时状态或覆盖别人的更新。
跨多个文件的修改需要共同发布。连续改名两个文件，中途发生故障会让它们处于不同版本。
小修改可能需要复制整份文件。文件很大时，复制时间和写入量会明显增加。

多个文件可以组织为一个版本目录，先把该版本内的内容保存完整，再通过一个共同的入口或清单切换版本。入口的替换和目录项持久化仍要满足相应条件。普通目录 rename 覆盖目标时通常要求目标目录不存在或为空；具体方案需要依据系统提供的接口设计。

文件日志与临时副本都先在另一位置保存恢复信息。临时副本保存完整文件版本，日志可以只保存本次受影响的位置和结果。因此，日志方法可以进一步用于应用的数据修改。

练习：银行数据分散在两个文件中，一笔转账要同时修改它们。分别创建临时文件，再依次 rename，第二次改名前断电，能否保证整笔转账原子性？采用日志时需要记录哪些信息？

解答：

第一个文件可能已经发布新版本，第二个仍是旧版本，两个改名各自成功也会留下半笔转账。需要建立保护这两个文件的共同提交决定。

日志可以给两项修改同一个事务标识，记录目标文件、目标位置和恢复所需的内容，持久保存完整记录后再提交。故障恢复根据该事务的有效提交状态，把两项共同恢复为完整结果。具体的写前顺序和重做、撤销规则将在下面展开。

事务边界

事务（transaction，简称 TX）把一组需要共同完成的操作组织起来。转账事务包含扣款与收款，常用 begin 标记开始、commit 请求提交。

转账的两项修改处于同一事务，成功回复位于提交点之后

提交点（commit point）是持久记录已经足以确认事务生效的时刻。通过这一点后，即使数据原位置尚未全部更新，恢复程序也要补齐事务结果。

图中初始余额为 10,10，新余额为 0,20。事务在内存中执行到哪一步，与故障后是否需要保留结果，还要结合提交记录判断。服务器应在确认提交后再发送成功回复。

begin、commit 是事务接口的边界标记。实现还需要保存日志、安排写入顺序并执行故障恢复，才能提供对应保证。

请求确认

提交已经持久成立、成功回复却丢失时，客户端需要沿用原业务身份查询结果。完成记录应与业务结果共同生效，重复请求的识别与保留条件见RPC 回复缓存。本节日志则提供故障后恢复这些记录的依据。

重做日志

重做日志（redo-only logging）保存各项修改的新值。提交之前，修改只保存在事务自己的临时内存中；完整日志持久保存后，才允许修改数据文件的共享页缓存。

这一区分很重要：普通局部变量由当前计算使用，写入共享映射则会改变文件页缓存，随后可能自动落盘。下面的 new_a、new_b 只是局部变量。

def transfer_with_redo(bank_file, account_a, account_b, amount, log):
    """先持久保存整个事务的新值，再更新共享文件。"""
    records = map_shared(bank_file)

    # 计算放在事务自己的临时内存中。
    new_a = records[account_a] - amount
    new_b = records[account_b] + amount
    entry = make_entry(
        updates=[(account_a, new_a), (account_b, new_b)]
    )

    # 条目包含边界和校验信息，同步成功确认事务提交。
    log.append(entry)
    log.sync()

    # 现在即使数据只写回一部分，也能根据日志补齐。
    records[account_a] = new_a
    records[account_b] = new_b
    notify_user()

make_entry 把本事务的全部新值编码成一条完整日志条目，并附加识别边界和校验所需的信息。这里 log.sync() 表示确认之前追加的条目已持久保存，调用者需要检查错误。

重做日志保存新余额 3 和 17，可把旧状态恢复到完整新状态

从 10,10 转账 7 元时，新值为 3,17。日志保存 a=3,b=17，恢复程序把两项设置为这些值。数据文件即使只落盘了 a，也可以补齐 b。

重做日志按下面的顺序执行：

读取旧余额，在私有内存中计算全部新值。
追加完整日志条目，确认条目持久保存。
根据条目修改共享页缓存，让系统随后把数据写回原位置。
在确认提交后报告成功。

若尚未建立有效提交记录就失败，临时计算结果可以丢弃，数据文件保持原来的已提交状态。若日志已经有效提交，恢复过程会完成它记载的修改。

思考题：写日志之前直接修改 mmap 中的余额，能否继续只使用重做日志？

解答：

共享映射中的余额进入文件页缓存后，操作系统可能把尚未提交的修改写回磁盘。故障后，这些修改需要恢复旧值，而重做日志只保存新值，缺少撤销依据。

这里的重做方案要求未提交修改保留在事务私有内存中，直到完整日志持久保存，才写入共享页缓存。

日志完整性

追加和同步一条日志也可能分多次写入。假设条目应包含 a=2,b=18，实际只保存了 a=2 和部分后续字节就发生故障，恢复程序必须发现这个条目不完整。

条目可以保存长度、事务标识、所有更新及校验和。扫描日志时，先确定边界，再读取所需字节、验证校验信息。发现未完成的尾部条目时，按未提交处理。

一条完整事务被编码为一个可验证的条目时，这个条目本身可以承担提交凭据。后面介绍的撤销重做日志分多条记录保存修改，需要额外提交记录来确认整笔事务完成。

思考题：sync 本身可能中途失败，怎样判断日志条目完整？校验成功意味着已经持久保存吗？

解答：

恢复时检查条目长度、边界和校验和，发现缺字节或校验不匹配就丢弃未完成的尾部条目。完整性检查有助于识别一次追加是否留下了有效记录。

正常执行时，还要等待日志同步成功，才能向用户确认持久保存。内存里的完整条目也可以通过校验，但它仍需要经过持久化过程。

重做恢复

下面连续进行三笔已提交转账，再尝试第四笔：

事务	日志中记录的新值	故障时的条目状态
T1	`a=8,b=12`	完整且有效
T2	`a=5,b=15`	完整且有效
T3	`a=3,b=17`	完整且有效
T4	`a=2,b=?`	写到一半

前三笔日志已保存，第四笔不完整，磁盘只回写了 a=3

图中 T1、T2、T3 先后提交，页缓存最后为 3,17。后台回写只把 a=3 保存到磁盘，b 仍为初始的 10，磁盘暂时是 3,10。写 T4 日志时发生故障，内存丢失，T4 尚未修改共享数据。

重启后先恢复，再接收新的账户请求。按日志从前向后重做：

步骤	处理	数据结果
恢复开始	读取故障后保存的数据	`3,10`
①	重做 T1：设置 a、b	`8,12`
②	重做 T2：设置 a、b	`5,15`
③	重做 T3：设置 a、b	`3,17`
④	丢弃 T4 的不完整尾部	仍为 `3,17`

顺序重做 T1、T2、T3，忽略 T4，恢复余额 3 和 17

后提交的事务可能覆盖早先的值，因此要按原来的日志顺序重做。最终余额总额为 20，三笔已提交转账都保留，T4 没有生效。

思考题：提交时需要立即 fsync 银行数据文件吗？为什么可以从旧数据或部分回写的数据恢复？

解答：

在这个重做方案中，每笔事务提交时只需先确认完整日志持久保存，银行数据文件可以随后回写。日志保留了所有待恢复的新值，故障后能够补齐。

已提交修改全部保存到数据文件之前，要保留相关日志。执行检查点并删除旧日志时，才需要确认被删除记录所代表的数据已经可靠保存。

提交时刻

正常执行中，log.append(entry) 之后的同步成功返回，程序就能够确认完整条目已持久保存。之后修改数据缓存、发送成功回复，都有日志作为恢复依据。

发生故障时，需要进一步看磁盘上的实际记录。一次同步尚未返回，设备也可能已经完成全部写入；服务器在成功回复送达前宕机，客户端会面对尚未确认的结果。

思考题：重做日志的提交点在哪里？同步返回之前发生故障，事务一定会被丢弃吗？

解答：

在这套模型中，完整且有效的事务条目持久保存时，事务的提交决定就已建立；日志同步成功返回，让程序能够确认已经通过提交点。

同步执行期间发生故障，可能留下不完整条目，也可能已经保存完整有效条目。恢复程序按持久记录的实际状态处理。客户端没有收到成功回复时，需要查询这次事务的状态；重试可携带稳定的事务编号，避免把同一笔转账重复执行。

提交后的数据仍可能暂时位于页缓存，这与“转账已经确认”可以同时成立。持久日志保存了恢复完整结果所需的信息，恢复过程负责把它落实到数据文件。

重复回放

恢复过程中也可能再次故障。重新启动后，部分日志会再次执行，所以需要考虑重复执行的结果。

值日志记录具体结果，例如 a=3,b=17。无论设置一次还是多次，两项都保持 3,17。这种重复执行与执行一次得到相同结果的性质，称为幂等性（idempotence）。

操作日志记录动作，例如 transfer(a,b,7)。它需要读取当时余额、再次扣款和加款，重复执行会再次转钱。

设置新值可以重复执行，重复执行转账会再次扣款

思考题：初始 a、b 各为 10，恢复时执行转账 7 元，随后故障并从头恢复。值日志与操作日志分别会得到什么？

解答：

值日志写入 a=3,b=17，第二次写入同样的值，结果仍为 3,17。

操作日志第一次执行得到 3,17；第二次又从 a 扣 7、向 b 加 7，结果变为 -4,24。两次结果的总额都为 20，但同一笔转账已执行两次，违反了这笔请求只执行一次的要求。

使用操作日志时，需要保存执行进度、事务身份等信息，确保动作按规定执行。使用值日志时，也要按事务顺序重放，并结合相应并发控制。

类似地，UPDATE t SET id = UUID() 调用 UUID 函数生成值。若在另一台机器重新执行语句，可能生成不同的 UUID。按行记录执行产生的数据变化，可以把已经生成的值传给副本，复制系统同时维护自己的应用进度。MySQL 文档列出了这类结果可能变化的语句。

值日志也有空间成本。ext3 的元数据日志以整个受影响块为单位保存内容，即使只改了块中的一个 bit，也要记录该块。这种格式便于恢复块内容，但日志量会超过单个修改值的大小。

日志开销

在这里的重做模型中，一笔事务把全部新值组织为一个条目，顺序追加并同步一次即可确认提交。顺序追加集中访问日志尾部，可以减少对多个分散数据位置逐个同步的等待。

它也有两项限制：

未提交修改全部放在私有内存中。事务修改范围很大时，缓存这些新值可能占用大量内存。
日志一直追加会持续增长。旧修改即使已经进入数据文件，日志仍占空间，也延长重启后的扫描时间。

思考题：事务的新值太多，私有内存放不下，可以把部分未提交修改写入数据文件吗？

解答：

可以设计允许未提交数据写入原位置的方案，用磁盘承载这些修改。但故障后必须能把未提交部分恢复成旧值，因此需要额外保存撤销信息。

对应的数据回写还要遵守日志先落盘的顺序，保证修改一旦进入磁盘，恢复程序就有依据处理它。

撤销重做

撤销重做日志（undo-redo logging）同时保存旧值和新值。旧值用于撤销尚未提交的修改，新值用于补齐已经提交的修改。

日志保存旧值 10 和新值 3、17，同时支持撤销与重做

图中初始余额为 10,10，转账 7 元后的余额为 3,17。两条修改记录分别保存：

a：旧值 10，新值 3；
b：旧值 10，新值 17。

事务未提交时，撤销（undo）把它改过的位置设置回旧值。事务已经提交时，重做把相关位置设置为新值。

def transfer_with_undo_redo(
    bank_file, account_a, account_b, amount, log, transaction_id
):
    """在每项修改之前保存旧值和新值，最后确认提交。"""
    records = map_shared(bank_file)

    # 先保存 a 的恢复记录，再允许共享页被修改。
    old_a = records[account_a]
    new_a = old_a - amount
    log.append_change(transaction_id, account_a, old_a, new_a)
    log.sync()
    records[account_a] = new_a

    # b 的修改也使用同样的顺序。
    old_b = records[account_b]
    new_b = old_b + amount
    log.append_change(transaction_id, account_b, old_b, new_b)
    log.sync()
    records[account_b] = new_b

    # 提交记录以及之前的相关记录持久保存后再报告成功。
    log.append_commit(transaction_id)
    log.sync()
    notify_user()

这段代码采用容易检查的保守顺序：每次修改共享映射之前，先同步对应恢复记录。此后，操作系统可以回写未提交脏页；如果事务最终失败，旧值日志用于撤销。

实际系统可以缓冲、批量同步日志，并在页真正回写时检查持久化进度，减少每项修改都等待同步的成本。核心约束是对应日志先于数据修改进入持久存储。

思考题：日志已经保存旧值，为什么还要保存新值？

解答：

旧值能够撤销失败事务。提交成功后，如果数据文件只保存了部分新内容，恢复还需要新值来补齐其他位置。

若只保存旧值，就必须在提交前把本事务全部数据修改同步到原位置。这样提交需要等待分散的数据写入。保存新值后，可以先同步连续的日志和提交记录，再让数据文件随后回写。

日志记录

重做方案的一条条目包含整个事务的修改；撤销重做方案的一条记录通常描述一次数据修改。两个事务执行时有重叠，它们的记录可以交错出现在日志中。

整笔事务条目与按单项修改追加的日志记录

上面的日志依次保存 T1、T2、T3、T4 的完整条目。下面的日志依次出现 1,2,1,2,1，这些数字表示事务编号：T1 有三条记录，T2 有两条记录。恢复需要能把属于同一事务的记录找出来。

事务编号和前一条记录指针把同一事务的记录连接起来

一条修改记录通常包括：

字段	含义
TID	事务编号，说明记录属于哪笔事务
前记录位置	同一事务上一条日志记录的位置
修改目标	文件或对象，以及要修改的偏移或字段
old	修改之前的旧值，用于撤销
new	修改之后的新值，用于重做
完整性信息	长度、类型、校验等，便于识别有效记录

偏移表示从文件或记录开头数过去的位置，用来找到要修改的内容。前记录位置指向日志中的另一条记录，用来沿同一事务向前查找。

图中 TID=1,PTR=80,old=3000,new=2000 表示：这条修改属于事务 1，它的前一条日志记录位于位置 80，本次把目标值从 3000 改为 2000。目标文件和字段由记录的其他信息确定。

写前日志

写前日志（write-ahead logging，WAL）规定：某项数据修改到达持久存储之前，对应恢复日志必须已经持久保存。

若数据先落盘，日志还没保存就发生故障，恢复程序可能既不知道旧值，也不知道这项修改属于哪个事务。先保存日志，就能识别修改并根据事务状态进行撤销或重做。

修改记录先保存到日志，事务完成时追加并保存提交记录

提交还需要第二条规则：本事务的相关修改记录和提交记录都持久保存后，才能确认成功。图中的黄色 C 表示提交记录，它需要标明所提交的事务。

两个顺序可以写成：

$\text{恢复日志持久化} \prec \text{对应数据修改持久化}$

$\text{本事务日志与提交记录持久化} \prec \text{成功回复}$

$\prec$ 表示左侧必须先完成。第一条保证磁盘上的修改有恢复依据，第二条保证已经确认的事务有完整提交凭据。

撤销恢复

恢复首先识别哪些事务具有有效提交记录。已提交事务需要保留；故障时仍未提交的事务需要撤销。

这里采用简化的恢复步骤：

从日志尾部向前扫描，确定事务状态和需要撤销的记录。
按反向顺序撤销未提交事务，恢复它们保存的旧值。
按正向顺序重做已提交事务，设置它们保存的新值。

这个说明针对能正确配合并发控制的事务执行；恢复期间暂停对外访问，直到数据恢复完整。事务之间访问同一数据时，还需要避免未提交值被其他事务错误使用或覆盖。

T1 已提交，T2 尚未提交，磁盘只写入了 a=3

示例从 a=10,b=10 开始。T1 的两条修改为 a:10→8、b:10→12，之后写入有效提交记录。T2 接着把 a:8→3，尚未完成下一步、也没有提交。

内存这时为 3,12。图中后台只回写 a，磁盘为 3,10；b 连 T1 的新值 12 都没落盘。因此恢复同时需要撤销 T2 和重做 T1。

步骤	操作	磁盘余额
故障后	保存了 T2 的 a，b 仍是初始值	`3,10`
撤销 T2	根据旧值将 a 设置为 8	`8,10`
重做 T1	将 a 设置为 8、b 设置为 12	`8,12`

撤销未提交的 T2，再重做已提交的 T1，恢复余额 8 和 12

思考题：为什么撤销要从后往前，重做要从前往后？只执行其中一项会怎样？

解答：

同一事务先把值从 10 改为 8，再从 8 改为 3，撤销需要先恢复到 8、再恢复到 10。如果按正向执行旧值赋值，最后可能停在 8。重做则按修改发生顺序设置新值，让后来的结果覆盖早先结果。

在图中的例子里，只撤销 T2 会得到 8,10，缺少 T1 对 b 的更新；只保留磁盘上的 a，则会留下 T2 的未提交扣款。完整恢复需要撤销 T2，再重做 T1，最终为 8,12，总额恢复为 20。

恢复过程中再次失败时，可以依据仍被保留的有效日志重新执行这些值赋值。多次执行把数据设置为同一旧值或新值，配合正确顺序能够再次得到相应结果。完成必要持久化之前，恢复依据也需要继续保留。

检查点

日志持续追加会占用越来越多空间，重启后扫描历史也会越来越慢。许多旧记录代表的修改已经进入数据文件，可以在确认恢复条件后回收。

检查点（checkpoint，常缩写为 CKPT）保存一个阶段的系统状态，以及从这个状态继续恢复所需的信息。恢复可以从这个阶段开始，减少重复处理旧历史。

这个概念也用于其他场景：

日志系统把一段历史整理进数据文件，再保留后续日志。
模型训练保存已训练的参数和进度；完整恢复还要保存优化器等所需状态。
进程检查点保存内存以及有关 CPU、GPU 执行状态，供之后恢复运行。
使用日志整理消息顺序的副本系统保存已经整理的状态，减少后续重放范围。

这些场景都在保存一份可用于继续运行的状态，具体需要保留的信息由任务决定。下面继续讨论银行数据与恢复日志。

已提交余额 3 和 17 保存到银行文件后，相应旧日志可以回收

在只有重做日志、且提交状态已正确整理进页缓存的情况下，可以把检查点覆盖的余额同步到数据文件，确认持久保存，再删除相应旧日志。

例如，T1、T2、T3 的最终结果是 3,17。一旦 bank 已可靠保存 3,17，这三笔事务的旧重做条目就可以回收。后续恢复从该银行状态和保留的后续日志继续。

执行检查点也需要按顺序进行。数据同步途中失败，旧日志仍要可用；数据完整保存以后，才能发布有效的检查点并删除被覆盖的历史。检查点记录本身也需要能够识别完整性、确认持久保存。

重新扫描全部日志、执行完整恢复后再删除历史，是一种直观办法，但会重复许多已经完成的工作。正常运行中的页缓存通常已经保存了计算结果，可以根据明确的日志边界和持久化规则建立检查点。

重做检查点

重做方案把未提交的新值保存在私有内存中，因此检查点同步共享页缓存时，可以只保存已经提交的余额。

T4 的新值 1 和 19 仍在局部变量中，共享余额为 3 和 17

图中 T4 正在计算 new_a=1,new_b=19，共享页缓存仍为 3,17。T4 尚未建立完整日志条目，也没有把新值写入共享映射。

检查点先把 3,17 保存到 bank，再删除已经被这一状态覆盖的 T1、T2、T3 条目。T4 的私有变量继续保留在运行中的内存里；若这时宕机，T4 尚未提交，可以丢弃。

检查点完成后，T4 追加新日志并提交，共享余额随后变为 1 和 19

T4 之后提交时，向保留的日志尾部追加 a=1,b=19 的完整条目，确认持久保存，再更新共享页缓存。bank 可以暂时保持检查点保存的 3,17；故障后根据 T4 的日志恢复 1,19。

思考题：重做日志的检查点与正在执行的 T4 会互相影响吗？检查点期间出现新的提交记录怎么办？

解答：

T4 提交前只修改私有变量，共享页缓存和旧日志的同步、回收不会保存这些未提交值。T4 之后提交，会写入新的有效日志，故障后仍能恢复。

检查点要明确一个被覆盖的日志边界，并确认边界内的已提交修改都已经应用并持久保存。期间产生的新提交记录属于保留的后续历史，需要继续保存。实现可以协调短时提交过程、切换日志段或使用版本标记，防止删掉尚未进入检查点数据的新记录。

撤销检查点

撤销重做方案允许未提交数据进入共享页缓存。直接同步全部页缓存、删除全部日志，会把未完成事务的修改留下，却丢失撤销依据。

未提交的 a=1 被检查点保存，旧值日志被删除，总额留下 18

检查点前，已提交状态为 a=3,b=17，总额为 20。T4 准备从 a 向 b 转 2 元：

保存 a:3→1 的日志。
在共享页缓存中把 a 改为 1，尚未把 b 改为 19。
检查点把页缓存 1,17 写入 bank。
如果此时删除所有旧日志，a 的旧值 3 也被删掉。
T4 提交前发生故障，磁盘只剩 1,17，恢复缺少撤销依据，总额为 18。

思考题：为什么同样的“同步页缓存后删日志”，在撤销重做方案中会出问题？

解答：

页缓存可能包含未提交修改，数据同步会把这些中间值保存到磁盘。T4 没有提交，恢复需要把 a 从 1 改回 3，因此 a:3→1 的日志仍有用途。

删除日志之前，需要为正在执行的事务保留足够的撤销与重做信息。只有事务已提交、相关结果又被检查点可靠保存时，其旧恢复记录才能按规则回收。

暂停事务

一种容易实现的办法是在检查点期间停止接收新事务，等待已有事务完成提交或撤销，再同步数据并回收历史。

检查点等待已有事务结束，后来的事务需要等待同步完成

图中检查点请求到来时，T1 已结束，T2、T3 仍在执行。红色区域表示等待它们结束；蓝色区域表示同步数据和回收日志。T4、T5 在这段时间到来，被阻塞，直到检查点结束才开始。

这样建立检查点时，数据中没有需要继续保留的未提交修改。实现还要处理事务失败：失败事务完成撤销后，才能把相应状态作为一致的检查点保存。

思考题：停止接收新事务并等待旧事务完成，有什么成本？

解答：

一个事务可能执行很久，检查点就要等很久。后续请求同时等待已有事务结束和检查点数据同步，服务暂停时间随长事务增加。

可以保留正在执行事务的恢复记录，让检查点只在单项修改的安全边界上协调。长事务能够跨越检查点继续执行，恢复时再根据它最终是否提交处理。

保留记录

事务由多项操作组成，单次记录追加、单个字段修改通常比整个事务短。检查点可以协调这些短操作，在没有单项修改进行到一半的时刻，收集活跃事务需要的恢复信息。

活跃事务是已开始、尚未完成提交或撤销的事务。CKPT 记录保存这些事务的必要旧值、新值、记录联系和状态，使旧日志回收后仍能进行恢复。

在这个简化方案中，可以按下列顺序建立检查点：

暂时协调单项修改，取得完整的日志与事务状态边界。
把活跃事务的必要恢复信息放入 CKPT 记录，确认它已持久保存。
将检查点覆盖的数据同步到原位置。
确认数据与检查点信息都有效后，回收已被替代的旧日志前缀。
保留 CKPT 及其后的日志，继续记录这些事务后续的操作和提交结果。

这里删除的是满足恢复条件的历史前缀，日志尾部还可能包含新的修改。检查点需要有明确的边界，协调数据同步和并发追加，持续保留恢复所需的信息。

CKPT 保留 T4 的 a:3→1，旧日志回收后仍能撤销到 3 和 17

图中 T4 已修改 a，尚未提交。CKPT 保存 T4,a:3→1，之后同步 bank，使其暂时为 1,17。旧日志可以回收，因为所需的撤销信息已在有效 CKPT 中保留。

发生故障后，恢复发现 T4 缺少有效提交记录，读取 CKPT 中的旧值，将 a 改回 3，最终得到 3,17，总额为 20。

思考题：CKPT 只保存“有事务 T4 正在运行”够吗？为什么要在单项操作边界上收集信息？

解答：

事务编号能帮助确认身份，撤销还需要修改位置与旧值，重做需要新值。若 CKPT 只保存指向已经删除日志的地址，也无法读取原来的恢复信息。可以直接保存所需记录，或保留这些指针所指向的有效日志范围。

单项修改执行到一半时，CKPT 可能漏掉刚新增的记录，或把数据修改与日志状态对应错误。先让当前短操作结束并建立清楚的边界，可以完整收集相关信息。实际等待时间取决于操作是否能正常推进，以及数据同步所需时间。

恢复判断

结合检查点，恢复根据两个时间关系处理事务：事务是否在检查点前已经完成，以及故障前是否已提交。

T1 至 T5 分别在检查点与故障前后的不同位置开始和提交

横轴时间向右推进。竖直虚线表示检查点，闪电所在竖线表示故障，带叉圆圈表示提交。虚线包围的记录表示已保存在 CKPT 中的检查点之前的活跃事务记录。

图中 T1 至 T5 的处理如下：

TX	检查点时的状态	故障时的状态	恢复动作
T1	已提交，结果已纳入检查点	已完成	无需处理已被覆盖的旧日志
T2	活跃，部分记录已进入 CKPT	检查点后已提交	重做 CKPT 中的必要记录及后续记录
T3	尚未开始	检查点后开始并提交	重做检查点后的记录
T4	活跃，部分记录已进入 CKPT	仍未提交	反向撤销后续记录及 CKPT 中的必要记录
T5	尚未开始	检查点后开始，仍未提交	反向撤销检查点后的记录

思考题：图中的 T1—T5 应该分别做什么？跨越检查点的事务为什么还需要早期记录？

解答：

T1 无需重做；T2、T3 重做；T4、T5 撤销。T2、T4 跨越检查点，恢复需结合 CKPT 中的早期记录与后续日志，才能补齐整笔事务或撤回全部未提交修改。

方案选择

选择日志方案时，需要同时考虑执行成本、内存占用、数据回写规则和恢复工作。

方案	未提交修改	提交前需要确认保存	故障恢复
重做日志	保留在私有内存	完整事务条目	按顺序重做已提交修改
撤销重做	可以进入数据原位置，但日志先保存	相关恢复记录与提交记录	撤销未提交事务，重做已提交事务
仅撤销	可以进入数据原位置，但撤销日志先保存	全部事务数据，再保存提交记录	撤销未提交事务

思考题：重做与撤销重做，哪一种执行和恢复更快？什么时候需要允许未提交数据落盘？

解答：

在这里的简化模型中，重做方案把整笔事务集中为一个条目，同步次数较少；恢复只需按顺序扫描有效条目，过程较简单。但提交前要在私有内存保存全部修改。

撤销重做记录单项修改的旧值、新值和事务状态，恢复需要区分提交结果，执行撤销与重做。它允许未提交数据回写，适合修改量大、内存无法容纳全部新值等需求。

实际系统还会考虑并发、页面缓存管理、日志批量同步和恢复时间等条件。这些优化会改变每笔事务实际等待的写入次数，需要按实现与负载评估。

在本节模型中，能在私有内存容纳更新时，重做日志提供较直接的实现；需要提前回写未提交修改时，可以使用撤销重做。并发控制和事务访问规则要与恢复算法共同设计。

仅撤销

仅撤销日志（undo-only logging）只保存旧值。它可以回退未提交事务，但已提交事务必须确保全部新数据已经进入原位置。

因此需要两项顺序：

某项数据修改写入磁盘之前，其旧值日志已经持久保存。
本事务的所有数据修改持久保存之后，才写入并持久保存提交记录、报告成功。

例如转账把 10,10 改为 3,17，日志保存两个旧值 10。提交前先确认 bank 的两个新值 3、17 都已经落盘，再保存提交记录。提交成功的事务已在数据文件中完整保存，恢复主要撤销缺少提交记录的事务。

若数据文件已保存新值，但提交记录仍未建立就发生故障，事务按未提交处理，根据旧值恢复 10,10。

这类方案的提交需要等待分散的数据位置同步，可能比只等待连续日志写入花费更多时间。恢复只需撤销，但系统通常也重视正常执行中的成本。

本节小结

故障会让磁盘保存一组修改的中间状态。全有或全无原子性要求恢复后保留完整旧结果或完整新结果，成功确认的事务还要能够持久保留。

临时副本把修改放进新文件，保存完整后通过共同入口发布；文件日志把修改记在 journal，依据提交状态恢复管理信息。应用日志进一步记录业务修改，使用新值重做、使用旧值撤销，并按写前日志规则安排持久化顺序。

检查点把已完成历史整理进数据状态，同时保留活跃事务需要的恢复信息，之后才回收相应日志。提交、回写和日志删除分别有自己的条件，需要按顺序执行。

日志可以保存在文件，也可以由多台服务器上的复制内存提供。后一种方案还需要完整追加、可靠保存和提交决定等协议保证，使规定故障范围内至少有可用的恢复依据。单机停止故障之外的部分节点失效、网络延迟和并发提交，需要进一步结合分布式系统讨论。

参考资料

Pillai 等，2014，All File Systems Are Not Created Equal: On the Complexity of Crafting Crash-Consistent Applications，OSDI。
Stephen C. Tweedie，1998，Journaling the Linux ext2fs Filesystem，LinuxExpo。
Saltzer 与 Kaashoek，2009，Principles of Computer System Design: An Introduction，第 9.1.5 节。
Mohan 等，1992，ARIES: A Transaction Recovery Method Supporting Fine-Granularity Locking and Partial Rollbacks Using Write-Ahead Logging，ACM Transactions on Database Systems。
Gray 与 Reuter，1993，Transaction Processing: Concepts and Techniques。
Jim Gray，1978，Notes on Data Base Operating Systems。
Linux，ext4 文档、journal 文档、mmap、fsync 与 rename 手册。
MySQL，Safe and Unsafe Statements in Binary Logging。