数据库理论之故障恢复日志

---

资料版本：数据库系统实现 数据库系统概念 事务处理 作者：高铭杰 邮箱：jackgo73@outlook.com 日期：2017年2月13日

---

1 日志规则

日志类型规则undoU1：如果事务T改变了X，那么日志< T, X, v >要先落盘U2：Commit日志要后于数据落盘redoU1：如果事务T改变了X，那么日志< T, X, v >要先落盘U2：Commit日志要先于数据落盘redo/undoUR1：如果事务T改变了X，那么日志< T, X, v, w >要先落盘UR2：COMMIT日志出现了必须立即落盘（避免日志延迟落盘导致提交的事务回滚）

2 日志恢复规则

2.1 undo

(1) Let S = set of transactions with < Ti, start > in log, but no< Ti, commit > (or < Ti, abort >) record in log (2) For each < Ti, X, v > in log, in reverse order (latest -> earliest) do: if Ti∈S then write (X, v), output (X) (3) For each Ti∈S do write < Ti, abort > to log

2.2 redo

(1) Let S = set of transactions with < Ti, commit > in log (2) For each < Ti, X, v > in log, in forward order (earliest -> latest) do: if Ti ∈ S then Write(X, v)

2.3 undo/redo日志

(1) 按照从前往后的顺序，重做所有已提交的事务。 (2) 按照从后往前的顺序，撤销所有未提交的事务。

4 例题

4.1 undo/redo检查点回溯

< START S > < S, A, 60, 61 > < COMMIT S > < START T > < T, A, 61, 62 > < START U > < U, B, 20, 21 > < T, C, 30, 31 > < START V > < U, D, 40. 41 > < V, F, 70, 71 > < COMMIT U > < T, E, 50, 51 > < COMMIT T > < V, B, 21, 22 > < COMMIT V >

假设我们在如下日志记录写入主存后，立即开始一个非静止检查点： a) < S, A, 60, 61 > b) < T, E, 50, 51 > 对于上述情况，说明： (i) 何时写入< END CKPT > (ii) 对于每一个可能发生故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中回溯多远。考虑 < END CKPT >写入和未写入两种情况。

a)

加入检查点后：

< START S > < S, A, 60, 61 > < START CKPT (S) > <---- create ckpt < COMMIT S > < START T > < T, A, 61, 62 > < START U > < U, B, 20, 21 > < T, C, 30, 31 > < START V > < U, D, 40. 41 > < V, F, 70, 71 > < COMMIT U > < T, E, 50, 51 > < COMMIT T > < V, B, 21, 22 > < COMMIT V >

(i) undo/redo日志的检查点可以出现在start ckpt后的任意位置，因为ckpt会刷所有缓冲区（提交/未提交）。 (ii)根据crash发生的位置，三种情况分别讨论：

crash位置回溯点crash发生在end ckpt之后恢复需要回溯到start ckpt即可，因为存在end ckpt可以保证start之前的所有改动都已经刷盘crash发生在commit s和end ckpt之间（end ckpt在后）由于commit s记录存在，所以进行redo动作，redo执行到start ckpt即可crash发生在commit s之前那么commit s不存在，需要undo，这个动作需要回溯到start s才能保证所有事务S造成的改变被撤销掉（需要undo的都需要回溯到start记录）

e)

加入检查点后：

< START S > < S, A, 60, 61 > < COMMIT S > < START T > < T, A, 61, 62 > < START U > < U, B, 20, 21 > < T, C, 30, 31 > < START V > < U, D, 40. 41 > < V, F, 70, 71 > < COMMIT U > < T, E, 50, 51 > < START CKPT (T, V) > <---- create ckpt < COMMIT T > < V, B, 21, 22 > < COMMIT V >

(i) undo/redo日志的检查点可以出现在start ckpt后的任意位置，因为ckpt会刷所有缓冲区（提交/未提交）。 (ii)根据crash发生的位置，两种情况分别讨论：

crash位置回溯点crash发生在end ckpt之后恢复需要回溯到start ckpt即可，因为存在end ckpt可以保证start之前的所有改动都已经刷盘crash发生在end ckpt之前存在活跃事务的commit记录则进行redo，回溯到start skpt即可不存在活跃事务的commit记录则进行undo，需要回溯到start x

4.2 undo检查点回溯

< START S > < S, A, 60 > < COMMIT S > < START T > < T, A, 10 > < START U > < U, B, 20 > < T, C, 30 > < START V > < U, D, 40 > < V, F, 70 > < COMMIT U > < T, E, 50 > < COMMIT T > < V, B, 80 > < COMMIT V >

假设我们在如下日志记录写入主存后，立即开始一个非静止检查点： a) < S, A, 60 > b) < T, A, 10 > 对于上述情况，说明： (i) 何时写入< END CKPT > (ii) 对于每一个可能发生故障的时刻，为了找到所有可能未完成的事务，我们需要在日志中回溯多远。考虑 < END CKPT >写入和未写入两种情况。

a)

加入检查点后：

< START S > < S, A, 60 > < START CKPT (S) > <---- create ckpt < COMMIT S > < END CKPT > <---- end ckpt < START T > < T, A, 10 > < START U > < U, B, 20 > < T, C, 30 > < START V > < U, D, 40 > < V, F, 70 > < COMMIT U > < T, E, 50 > < COMMIT T > < V, B, 80 > < COMMIT V >

(i) 检查点需要在commit s后面。 (ii) 如果end ckpt存在，说明所有未提交事务都在前一个start ckpt后开始（检查点过程中会等待start ckpt中所有未提交事务提交之后，才能写入end ckpt）所以我们undo到start ckpt即可。end ckpt不存在，但commit s存在，由于undo日志可以保证s事务已经罗盘。如果commit s不存在，需要undo到start s。

b)

加入检查点后：

< START S > < S, A, 60 > < COMMIT S > < START T > < T, A, 10 > < START CKPT (T) > <---- create ckpt < START U > < U, B, 20 > < T, C, 30 > < START V > < U, D, 40 > < V, F, 70 > < COMMIT U > < T, E, 50 > < COMMIT T > < END CKPT > <---- end ckpt < V, B, 80 > < COMMIT V >

(i) 检查点需要在commit t后面。 (ii) 如果end ckpt存在说明所有未提交事务都在前一个start ckpt后开始（检查点过程中会等待start ckpt中所有未提交事务提交之后，才能写入end ckpt），说明T已经提交，我们根据start ckpt后面的事务是否存在commit决定是否去undo。如果end ckpt不存在，T事务提交需要根据commit T是否存在来决定，其他事务的处理同上。