1.何时需要REDO，何时需要UNDO
数据库中Crash Recovery模块主要用来保证（局部）事务的Atomicity和Durability。那么它是怎么做到的呢？
很多人肯定都知道redo log和undo log。但是很少有人能说清楚它们的作用分别是什么？只需要redo log行不行？什么情况下两者都需要呢？
其实，要搞清楚这些问题，还需要先介绍下数据库的缓存刷新策略。为了保证数据库的Atomicity和Durability，数据库会先把数据的更新记录在日志中，再写行数据（row data），最后提交。在事务提交时，日志是必须要写入稳定存储的。
但是行数据呢？最理想的情况是在事务提交那一刻写入稳定存储中，这种策略称之为force刷新策略，但是这个会严重影响性能（产生很多小的磁盘随机io和写放大）
因此现实中的数据库大多使用no-force策略（即事务提交的时候不会强制刷新行数据缓冲page到磁盘）。
现在，行数据可以在事务提交前和提交后写入稳定存储，在事务提交前就写入磁盘的情况称之为steal策略（意思是在事务提交前，缓存中的一个行数据page被偷走了写入磁盘），相反，在事务提交前行数据绝不会写入磁盘的称之为no steal策略。
明白了force/no-force和steal/no-steal策略后，就很容易理解redo log和undo log了。
设想，在事务提交之前，如果有些行数据page被steal了，如果最终事务没有执行成功需要进行回滚或着发生Crash，由于事务未提交，但是行数据已经写入了磁盘，就会造成事务出现不一致的状态。
那么为了保证事物的Atomicity（即要么全部成功要么全部失败），此时需要记录undo log，以便在进行回滚操作或者Crash Recovery时，可以根据undo log对为提交的事务进行回滚。
同样，如果行数据是在事务提交之后的某个时刻才被写入磁盘，那么假设事务提交后就发生了Crash（此时行数据还未写入磁盘），那么数据库的Durability就不满足了（即已提交的事务必须是Durability的，稳定不可丢失的）。因此，为了满足Durability，需要记录redo log，这样在Crash之后重启时，Recovery模块会对所有已提交的事务执行redo log，保证事务的Durability特性。图3概括了这几种情况。
NO STEAL + FORCE
shadow paging
基于NO REDO, NO UNDO LOG的DB A，D的实现方式 就是shadow paging了
凡是你要修改的页，都会有2个实例，一个是MASTER（数据库用的页），一个是你的复制出来的用来临时修改的（SHADOW）
当前事务的修改只会发生在SHADOW页上。当一个事务提交，把SHADOW页通过一个原子性的切换指针的操作，把MASTER指向的页换到SHADOW页 来保证原子性。
下面一个问题是一个事务可能会涉及到改动多个页，你单个指针可以原子性的转换。那么有多个页该如何保证原子性呢？
在这个算法里，DB的页会被以树的形式组织，而根节点一定是一个单页。
然后也是有一个MASTER，一个SHADOW，根节点指向MASTER COPY，更新都会发生在SHADOW COPY。
凡是修改的页指针先会在SHADOW PAGE的树里修改，然后如果事务提交。我们只要转移DB ROOT的指针就好。
SHADOW PAGING的缺点
缺点1 复制整个PAGE TABLE是昂贵的。
解决上述问题可以把PAGE TABLE组织为B+树，我们不需要COPY整个树，而是修改要更新的叶子节点的那个路径COPY出来即可。
缺点2 提交时要做的事很多
如要FLUSH所有更新的页。 FLUSH 非连续的页去磁盘上是很慢的。
数据会碎片化，还需要GC来回收不用的页。
WAL（Write-ahead log）
DBMS将所有txn的日志记录分阶段存储在内存中（通常由缓冲池支持）。
确保在页面本身被重写到磁盘之前，所有与更新页面有关的日志记录都被写入到磁盘。
在将所有相关日志记录写入稳定存储之前，不会将txn视为已提交。
每一条LOG记录都会包含TRANSACTION ID， Object ID, BEFORE VALUE(undo), AFTER VALUE(redo)
我们什么时候把LOG ENTRY 给刷到磁盘呢？
在TXN COMMIT的时候，可以使用GROUP COMMIT的继续，来批量把多个LOG一起刷到磁盘来均分成本。
但是什么时候把内存里的脏RECORD（还未被落盘的数据）刷到磁盘呢？
如果我们可以确保在TXN COMMIT的时候刷回去，这样我们就不需要UNDO LOG了。
但是如果一个事务修改了条目数 超过了 内存的大小，这个方案就不WORK了。
此外，如果有些数据事务的状态还未定，就提前落盘了。我们也会因为没有UNDO LOG而存在麻烦。万一未来要ABORT了呢
3种LOG 类型
•物理记录
- 记录对数据库中特定位置所做的更改
- 示例：记录在页面中的位置
•逻辑记录 - 记录事务执行的高级操作。 不一定限于单页。 每个日志记录中写入的数据少于物理日志记录。 如果在非确定性并发控制方案中有并发事务，则很难使用逻辑日志记录实现恢复。
- 示例：事务调用的UPDATE，DELETE和INSERT查询。
•混合记录 - 混合方法，其中日志记录以单个页面为目标，但未指定页面的数据组织。
- 最常用的方法。
解决WAL无限增长的问题
崩溃后，DBMS必须重播整个日志，如果日志文件很大，这可能需要很长时间。 因此，DBMS可以定期获取检查点，将所有缓冲区刷新到磁盘。
DBMS采用检查点的频率并直接。频繁打CHECKPOINT 检查点，经常导致运行时性能降低。如果很少打CHECKPOINT， 但随着恢复时间的增加，等待很长时间同样糟糕。
阻止检查点实施：
•DBMS停止接受新事务并等待所有活动事务完成。
•将当前驻留在主内存中的所有日志记录和脏块刷新到稳定存储。
•将<CHECKPOINT>条目写入日志并刷新到稳定存储。
WAL 是最常用的解决在数据再内存丢失的问题的方法。
通常我们会结合CHECK POINT一起用
在恢复的时候，使用UNDO LOG去处理没有COMMIT的事务，使用REDO LOG去恢复COMIT的事务。
