01数据库并发控制的作用
1.1 事务的概念
在介绍并发控制前，首先需要了解事务。数据库提供了增删改查等几种基础操作，用户可以灵活地组合这几种操作，实现复杂的语义。在很多场景下，用户希望一组操作可以做为一个整体一起生效，这就是事务。事务是数据库状态变更的基本单元，包含一个或多个操作（例如多条SQL语句）。
经典的转账事务，就包括三个操作：（1）检查A账户余额是否足够。（2）如果足够，从A扣减100块。（3）B账户增加100块。
事务有个基本特性：这一组操作要么一起生效，要么都不生效，事务执行过程中如遇错误，已经执行的操作要全部撤回，这就是事务的原子性。
如果失败发生后，部分生效的事务无法撤回，那数据库就进入了不一致状态，与真实世界的事实相左。例如转账事务从A账户扣款100块后失败了，B账户还未增加款项，如果A账户扣款操作未撤回，这个世界就莫名奇妙丢失了100块。原子性可以通过记日志（更改前的值）来实现，还有一些数据库将事务操作缓存在本地，如遇失败，直接丢弃缓存里的操作。
事务只要提交了，它的结果就不能改变了，即使遇到系统宕机，重启后数据库的状态与宕机前一致，这就是事务的持久性。
数据只要存储非易失存储介质，宕机就不会导致数据丢失。因此数据库可以采用以下方法来保证持久性：（1）事务完成前，所有的更改都保证存储到磁盘上了。或（2）提交完成前，事务的更改信息，以日志的形式存储在磁盘，重启过程根据日志恢复出数据库系统的内存状态。一般而言，数据库会选择方法（2），原因留给读者思考。
数据库为了提高资源利用率和事务执行效率、降低响应时间，允许事务并发执行。但是多个事务同时操作同一对象，必然存在冲突，事务的中间状态可能暴露给其它事务，导致一些事务依据其它事务中间状态，把错误的值写到数据库里。需要提供一种机制，保证事务执行不受并发事务的影响，让用户感觉，当前仿佛只有自己发起的事务在执行，这就是隔离性。
隔离性让用户可以专注于单个事务的逻辑，不用考虑并发执行的影响。数据库通过并发控制机制保证隔离性。由于隔离性对事务的执行顺序要求较高，很多数据库提供了不同选项，用户可以牺牲一部分隔离性，提升系统性能。这些不同的选项就是事务隔离级别。
数据库反映的是真实世界，真实世界有很多限制，例如：账户之间无论怎么转账，总额不会变等现实约束；年龄不能为负值，性别最多只能有男、女、跨性别者三种选项等完整性约束。事务执行，不能打破这些约束，保证事务从一个正确的状态转移到另一个正确的状态，这就是一致性。
不同与前三种性质完全由数据库实现保证，一致性既依赖于数据库实现（原子性、持久性、隔离性也是为了保证一致性），也依赖于应用端编写的事务逻辑。
1.2 事务并发控制如何保证隔离性
为了保证隔离性，一种方式是所有事务串行执行，让事务之间不互相干扰。但是串行执行效率非常低，为了增大吞吐，减小响应时间，数据库通常允许多个事务同时执行。因此并发控制模块需要保证：事务并发执行的效果，与事务串行执行的效果完全相同（serializability），以达到隔离性的要求。
为了方便描述并发控制如何保证隔离性，我们简化事务模型。事务是由一个或多个操作组成，所有的操作最终都可以拆分为一系列读和写。一批同时发生的事务，所有读、写的一种执行顺序，被定义为一个schedule，例如：
T1、T2同时执行，一个可能的schedule:
T1.read(A),T2.read(B),T1.write(A),T1.read(B),T2.write(A)
如果并发事务执行的schedule效果与串行执行的schedule（serial schedule）等价，就可以满足serializability。一个schedule不断调换读写操作的顺序，总会变成一个serializable schedule，但是有的调换可能导致事务执行的结果不一样。一个schedule中，相邻的两个操作调换位置导致事务结果变化，那么这两个操作就是冲突的。冲突需要同时满足以下条件：
- 这两个操作来自不同事务
- 至少有一个是写操作
- 操作对象相同
因此常见的冲突包括：
- 读写冲突。事务先A读取某行数据、事务B后修改该行数据，和事务B先修改某行事务、事务A后读该行记录两种schedule。事务A读到的结果不同。这种冲突可能会导致不可重复读异象和脏读异象。
- 写读冲突。与读写冲突产生的原因相同。这种冲突可能会导致脏读异象。
- 写写冲突。两个操作先后写一个对象，后一个操作的结果决定了写入的最终结果。这种冲突可能会导致更新丢失异象。
数据库只要保证，并发事务的schedule，保持冲突操作的执行顺序不变，只调换不冲突的操作，可以成为serial schedule，就可以认为它们等价。
这种等价判断方式叫做conflict equivalent：两个schedule的冲突操作顺序相同。例如下图的例子，T1 write(A)与T3 read(A)冲突，且T1先于T3发生。T1 read(B)和 T2 write(B)冲突，且T2先于T1，因此左图事务执行的schedule，与T2,T1,T3串行执行的serial schedule（右图） 等价。左图的执行顺序满足conflict serializablity。
再分析一个反例：T1 read(A)与T2 write(A)冲突且T1先于T2，T2 write(A)与T2 write(A)冲突且T2先于T1。下图这个个schedule无法与任何一个serial schedule等价，是一个不满足conflict serializablity的执行顺序，会造成更新丢失的异象。
总体来说，serializability是比较严格的要求，为了提高数据库系统的并发性能，很多用户愿意去降低隔离性的要求以寻求更好的性能。数据库系统往往会实现多种隔离级别，供用户灵活选择，关于事务隔离级别，可以参看这篇文章。
并发控制的要求清楚了，如何实现呢？后文将依据冲突检测的乐观程度，一一介绍并发控制常见的实现方法。
02基于两阶段锁的并发控制
2.1 2PL
既然要保证操作按正确的顺序执行，最容易想到的方法就是加锁保护访问对象。数据库系统的锁管理器模块，专门负责给访问对象加锁和释放锁，保证只有持有锁的事务，才能操作相应的对象。锁可以分为两类：S-Lock和X-Lock，S-Lock是读请求使用的共享锁，X-Lock是写请求使用的排他锁。它们的兼容性如下：操作同一个对象，只有两个读请求相互兼容，可以同时执行，读写和写写操作都会因为锁冲突而串行执行。
2PL（Two-phase locking）是数据库最常见的基于锁的并发控制协议，顾名思义，它包含两个阶段：
- 阶段一：Growing，事务向锁管理器请求它需要的所有锁（存在加锁失败的可能）。
- 阶段二：Shrinking，事务释放Growing阶段获取的锁，不允许再请求新锁。
为什么加锁和放锁要泾渭分明地分为两个阶段呢？
2PL并发控制目的是为了达到serializable，如果并发控制不事先将所有需要的锁申请好，而是释放锁后，还允许再次申请锁，可能出现事务内两次操作同一对象之间，其它事务修改这一对象（如下图所示），进而无法达到conflict serializable，出现不一致的现象（下面的例子是lost update）。
2PL可以保证conflict serializability，因为事务必须拿到所有需要的锁才能执行。例如正在执行的事务A与事务B冲突，事务B要么已经执行完，要么还在等待。因此那些冲突操作的执行顺序，与BA或AB串行执行时冲突操作执行顺序一致。
所以，数据库只要采用2PL就能保证一致性和隔离性了吗？来看一下这个例子：
以上执行顺序是符合2PL的，但T2读到了未提交的数据。如果此时T1回滚，则会引发级联回滚（T1的更改，不能被任何事务看到）。因此，数据库往往使用的是加强版的S(trong)S(trict)2PL，它相较于2PL有一点不同：shrinking阶段，只能在事务结束后再释放锁，完全杜绝了事务未提交的数据被读到。
2.2 死锁处理
并发事务加锁放锁必然绕不开一个问题--死锁：事务1持有A锁等B锁，事务2持有B锁等A锁。目前解决死锁问题有两种方案：
- Deadlock Detection：
数据库系统根据waits-for图记录事务的等待关系，其中点代表事务，有向边代表事务在等待另一个事务放锁。当waits-for图出现环时，代表死锁出现了。系统后台会定时检测waits-for图，如果发现环，则需要选择一个合适的事务abort。
- Deadlock Prevention：
当事务去请求一个已经被持有的锁时，数据库系统为防止死锁，杀死其中一个事务（一般持续越久的事务，保留的优先级越高）。这种防患于未然的方法不需要waits-for图，但提高了事务被杀死的比率。
2.3 意向锁
如果只有行锁，那么事务要更新一亿条记录，需要获取一亿个行锁，将占用大量的内存资源。
我们知道锁是用来保护数据库内部访问对象的，这些对象根据大小可能是：属性（Attribute）、记录（Tuple）、页面（Page）、表（Table），相应的锁可分为行锁、页面锁、表锁（没人实现属性锁，对于OLTP数据库，最小的操作单元是行）。对于事务来讲，获得最少量的锁当然是最好的，比如更新一亿条记录，或许加一个表锁就足够了。
层次越高的锁（如表锁），可以有效减少对资源的占用，显著减少锁检查的次数，但会严重限制并发。层次越低的锁（如行锁），有利于并发执行，但在事务请求对象多的情况下，需要大量的锁检查。数据库系统为了解决高层次锁限制并发的问题，引入了意向（Intention）锁的概念：
- Intention-Shared (IS)：表明其内部一个或多个对象被S-Lock保护，例如某表加IS，表中至少一行被S-Lock保护。
- Intention-Exclusive (IX)：表明其内部一个或多个对象被X-Lock保护。例如某表加IX，表中至少一行被X-Lock保护。
- Shared+Intention-Exclusive (SIX)：表明内部至少一个对象被X-Lock保护，并且自身被S-Lock保护。例如某个操作要全表扫描，并更改表中几行，可以给表加SIX。读者可以思考一下，为啥没有XIX或XIS
意向锁和普通锁的兼容关系如下所示：
意向锁的好处在于：当表加了IX，意味着表中有行正在修改。
（1）这时对表发起DDL操作，需要请求表的X锁，那么看到表持有IX就直接等待了，而不用逐个检查表内的行是否持有行锁，有效减少了检查开销。（2）这时有别的读写事务过来，由于表加的是IX而非X，并不会阻止对行的读写请求（先在表上加IX，再去记录上加S/X），事务如果没有涉及已经加了X锁的行，则可以正常执行，增大了系统的并发度。
3303基于Timing Order（T/O）的并发控制
为每个事务分配timestamp，并以此决定事务执行顺序。当事务1的timestamp小于事务2时，数据库系统要保证事务1先于事务2执行。timestamp分配的方式包括：（1）物理时钟；（2）逻辑时钟；（3）混合时钟。
3.1 Basic T/O
基于T/O的并发控制，读写不需加锁， 每行记录都标记了最后修改和读取它的事务的timestamp。当事务的timestamp小于记录的timestamp时（不能读到”未来的”数据），需要abort后重新执行。假设记录X上标记了读写两个timestamp：WTS(X)和RTS(X)，事务的timestamp为TTS，可见性判断如下：
读：
- TTS < WTS(X)：该对象对该事务不可见，abort事务，取一个新timestamp重新开始。
- TTS > WTS(X)：该对象对事务可见，更新RTS(X) = max(TTS,RTS(X))。为了满足repeatable read，事务复制X的值。
- 为了防止读到脏数据，可以在记录上做特殊标记，读请求需等待事务提交后再去读。
写：
- TTS < WTS(X) || TTS < RTS(X)：abort事务，重新开始。
- TTS > WTS(X) && TTS > RTS(X)：事务更新X，WTS(X) = TTS。
这里之所以要求TTS > RTS(X)，是为了防止如下情况：读请求的时间戳为rts，已经读过X，时间戳设为RTS(X)=rts，如果新事务的TTS < RTS(X)，并且更新成功，则rts读请求再来读一次就看到新的更改了，违反了repeatable read，因此这是为了避免读写冲突。记录上存储了最后的读写时间，可以保证conflict serializable
这种方式也能避免write skew，例如：初始状态，X和Y两条记录，X=-3，Y=5，X+Y >0，RTS(X)=RTS(Y)=WTS(X)=WTS(Y)=0。事务T1的时间戳为TTS1=1，事务T2的时间戳TTS2=2。
它缺陷包括：
- 长事务容易饿死，因为长事务的timestamp偏小，大概率会在执行一段时间后读到更新的数据，导致abort。
- 读操作也会产生写（写RTS）。
04基于Validation（OCC）的并发控制
执行过程中，每个事务维护自己的写操作（Basic T/O在事务执行过程中写就将数据写入DB）和相应的RTS/WTS，提交时判断自己的更改是否和数据库中已存在的数据冲突，如果不冲突才写入DB。OCC分为三个阶段：
- Read & Write Phase：即读写阶段，事务维护读的结果和即将提交的更改，以及写入记录的RTS和WTS。
- Validation Phase：检查事务是否与数据库中的数据冲突。
- Write Phase：不冲突就写入，冲突就abort,restart。
Read & Write Phase结束，进入Validation Phase相当于事务准备完成，进入提交阶段了，进入Validation Phase的时间被选做记录行的时间戳，来定序。不用事务开始时间是因为：事务执行时间可能较长，导致后开始的事务可能先提交，这会加大事务冲突的概率，较小时间戳的事务后写入数据库，肯定会abort。
Validation过程
假设当前只有两个事务T1和T2，并修改了相同数据行，T1的时间戳 < T2的时间戳（即validation顺序：T1 < T2，对用户而言，T1先发生于T2），则有如下情况：
（1）T1在validate阶段，T2还在Read & Write Phase。此时只要T1和T2已经发生的读写没有冲突，就可以提交。
- 如果WS(T1) ∩ (RS(T2) ∪ WS(T2)) = ∅，说明T2和T1写的记录无冲突，validation通过，可以写入。
- 否则，T2与T1之间存在读写冲突或写写冲突，T1需要回滚。读写冲突：T2读到了T1写之前的版本，T1提交后，它可能读到T1写的版本，不可重复读。写写冲突：T2有可能在旧版本基础上更新，再次写入，造成T1的更新丢失。
（2）T1完成validate阶段，进入write阶段直到提交完成，这已经是不可逆的了。T2在T1进入write phase之前的读写，肯定和T1的操作不冲突（因为T1 validation通过了）。T2之后继续的读写操作，有可能冲突与T1要提交的操作，因此T2进入validate阶段：
- 如果WS(T1) ∩ RS(T2)= ∅，说明T2没读到T1写的记录，validation通过，T2可以写入。（为什么不验证WS(T2)了呢？WS(T1)已经提交了，且它的时间戳小于WS(T2)，WS(T2)里之前的一部分肯定没有冲突，之后的一部分，因为没有读过T1的写入的对象，写进去也没问题，不会覆盖WS（T1）的写）
- 否则，T2与T1之间存在读写冲突和写写冲突，T2需要回滚。读写冲突：T2读到了T1写之前的版本，T1提交后，它可能读到T1写的版本，不可重复读。写写冲突：T2有可能在旧版本基础上更新，再次写入，造成T1的更新丢失。
05基于MVCC的并发控制
数据库维护了一条记录的多个物理版本。事务写入时，创建写入数据的新版本，读请求依据事务/语句开始时的快照信息，获取当时已经存在的最新版本数据。它带来的最直接的好处是：写不阻塞读，读也不阻塞写，读请求永远不会因此冲突失败（例如单版本T/O）或者等待（例如单版本2PL）。对数据库请求来说，读请求往往多于写请求。主流的数据库几乎都采用了这项优化技术。
MVCC是读和写请求的优化技术，没有完全解决数据库并发问题，它需要与前述的几种并发控制技术组合，才能提供完整的并发控制能力。常见的并发控制技术种类包括：MV-2PL，MV-T/O和MV-OCC，它们的特点如下表：
MVCC还有两个关键点需要考虑：多版本数据的存储和多余多版本数据的回收。
多版本数据存储方式，大致可以分为两类：
（1）Append only的方式，新旧版本存储在同一个表空间，例如基于LSM-Tree的存储引擎。
（2）主表空间记录最新版本数据，前镜像记录在其它表空间或数据段，例如InnoDB的多版本信息记录在undo log。多版本数据回收又称为垃圾回收（GC），那些没有机会再被任何读请求获取的旧版本记录，应该被及时删除。
06总结
本文依据冲突处理的时机（乐观程度），依次介绍了基于锁（在事务开始前预防冲突）、基于T/O（在事务执行中判断冲突）和基于Validation（在事务提交时验证冲突）的事务并发控制机制。
不同的实现适用于不同的workload，并发冲突小的workload，当然适合更乐观的并发控制方式。而MVCC可以解决只读事务和读写事务之间相互阻塞的问题，提高了事务的并发读，被大多数主流数据库系统采用。
