[db] 4 - Phantom Problem

产生原因

要实现真正的可串行化，幻象问题是我们绕不过去的坎。诶，但是之前介绍 2PL 时不是说严格遵守两阶段锁协议就能够实现事务的可串行化吗。对，但这是有条件的，两阶段锁能保证可串行化的前提是读写的数据项集合不发生改变，也就是说没有插入/删除操作。

插入和删除操作会如何破坏两阶段锁的可串行化呢，我们来看教材上的例子（修改了一点字段）：

也可以看这里的课件 pdf 页码69有类似例子

事务T1第一次统计 $salary>9000$ 的职员有10人，如果此时T2 恰巧提交了插入数据，T1第二次统计 $salary>9000$ 的职员就变为了11人。

串行化要求事务 T1 和 T2 并发执行时，得到的结果与单线程执行时一致。即对事务 T1 来说，要么它看到的是 T2 先于自己执行完毕，此时两次查询都要能看到 T2 新插入的数据；要么看到的是自己先执行完，两次查询都看不到 T2 新增的数据项。而现在事务 T1 的两次查询返回了不同的结果（虽然我们依然遵守两阶段锁协议），这显然不是一个可串行化的调度。

出现幻象问题的原因在于：使用两阶段锁我们无法阻止其他事务插入数据（删除需要获取互斥锁，而读事务应当已经持有共享锁，所以删除操作会被block，这不会造成问题），如果其他事务插入的数据正好出现在当前事务查询的 where 子句范围中（若没有 where 则可认为 where 的范围是全部数据），那么当前事务后续相同的查询就会看到这一更新，这就破坏了可串行化性质。

解决方法

所以解决思路也是比较清晰的，我们要想办法阻止这样的插入/删除操作直到当前事务提交。总结来说有以下三种方法¹：

索引锁（Index Locking）

教材²上对于索引锁给出了比较详细的描述：

对于所有数据的访问必须经由索引进行（全表扫描看作对所有叶节点的扫描）
查找时必须在对应叶节点上获得共享锁
进行增、删、改操作时，需要获取叶节点上的互斥锁
遵守两阶段协议

如果某个谓词范围内本身没有数据，那么我们就要找到该谓词对应数据存在时应当要插入的节点。如上述图中的例子假设我们查询的数据为 $ salary>9000 $，而数据库中原本只包含 $ [8000,8200], [8400,8700], [8800,8900] $ 的数据（分为三个节点），则因为 $salary>9000$ 数据插入需要经过最后一个节点，所以我们需要获取最后一个节点的共享锁才能读取数据。这样保证了某个事务执行查询的过程中，其他事务无法对谓词约束范围内的数据进行修改(尽管有些不会发生谓词冲突的修改也被封锁了)，从而避免幻象现象。

谓词锁（Predicate Locking）

对于查询操作，我们在 where 子句上“加上共享锁”；更新/插入/删除操作则需要“加上互斥锁”。因为锁是加在 where 这一 predicate 上，故称之为谓词锁。但是如何对谓词加锁呢，大致方法是事务执行过程中记录下每个碰到的 where 子句表示的范围（建立谓词锁），往后的操作都要判断是否与现有谓词锁冲突（数据范围与被谓词锁锁住的数据不能有交集），如果有则需要推迟操作等待谓词锁的释放。可以想象如果数据的维度较高则需要在每个维度都进行检查，新的SQL语句任何一个维度下的谓词都不能与现有谓词锁冲突（否则就不授予锁），现实场景下SQL语句众多，这个过程会变得异常繁琐。事实上谓词锁因为开销太大基本上没有数据库采用。

重新扫描（Re-Execute Scans）

顾名思义，我们在事务查询时保存得到的 scan set，然后事务提交前重新执行查询看是否得到相同的结果；若结果不一致则需要回滚事务。

总结

通过上面的介绍可以看出，幻象问题是因为我们只能对已存在的数据加锁才出现的。那么对于时间戳排序和有效性检查两类不用锁的并发控制手段，幻象问题存在吗？

先看时间戳排序。我们假设事务1先查询 department=CS 的查询，在它提交之前，一个新的事务2开始执行并插入10条 department=CS 的数据。因为新数据并没有被其他事务读取或修改过，所以事务2可以提交。然后事务1再次进行相同查询，是否会出现幻象问题呢：此时事务1会看到这10条新数据，但是因为插入它们的事务2时间戳比事务1要新，因此根据时间戳排序的要求，事务1的读取操作会被拒绝，并且回滚。所以可见时间戳排序不会出现幻象问题。

简述时间戳排序的运作流程³：
每个数据项 Q 拥有一个写时间戳 W-TS(Q) 和一个读时间戳 R-TS(Q)，分别在 Q 被成功写入和读取时更新为执行对应操作的所有事务中最大的时间戳，$TS(T_i)$ 为事务开始时获取的事务时间戳。
读操作： 1）若 $TS(T_i)$ < W-TS(Q)，说明 Q 在 $T_i$ 开始执行之后，被另一个更新的事务修改，因此 $T_i$ 的读操作被拒绝，并回滚； 2）若 $TS(T_i)$ >= W-TS(Q)，则读操作可执行，更新R-TS(Q)=max{$TS(T_i)$, R-TS(Q)}
写操作： 1）若 $TS(T_i)$ < W-TS(Q) 或 $TS(T_i)$ < R-TS(Q)，说明Q已被更新的事务修改或已被更新的事务读取，此时$T_i$都不能修改Q，因此拒绝操作，并回滚； 2）其他情况则可执行写操作，并更新W-TS(Q)

有效性检查的方法目前了解不多，看教材描述的过程似乎与 MVCC 类似，在事务开始时生成数据项的副本，然后需要修改时在副本上进行，提交时要先通过有效性检查，才将修改应用到数据库中。有效性检查需要查看两个并发事务1的写与事务2的读不相交（事务1先于事务2开始），且事务1的提交在事务2开始验证之前，才允许写入。有效性检查的要求比MVCC要严格，但是能够保证串行化，同时也不会出现幻象。// TODO：needs update

MVCC 因为隔离了读写事务能观测到的数据版本，也不用担心幻象（关于MySQL MVCC 有些奇怪的问题还没搞懂，先码一下⁴,⁵,⁶）；但是 MVCC 所实现的快照隔离等级（Snapshot Isolation）会产生新的问题导致它也不是完全的可串行化，也许我们下次会深入了解一下。

The End