1.Crash Recovery

当一个事务对数据对象进行修改之后，如果我们先将对象在内存中进行修改，再落地到磁盘中的话，那么这两个操作是不能保证原子性的。在这一过程中若系统崩溃了，就会造成已提交的修改没有实际落地到磁盘中，造成数据不一致；如果直接落地到磁盘中，随机I/O会造成写效率的低下。

数据库需要实现一种算法，该算法需要保证若数据库表示一个事务已经提交了，那么它做的修改都是原子的，持久化且可恢复的。同时，还要具有一定的性能。主要关注以下两个方面：

• 运行时：该算法需要在系统运行时执行操作。
• 回滚：在事务失败或系统崩溃后可以回滚。

目前有两种主要的算法：

• Shadow Paging：对于一个未提交事务所需要修改的对象所在的page，维护一个临时page。
• Write-Ahead Logging：将修改的日志先落地到磁盘中，然后在内存中进行修改。周期性的根据日志的内容更新数据库的对象。

2.错误类型

• 事务失败

• 逻辑错误：比如修改不符合完整性约束，又或者是遇到了死锁。

• 内部错误：如死锁或者在OCC中冲突的情况。

• 系统错误

• 软件错误：由DMBS底层实现发生的逻辑问题。

• 硬件错误：如断电等情况。
• 存储介质错误：如用于存储数据的磁盘发生故障。这是不可能避免的，但在分布式数据库中可以通过冗余复制进行规避。

3.Shadow Paging

本质也是为每个事务要修改的Read Set和Write Set维护一个事务私有的副本，在自己的副本中进行修改。如果该事务顺利提交了，就将该私有副本的变化落地到数据库中。

为什么需要维护一个私有副本？记得曾经提到过，数据库的数据是以page为单位的吗？若T1需要修改A，T2需要修改B，且A和B在同一个page中。若事务的执行顺序为T1->W(A),T2->W(B),T2->COMMIT,T1->abort，很明显，若该page落地到磁盘中，则T1做的修改也会在数据库中生效，然而T1没有提交；若不落地到磁盘中，那么若此时系统崩溃了，T2做的修改会消失，不符合原子性。

做法是系统维护一个Main Page Table，每个事务维护一个Shadow Page Table，其中Main Page Table和Shadow Page Table一开始都指向磁盘的Page。

在修改某一个Page的时候，Shadow Page Table对该page作出一个副本，并在同样的索引处指向该副本。在提交事务的时候，原子性地将指向Main Page Table的指针指向Shadow Page Table。在需要回滚的时候，只需要将page的副本移除即可。

显然，在并发事务数量多的时候，要维护多个Shadow Page Table的代价是巨大的。如果只有一个Shadow Page Table呢？SqLite的做法是一次只能提交一个事务（也可以为多个提交的事务进行排序，以单线程的方式运行），有些系统也采用批量提交事务的方式（这样子就可以把多个事务的结果聚合或内部排序）。

显然，这对性能和空间以及并发事务的支持都不友好，因此没有实际使用该做法的系统。

4.Write-Ahead Logging

WAL的思想是最大程度地利用磁盘的顺序I/O，将所有修改落地到磁盘的日志中，再对内存中的数据进行修改。

若系统中途奔溃，我们可以根据日志查看该事务是否提交，若提交需要对数据做什么修改；如果没有提交，则直接略过这一段日志即可。

每一个日志记录中，需要至少而不限于记录以下信息：

• Transaction Id
• Object Id
• After Value（redo）
• Before Value（undo）

特殊地，我们还需要在日志中标记事务的起点BEGIN，事务的提交点COMMIT以及事务的放弃点ABORT。

MySQL中采用环形区域写入称之为redo log的日志，当环形区域满了之后，再将日志对应的修改写入到磁盘的数据中。

一种常见的优化是WAL也不是每产生一个日志就立刻写入磁盘中，而是会拥有一个或多个WAL缓存池。至少但不限于以下情况会将缓存池的内容写入磁盘中：

• 有事务COMMIT。
• WAL缓存池满了。若有多个缓存池，可以在对一个缓存池进行磁盘写入时，将指针指向另一个缓存池进行交替。
• 超过设定的时间时。

WAL的日志有三种实现方式：

• Physical Logging：如上所述，记录每一个操作带来的实际影响。
• Logical Logging：只记录逻辑指令，如我的SQL语句内容。
• Physiological Logging：以上两种方式的结合。

Physical Logging主要的问题是需要记录许多信息，当我的操作需要更新很多对象时，会产生大量的日志。而对比只记录逻辑指令来说，他更容易进行redo和undo。

目前用的最多的是第三种方式，它相当于更精确的Logical Logging，即记录了逻辑语句且也记录了我所要修改的对象所在的Table以及Page，但我记录更多的是体积更小的间接或逻辑信息，由系统间接推导出来结果。

UPDATE foo SET val = XYZ WHERE id = 1

对于这一个语句，三种不同方式会记录以下的伪日志

• ...
• ...
• ...

5.Checkpoints

WALs记录的相当于是增量信息，CheckPoint相当于提供了一个完整的副本，且该副本已经应用了所有的WALs，即所有变化都落地到了数据库的磁盘数据中。

这种做法减少了WALs日志不断增加，会导致回滚时间过长以及占用体积过大的问题。

Checkpoint制作需要进行以下操作：

• 阻塞正在进行的事务，停止接受新来的事务直到Checkpoint制造完成。
• 应用所有WALs，并将dirty page写入到磁盘中。
• 将\<CHECKPOINT>写入WAL和磁盘中。