undo日志

原文地址：
http://www.mathcs.emory.edu/~cheung/Courses/377/Syllabus/10-Transactions/undo-log.html

使用Undo日志实现事务处理

实现事务

• 概要

事务实现需要记录事务所执行的每个更新操作的日志信息

• 事务日志

  1. 事务日志 = 一个只能在尾部进行append写入的文件，包含了一些日志记录
  2. 事务日志中存储的信息能够让数据库系统进行以下行为：
     1. 回滚一个事务
     2. 重做一个事务

• 一般来说，有两种方式可以实现事务处理，具体取决于何时进行写入/更新操作:

  1. 事务执行在原地更新操作，此时需要UNDO日志来实现事务
  2. 事务执行延后更新操作，此时需要REDO日志来实现事务

• 我们先讨论原地更新/UNDO日志这种方案

---

原地更新操作

• 原地更新(即时更新)

原地更新操作 = 立即将更新应用到数据库

    当事务T1原地更新数据X后，另一个事务T2读取数据X，会读到X更新后的新值。

---

Undo日志

• UNDO日志是一个日志文件，其中包括了用于撤销事务效果的信息。

• 事务的效果会改变数据库中某些数据的值。撤销事务效果就是撤销事务进行的更新操作。

• 为了撤销事务进行的更新操作，我们将每个更新的数据的原始值保存下来!!!

• UNDO日志中包括了以下几种类型的日志记录：

  1. [start, TID] 说明事务TID开始了
  2. [write, TID, X, old_value] 说明事务TID覆盖写了数据项X的值，X的原始值是old_value
  3. [commit, TID] 说明事务TID已经成功完成了
  4. [abort, TID] 说明事务TID终止了

• 操作

  1. 当开始一个新事务时：
     • 给这个事务分配一个唯一的事务ID，记为T
     • 将[start, T]添加到UNDO日志
  2. 当事务T读取数据项X时：
     • 不需要做任何事情......
  3. 当事务T写一个数据项X时：
     • 将[write, T, X, old_value]添加到UNDO日志中
     • 当日志成功写入后，使用新的值更新X
  4. 当事务T成功执行完成时：
     • 将[commit, T]添加到UNDO日志
  5. 当事务T终止时：
     • 将[abort, T]添加到UNDO日志

• 注意：

  非常关键的一点：

    首先将写操作记录到日志中，然后再原地的更新数据库。
  

  如果将这两个步骤弄反了，那么事务将不能保证是原子的。

---

使用原地更新和UNDO日志的事务处理例子

• 考虑一个简单的事务:

    T: 
        x := x - 1000
        y := y + 1000

    (转移1000从X的账户到Y的账户)

• 一开始，数据库状态如下：

  initially.jpg

• 事务处理如下所示：

  1. 当事务T开始时，事务处理系统写入一个开始事务到日志文件中:
     

     t1.png

  2. 事务T必须将数据项X的值从磁盘中读取到内存中:
     

     t2.jpg

  3. 为了更新磁盘上的数据，事务首先更新内存中数据项X的值：
     

     t3.jpg

  4. 事务T将数据项X的值从内存中写入到磁盘中：
     

     t4.jpg

  注意到X的原始值首先写入到日志中，然后再更新X的新值到数据库中。

  5. 事务T将数据项Y的值从磁盘中读取到内存中：
     

     t5.jpg

  6. 事务T首先更新内存中数据项Y的值：
     

     t6.jpg

  7. 事务T将数据从内存中写入到磁盘:
     

     t7.jpg

  和之前一样，首先将Y的值记录到日志中，然后再更新数据库中Y的值。

  8. 最终事务T完成:
     complete.jpg

---

原地更新+undo日志如何保证原子性

• 事务的执行是原子的：
  • 要么所有事情都完成了(x和y都更新了)
  • 或者什么都没有完成(x和y都没有更新)

• 问题：
  什么会导致部分执行?

• 答案：
  • 系统故障
  • 读取冲突(后面再讲)

• 考虑上面执行过程中出现系统故障的情况：
  • 在第一步完成之前出现故障:
    fstep1.jpg
    x和y都没有更改，没问题
  • 在第二步完成之前出现故障:
    fstep2.jpg
    x和y都没有更改，没问题
  • 在第三步完成之前出现故障:
    fstep3.jpg
    x和y都没有更改，没问题
  • 在第四步完成之前出现故障:
    fstep4.jpg

    • 如果故障发生在写日志之前，数据库中的x和y都没有变化，没有问题

    • 如果故障发生在写日志之后，但是写数据库之前，那么：

      1. 数据库中的x和y没有变化
      2. 然而，日志中包括了old x = 4000

      我们不能确定x是否被修改了，但是我们需要保证x可以回退到原始值。为了保证事务是原子的，我们将x恢复到它的原始值old x = 4000

    • 如果故障发生在写数据库之后，那么：

      1. x = 3000 同时y没有变化- 我们损失了1000!!!
      2. 幸好日志中记录了old x = 4000

      我们又使用日志记录来将x恢复到原始值old x = 4000

  • 注意：
    • 这里我们看到了为什么必须要在更新数据库中的数据之前写入日志
    • 如果首先更新数据X，同时系统在写入日志之前故障了，我们就不能将x恢复到原始值(因为我们没有日志记录--由于系统故障而没有完成日志写入)
  • 在第五步完成之前出现故障:
    fstep5.jpg
    x = 3000 y= 6000 - 损失了1000，
    不过日志中记录了old x = 4000， 我们使用日志记录恢复了x的值。
  • 在第六步完成之前出现故障:
    fstep6.jpg
    x = 3000 y= 6000 - 损失了1000，
    不过日志中记录了old x = 4000， 我们使用日志记录恢复了x的值。
  • 在第七步完成之前出现故障:
    fstep7.jpg
    • 如果故障发生在写入日志之前，那么x = 3000，y = 6000。我们可以使用日志记录来恢复x的值，不需要恢复y。
    • 如果故障发生在写入日志之后，但是在写入y到数据库之前，那么x = 3000，y = 6000，都在数据库中。我们不能确定y是否被修改，但是我们必须能够保证x和y都能够恢复到原始值。为了保证事务的原子性，我们将x和y都恢复到原始值。
    • 如果故障发生在写入数据库之后，那么：x = 3000，y = 7000。虽然这是正确的结果，但是我们没有办法知道y已经被更新了。为了保证事务的原子性，我们必须选择将x和y都恢复到原始值，这是唯一正确的选择。
  • 在第八步完成之前出现故障：
    fstep8.jpg
    有两种可能：
    • 故障发生在commit记录写入之前。这种情形，我们没有办法确定x和y都被更新了。我们知道它们的原始值，因此：我们选择恢复x和y的原始值。
    • 故障发生在commit记录写入之后。这种情形，我们可以根据commit记录来确定x和y都已经更新了。因此当我们看到[commit, T]记录时，就不需要撤销事务(恢复原始值)了。

---