数据库并发控制
并发控制概述
事务并发执行带来的问题
-
存取不正确的数据
-
破坏事务的隔离性和数据库的一致性
事务并发的问题：不正确、隔离性、一致性（修改丢失、不可重复读、读脏数据）
三种数据不一致性
https://www.51cto.com/article/697668.html
- 丢失修改：指的是事务A和实物B读入同一个数据并修改，事务B的提交结果破坏了事务A提交的结果，导致事务A的修改被丢失。（写丢失，先后读）
- 不可重复读：指的是事务A读取数据后，事务B执行更新操作，使事务A无法再现前一次读取的结果。（不同、消失、出现、幻影）
三种不可重复读：
1.更新了 2.删掉了 3.增加了
2和3成为幻影现象
-
读脏数据：事务B修改某一数据，并将其写回磁盘。事务A读取同一数据后，事务B由于某种原因撤消已修改过的数据恢复原值（暗示事物B未提交），事务A读到的数据就与数据库中的数据不一致，是不正确的数据，又称为“脏”数据。
读未提交(有脏读问题)、读已提交(有不可重复读的问题)、可重复读(有幻读的问题)
封锁协议
封锁
封锁就是在事务T在对某个数据对象操作之前，先想系统发出请求，对其加锁。在释放锁之前其他事务不能更新此数据对象。
事务对数据对象操作前，申请加锁
基本封锁类型（重要）
- 排他锁（X锁）：只允许T读取和修改A，其他任何事务都不能再对A加任何类型的锁，直到T释放锁
- 共享锁（S锁）：若事务T对数据对象A加上S锁，则其他事务只能再对A加S锁，而不能加X锁，直到T释放A上的S锁。
封锁协议：三级封锁协议（十分重要）
1级封锁协议
事务在修改数据之前必须对其加X锁，直到事务结束才释放（写锁）
1级协议可以防止数据丢失修改，但是如果是读数据的话，是不需要加锁的，所以它不能保证可重复读和不读“脏”数据。
意思就是说其实这个锁只是防止别人同时修改，但是你在修改的时候别人还是可以读的。所以才会出现读取脏数据和不可重复读的问题。
2级封锁协议
在1级的基础上，事务T在读取数据前必须先加S锁，读取完成之后释放。（读锁）
2级协议可以防止读取脏数据
其实就是在读数据的过程禁止修改。
3级封锁协议
在1级的基础上，事务T在读取数据R之前必须加S锁，直到事务结束才释放,3级就可以防止不可重复读了
说白了就是不能在别人查询的周期中修改别人可能需要的数据。
活锁和死锁据查询语言DQL
封锁可能会带来活锁或者死锁的问题。
避免活锁：先来先服务
活锁：指事物1可以使用资源，但它让其他事物先使用资源；事物2可以使用资源，但它也让其他事物先使用资源，于是两者一直谦让，都无法使用资源。
死锁预防：
- 一次封锁法：一次性将需要使用的数据全部加锁
- 顺序封锁法：规定封锁顺序，按照顺序执行封锁
操作系统上的预防死锁策略其实并不适合数据库，更广泛采用的方法是诊断并解除死锁。
检测死锁的方法：
- 超时法：实现简单，但是可能误判或者不能即使发现
- 等待图法：用节点表示正在运行的事务，用边来表示事务的等待情况。如果T1等待T2，则连一个从T1到T2的有向边。如果出现回路，则出现了死锁。
死锁解除
选择一个代价最小的事务，将其撤销，释放这个事务的所有锁。
一般选择最迟交付的事务、获得锁最少的事务、回退代价最小的事务。
封锁粒度（应该不是很重点）
https://www.cnblogs.com/fangzhiyou/p/13100451.html
封锁的对象可大可小，封锁对象的大小就是封锁的粒度。
多粒度封锁
选择封锁粒度的原则：
- 需要处理多个关系的大量元组的用户事务：以数据库为封锁单位；
- 需要处理大量元组的用户事务：以关系为封锁单元；
- 只处理少量元组的用户事务：以元组为封锁单位
用树形结构来表示多级封锁粒度
对一个节点加锁意味着其后裔节点也加锁，由此分为显式封锁和隐式封锁
- 显式封锁：直接加到数据对象上的锁
- 隐式封锁：由于上级节点加锁而使该数据对象加了锁
加锁时系统检查的内容
- 对该对象：有没有和显式封锁冲突
- 对上级节点：看是否与隐式封锁冲突
- 对下级节点：看有没有和下级节点的显示封锁冲突
意向锁：提高加锁检查效率
-
对任一节点加基本锁，必须先对其上层节点加意向锁
-
对任何一个节点加意向锁，说明该节点下层节点正在被加锁
IS锁
如果对一个数据对象加IS锁，表示它的后裔结点拟（意向）加 S锁。例如，要对某个元组加 S锁，则要首先对关系和数据库加 IS锁。
IX锁
如果对一个数据对象加 IX锁，表示它的后裔结点拟（意向）加 X锁。例如，要对某个元组加 X锁，则要首先对关系和数据库加 IX锁。
SIX锁
如果对一个数据对象加 SIX锁，表示对它加 S锁，再加IX锁，即 SIX=S+IX。例如对某个表加 SIX锁，则表示该事务要读整个表（所以要对该表加 S锁），同时会更新个别元组（所以要对该表加 IX锁）。
相容矩阵
并发调度的可串行性
可串行化指的是并行事务的调度运行结果等价于事务串行运行的结果
冲突可串行化，通过相邻不冲突操作将调度转化为串行调度，对不同的数据读写、或者相同的数据只读均为非冲突操作
并发调度中不同的调度可能会产生不一样的执行结果，当并发的时候必须保证并行操作的正确性。
选择合适的串行调度顺序保证并发调度的正确性
几个事务的并行执行是正确的，当且仅当其结果与按某一次序串行地执行它们时的结果相同。这种并行调度策略称为可串行化调度
冲突可串行化和事务优先图：https://zhuanlan.zhihu.com/p/516557516
来自不同事务中两个操作 I、 J，只有它们操作的数据项为同一个或有共同部分且至少有一个操作为写操作时，它们的相对顺序才重要。这种情况，我们称 I 和 J 冲突。
调度 S1 中任意两个相邻的不冲突操作调换顺序就可以得到一个的调度 S2，如果在 S2 中继续这种调换，则可以得到更多的调度，由于只是调换了不冲突的相邻操作，对执行结果没有影响，所以这些经过调换相邻非冲突操作得到的调度都是冲突等价（conflict equivalent）的。
串行执行事务得到的 schedule 称为串行 schedule。如果一个 schedule 和某个串行 schedule 冲突等价，则称该 schedule 是冲突可串行化（conflict serializable）的。
判断是否冲突可串行化：相邻的非冲突操作可以调换，保持冲突操作的相对顺序不变即可，使用状态图，节点为事务，如果事务a操作i和事务b操作j冲突，前面的事务指向后面的事务。如果不成环，说明冲突可串行化。
两段锁协议（2PL）（重要）
- 在对任何数据进行读、写操作之前，事务首先要获得对该数据的封锁。（拓展阶段）
- 在释放一个封锁之后，事务不再获得任何其他封锁。（收缩阶段）
也就是说，如果你要释放了，你之后就不能再申请了，所以你必须在释放之前申请完所有你需要的。保证并发操作调度正确
遵循了2PL，则对事务的所有并行调度策略都是可以串行化的，其并行执行的结果一定是正确的。ff·
事务遵守2PL只是可串行的充分条件，不是必要条件。
https://baike.baidu.com/item/%E4%B8%A4%E6%AE%B5%E9%94%81%E5%8D%8F%E8%AE%AE/1008117
区分两段锁协议和一次性加锁，一次性加锁是两段锁协议特例，一定无死锁，两段锁协议可能死锁
串行可调度和冲突串行可调度
第11章 并发控制
数据库并发控制->防止不一致性->三种不一致性->封锁->三种封锁->死锁和活锁->封锁粒度->意向锁
可串行调度->冲突可串行->两段锁协议
1． 在数据库中为什么要并发控制？ 答：数据库是共享资源，通常有许多个事务同时在运行。当多个事务并发地存取数据库时就会产生同时读取和／或修改同一数据的情况。若对并发操作不加控制就可能会存取和存储不正确的数据，破坏数据库的一致性。所以数据库管理系统必须提供并发控制机制。
共享资源、多事务运行->同时读写->不正确数据、隔离性、一致性
2 ．并发操作可能会产生哪几类数据不一致？用什么方法能避免各种不一致的情况？ 答：并发操作带来的数据不一致性包括三类：丢失修改、不可重复读和读“脏’数据。 ( l ）丢失修改（lost update ) 两个事务 Tl 和T2读入同一数据并修改，T2提交的结果破坏了（覆盖了） Tl 提交的结果，导致 Tl 的修改被丢失。 ( 2 ）不可重复读（ Non 一 Repeatable Read ) 不可重复读是指事务 Tl 读取数据后，事务T2执行更新操作，使 Tl 无法再现前一次读取结果。 ( 3 ）读“脏”数据（ Dirty Read ) 读“脏”数据是指事务 Tl 修改某一数据，并将其写回磁盘，事务T2读取同一数据后， Tl 由于某种原因被撤销，这时 Tl 已修改过的数据恢复原值，T2读到的数据就与数据库中的数据不一致，则T2读到的数据就为“脏”数据，即不正确的数据。 避免不一致性的方法和技术就是并发控制。最常用的技术是封锁技术。也可以用其他技术，例如在分布式数据库系统中可以采用时间戳方法来进行并发控制。
修改丢失、读脏数据、不可重复读（事务T1、T2）
封锁技术
3 ．什么是封锁？基本的封锁类型有几种？试述它们的含义。 答：封锁就是事务 T 在对某个数据对象例如表、记录等操作之前，先向系统发出请求，对其加锁。加锁后事务 T 就对该数据对象有了一定的控制，在事务 T 释放它的锁之前，其他的事务不能更新此数据对象。封锁是实现并发控制的一个非常重要的技术。 基本的封锁类型有两种：排它锁（ Exclusive Locks ，简称 x 锁）和共享锁 ( Share Locks，简称 S 锁）。排它锁又称为写锁。若事务 T 对数据对象 A 加上 X 锁，则只允许 T 读取和修改 A ，其他任何事务都不能再对 A 加任何类型的锁，直到 T 释放 A 上的锁。这就保证了其他事务在 T 释放 A 上的锁之前不能再读取和修改 A 。共享锁又称为读锁。若事务 T 对数据对象 A 加上 S 锁，则事务 T 可以读 A但不能修改 A ，其他事务只能再对 A 加 S 锁，而不能加 X 锁，直到 T 释放 A 上的 S 锁。这就保证了其他事务可以读 A ，但在 T 释放 A 上的 S 锁之前不能对 A 做任何修改。
事务对数据对象操作前，请求加锁，加锁，释放前一直独占
排他锁：读写，禁止别人加锁
共享锁：读，禁止别人加排他锁
三级封锁协议：加排他锁（写丢失）、再加S锁且读后释放（读脏数据）、再加S锁且事务结束后释放（不可重复读）
4 ．什么是活锁？什么是死锁？ 答： 如果事务 Tl 封锁了数据 R ，事务T2又请求封锁 R ，于是T2等待。T3也请求封锁 R ，当 Tl 释放了 R 上的封锁之后系统首先批准了T3的请求，T2仍然等待。然后T4又请求封锁 R ，当T3释放了 R 上的封锁之后系统又批准了T4的请求 … … T2有可能永远等待，这就是活锁的情形。活锁的含义是该等待事务等待时间太长，似乎被锁住了，实际上可能被激活。如果事务 Tl 封锁了数据 Rl ，T2封锁了数据R2，然后 Tl 又请求封锁R2，因T2已封锁了R2，于是 Tl 等待T2释放R2上的锁。接着T2又申请封锁 Rl ，因 Tl 已封锁了 Rl ，T2也只能等待 Tl 释放 Rl 上的锁。这样就出现了 Tl 在等待T2，而T2又在等待T1的局面， T1和T2两个事务永远不能结束，形成死锁。
活锁：由于封锁顺序没有先来后到，谦让等待
死锁：持有等待
5 ．试述活锁的产生原因和解决方法。 答：活锁产生的原因：当一系列封锁不能按照其先后顺序执行时，就可能导致一些事务无限期等待某个封锁，从而导致活锁。避免活锁的简单方法是采用先来先服务的策略。当多个事务请求封锁同一数据对象时，封锁子系统按请求封锁的先后次序对事务排队，数据对象上的锁一旦释放就批准申请队列中第一个事务获得锁。
封锁顺序没有先来后到，事务无限等待，先来先服务，队列
6 ．请给出检测死锁发生的一种方法，当发生死锁后如何解除死锁？ 答：数据库系统一般采用允许死锁发生， DBMS 检测到死锁后加以解除的方法。 DBMS 中诊断死锁的方法与操作系统类似，一般使用超时法或事务等待图法。超时法是：如果一个事务的等待时间超过了规定的时限，就认为发生了死锁。超时法实现简单，但有可能误判死锁，事务因其他原因长时间等待超过时限时，系统会误认为发生了死锁。若时限设置得太长，又不能及时发现死锁发生。 DBMS 并发控制子系统检测到死锁后，就要设法解除。通常采用的方法是选择一个处理死锁代价最小的事务，将其撤消，释放此事务持有的所有锁，使其他事务得以继续运行下去。当然，对撤销的事务所执行的数据修改操作必须加以恢复。
允许死锁，DBMS解除死锁，超时法（误判、不及时）、有向图法（撤销代价最小的事务，释放它的所有锁）
7 ．什么样的并发调度是正确的调度？ 答：可串行化（ Serializable ）的调度是正确的调度。可串行化的调度的定义：多个事务的并发执行是正确的，当且仅当其结果与按某一次序串行执行它们时的结果相同，称这种调度策略为可串行化的调度。
可串行化调度：等价于事务串行执行
8 ．举例说明，对并发事务的一个调度是可串行化的，而这些并发事务不一定遵守两段锁协议。
答：
9 ．为什么要引进意向锁？意向锁的含义是什么？
答：引进意向锁是为了提高封锁子系统的效率。该封锁子系统支持多种封锁粒度。原因是：在多粒度封锁方法中一个数据对象可能以两种方式加锁 ― 显式封锁和隐式封锁。因此系统在对某一数据对象加锁时不仅要检查该数据对象上有无（显式和隐式）封锁与之冲突，还要检查其所有上级结点和所有下级结点，看申请的封锁是否与这些结点上的（显式和隐式）封锁冲突，显然，这样的检查方法效率很低。为此引进了意向锁。意向锁的含义是：对任一结点加锁时，必须先对它的上层结点加意向锁。例如事务 T 要对某个元组加 X 锁，则首先要对关系和数据库加 ix 锁。换言之，对关系和数据库加 ix 锁，表示它的后裔结点 ― 某个元组拟（意向）加 X 锁。引进意向锁后，系统对某一数据对象加锁时不必逐个检查与下一级结点的封锁冲突了。例如，事务 T 要对关系 R 加 X 锁时，系统只要检查根结点数据库和 R 本身是否已加了不相容的锁（如发现已经加了 ix ，则与 X 冲突），而不再需要搜索和检查 R 中的每一个元组是否加了 X 锁或 S 锁。
意向锁作用：提高封锁效率，多粒度封锁
意向锁：如果对一个结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。
https://baike.baidu.com/item/%E6%84%8F%E5%90%91%E9%94%81/244186
10 ．试述常用的意向锁： IS 锁、 ix 锁、 SIX 锁。 答： IS锁：如果对一个数据对象加 IS 锁，表示它的后裔结点拟（意向）加 S 锁。例如，要对某个元组加 S 锁，则要首先对关系和数据库加 IS 锁 IX 锁：如果对一个数据对象加 IX 锁，表示它的后裔结点拟（意向）加X 锁。例如，要对某个元组加 X 锁，则要首先对关系和数据库加 ix 锁。 SIX 锁：如果对一个数据对象加 SIX 锁，表示对它加 S 锁，再加 IX 锁，即 SIX = S + IX 。