数据管理器(DM)

数据项及其操作

我们从DM为上层模块提供的抽象说起.

我们都知道, 为了数据的持久化, 是需要将数据存储在磁盘上的, 于是便涉及了对磁盘的读写. DM的首要工作, 就是对磁盘文件进行一层封装, 使得上层模块不用关心磁盘读写细节. 总的来说, DM的实现方式为对DB进行分页管理, 并为上层模块提供了数据项(data item)的概念.

DM分页管理的细节将会被略过, 此处重点是描述数据项及其操作. 经过DM的抽象后, 上层模块便能够将DB当做一个集合了, 而集合内的元素, 则是一个个数据项. 我们用靠后的小写字母来表示数据项, 如x, y, z等.

和指针类似, x只是标识了某个数据项, 数据项还有自身的值. 于是, 根据上下文的情景, x可能会用于标识某个数据项, 也可能会表示某个数据项的值. 如, "读取x的值", 这里的x就是作为某个数据项的标识. 如, "x大于y", 这里x和y表示的是值. 如, "把x存入DB", 这里x表示的是值. 虽然我们同时用x来标识数据项和其值, 但是根据上下文, 一般来说不会产生混淆.

抽象出数据项后, DM还为上层模块提供了一些访问和修改数据项的操作, 他们有:

  1. I(x): 在DB中插入x;
  2. R(x): 读取x的值;
  3. U(x): 更新x的值, 至于将x的值更新成多少, 在我们的模型中并不关心, 因此更新操作只有一个参数;

需要注意的是其中并没有Delete操作, 其原因我们留到VM章节中介绍. 另外, 这些操作是原子性的, 其原子性将会由DM的恢复机制保证.

有了数据项及其操作, 上层模块将不用再考虑文件细节, 能够更加抽象的完成自身的逻辑. 上层模块怎么使用这些操作, 将在本篇文档之后一些部分进行介绍.

缓存

DM会对DB进行缓存以加快对DB的读写. 由于缓存的出现, 使得NYADB得区分"内存"和"磁盘"的概念了. 本小节将重点描述"内存"和"磁盘"的概念, 以及DM的访问行为. 至于缓存实现的细节, 如置换算法, 刷新策略, 我们将不具体描述.

由于缓存的出现, DM中的整个数据模型将会变成下面这样:

+----+       +----------+       +----------+       +------+
| DM | <---> | dm cache | <---> | os cache | <---> | disk |
+----+       +----------+       +----------+       +------+

上图中, "dm cache"为NYADB自己缓存的DB数据, 当DM准备访问数据项时, 会率先尝试从"dm cache"中查询.

如果在其中找到了需要的数据项, 则直接返回, 否则将从disk中读取数据项到"dm cache"中, 再返回. 同样的, 对于写入操作, DM会先将数据写入到"dm cache"中, 当"有需要"时, 再将数据同步到磁盘上.

上句话中, 什么时候"有需要", 就取决于缓存的刷新策略了, 这里先略过. 上图中的"os cache"是操作系统对于读写的自动缓存. 实际上DM并不在乎"os cache", 对DM而言, "dm cache"之后其实就是"disk"了. 这里将"os cache"标识出来只是为了提醒, 因为它的存在, 在写代码时, DM常常不得不在"write"后跟一个"flush".

日志和恢复

该部分介绍DM怎样通过日志的方式来保证NYADB的可恢复性. 同上部分一样, 该篇只介绍日志的策略, 日志的细节, 如日志的二进制格式等, 将不具体描述.

我们先不考虑并发的情况, 假设在任意时刻, NYADB中最多只有一个事务进行. 我们用T来表示一个事务. 用Ti或Tj, Tk之类的下标, 来区分各个事务. 我们用terminated和active来表示事务当前的状态. active表示该事务还在进行. terminated表示事务已经结束, 结束可能是因为被提交(committed), 也可能是因为被撤销(aborted), 这两种情况暂时不用区分.

现在介绍DM的日志策略, 一句话: 进行I和U的数据项操作之前, 必须进行对应的日志操作, 并保证日志到达磁盘后, 才执行数据项操作.

该策略异常简单, 优点有二:

  1. 简单, 实现方便, 但是却可靠;
  2. 使得数据项的磁盘同步操作能更加随意;

现在对第二点做个详细说明. 正如"缓存"那个小节所说, DM操作数据项时, 先修改的是内存中的数据, 至于什么时候刷新到磁盘, 是需要策略的. 如果在修改数据项之前, 能够保证对应日志已经到达磁盘, 那在修改数据项后, 即使暂时不刷新到磁盘, 也没关系. 假如在该段时间内NYADB发生了崩溃, 那磁盘上的数据项则会有误, 因为正确的数据项内容还未被刷新到磁盘上. 但是因为NYADB在修改数据项前就保证了日志已经到达磁盘, 那么NYADB在下次启动时, 一定可以根据上的日志内容来进行恢复.

下面, 我们看看对于每种数据项操作, DM会怎样进行日志. 对于I和U操作, 日志分别为:

  • (Ti, I, x): 表示事务Ti插入了x;
  • (Ti, U, oldx, newx): 表示事务Ti把x的值从oldx更新为newx;

R(x)自然是不需要日志. 我们用O表示I或者U, o表示任意的数据项.

由于不考虑并发, 那么在任意时刻, 日志的情况只会是诸如下面的情况: 

(Ti, O, o), ..., (Ti, O, o), (Tj, O, o), ..., (Tj, O, o), (Tk, O, o), ..., (Tk, O, o)

上面序列想表达的意思是各个事务(如上面的Ti, Tj, Tk)的日志, 是不会相互交叉的, 也就是不会出现: 

(Ti, O, o), (Tj, O, o), (Ti, O, o), ...

这样的情况. 因为现在没考虑并发.

下面就是怎么样利用日志进行恢复了, 其实整个过程很简单, 直观, 自然. 假设最后一个出现在日志中的事务是Ti, 那么过程分两步:

  1. 对Ti之前所有事务, 进行redo(重做).
  2. 接着检查Ti, 如果Ti是terminated, 那么对Ti进行redo, 否则, 进行undo(撤销).

下面描述怎么样对事务进行redo和undo. 先说redo:

  1. 正序扫描事务T的所有日志;
  2. 如果该日志是插入操作(T, I, x), 那么将x重新插入到DB;
  3. 如果是更新操作(T, U, oldx, newx), 则把DB中x的值设置为newx;

再说undo:

  1. 倒序扫描事务T的所有日志;
  2. 如果是(T, I, x), 则将x从DB中删除;
  3. 如果是(T, U, oldx, newx), 则将DB中x的值设置为oldx;

对所有的事务进行redo或者undo后, 数据库便会恢复到崩溃前, 最后一个terminated事务结束时的状态了. 需要特殊说明的是, terminated并没有区分commmit和abort. 那么进行恢复后, 被撤销的事务, 对DB的影响便也会保留下来. 但是这样是正确的, 因为NYADB并没有真正的"撤销"操作, 该疑问将会在VM章节中被揭开.

至此, 我们讨论完了单线程下的恢复性保证. 并发下的恢复性保证会比单线程下复杂的多. 复杂的原因, 以及处理这些复杂情况的一些措施, 本文档就不展开讲了, 请参考其他数据库相关的书籍.

这里只描述最后的解决方案. 由于VM的存在, 传递到DM的执行序列, 会被得到以下的两点保证:

  1. 事务Ti不会读取任何其他未提交事务Tj产生的数据;
  2. 事务Ti不会去修改任何其他未提交事务Tj修改或产生的数据.

下面叙述一下这两条保证对可恢复的意义.

第一条规则保证了最低的"读提交"(read committed)隔离度, 避免了事务间的相互读取依赖, 避免了联级回滚. 假设有下面的执行序列:

T1 begin
T2 begin
T2 U(x)
T1 R(x)
...
T1 commit
NYADB break down(T2 is active now)

T1在T2提交前, 就读取了T2改动的数据, 既x, T1提交后, NYADB发生了崩溃. 那么在NYADB下次重启时, T2未结束, 则应该撤销, 它对DB的影响会被消除. 那么T1呢? T1已经被commit, 那么它不应该被撤销. 但是T1对DB的影响又依赖了T2对x的修改, 现在T2撤销了, 那T1也应该被撤销(该情况称为联级回滚). 但是如果真的撤销T1的话, 又和T1的commit语义产生了矛盾(一旦事务commit, 它的影响应该被持久化). 规则一则是防止了这种情况.

第二条规则的目的其实是为了保证事务操作的可串行化, 但却很"巧合"的方便了恢复. 它使得DM能够直接简单的利用"前相"(before image)来撤销事务. "前相"其实就是(T, U, oldx, newx)日志记录中的oldx. 如果没有这条规则, 在并发的情况下, 之前对修改操作的撤销方法, 是不合法的, 比如下面这个情况: 

(假设x一开始等于0)
T1 begin
T2 begin
T1 set x = x+1 // 产生的日志为(T1, U, 0, 1)
T2 set x = x+1 // 产生的日志为(T1, U, 1, 2)
T2 commit
NYADB break down(T1 is active now)

当NYADB下次重启时, 会对T1进行undo, 对T2进行redo. 但是不管他们的先后顺序如何, 最后x的值要么为0, 要么为2, 但这都是错误的. 出现这种问题的原因, 归根结底是因为我们的日志太过简单, 仅仅记录了"前相"和"后相". 并单纯的依靠"前相"undo, 依靠"后相"redo. 这种简单的日志方式和恢复方式, 并不能涵盖住所有数据库操作形成的语义.

解决办法有两种:

  1. 增加日志种类, 如上面, 我们可以增加一种Inc(x)日志, 以更精确的表示事务的操作.
  2. 对数据库操作进行限制.

在两种方案中, 我选择了第二种, 因为简单. 限制的结果就是之前的第二条规则.

有了上面的两条保证, 对并发情况下日志的恢复也就变得简单了. 分下面几步:

  1. redo所有崩溃时为terminated的事务.
  2. undo所有崩溃时为active的事务.

这样恢复后, DB便会变到所有terminated事务结束, 所有active事务未进行的状态. 如果你觉得这样恢复有问题, 那么你应该把问题情况列举出来, 并检查上面两条保证能不能杜绝这种错误情况的出现.

总结

本章的前三节, 刚好对应了DM的三个主要作用, 1) 管理DB, 提供抽象; 2) 缓存; 3) 保证可恢复性.

本章的内容, 有下面几个需要特别注意的地方:

  1. DM将DB从文件抽象为了数据项的集合, 使得上层模块不再需要关系文件细节.
  2. 在提供抽象时, 没有提供Delete(x)的操作, 这是由VM造成的.
  3. 由于DM的缓存, 数据的位置将会有"内存"和"磁盘"的概念, 这两个位置之间的数据是需要同步的.
  4. DM通过日志的方式来保证可恢复性.
  5. DM的可恢复性保证, 需要得到上层模块对两个规则的支持, 而这是由VM模块完成的. 其他DM的细节请参考代码注释.