[DB] 并发控制
并发控制simultaneous concurrency
并发控制概述
事务是并发控制地基本单位，为了保证事务地隔离性和一致性，DBMS需要对并发操作进行正确的调度。
并发操作带来的数据不一致性包括丢失数据、不可重复读、读脏数据。
丢失数据lost update：两个事务读入同一数据并修改，一个提交的结果破坏了另一个提交的结果，导致修改被丢失。
不可重复读non-repeatable read：指事务T1读取数据后，事务T2执行更新操作，使T无法再现前一次读取结果。具体分三种：
- T1读某一数据后，T2修改，T1再读，得到不同值。
- T1读某一数据后，T2删除，T1再读，数据消失。
- T1读某一数据后，T2插入，T1再读，多了数据。
后两种不可重复读有时也被称为幻影(phamtom row)现象。
读脏数据dirty read：T1修改某一数据并写回磁盘，T2读该数据，T1 rollback，T2读到的数据与数据库中的数据不一致。
并发控制的主要技术：封锁(locking)，时间戳(timestamp)，乐观控制法(optimistic scheduler)，多版本并发控制(multi-version concurrency control,MVCC)
封锁
事务对某个数据进行加锁，在其释放前，其他食物不能更新此数据对象。
基本的封锁类型有两种：
- 排他锁(写锁)-X锁，释放前只允许自己读写，且禁止其他事务加任何类型的锁。
- 共享锁(读锁)-S锁 ，释放前自己也只能读，其他事务可以读，可以加同样的S锁。
封锁协议locking protocol
封锁协议：规定合适申请X锁或S锁、持锁时间、何时释放等。
一级封锁协议：事务T在修改数据R之前必须先对其加X锁，直到事务结束才释放。事务结束包括COMMIT, ROLLBACK。
一级封锁协议中，如果仅仅是读数据而不是对其进行修改，是不需要加锁的，所以它**不能保证 可重复读 和 不读脏数据。
二级封锁协议：在一级封锁协议的基础上，增加事务T在读取数据R之前必须先对其加S锁，读完后即可释放S锁。
由于读完即可释放S锁，所以他不能保证 可重复读。
三级封锁协议：在一级封锁协议的基础上增加 事务T在读取数据R之前必须先对其加S锁，直到该事务结束之后才释放。
可解决不可重复读、读脏数据问题。
三级协议的主要区别在于什么操作需要申请封锁，以及合适释放锁。
活锁和死锁
活锁 ：T1封锁数据R，T2请求封锁R，后T3也请求封锁R，T1释放R后首先批准了T3的请求，也就是说T2被插队了，如果T2一直被插队，那么称之为活锁。
解决方法：先来先服务。
死锁 ：循环等待。
死锁的预防：
一次封锁法：要求每个事务必须一次将所有要使用的数据全部加锁，否则就不能继续执行。
缺陷：1.扩大封锁范围，降低并发度；2.很难事先确定需要封锁的数据对象。
顺序封锁法：预先对数据对象规定一个封锁顺序，所有事务都按照这个顺序实施封锁。
缺陷：1.数据库系统中封锁的数据对象极多，并且不断变化，要维护这样的资源的封锁顺序非常困难，成本很高；2.很难事先确定要封锁那些对象，一次也就很难按规定的顺序去施加封锁。
死锁的诊断与解除 ：
- 超时法：如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。
- 等待图法：用一个有向图G=(T, U)表示事务的情况，动态地反映所有事务地等待情况，周期性生成事务等待图，并进行检测，如果发现图中存在回路，则表示系统中出现了死锁。
解除死锁：选择一个处理死锁代价最小的事务，将其撤销，释放此事务持有地所有锁。
并发调度地可串行性
可串行化调度：多个事务地并发执行是正确的，当且仅当其结果与按某一次序串行执行这些事务地结果相同时，称这种调度策略为可串行化serializable的。
可串行性是并发实物正确调度的准则。
冲突化可串行调度
冲突操作是指不同事务对同一数据的读写操作和写写操作。而其他操作是不冲突操作。
通过交换两个事务不冲突操作的次序得到另一个调度Sc‘，如果Sc’是串行的，则称调度Sc为冲突可串行化的调度。因此可以用这种方法来判断一个调度是否是冲突可串行化的。
冲突可串行化调度是可串行化调度的充分条件，不是必要条件。
两段锁协议 TwoPhase Locking
所谓2PL协议是指所有事务必须分两个阶段对数据项加锁和解锁：
- 在对任何数据进行读、写操作之前，首先要申请并获得对该数据的封锁
- 在释放一个锁之后，事务不再申请和获得任何其他封锁
事务分为两个阶段，第一阶段是获得封锁，也成为扩展阶段，此阶段可以申请获得任何数据项上的任何类型的锁，但是不能释放任何锁；第二阶段是释放封锁，也称为收缩阶段，该阶段事务可以释放任何数据项上的任何类型的锁，但是不能再申请任何锁。
若并发执行的所有事务均遵循两段锁协议，则对这些事务的任何并发调度都是可串行化的。
严格两段锁协议：除要求满足两段锁协议规定外，还要求事务的排它锁必须在事务提交之后释放
强两段锁协议：除要求满足两段锁协议规定外，还要求事务的所有锁都必须在事务提交之后释放
事务遵守两段锁协议是可串行化调度的充分条件，而不是必要条件。
封锁的粒度 Granularity
封锁对象的大小称为封锁的粒度，封锁粒度与系统的并发度和并发控制的开销密切相关。
封锁的粒度越大，数据库所能封锁的单元就越少，并发度越小，系统开销越小。
多粒度封锁：一个系统中同时支持多种封锁粒度供不同的事务选择。
引入多粒度树的概念，三级粒度树(数据库，关系，元组)，四级粒度树(数据库，数据分区，数据文件，数据记录)。多粒度封锁协议允许多粒度树中的每个结点被独立的加锁。对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁。
显式封锁：应事务要求直接加到数据对象上的锁。
隐式封锁：该数据对象没有被独立加锁，而是由于其上级结点加锁而使该数据对象加上了锁。
一般地，对于某个数据对象加锁，系统要检查该数据对象上有无显式封锁与之冲突，还要检查上级结点传下来的隐式封锁是否冲突，以及传给下级结点的封锁是否冲突，这样的检查方法效率很低，因此引入意向锁。
意向锁
意向锁：如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。
三种常用的意向锁，意向共享锁(Intent Share Lock，IS锁)，意向排他锁(Intent Exclusive Lock, IX锁)，意向共享排他锁(Share Intent Exclusive Lock, SIX锁)
IS锁：如果对一个数据对象加IS锁，表示它的后裔结点拟加S锁。
例如，事务T1要对R1中某个元组加S锁，则要首先对关系R1和数据库加IS锁
IX锁：如果对一个数据对象加IX锁，表示它的后裔结点拟加X锁。
SIX锁：如果对一个对象加SIX锁，表示对它加S锁，再加IX锁，即SIX=S+IX。
课后题：
正确的调度->可串行化的调度->遵守两阶段封锁的调度->串行调度