万圣节问题的底层逻辑是，update操作
Update id = id+1
会新增插入数据，然后scan操作又把新插入的数据视作原来表中的数据，重复删除新增的数据再插入数据如此反复导致死循环。
update操作需要使用扫描表中符合条件的行，可以发现update执行器有子执行器，其实就是scan执行器，所以这两个操作的事务id和sql语句是相同的。只需在scan环节对元组做判断是否为相同的事务id和sql语句cid，相同则不送出该元组（火山模型，一次只返回一行）

实现mvcc，使用事务版本号（某种意义上是逻辑时间戳）。每个事务都有一个唯一的事务ID，被称为XID。注意：除了被BEGIN - COMMIT/ROLLBACK包裹的一组语句会被当作一个事务对待外，不显示指定BEGIN - COMMIT/ROLLBACK的单条语句也是一个事务。

本实验框架和pgsql的mvcc相似，其实现原理如下：

1）数据文件中存放同一逻辑行的多个行版本；
2）每个行版本的头部记录创建该版本的事务ID以及删除该行版本的事务的ID（分别称为xmin和xmax）；
3）系统保存了每个事务的状态（运行中，中止或提交）
4）根据上面的数据并运用一定的规则每个事务只会看到一个特定的行版本。
通过MVCC，读写事务可以分别在不同的行版本上工作，因此能够在互不冲突的情况下并发执行。

我们需要先介绍下隔离级别：
Alt text
本实验要求实现读已提交，可重复读和可串行化。
在一般情况中，隔离级别能解决的问题如下表。
读脏（Dirty Read)会导致读取到未提交的数据，不可重复读会导致同个事务对同一行数据第二次读取得到的结果不一样（第二次查询时读到了其他事务新提交的数据），幻读（Phantom）会导致同个事务对同一个表第二次读取得到的行数不一样（如多了一行，少了一行）。
然后是mvcc中，快照读可见性判断的例子（前四个测试案例文件只需实现快照读）：
假设当前正执行的事务版本号为xid，要判断一个元组是否可见：
1.插入该元组的事务（也就是版本号为xmin）已经提交了的情况下，那么在xmin事务之后开始的新事务就都能够看到该元组，即xid>=xmin的事务均能看到该行（xid=xmin则是一个事务未结束时再次scan表，能读取到之前插入的元组）；同理，xmax事务已提交的情况下，xid>=xmax的事务就读不到该行数据了。但若xmin未提交，那么即使xid>=xmin，事务xid也不能看见该行，xmax同理；
2.xmin或xmax>xid，说明事务xmin(xmax)比当前事务晚创建，在可重复读隔离级别的事务中是不能看见的；但是如果是在隔离级别为读已提交的事务中，若对应该元组的插入或删除操作已经提交（xmin或xmax事务已提交），那么当前事务在第二遍scan表时则能读取到该元组的变化（提交插入，则第二遍扫描表时能看到该元组；提交删除，则该元组第二遍时不会被读取到）。
本实验中，快照读中，元组对一个事务是否可见的完整判断逻辑，如下图：

tup
mvcc需要借助活跃事务集来判断一个元组的修改是否已提交。可重复读和读已提交获取的活跃事务集方法是不一样的。隔离级别为可重复读的事务因为看不到后续创建的新事务，所以它的活跃事务集应该是一个快照，包含在该事务创建时的所有活跃事务的集合，而隔离级别为读已提交的事务看到的活跃事务集则会随着新事务的开始和提交而更新。
快照读可以直接在tablescan中实现，但是若需要当前读，还需要在其他执行器中添加处理逻辑，同时对快照读实现中元组可见判断的一部分逻辑迁移到seqscan执行器中执行。

实现MV2PL
在mvcc中引入两阶段锁（two-phase-lock)。两阶段锁中，有粒度锁的概念，粒度有行级和表级。同时，有五种锁，分别为共享锁（Share)、排他锁(Exclusive)、意向共享锁（Intention Share Lock)、意向排他锁（Intention Exclusive Lock)、共享意向排他锁
t
意向锁是表级锁，只能对表上锁，意向共享锁代表的是要对该表的某些行进行读操作；意向排他锁代表要对该表的某些行进行写操作；共享锁和排他锁，两者均能对表和行上锁。
两阶段锁的实现
然后介绍下不同sql语句对应不同的加锁情况。
首先需要根据sql语句是否需要更新数据来判断。普通select语句，seqscan执行器只会对表加IS锁；
修改语句：
update：嵌套在update中的子seqscan执行器，其Ismodifedsql（）为true，即数据更新语句，需要加IX锁；
insert的子执行器不为seqscan执行器，所以直接在本执行器中对表上IX锁即可；
delete的子执行器同update一样，故在seqscan执行器中上IX锁；
本实验测试案例中的SIX锁：先对表设为share mode，也就是上S锁，再执行Insert操作加上IX锁，就变成了SIX锁。
当前读 Select for update 和 share的上锁：update是对行加写锁，share则是对行加读锁。
当前读不再是严格的snapshot Isolation，因为返回的是最新的数据
t
锁维护使用的数据结构

维护每个表的锁请求队列，只要该锁请求的锁类型能兼容该队列中的任何锁请求的锁类型，则将该锁请求加入队列，如果该锁请求的锁类型不能兼容该队列中的任何一个，则返回false
锁升级的实现思路是，首先找到该事务xid想要上锁的表的锁请求队列，遍历一遍队列锁升级的类型是否与其他事务上的锁类型兼容，若兼容，再判断之前xid上过的锁能否直接升级，不能则再上新锁（锁类型为想要升级的类型）。
何为两阶段锁：第一阶段只能上锁不能解锁，第二阶段只能解锁不能上锁。
在事务提交后，才会将锁一次性释放，也就是强两阶段锁，保证了可串行化。