版本管理器(VM)
引言
如果说DM是NYADB中数据处理的核心模块, 那么VM就是事务处理的核心模块了. 在正式开始介绍VM之前, 我们需要一些基本的事务处理的概念.
冲突, 可串行化调度和2PL
对于接下来即将出现的一些概念, 本篇文档只是简单, 浅薄的描述. 如果你想进行更深入的了解, 请参考任意一本有关"数据库"或是"事务处理"的书籍.
首先让我们来看看数据项操作之间"冲突"的概念. 我们用O来表示DM提供的U或者R操作. 注意O并不能代表I, 我们不考虑I操作. 同时利用下标, 来表现该操作是哪个事务进行的操作, 如Oi(x), 表示事务Ti对x进行操作. 同时, 我们用类似于"x is y"这样的术语, 来表示x和y虽然符号不同, 但是其实是一个数据项.
需要注意"x is y"和"x == y"的区分, 请对比"指针"或"引用"的概念, 这里就不赘述了, 相信大家都是学过编程的:) 现在给出冲突操作的定义, 对于任意两个操作Oi(x)和Oj(y), 如果:
- i != j, and
- x is y, and
- Oi == U or Oj == U;
那么这两个操作冲突.
由于只考虑U和R, 那么冲突的操作可以有下面两种情况:
- 两个不同事务间U操作相互冲突;
- 两个不同事务间的U, R操作冲突.
那么冲突不冲突有什么用呢? 作用就是下面这句话: 调换两个相互不冲突操作的顺序, 不会对数据库结果造成影响.
需要注意的是, 我们禁止对同一个事务内不同操作进行顺序调换, 因此上面的两个不冲突操作是指不同事务间的.
接下来将"冲突"放一边, 来看看并发的情况下, 同时处理多个事务的操作, 会带来哪些新问题. 如果没有并发, DM只需要顺序的执行事务需求的操作就可以了. 并发的情况下, 就不好说了, 如下:
(假设一开始x为0) T1 begin T2 begin R1(x) // T1读到0 R2(x) // T2读到0 U1(0+1) // T1尝试把x+1 U2(0+1) // T2尝试把x+1 T1 commit T2 commit
最后x的结果为1, 显然不对.
VM一个很重要的职责就是管理各个事务操作的调度顺序, 杜绝上面的情况, 实现调度序列的"可串行化". 实现"可串行化"的做法有很多, VM采用的是"两段锁协议"(2PL, two phase lock). 关于"可串行化"和"两段锁协议"这里不会再展开说了, 只是引出他们, 如果你觉得不熟悉, 请自行查阅资料.
使用2PL后, 且现在Ti已经锁定了x, 如果Tj也想操作x, 但是Tj的操作和Ti之前的操作相互"冲突"的话, 那么Tj就会被阻塞. 例如Ti因为Ui(x)锁定了x, 那么Tj想要执行Rj(x)或是Uj(x)都是不可能的了, Tj必须等待Ti释放掉x的锁. 可见, 2PL虽然保证了"可串行化", 但是却造成了事务间的相互阻塞, 甚至是死锁, 降低了数据库效率.
NYADB为了降低事务间的阻塞率, 实现了"多版本并发控制"(MVCC), 见下一小节
记录和版本
NYADB实现MVCC是为了消除Ri(x)和Uj(x)之间的冲突和阻塞, 既"读写"阻塞. 两个更新操作Ui(x), Uj(x)之间的阻塞, MVCC也是无能为力的.
首先我们介绍记录(entry)和版本(version)的概念. DM对DB文件进行管理, 并提供了数据项的概念供VM使用. 同样, VM对所有的数据项进行管理, 并提供了"记录"(entry)的概念供更上层模块使用. 上层的模块会利用VM来存储和操作数据, 而他们操作数据的最小单位, 就是记录. 而在VM内部, 会为每条记录, 维护多个"版本"(version).
每次上层模块修改记录, VM就会为该记录增加一个新的版本. 而每个记录的每个版本, 实际上就对应了DM的一个数据项. 我们用靠后的大写字母, 来表示记录, 如X, Y, Z. 我们用大写字母对应的小写字母+下标, 来表示它的各个版本, 如x0, x1, y3, z2等.
举一个例子来说明"记录"->"版本"->"数据项"的对应情况. 假设一开始DB中并没有数据, 则NYADB的情况如下:
Upper Model: Nothing Now VM: Nothing Now DM: Nothing Now
现在, Upper Model, 写入了一条新的记录, X. 则VM会为X建立其第一个版本, x0. 接着利用DM提供的操作, 将x0当做数据项存入到DB. 此时, 图如下:
Upper Model: X
|
v
VM: x0
|
v
DM: x
接着, Upper Model更新了X. 则VM会建立一个新的版本x1, 并也将其作为数据项存入到DB.
Upper Model: X
|
v
VM: x0 -> x1
| |
v v
DM: x y
同理, 如果Upper Model又更新了X, 则图如下.
Upper Model: X
|
v
VM: x0 -> x1 -> x2
| | |
v v v
DM: x y z
如果此时Upper Model又写入了一个新的记录, Y, 则图如下.
Upper Model: X Y
| |
v v
VM: x0 -> x1 -> x2 y0
| | | |
v v v v
DM: x y z w
y0下面是w, 而不是y. 因为y被用掉了, 我们只是用w来表示y0被存入DM后的那个数据项, 一个符号而已.
同DM一样, VM除了提供"记录"的抽象, 还提供了抽象上的操作. 提供了下面几种操作:
- R(X): 读取X的值;
- U(X): 更新X;
- D(X): 删除X;
- I(X): 插入新记录X;
注意, 在这里, VM提供了DM没有的Delete操作. VM怎么实现Delete, 请继续往下看.
现在可以描述MVCC解决"读写"阻塞的基本思路了. VM对每条记录进行上锁操作, 遵循2PL协议. 如事务Ti对上面的X由进行了更新, 那么它会先锁定了X, 再创建一个更新的版本x3. 如果Tj想要读取X的值, 怎么办呢, 直接返回给它某个更老的x版本, 如x2的内容. 这样, 最后的执行结果就相当于是Tj先执行, Ti后执行, 调度序列还是"可串行化"的. 至此, VM利用2PL+MVCC, 既保证了"可串行化", 又消除了"读写"阻塞.
同时, 由于2PL的存在, 使得某个事务不会去修改另外某个事务修改过但是还未提交的数据项, 也保证了DM章节中的规则二.
读提交下的版本可见性
本小节描述VM怎么为事务选择它对应的数据版本. 首先需要引入的是版本可见性的概念.
版本可见性和事务隔离度是有关的, 我们先介绍"读提交"(read committed)隔离度下的可见性判断. "读提交"就是要保证事务在读取数据时, 只能读取已经提交事务产生的数据.
"读提交"的好处在DM中已经举例说明了, 主要有两点:
- 避免联级回滚;
- 避免commit的语义冲突;
如果你感觉有点不理解上面两句话, 请跳回DM那再看一下例子.
接下来我们说说怎么实现"读提交". 我在VM中, 直接借鉴了POSTGRESQL的做法, 感谢开源:)
我们为每个版本, 维护两个特殊的变量, XMIN, XMAX, 他们含义如下:
- XMIN: 创建该版本的事务XID;
- XMAX: 删除该版本的事务XID;
XMIN自然是在版本被建立的时候填写. XMAX是在该版本被删除, 或是有新版本出现时, 被填写.
如上面的例子, 如果Ti创建了x3, 那么在创建x3的时候, x2的XMAX就应该被填写为Ti, x3的XMIN也为Ti. 这下你应该知道为什么DM不用提供删除操作了, 因为VM的"删除", 其实就是更新XMAX.
有了这两个信息, 我们就可以定义版本对事务的可见性逻辑了, 如下:
(XMIN == Ti and // created by Ti itself and XMAX == NULL // not deleted now ) or // or (XMIN is commited and // created by a commited transaction and (XMAX == NULL or // not deleted now or (XMAX != Ti and XMAX is not commited) // deleted by a uncommited transaction ))
如果上述逻辑为true, 则该版本对Ti可见.
那为Ti查找适合它的版本就很简单了, 从最新版本开始, 依次检查可见性, 如果为true, 则返回该版本. 该版本也一定是由某个已经提交事务产生或者由Ti自己产生. 同时, 由于更新的版本出现时, 当前最新的版本将会被删除, 因此在任意时刻, 最多只会有一个版本对Ti可见.
快照技术与可重复读的版本可见性
"读提交"可能会使一个事务在执行期间对同一个数据项的读取得到不同结果. 如下面这种情况:
(假如X一开始为0) T1 begin R1(X) // T1读得0 T2 begin U2(X) // 将X修改为1 T2 commit R1(X) // T1读的1
在上面的两次R1(X)中, 读出的X是不一样的. 有些事务是不希望出现这种情况的, 为此, 我们提供一个更加严格的隔离度"可重复读"(repeatable read).
"可重复读"在"读提交"的基础上, 还保证事务执行期间, 多次对同一记录的读取, 将会是一致的.
现在分析一下怎么在"读提交"的基础上, 实现"可重复读". 同一个事务内出现多次读取不一致, 实质是在两次读取间, 有新的事务对记录进行了修改, 并提交. 于是, 我们规定: 事务Ti只能读取它开始时, 就已经结束的那些事务产生的数据版本. 如果Ti遵守这条限制, 那么便不会出现两次读取不一致的情况.
现在我们来实现这条规定, 思路同样借鉴于POSTGRESQL, 感谢开源:) "只读取Ti开始前", 其实也就等价于忽略下面两种情况的数据:
- 比Ti后开始的事务的数据;
- Ti开始时还为active状态的事务的数据;
对于第一条, 我们直接通过比较版本的XID, 即可完成, 既事务只能读取XID比他小的事务产生的数据版本.
对于第二条, 引入"快照"(snapshot)技术, 在Ti开始时, 我们记录下当前所有活跃的事务, 并存在SP(Ti)中. 那么, 如果某个版本的XMIN在SP(Ti)中的话, 那么该版本应该对Ti不可见.
于是, 我们将这两条规则, 添加到可见性的判断逻辑中:
(XMIN == Ti and // created by Ti itself and
(XMAX == NULL or // not deleted now or
))
or // or
(XMIN is commited and // created by a commited treansaction and
XMIN < XID and // the transaction begin before Ti and
XMIN is not in SP(Ti) and // the transaction commited before Ti begin and
(XMAX == NULL or // not deleted now or
(XMAX != Ti and // deleted by another transaction but
(XMAX is not commited or // the transaction is not commtied now or
XMAX > Ti or // begain after Ti or
XMAX is in SP(Ti) // not commited when Ti begain
))))
这样, 新的可见性逻辑, 便会保证Ti只能看到Ti开始之前的数据, 保证其读取的一致性.
事务撤销
多版本机制除了能够消除"读写"冲突, 还有一个意外的好处, 那就是使得撤销事务异常简单. 假设现在有事务Ti, Ti已经进行了很多操作了, 对DB造成了很多影响, 如果要撤销它, 则只需要: 让TM将Ti标记为aborted.
为什么只需要做这么一点操作呢? 请参考之前的"可见性判断"逻辑, 如果Ti在TM中不是committed的, 那么他产生的数据, 对其他事务, 不会有任何影响. 让Ti对其他事务不会有任何影响, 也就是完成了对Ti的撤销.
版本跳跃问题
除了易撤销的好处, 多版本机制也会带来一个问题, "版本跳跃问题". 假设两个"可重复读"的事务, 有如下的执行序列:
(假设X一开始只有x0版本) T1 begin T2 begin R1(X) // T1读取x0 R2(X) // T2读取x0 U1(X) // T1将X更新到x1 T1 commit U2(X) // T2将X更新到x2 T2 commit
上述操作本身不会有任何问题, 但是逻辑上却有不妥. T1是将X从x0->x1, 这没问题. 但T2实际上是想将X从x0->x2, 跳过了x1这个版本, 因为T2读取时, X还只有x0. 这是有问题的.
于是, 我们对两个隔离度的事务, 分别做出如下的规定:
- "读提交"的事务允许出现版本跳跃;
- "可重复读"的事务不允许出现版本跳跃;
接下来我们就要处理"可重复读"隔离度下的版本跳跃问题.
解决的思路是, 如果Ti想要修改X, 但X已经被某个Ti不可见的事务Tj修改过了, 那么要求Ti回滚.
更加严谨的表述如下: 如果Ti想要修改X, 但X的最新版本是Tj创建的, 且XID(Tj) > XID(Ti) 或者 Tj在SP(Ti)中, 则令Ti回滚, 以防止版本跳跃.
实现的时候也非常简单, 直接取出X的最新版本, 如果该版本对Ti不可见, 那么Ti要求修改X则一定会发生版本跳跃, 于是要求Ti回滚.
至此, 解决了版本跳跃问题.
解决死锁
VM利用2PL来实现"可串行化"调度, 2PL处理除了会阻塞事务外, 更严重的, 会造成死锁问题. 本章来解决这个问题.
如果Ti锁定了X, 现在Tj准备更新X, 那么Tj会被阻塞, 等待Ti释放X的锁. 这种等待关系可以用有向图来表示, 比如上述关系就可以表示为"Tj -> Ti". 于是, 将所有这样的关系, 转化为图后, 死锁判断就简单了. 如果图中有环, 则有死锁; 否则无死锁. 笔者认为这是一个很显然的结论, 就不严谨的去证明了.
那么怎么检测某个图是否有环呢? NYADB采用了非常简单的办法, 即:
- 设置一个时间戳stamp = 0;
- 为每个点设置一个"访问戳", visStamp, 初始化为-1;
- 任意选择一个visStamp为-1的点, 设它为s;
- stamp++;
- 从s开始遍历, 对每个遍历到的点u进行下面的判断:
- ===> 如果visStamp[u] == -1, 则visStamp[u] = stamp, 继续遍历;
- ===> 如果visStamp[u] != -1 and visStamp[u] < stamp, 跳过点u, 即不以它为节点继续向下遍历;
- ===> 如果visStamp[u] == stamp, 则有环, 结束算法;
- 当从s开始遍历完且并没发行环, 重复3), 直到没有visStamp为-1的点.
- 当整个算法结束时, 都没发现环, 则无环.
在此只描述算法的过程, 并不对其正确性进行证明.
有了检测死锁的思路, 再来想想什么时候进行检测呢? 检测到了死锁, 怎么消除他呢? NYADB为了简单, 采用的办法是: 将等待图维护在内存中, 每当出现等待时, 则向图中加入一条边. 每向图中加入一条边, 便进行一次死锁检测. 如果加入某条边后检测到了死锁, 则撤销加入这条边的事务.
至此, 解决了死锁问题.
总结
梳理一下VM的思路:
- 为了实现"可串行化"调度, VM使用了2PL;
- 为了减少2PL的阻塞率, VM实现了MVCC;
- 为了实现MVCC, VM抽象出了"记录"和"版本";
- 为了对应"版本"和事务, VM使用了可见性判断;
- 为了实现更严格"可重复读"隔离度的可见性, VM引入了"快照"技术;
- "多版本"使得VM的"删除"和"撤销"操作变得意外的简单;
- 但是"多版本"却会导致"版本跳跃", 为了解决它, VM会限制出现版本跳跃的事务回滚;
- VM还解决了2PL带来的"死锁"问题.