恢复是为了在发生错误时保证数据库的原子性、一致性和持久性。
恢复包含两部分：在正常事务执行时进行的操作来保证当错误发生时能够恢复（log）；和在错误发生后进行的恢复保证原子性、一致性和持久性。

最初的针对内存数据库的恢复都是假设没有持久性存储(disk)的，但是这种硬件没有广泛使用，所以这里还是用SSD/HDD。

内存数据库的恢复比面向磁盘的数据库简单，在：恢复时不需要追踪脏页防止崩溃；不需要存undo 记录，只需要redo；不需要记录对索引的修改。（这是如何体现的呢）
但内存数据库仍受限于disk的同步。

Logging Schemes
一样有物理日志和逻辑日志——物理日志记录的是修改，比如存一个属性被修改前后的值；而逻辑日志记录的是事务更高等级的操作，比如可能直接存了一个事物的sql语句。
逻辑日志记的东西少，但是如果有并发事务很难用逻辑日志进行恢复：如果隔离水平比较低很难确定查询修改了哪些数据；需要更长的时间因为需要重新执行事务的操作。

Log Flushing
两种处理方式：1.一次全部flush——事务完全提交后再将日志记录写入磁盘；2.允许在事务还未提交之前将日志记录写入磁盘

批量提交——可以把几个事务的日志记录一起提交（超时或者缓冲池要满的时候），可以把I/O成本分摊到几个事务上

MVCC中的delta records和物理日志是一样的，在undo的时候直接可以取出来旧的值。

MSSQL的constant time recovery

把MVCC的time-travel表作为恢复日志（time-travel table是除了主表之外的表，总是在主表中进行数据的修改，然后将原来的值放在time-travel表中），在WAL中利用版本的元数据来处理undo而不用处理undo记录。恢复时间由必须要从磁盘中读的版本记录的条数来定的。

MSSQL.png

持久化版本存储

1. In-row Versioning: 把对这个元组的小的更新作为一个增量记录内嵌到主表中这条记录
2. off-row Versioning: 专门有个表来存旧版本，并为并发插入优化；所有表的版本都存到一个表中，要存所有的插入的redo记录在这张表中(WAL)

MSSQL CTR 恢复协议
三阶段，分析、redo、undo

1. 分析：确定在log中每个事务的状态——哪些事务要REDO，哪些要undo
2. Redo：恢复主表和版本到崩溃时的状态
3. Undo: 标记尚未提交的事务为aborted在全局事务状态表中，使得未来的事务忽略到它们的版本；通过logical revert来逐渐移除旧的版本

logical revert

1. 后台清理：GC线程扫描所有的块，溢出要回收的版本；如果主表中最新的版本来自于aborted事务，它会把已经已提交的版本再拿回主表
2. 丢弃版本重写：如果一个版本来自于aborted事务，事务会重写这个最新的版本(而不再把主表中这个废弃的版本再像平常一样存到time-travel表中)

SILO

用的是单版本化OCC和epoch-based GC
SiloR用的是 物理日志+检查点来保证事务的持久性（通过并行 日志、检查点和恢复保证了高性能）

日志协议

DBMS假设每个CPU socket都有存储设备（socket就是路，几路CPU大概就是插了几块CPU的意思吧）——假设每个存储设备有一个日志线程，每个CPU socket有若干个worker 线程
当worker执行一个事务时，会创建新的日志记录包含写入数据库中的值(redo)

每个日志线程都会维护一个日志缓冲池给worker线程。当日志缓冲池满了，日志线程就flush到磁盘中，尝试获得一个新的日志缓冲池，如果没有新的，stall

日志文件
日志线程要把日志缓冲池中的数据写到磁盘中的文件中，每隔100 epochs创建一个新文件，旧文件用它包含的最大的epoch命名。

日志记录的格式：
修改记录的事务id——Tid
日志三元组——表，关键字，值(修改前后)
值可以使 属性+值对的形式

一个特殊的日志线程会track当前的持久化epoch(pepoch)，特殊的日志文件也会维护所有的日志线程的最新的持久化的epoch

一个事物在epoch e执行，只有在pepoch持久化到了磁盘才能释放其结果。

SILOR 恢复协议

两阶段
1.加载上一个检查点：把上一个检查点的东西全部取出，所有的索引也需要由检查点重建
2.Log replay：逆向执行日志来重构上一个版本的元组；执行时产生的事务id可以保证恢复的串行化顺序

Log replay
检查pepoch文件来决定最近的持久化epoch，在pepoch之后的日志记录统统忽略。

日志文件从新到旧进行处理：

• 值logging可以按任意顺序（什么 是value logging）;
• 对于每条日志记录，线程都需要检查它对应的元组是不是存在，如果不存在就根据这条记录中的值创建，如果存在看这条记录的Tid与已经存在的这个元组的Tid大小比较，如果日志记录的Tid更新，那么修改。

内存数据库的检查点协议

检查点的实现与并发控制协议是息息相关的
检查点线程会扫描每个表，然后把数据异步写入磁盘。

Ideal 检查点协议：不会降低一般事务处理速度；不导致大延迟；不能有过度的内存开销。

实现

1. 一致性检查点：数据库在某个时刻的一致性快照——no uncommited changes，恢复的时候按照检查点恢复就好，无需额外操作
2. 模糊检查点：可能包含一些尚未提交的事务修改过的记录，必须做额外的处理把这些修改先给清理掉

检查点可以由DBMS创建，也可以用OS fork snapshots，fork一个子进程让它把数据库的内容(everything)写到磁盘上，但是需要清理uncommited changes（如果有非活跃事务可以对其进行一致性检查，否则用内存中的undo log回滚事务到子进程）

检查点的内容

1. Complete Checkpoint 把每个表的每个元组都记录下来，无论上个检查点以来是否做了修改
2. Dleta Checkpoint 只把上个检查点以来修改的元组记录下来，后台可以把多个检查点合并

设立检查点的频率

1. 基于时间：在上个检查点完成后等待固定的时间设立新检查点
2. 基于日志文件大小：在日志文件中写了足够的数据后设立检查点
3. 在DBA关闭系统时（强制性的）

Restart Protocol

DBMS不是所有重启都是因为崩溃，也可能是因为更新系统、硬件和DBMS，所以需要一种方式快速的重启而不用从磁盘中重新读整个数据库

其中FaceBook SCUBA的做法是，把数据库的内存生命周期和进程周期分开，把数据库存在共享内存中，DBMS进程重启时内存中的内容还在就不需要reload了。

FaceBook SCUBA是一个分布式内存数据库，进行时间序列事件分析和异常检测。
分叶子节点和聚合节点，叶子节点执行查询，聚合节点把从叶子节点的查询结果进行聚合。

共享内存重启
实现方法

1. 共享内存堆：正常操作时所有的数据都分配在共享内存中；需要自定义分配器来细化内存段实现线程安全和可扩展性；不能延迟分配备份页
2. 正常操作时所有数据都分配在本地内存；shutdown时把数据从本地内存堆中复制到共享内存

restart流程如下：
当管理员启动重启，节点停止更新；DBMS开始把数据从堆内存复制到共享内存（每个block复制成功后就从堆中删除）；快照复制结束，DBMS重启。
重启时首先检查共享内存中是否有合法的数据库如果有就复制到堆中，没有的话需要从磁盘中重启。

---

物理日志是通用的选择，因为它支持所有的并发控制模式。

MVCC用Copy-on-update检查点