事务与并发控制
简单介绍一下事务？
事务作为数据库执行过程中的一个逻辑单位，可以表明一组操作，这一组操作要么一起成功，要么全部回滚，并且事务之间一定程度上相互隔离，互不影响。事务具有事务的四大特性 ACID，分别为原子性 一致性 隔离性与持久性
介绍一下事务的四大特性
事务的四大特性分别为原子性、一致性、隔离性与持久性
对于原子性，则事务本身作为一个整体，要么全部成功执行，要么全部失败回滚，不存在执行成功一半的中间态。
一致性表明数据库在事务执行前和执行后，数据库的状态必须满足预定的一致性规则，即数据库只能从一种状态转换为另外一种一致性状态，最简单的例子即为银行转账，只有转账前与转账后的两种一致性状态，不存在一人转出而另一人未收到的中间状态。此外一致性分为数据库一致性和事务一致性，数据库只保证数据库一致性，就像上面所说的那样，而事务一致性则更是一种逻辑关系，需要操作人员去手动约束
此外 数据库的一致性应当与分布式系统当中的一致性的概念相区分，分布式当中的一致性指的是在多个节点上数据保持一致的状态，比如其中最严格的线性一致性就要求对外需要表现成单机节点，如果一次写入完成那么后续就一定要能够读取到数据
隔离型：并发执行的多个事务之间应当隔离，使每个事务感觉在独立的操作数据库，防止事务之间的相互干扰与数据污染
持久性：持久性表明一旦事务提交，那么其做出的更改应当为永久性的
说一下事务的隔离级别
四种隔离级别的差别主要聚焦于读操作上，对于写操作，为了保证数据库一致性，只有写入的锁只有数据提交时才能够释放，如果中途释放锁，写入的操作结果可能会被其他的覆盖，从而违反了数据库一致性。单独看写锁的话，都是采用了严格两阶段锁的策略，保证一致性，同时避免级联中止。
READ UNCOMMITTED
最宽松的隔离级别，根据上表可以看到脏读 不可重复读 幻读都会发生
在实现上读操作不需要加锁，写操作和其他的一致，因此所有读相关的锁都不支持，如果想尝试加[S,IS,SIX]，都会抛出异常。由于只支持写锁，在shrinking阶段，任何加锁操作都是不允许的，会抛出异常。
因此并不保证读取到的数据一定是提交的数据，由于并没有加读锁和其他的事务进行互斥，其他的事务一旦写入之后就可以被读取，因此当读取到之后，如果写入数据的事务中止回滚，那么读取到的数据就变成了脏数据产生脏读。
READ COMMITTED
相比于读未提交解决了脏读的问题，但是依旧会出现不可重复读和幻读
在实现上读操作需要在Table上加IS，在Row上加S，并且当完成一次读取之后即可将锁释放，无需等待事务的提交。释放S锁并不会导致事务从growing向shrinking转变。
由于通过S锁进行互斥，从而保证那些正在写入的事务在提交前不应被读取到，能够读取到的数据一定是提交之后稳定写入的数据。
REPEATABLE READ
在读提交的基础上又解决了不可重复读的问题，存在幻读。
实现上加锁策略和READ COMMITTED并没有区别，但是在释放锁上读写锁全部采用严格两阶段锁的策略，此次事务会一直持有读锁，从而中途不可能被其他的事务重新写入更新，在一次事务当中读取的数据全部为一致的。
shrinking阶段不允许添加任何的锁，释放S X锁就会向shrinking进行转变。
可串行化
最严格的隔离级别，简单来说就是在该隔离级别下，事务的执行可以等价成一次不存在并发的串行执行。最简单的判断是否为可串行化的方法就是交换一系列不冲突的指令，从而看原本的事务调度是否可以被分为两个在时间上完全错开的串行调度，简单用读写来表示，一次通过交换或重拍转换成串行结果如下：
在15-445当中没有实现该隔离级别，不过在6.830当中实现过，就简单说一下6.830的实现方式
其相比于REPEATABLE READ，避免的幻读的发生，最简单的实现手段是加表级别的锁，从而保证在读的时候没有其他的事务能够插入新的数据，这样虽然可以保证各个方面的安全，脏读 不可重复读 幻读全部解决，但是带来的问题就是并发度很低，如果一张表上存在写入的事务，那么就没有并发度了。
如何判断事务之间为可串行化
最简单的方式即为像上面那样去交换两条不冲突的指令，如果能够通过交换的形式把两个事务的指令在时间顺序上完全隔开，那么就是满足可串行化的。
此外还有一种方法是，对于存在冲突的两个指令，建立一条边，从时间较早的指向时间较晚的，如果在之间出现了环，那么就是不可串行化调度的
并发控制手段都有哪些
并发控制协议是DBMS如何决定在多事务时的正确交叉执行
- 悲观锁：悲观锁：对于同一个数据的并发操作，悲观锁认为自己在使用数据的时候一定有别的线程来修改数据，因此在获取数据的时候会先加锁，确保数据不会被别的线程修改。Java中，synchronized关键字和Lock的实现类都是悲观锁。而在MySQL当中，排他锁即为悲观锁
- 乐观锁：乐观锁认为自己在使用数据时不会有别的线程修改数据，假设并发冲突很罕见，所以不会添加锁，只是在更新数据的时候去判断之前有没有别的线程更新了这个数据（具体方法可以使用版本号机制和CAS算法）。如果这个数据没有被更新，当前线程将自己修改的数据成功写入。如果数据已经被其他线程更新，则根据不同的实现方式执行不同的操作：重试或者报异常。
锁(Lock)和锁存器(Latch)当中有什么区别
锁的概念更加属于数据库的抽象逻辑层面的，意在保护数据库的逻辑结构 ，如tuple或者 表等
锁存器意在保护数据库的物理结构 如真实的数据结构等，如使用锁存器保证buffer pool的线程安全，来解决一个B+树的并发问题，所讨论的就是使用锁存器来对那个树的节点来进行加锁保护。对于锁存器来说，线程为其的竞争或者持有者，而锁则是以事务为单位
介绍一下两阶段锁协议
考虑这样一种情况，一个简单的银行转账的例子，事务T1负责完成转账，其获取锁之后修改了A的余额，释放锁，正准备获取B的锁修改B的余额时，事务T2获取到了AB的锁，读取数据，结果读取到了一种中间态，违反了事务的一致性。
这种问题可以通过引入两阶段锁协议进行解决，即将加锁和释放锁过程划分为两个阶段，第一个阶段称为growing，只进行加锁，第二阶段称为shrinking，只进行解锁操作。
引入两阶段锁协议之后，在看上述问题，T1修改完A之后不释放A的锁，之后尝试对B上锁，此时出现两种情况，如果T2还未对B上锁，那么顺利执行，不会违反一致性，而如果B上锁，那么就会造成死锁，需要通过死锁检测来进行解决
两阶段锁协议会引入什么问题？
还是以银行转账为例，T1首先完成对A和B的更新，更新后的数据为A1B1之后进入shrinking阶段，释放了AB的锁，此时事务T2在A1B1的基础上进行修改，产生副本A2B2，但是之后，事务T1由于某些问题需要中止进行回滚，其产生的数据A1B1就成了脏数据，从而在基础上进行修改的A2B2也同样无效，应当回滚，这就产生了级联中止，即一个事务的中止导致了其他事务的中止
此外，就像上面的例子那样，两阶段锁协议同样还会引入死锁的问题。
级联中止有什么解决方案？
一种解决方案为将两阶段锁协议升级为严格两阶段锁协议，即growing阶段不变，而shrinking阶段改变为只有事务提交时才能够释放锁，而在上述的例子当中，事务T2就无法在T1的基础上进行修改得到A2B2，只会读取到T1提交或者中止后的结果，从而避免的级联中止
死锁的产生条件
移步OS
死锁的解决条件
主要有破除和预防两个方案来解决死锁问题
破除：最简单的方式即为超时等待，在获取锁是通过一个自旋锁的方式，在自旋当中进行检查，如果超出了规定的时间就放弃获取锁，并将事务中止。
此外，还可以通过构建等待图 + DFS的形式来进行解决，即如果一个事务在等待另外一个事务上的锁时，就添加一条边，从等待者指向资源持有者，之后通过DFS的方式进行搜索，而如果在等待图当中出现了环，那么就证明出现了死锁，此时需要挑选一个受害者(victim)，将其持有的锁释放，并且对事务进行回滚
对于死锁的处理，可以通过锁的合理分配，来达到提前避免，首先假设时间较久的时间戳的事务拥有较高的优先级，则通常有以下两种策略：
Wait-Die（old waits for young）
- 如果申请锁的比现在持有锁的拥有更高的优先级，那么申请锁的继续等待，直到持有锁的释放锁
- 其他情况申请的事务放弃（ aborts）
Wound-Wait(young wait for old)
- 如果申请锁的比现在持有锁的拥有更高的优先级，那么持有锁的放弃（aborts），然后释放锁
- 其他情况申请锁的等待
在死锁破除当中如何选择Victim
牺牲者的选取通常由一下几个因素进行综合考虑：
- 年龄，即事务创建的时间戳
- 任务，比如如果一个事务需要执行大量的查询，那么最好把他当作牺牲者（最好不要把他当作牺牲者）具体是否选取取决于不同的数据库
- 持有的锁的数量
- 回滚时关联的其他的事务的多少（级联终止）强限制两阶段锁并不是必须的，有的系统采用普通的两阶段锁协议，锁定然后级联中止的处理方式
数据库当中常见的锁级别
在基础的读写锁模型上，为了提高并发度，在数据库当中通常还支持意向锁来提高并发度和便于锁的管理
意向锁是一种不与行级锁冲突表级锁，因此可以不去检查底层的节点（tuple）是否存在冲突就去对更高一级别的节点去加锁（Table）即表明我对这张表的某些行有读取或者写入的意向
共享意向排他锁（Shared Intention Exclusive Lock）：= S-LOCK + IX-LOCK，S-LOCK这一属性表明要去读取表的所有的记录，其他的事务就不会并发的更新任意的记录，IX-LOCK让其他事务知道我们要更新目标表的一部分记录，其他事务就不会并发的读取所有的记录，这里只会阻止对表的整体的操作，如SeqScan(表级S锁)，和全表更新(表级X锁)，对于部分更新，则在表级别上添加IX锁，不会和SIX发生冲突，一定程度提高并发度
而在加锁时，首先需要对表级别加意向锁，如IS IX SIX，之后再对行级别加读写锁 S X，在加锁时首先需要检查在Table上是否发生冲突，如果发生冲突则直接阻塞，当获取到Table上的锁之后，再判断row是否存在冲突，而在释放锁时，行锁可以按需释放，表锁需要保证在行锁全部释放完毕后才能释放
说一说时间戳排序并发控制
先介绍一下基本时间戳顺序协议
首先通过时间戳来对事务进行标记，同时对于一个tuple 需要记录其 W-TS和R-TS，即最后一次对其进行读写操作的事务的时间戳，用于在一个事务要对一个tuple进行读写操作时判断是否有其他事务会和它产生冲突
在基本时间戳顺序协议中，时间戳记录的是该事务开始时的时间，即通过BEGIN关键字声明开启事务时旧分配一个时间戳，但是DBMS本身还是并发的，因此可能会出现后续的事务在较早的事务之前执行，此时就可能存在问题，可能要考虑将较早的事务给撤销，并重新分配时间戳重新执行
当一个事务访问到一个tuple时，发现TS < W-TS ，则证明未来的一次写入覆盖了目前正在读的数值，即出现了脏读问题，读取到的是旧值，需要终止
对于读写，有以下的规则：
读：
如果TS($T_i$) < W-TS(X),则违反了时间戳顺序，读到了旧的值，该事务需要重启并分配新的时间戳
否则：
- 允许事务T去读取tuple X
- 更新R-TS（X）为$max(R-TS(X),TS(T_i))$
- 生成一个本地副本用于该事务后续的重复读（如果再去读最新的数据则会产生两次读取不一致的不可重复读的问题）
写：
如果$TS(T_i)<R-TS(X) or TS(T_i) < W-TS(X)$ 放弃$T_i$并重启$T_i$
- $TS(T_i)<R-TS(X)$会导致后续读取操作读取不到此次的写入
- $TS(T_i) < W-TS(X)$会导致此次的写入无意义
否则：
- 允许事务$T_i$去写入，并且更新W-TS(X)
- 生成一个本地副本用于可重复读
对于写操作，还可以通过Thomas Write Rule进行优化：
- $TS(T_i) <R-TS(X)$:放弃并重启$T_i$（与原本一致）
- $TS(T_i) <W-TS(X)$:忽略此次写入，并允许事务继续执行
- 其他情况则未违反协议，允许$T_i$写入，并更新$W-TS(X)$
虽然本质上违反了协议，但是当前此次写后续会被覆盖掉，因此可以直接进行忽略
总的来说，基本时间戳顺序协议的精髓为当一个事务创建时分配一个时间戳，由于事务的原子性，将事务当中所有的指令的发生时间全部集中于begin的这一时间戳上，之后如果有违反时间顺序的，事务则会中止回滚，并尝试重新开启事务，如读取时发现有未来的事务已经对其进行了写入。
说一说乐观并发控制
基本思想也为将事务的所有指令全部视为在一个时间点上发生
DBMS给每个事务均分配一个私有的工作空间：
- 进行读操作时将读的结果copy到私有的工作空间当中
- 修改操作则针对于工作空间来进行修改
当一个事务准备提交时，再将工作空间和全局Database进行比较，查看是否存在冲突，这个过程称为Validation
如果不存在冲突，则将工作空间的结果应用到全局Database当中
阶段
- Read Phase：当事务进行读写操作时，将所有访问到的数据（tuple）读取到私有的工作空间后，再工作空间上进行操作
- Validation Phase：在事务commit前验证是否和其他事务存在冲突
- Write Phase：如果不存在冲突，则将私有工作空间的做的更改应用到全局数据库上，否则放弃并重启事务
在还未进行validate时，副本的时间戳设置为∞，如果进行了写操作，那么此时私有空间中W-TS即为∞
在验证节点才会获取一个时间戳，因此将验证的时间操作视为事务真正的开始时间，A先于B进行验证，则认为A先于B开启事务
悲观并发控制和乐观并发控制各自的应用场景
来自GPT
悲观并发控制（Pessimistic Concurrency Control，简称 PCC）和乐观并发控制（Optimistic Concurrency Control，简称 OCC）是两种不同的并发控制策略，它们在不同的应用场景下有各自的优势。悲观并发控制采用一种悲观的思想，即认为在多用户并发环境下，数据冲突的可能性较高。因此，在读写数据时会对数据加锁，以确保数据的独占访问。悲观并发控制适用于数据竞争激烈的场景，以及发生并发冲突时使用锁保护数据的成本要低于回滚事务的成本的环境中在这种场景下，悲观锁可以有效地保护数据的一致性和完整性。
乐观并发控制则采用一种乐观的思想，即认为在多用户并发环境下，数据冲突的可能性较低。因此，在读写数据时不会对数据加锁，而是在提交数据更新之前检查是否有其他事务修改了数据。如果发现冲突，则回滚事务并通知用户，乐观并发控制适用于数据争用不大，数据冲突较少的场景下在这种场景下，乐观锁可以提高系统的整体吞吐量，因为它避免了锁的开销。总的来说，乐观锁适用于写操作较少的情况下（多读场景），即冲突真的很少发生的时候而悲观锁适用于多写的场景，因为在这种情况下，冲突较容易发生，使用悲观锁可以避免不断的重试操作，从而提高性能。
说一说幻读
幻读是在事务并发执行时可能出现的一种现象，它指的是在一个事务内部，多次执行相同的查询操作，但在不同的查询中返回的行数却不一致。通常是由于其他事务并发地插入或删除了符合查询条件的数据所导致的。
为了解决幻读问题，可以采取以下几种方案：
- 使用间隙锁：在某些数据库系统中，可以使用间隙锁（Gap Lock）来锁定一个范围内的空间，以阻止其他事务在该范围内插入新的数据。这可以有效地解决幻读问题。
- 版本控制：使用版本号或时间戳来跟踪数据的变化。在读取操作时，根据事务开始时的版本号或时间戳来确定读取的数据快照，以保证一致性。可以通过MVCC（多版本并发控制）等机制来实现。
- 提升隔离级别：将隔离级别提升到可串行化（Serializable）级别。可串行化级别能够解决幻读问题，但也会牺牲一定的并发性能，因为它会对并发操作进行严格的序列化。
MVCC
来自 GPT
MVCC（Multi-Version Concurrency Control，多版本并发控制）是一种并发控制方法，主要用于数据库管理系统中实现对数据库的并发访问，在编程语言中实现事务内存MVCC通过保存数据的历史版本，根据比较数据的版本号来决定数据的是否显示，在不需要加读锁的情况就能达到事务的隔离效果，最终可以在读取数据的时候可以同时进行修改，修改数据时候可以同时读取，极大的提升了事务的并发性能。在InnoDB存储引擎中，MVCC是通过在每行记录后面保存两个隐藏的列来实现的。这两个列，一个保存了行的创建时间，一个保存了行的过期时间（或删除时间），当然存储的并不是实际的时间值，而是系统版本号。每开始一个新的事务，系统版本号都会自动递增。事务开始时刻的系统版本号会作为事务的版本号，用来和查询到的每行记录的版本号进行比较。MVCC的优点包括：1. 支持并发读取：多个事务可以同时读取数据库中的数据，提高了并发性能。
- 避免了锁竞争：在读取过程中，不需要对记录进行加锁，因此避免了锁竞争的情况，提高了并发性能。
- 保证数据一致性：MVCC通过版本控制，可以保证在并发读取的情况下，数据的一致性。
然而，MVCC也存在一些局限性：1. 增加存储空间：为了实现版本控制，MVCC在每条记录上都需要添加时间戳，因此会增加存储空间。
- 无法解决幻读问题：虽然MVCC通过版本控制可以避免锁竞争，但是在一些情况下，仍然会出现幻读的问题
- 无法实现一些锁的功能：例如 SELECT … FOR UPDATE、SELECT … LOCK IN SHARE MODE 等锁的功能，无法在 MVCC 中实现。
总之，MVCC是一种基于版本控制的并发控制机制，通过版本控制和时间戳比较来保证数据的一致性和并发性能，但也存在一些局限性。在数据库中，可以采用MVCC与悲观锁或乐观锁的组合方式来最大程度地提高数据库并发性能，并解决读写冲突和写写冲突导致的问题。
MVCC与 PCC和 OCC之间有什么联系
MVCC主要解决了以下问题：1. 读写之间的阻塞问题：通过MVCC可以让读写互相不阻塞，即读不阻塞写，写不阻塞读，从而提升事务并发处理能力
- 降低死锁的概率：因为InnoDB的MVCC采用了乐观锁的方式，读取数据时并不需要加锁，对于写操作，也只锁定必要的行
MVCC可以解决读-写冲突，但不能解决写-写冲突为了解决写-写冲突，可以将MVCC与其他并发控制方法结合使用，例如：
MVCC + 悲观锁：MVCC解决读写冲突，悲观锁解决写写冲突
MVCC + 乐观锁：MVCC解决读写冲突，乐观锁解决写写冲突