事务并发与MVCC随记
为了了解前沿技术，最近看了篇FAST23的文章，讲事务内存的。本来以为重点在内存上，结果background还没读完，直接给事务并发整不会了。然后直接上某乎恶补了一下，大概有个基本的认识了，在此记录一下。
一 事务并发的原因
事务并发主要存在的问题，简单来讲，围绕的还是事务ACID四个特性打转转。
首先是事务的基础，原子性Atomicity和一致性Consistency。这两点与并发事务没有直接关系，现在主要通过
undo log和redo log两种日志保障。其中redo log用于保障事务的向后一致性，即经典的WAL（Write-Ahead Logging），通过提前把写操作记录到专门的区域，来保障即使写过程中出现问题导致写未完成，也能通过重新执行redo log中的操作，将数据更新到期望的状态——换句话说，就是大家经常提到的操作的幂等性，即允许一个操作被重复执行任意次，仍然保持正确的数据语义；而undo log用于保障事务的向前一致性，即通过记录事务修改数据后恢复到事务执行前的必要操作，保证即便在事务执行失败的情况下，可以回退到上一个合法的数据版本。但是话又说回来，历史的车轮滚滚向前，即便是撤销事务也要通过新的数据来记录这些流程，也就是说，undo log的正确性最终也还是离不开redo log的保障。
其次就是并发事务的核心所在了：隔离性Isolation和持久性Persistency两位神仙打架。持久性很好理解：一个事务执行完成之后，其数据被持久化，之后对任何相关数据的读操作返回的都应该是事务执行后的结果。然而在并发这个令人头大的前提条件下，一切都麻烦了起来：受到现有计算机体系结构的限制，处理器并不能以单条指令的形式来处理每一个事务，只能通过上锁的形式来保证在当前事务执行的过程中，不被其他的事务破坏其原子性。最为传统的上锁方式就是我全都要——锁表，甚至锁库。然而这种方法性能很差，不能充分利用现有多核处理器架构的性能，因而需要通过并发的方式提升资源的利用效率。
二 事务并发带来的问题
那么该怎么办呢？既然要并发，那就不能轻易上锁，只好试着分析看看，在无锁的情况下，事务的并发会出现什么问题吧。既然数据的完整性最终通过读操作反映，那么就考虑从读操作上可能会出现的问题入手分析。一般认为，导致事务之间存在冲突的根源还是操作系统对处理器资源的时分复用，导致多个事务被同时执行，而当多个事务恰好轮流操作到同一份数据的时候，问题产生。
好在前人早已为我们做好了总结：无锁事务并发主要会遇到三种问题。依照对并发性的影响程度从低到高依次为：脏读、不可重复读、幻读。
当一个事务在执行时，读取到另一事务未提交的数据，定义为脏读。这里的“脏”数据可以理解为破坏了一致性的数据：若事务A读取到事务B修改过的数据，而事务B却在未来执行了回滚操作，而基于事务的原子性，回滚时并不考虑其它事务会读取到这份数据；那么这会导致事务A采用错误的数据继续向下执行，轻者使得该项数据错误，重者再被其他事务采用，扩散至整个数据库。
当一个事务在执行时，多次读取同一数据期间，由于另一事务修改了该项数据，导致前后读取结果不一致的情况，定义为不可重复读。考虑事务A执行过程中，事务B“插队”并且快速执行完，还修改了事务A要读取的数据。由于出现前后读结果不一致的时刻只有事务A正在执行，所以相比于脏读，读到的新数据是“干净”的，但是由于事务的持久性，又无法读出之前的旧值，因而命名为“不可重复”读。
当一个事务在执行时，多次范围查询同一数据期间，由于另一事务进行了条目的插入或者删除，导致范围查询结果不一致的情况，定义为幻读。注意到与之前不同的地方在于，这里强调了执行的操作是范围查询，且产生的不一致包含条目数量的变化，在数据形式上表现为像是食了云南VR启动器一样的幻觉，发现查询条目或多或少，因而定义为“幻”读。
三 事务并发的解决方案
兵来将挡，水来土掩。对付三种破坏数据一致性的问题，自然有四种不同级别的事务隔离，它们分别是：读未提交RU, Read Uncommitted、读已提交RC, Read Committed、可重复读RR, Repeatable Read、串行化Serializable。实际上可以视为，每一种隔离级别都在上一种的基础上加上一条新的限制，以进一步解决新问题，同时付出一定的性能作为代价。
读未提交对应的是不考虑三种并行事务冲突场景下的隔离级别，只保证对数据访问的原子性，即同一时刻只有一个事务可以访问同一个数据；
读已提交隔离级别解决脏读的问题，有两种可能的实现方式：一是使用行级记录锁，但仅上锁保护当前正在处理的数据行；二是语句级的ReadView，可以视作数据快照，这个在后文MVCC实现思路部分将展开讨论；
可重复读隔离级别解决不可重复读的问题，同样是两种可能的实现方式：一是使用行级记录锁，上锁保护当前事务所要操作的所有数据行；二是事务级的ReadView，从逻辑上将数据库中的每行数据“锁定”为当前事务开始时的版本。
串行化再在上面的基础上解决幻读的问题，通过行级间隙锁（可以理解为范围锁）或者表级锁实现。说白了，加了这么多限制条件，约等于回到没有事务并行的时代了。
四 无锁事务并发
工程界的问题解决思路自然是捡现成的，能用就行，因而不少数据库早期均采用缩小锁粒度的方式来实现事务并发的原型版本。然而，锁终究是抢占的、单线程的，没人能保证锁在某些特定情况下不会成为性能瓶颈，那么这个锁自然是能拿掉最好，于是多版本并发控制MVCC, Multi-Version Concurrency Control诞生了。简要概括的话，MVCC采用了以空间换时间的思路，通过保留数据的历史版本的方式，来为不同事务提供各自独特版本的数据空间。
那么问题是，这个数据如何存储？会成为一项新的存储开销大头吗？
答案是否定的。还记得前面的undo log吗？在文章开始不久的地方有提到，基于undo log可以将数据恢复到历史版本，而MVCC巧妙地利用了这一点，不再额外添加新的历史版本记录，而是在实际需要旧版本数据的时候，利用undo log的差量备份，回溯到所需要的数据版本。而接下来要讨论的，就是基于undo log的MVCC基本实现方法。
不同事务操作同一数据行的时候，必然会在事务间留下中间版本。undo log记录这些中间版本的必要信息（最直接的记录方法则是直接复制，复杂点就可能是语句级别，比如delete对应insert，或update到旧数据等方式），并附加一个版本号和一个指针域，分别记录修改的提交时间和修改前的undo log条目项，称作版本链。
那么如何利用版本链实现事务并发呢？关键在于事务号之上。在MVCC中，每个事务都被赋予了一个事务号，该事务号可视作一个自增计数器，按照事务开始执行的先后顺序获取；此外，在系统中维护一组事务号信息，包含如下三大类，以MySQL为例：
min_limit_id：系统当前编号最小的未提交事务id；m_ids：系统当前未提交的事务id列表——也就是说，min_limit_id是m_ids中的最小值；max_limit_id：系统将为下一个新创建的事务分配的事务id，显然永远大于m_ids中的所有事务id。
再加上事务本身被分配的事务idcreator_trx_id和读取的具体数据条目的版本号trx_id，则构成一个完整的read view。read view可以视作一个系统中当前事务进程的快照，当其条件被触发时形成，通过这个read view可以唯一确定一个可供事务使用的、正确的数据版本，具体逻辑如下：
首先前提是，对数据的读取永远从最新条目向旧版本开始搜索；
- 如果待读取数据的
trx_id小于min_limit_id，意味着当前读取到的数据版本在本事务开始执行前已经提交，对当前事务可见，返回该数据； - 如果待读取数据的
trx_id大于max_limit_id，意味着当前读取到的数据版本非常新，甚至是在read view形成之后才提交，这意味着该数据版本一定对当前事务不可见，需要向前搜索合法的旧版本； - 剩下的情况集中于
min_limit_id<trx_id<max_limit_id条件下，此时则依照trx_id与m_ids的关系讨论具体逻辑：- 当
trx_id不存在于m_ids中的时候，意味着当前事务已经提交（因为不存在分配了版本号但没开始执行的事务），那么该版本数据对当前事务可见，返回该数据； - 当
trx_id存在于m_ids中的时候，属于读取到尚未提交事务的数据，具体又可分为两种情况： - 当
trx_id==creator_trx_id的时候，意味着读到了当前事务自己对数据的修改，显然事务内数据是可见的，返回该数据； - 当
trx_id!=creator_trx_id的时候，意味着读到了别的未提交事务的数据，依照ACID原则和上面提到的并发问题，这种情况属于脏读，破坏了数据的一致性，需要向前搜索合法的旧版本。
- 当
对于以上的逻辑，简单概括还是前面提到的一句话：读取到的数据永远应该是当前状态下已提交事务的最新结果，否则向前搜索到满足该条件为止。
通过上述逻辑描述，我们可以看到的是，MVCC从设计上就避免了脏读的产生，也就是说使用了MVCC方案的并发数据库引擎天生就不会遇到脏读问题，最低是RC隔离级别。
那么可重复读和幻读呢？
答案是依然要借助之前提到的数据库隔离级别才能解决这些问题。上面提到，read view决定了当前执行的语句会读取到什么版本的数据，而满足触发条件的时候，read view形成，而这个条件正是决定隔离级别的关键：
- 当条件为【在执行当前语句时生成
read view】时，实现的是RC隔离级别，因为无法保证语句执行之间没有新的事务迅速执行并提交； - 当条件为【在执行当前事务时生成
read view】时，实现的是RR隔离级别，因为即便在事务执行中有新数据提交，仍然会按照事务开始时生成的read view寻找更旧版本的数据。
而关于幻读的话，理论上也是予以解决了的，因为我们可以将搜索版本链而没有获得合适版本的情况视作该数据条目不存在，从而实现“屏蔽”新数据条目的问题。然而，https://www.cnblogs.com/yizhiamumu/p/16804566.html 这篇文章的作者提出了不同的意见，指出MVCC无法解决以下问题，进而认为MVCC无法处理幻读：
A:
START TRANSACTION; SELECT FROM USER WHERE ID=5;B:
START TRANSACTION; INSERT INTO USER (ID, NAME) VALUES (5, 'MYNAME'); COMMIT;A:
INSERT INTO USER (ID, NAME) VALUES (5, 'MYNAME'); COMMIT;
大意是说如果在一个事务执行的时候，新起一个事务插入一条记录并提交，再回到原有事务插入相同数据会遇到主键冲突的问题。
我的观点是，他提出的问题是存在且有意义的，但是这是写后写WAW, Write-After-Write问题，已经不属于幻读的范畴了。从上面我们的定义可以看出，本文讨论的问题主要是写后读RAW, Read-After-Write问题，无论脏读、不可重复读还是幻读都是从读的角度定义的，那么就定义来看问题是解决的。
答案是锁是万能的，但是慢。