rhb_blog

rao的博客

0%

数据库_并发控制

发表于 更新于 分类于 ，

并发控制概述

并发的背景：

  • DBMS作为系统软件，对外提供数据访问服务
  • 多个用户同时访问一个数据库
  • 各种任务以事务为逻辑单位运行
  • 同一时间并发运行的事务数可达数百个

多个事务的运行过程

串行执行

——事务依次执行，且每个事务必须等待前一个事务结束后方能运行

事务串行执行降低了系统资源利用率

事务执行过程中会占用多种资源：

  • CPU——比较、计算、统计等
  • 数据
  • 网络——收发指令和数据

单个事务执行过程中部分资源可能处于空闲状态

并行执行

  • 单处理机——CPU时间片轮转，多道程序交替运行
  • 多CPU——并行处理技术，多种共享内存以及硬盘策略

注意，数据是临界资源。在事务执行过程中，它所访问的数据集合应该在事务终止前是一致的、相容的

数据库事务并发带来的问题

操作系统层面的并发控制手段：信号量
——保护对象明确、相对集中
——控制保护时间一般较短
——直接阻塞任务进程——信号量资源有限

数据库事务并发控制：
——事务访问的数据对象及其范围相对灵活，一致性所涉及的范围更广。
——事务的执行一般包括一个读写操作的序列，时间相对比简单的应用程序变量操作要长。
——需要被保护的对象个数可能远多于信号量数目。
——事务的执行可能涉及DBMS的多个进程。

数据库系统中的并发错误

事务是数据库中并发控制的基本单位，事务处理需要保证事务的ACID特性，并发控制要能保证事务的隔离性和一致性。

当多个用户/进程/线程同时对数据库进行操作时，会出现3种冲突情形：

  1. 读-读，不存在任何问题
  2. 读-写，有隔离性问题，可能遇到脏读（会读到未提交的数据） ，幻影读等。
  3. 写-写，可能丢失更新

要解决冲突，一种办法是是锁，即基于锁的并发控制，比如2PL，这种方式开销比较高，而且无法避免死锁。

多版本并发控制（MVCC）是一种用来解决读-写冲突的无锁并发控制，也就是为事务分配单向增长的时间戳，为每个修改保存一个版本，版本与事务时间戳关联，读操作只读该事务开始前的数据库的快照。 这样在读操作不用阻塞写操作，写操作不用阻塞读操作的同时，避免了脏读和不可重复读

乐观并发控制（OCC）是一种用来解决写-写冲突的无锁并发控制，认为事务间争用没有那么多，所以先进行修改，在提交事务前，检查一下事务开始后，有没有新提交改变，如果没有就提交，如果有就放弃并重试。乐观并发控制类似自选锁。乐观并发控制适用于低数据争用，写冲突比较少的环境。

多版本并发控制可以结合基于锁的并发控制来解决写-写冲突，即MVCC+2PL，也可以结合乐观并发控制来解决写-写冲突。

基于封锁的并发控制

封锁概述

封锁的基本思想

封锁是数据库管理系统实现并发控制的一种重要技术。

并发控制方法：
① 锁（Locking）——商用数据库典型方法
② 时间戳（timestamping）
③ 乐观（Optimistic）

流程——事务在对某个数据对象（表、记录集合等）进行读写操作之前，先向系统发出封锁请求，系统依据请求对数据对象加锁，事务在获得锁后才能对数据对象进行操作，操作完成后在适当时机释放锁。

约束——系统在事务持有锁期间提供与锁配套的对数据的并发访问保护功能，其他事务不能违反保护规则进行与锁互斥的数据操作。

封锁的基本规则

① 将要存取的数据须先申请加锁；

② 已被加锁的数据不能再加不相容锁；

③ 一旦完成使用应“尽早”释放锁；

④ 未被加锁的数据不可对之解锁。

申请的时机

①针对事务执行确定一个时间点整体申请
一次封锁——无死锁
锁开销少——用少数的锁保护较大范围的数据
并发度低——锁冲突概率增加。

②针对单条SQL语句执行申请
申请频繁——申请时机增多
死锁——部分占有与互斥等待
锁开销大——被保护的数据对象集合增多
并发度高——细粒度的封锁

申请的方式

①显式

应事务的要求直接加到数据对象上。

②隐式

该数据对象没有直接加锁，由于数据对象的多粒度层次结构中的上级结点加了锁，使该数据对象隐含的加了相同类型的锁。

封锁的类型

基本的封锁类型有两种：排它锁（exclusive locks，简称X锁）和共享锁（share locks，简称S锁）。

（1）排它锁（X锁）
若事务T持有数据D的X锁，则T可读、写D，其它任何事务不能再对D加任何锁，直至T释放该X锁。X锁一般用于写保护，可防止丢失更新。

（2）共享锁（S锁）
若事务T持有数据D的S锁，则T仅能够对D进行读操作，其它事务仍可对D加S锁，但不可加X锁，直到T释放该S锁。

S锁一般用于读操作，一旦施加S锁，读可共享，但其它事务不可改。

除了X锁和S锁外，还有：

更新锁（U锁）：

意向锁：对多粒度树中的结点加意向锁，则说明该结点的下层结点正在被加锁；对任一结点加锁时，必须先对它的上层结点加意向锁。

注：当出现解锁时，就认定解锁任务开始，在解锁阶段不能再加任何锁

封锁的协议

在运用X锁和S锁时，针对并发操作不正确调度可能产生的丢失修改、不可重复读和读脏问题，可以通过三级封锁协议不同程度上解决这些问题。不同的封锁协议达到的系统一致性级别是不同的。

发生丢失更新的过程

T1读取库存后，T2也读取了同一个库存；T1修改库存，回写更新后的值；T2修改库存，也回写更新后的值。此时库存为T2回写的值，T1对库存的更新丢失。

顺序 任务 操作 库存量
１ T1 读库存量 50
２ T2 读库存量 50
３ T1 库存量=50+100
４ T2 库存量=50-40
５ T1 写库存量 150
６ T2 写库存量 10

T2使用T1的“脏数据”的过程

当T1和T2并发执行时，在T1对数据库更新的结果没有提交之前，T2使用了T1的结果，而在T2操作之后T1又回滚，这时引起的错误是T2读取了T1的“脏数据”。

顺序 任务 操作 库存量
１ T1 读库存量 50
２ T1 库存量=50+100
３ T1 写库存量 150
４ T2 读库存量 150
５ T2 库存量=150-40
６ T1 ROLLBACK 50
７ T2 写库存量 110

T1对数据A“不可重复读”的过程

当T1读取数据A后，T2执行了对A的更新，当T1 再次读取数据A（希望与第一次是相同的值）时，得到的数据与前一次不同，这时引起的错误称为“不可重复读”。

顺序 任务 操作 库存量A 入库量B
１ T1 读A=50 50 100
2 T1 读B=100
3 T1 求和=50+100
４ T2 读B=100 50
５ T2 B←B×4
６ T2 回写B=400 50 400
７ T1 读A=50 50
8 T1 读B=400
9 T1 和=450（验算不对）

（1）1级封锁协议
①策略
事务T在修改数据D之前须先对其加X锁，直到事务T结束（commit/rollback）才释放。
②功能
防止丢失修改；并保证事务T是可恢复的。
③问题
不能防止不可重复读和读“脏”数据。（仅对修改操作申请加锁保护，若读则不加锁）

时间 TA D值 TB 说明
1 X lock D;
R(D)=100
 100 TA对X加锁成功后读D
2 X lock D
等待		 TB对X加锁未成功后等待
3 W(D)=D-1 99 等待 TA修改，D结果写回数据库并释放X锁
4 X lock D
R(D)=99
W(D)=D-1
COMMIT
Unlock D		 TB获得D的X锁读D得99（已更新后结果）将修改后D（98）写回数据库

上述过程发生了脏数据的读取

1级封锁协议为什么不能避免读脏数据？

排它锁X只能防止该数据无法被其他线程写，不能防止该数据被其他线程读。在改数据和回滚的过程有可能会产生脏数据

（2）2级封锁协议
①策略
在1级封锁协议基础上，再加上约束：事务T在读取D之前先对D加S锁，读完后即可释放该S锁。[无需等待事务结束]
②功能
防止丢失修改；防止读脏。
③问题
不能防止读不可重复（读完即释放，重读可能其它事务对之修改）。

时间 TA D值 TB 说明
1 X lock D;
R(D)=100
W(D)=X*2		 100

200		 TA对X加锁成功
2 S lock D
等待		 TB申请S锁TA未释放，TB等待
3 Rollback
(W(X)=100)
UnLock D		 100 等待 TA因故撤消D值恢复为100
4 S lock D
R(D)=100
Unlock D		 TB获得S锁TB读到值与数据库中值一致，防止了读脏

为什么二级封锁协议可以解决脏读？

​ 前面我们说过脏读产生的原因：因为B事务读取到了A事务修改过尚未提交的数据，根据二级封锁协议要求：读数据的时候必须加S锁，但因为A事务在修改的时候已经加了X锁，在X锁的基础上是不能加S锁的，所以B事务无法获取S锁，就会导致B事务无法读取A事务中正在操作的数据，从而避免了脏读的发生。

（3）3级封锁协议
①策略
在1级封锁协议的基础上，加上约束：T读D前须先对D加S锁，直至T结束后才释放该S锁。
②功能
防止丢失修改；防止读脏；防止不可重复读。

时间 TA 数据库中A和B的值 TB 说明
1 S Lock A
R(A)=50
S Lock B
R(B)=100
C = A+B		 A：50
B：100

A：50		 TA对A、B加S锁TB不能再对之加X锁
2 X lock B
等待		 TB对B加X锁不成功TB等待
3 R(A)=50
R(B)=100
D=A+B
COMMIT
Unlock A
Unlock B

A：50
B：100		 等待 TB等待TB重读A、B，结果相同
4

A：50
B：200		 X Lock B
R(B)=100
W(B)：=B*2
写回B=200		 TB获得B的X锁

为什么三级封锁协议可以解决不可重复读？

​ 前面我们也说过了不可重复读产生的原因：是因为B事务读取到了A事务已经修改过的数据，导致前后两次读取的数据不一致。现根据三级封锁协议的要求：读取数据时必须加S锁，在S锁的基础上只能加S锁，不能加X锁，所以在B事务读取数据期间，A事务无法对数据进行修改，从而避免了不可重复读问题的发生。

并行调度的可串行性

正确性标准

（1）单个事务

——若非并发的执行，每个事务都能保证DB的正确性。
（丢失修改、不可重复读、读脏数据，都是因事务并发执行产生）

（2）多个事务

——多个事务以任意串行方式执行都能保证DB的正确性。
给定三个事务：T1，T2，T3。
T1→T2→T3 T1→T3→T2
T2→T1→T3 T2→T3→T1
T3→T1→T2 T3→T2→T1
显然，任何一事务并发执行时禁止其它事务执行，总能保证DB正确性，但不利于数据共享。

（3）可串行化调度（serializable）

——当且仅当多个事务并发执行的结果与这些事务按某一顺序串行执行的结果相同时，则该并发执行是可串行化的。
（可串行化调度是并发事务正确性的唯一准则）

例：有两个事务TA，TB （A=10, B=2, C=0）包含如下操作序列
TA：读B；A:=B+1；写回A；
TB：读C；读A；B:=A+C+1；写回B；
则至少可能有四种不同的调度方式:

1、先执行TA，再执行TB——RA(B) WA(A) RB(C) RB(A) WB(B)；结果：A=3，B=4，C=0。【串行调度】

2、先执行TB，再执行TA——RB(C) RB(A) WB(B) RA(B) WA(A) ；执行结果：A=12，B=11，C=0。【串行调度】

3、两事务TA、TB按ti并发执行——RA(B) RB(C) RB(A) WA(A) WB(B)，结果为A=3，B=11。
按事务并发可串行化的正确性准则，该结果与TA、TB两个串行执行的任何结果（A=3，B=4；A=12，B=11）均不同，调度结果错误。【交错执行（不可串行化）调度】

4、按ti交错执行——RA(B) RB(C)WA(A)RB(A)WB(B)；执行结果：A=3，B=4。该结果正确，因为与串行化调度1结果相同，该调度是可串行化调度【交错执行(可串行化)调度】

冲突可串行化调度

——可串行化调度的充分而非必要条件。

冲突操作：① Ri(x)与Wj(x) ② Wi(x)与Wj(x)

操作顺序的交换（可交换、不可交换）
——不同事务的冲突操作和同一事务的两个操作均是不可交换的。否则可能使操作序列的结果不等价。

在可交换的前提下，若干事务的操作交换顺序的结果是一个串行调度，则称这个调度是冲突可串行化的。

前趋图：事务均为节点，事务之间存在冲突操作（读写、写读、写写）时，则事务之间存在由冲突操作的先执行事务指向后执行事务的有向边。

前驱图中不存在环路等价于调度是冲突可串行化的

冲突可串行化是可串行化的充分条件，不是必要条件。

两段锁协议

参考文章

问题分析

  • 并发调度的正确性标准：可串行化调度
    n个事务的可串行化调度结果——n！种
    可串行化的充分而非必要条件：冲突可串行化调度

  • 基于封锁的并发控制：一种基于悲观思想的并发控制策略。
    操作之前先查验冲突

  • 封锁如何解决并发错误？
    三级封锁协议
    排它锁保护写操作——写之前申请，事务结束时释放。
    在此基础上，共享锁保护读操作——读之前申请，释放时机（读完之后即可释放、事务结束时释放）

三级封锁协议的选择依据

权衡并发调度正确性和并发性能。

三级封锁协议的特点之一：事务对数据的保护时间较为统一，其中比较强的往往保护至事务结束。

能否制定相对灵活的封锁协议?
两阶段封锁（TwoPhase Locking，简称2PL）

基于2PL协议的调度

基本思想：所有事务必须分为两个阶段对数据项加锁和解锁，第一阶段称为扩展阶段（获得锁）；第二阶段称为收缩阶段（释放锁）。

协议内容：
（1）在对任何数据读、写之前，须先获得该数据的锁；
（2）在释放一个封锁之后，该事务不能再申请任何其它锁。【正确的遵守2PL协议，所有获得锁均在释放锁之前。】

两个阶段：事务的第一个释放锁操作成为分界线。
扩张和收缩：事务对数据资源的占有。

两段锁协议的目标：实现并发事务调度的可串行化。

两阶段锁协议的特点

  • 定理：若所有事务都遵守2PL协议，则对这些事务的所有并发调度策略都是可串行化的。

证明思路：
前趋图——事务均为节点，事务之间存在冲突操作（读写、写读、写写）时，则事务之间存在由冲突操作的先执行事务指向后执行事务的有向边。

前驱图中不存在环路等价于调度是冲突可串行化的

反证法：假设调度遵循2PL协议但不是可串行化的 → 与2PL有矛盾。冲突可串行化是可串行化的充分而非必要条件。

假如调度不是可串行化的，则该调度也不是冲突可串行化的。
① 假设某个遵守2PL的调度不是可串行化调度；
② 按Lock、UnLock操作中因锁不兼容而等待的关系构造调度的前趋图G；
③ 依据假设，若调度不是可串行化，则G中必存在环路，不妨设为：Ti1→Ti2→……→Tjp→Tin。
④ 其中某个冲突事务获得锁的前提是前面的冲突事务释放锁，则意味着Ti1解锁后Tjp才能获得锁，之后在环路中又出现Tin加锁；
⑤ “④”中Ti违反了两阶段锁协议。

  • 2PL协议是可串行化的充分条件，不是必要条件。
  • 遵守两阶段锁协议的事务可能发生死锁。

总结

两阶段锁（2PL）：通过事务的扩张和收缩阶段的划分，而不是提交之前与提交之时的这种划分，对锁的申请和释放流程进行的一种约定，从而实现了调度正确性的一个充分而非必要条件。

封锁的粒度

到目前为止我们都没有对不同粒度的锁进行讨论，一直以来我们都讨论的都是数据行锁，但是在有些时候我们希望将多个节点看做一个数据单元，使用锁直接将这个数据单元、表甚至数据库锁定起来。这个目标的实现需要我们在数据库中定义不同粒度的锁

多粒度封锁

封锁的粒度：封锁对象的大小。
（1）逻辑单元：整个数据库、整个关系、整个索引、关系的分区、元组、索引项、属性值集、属性值。
（2）物理单元：数据页（块）、索引页

封锁的粒度与数据库并发性能的两个重要因素相关：

  • 并发度
  • 并发控制的开销

粒度小——封锁开销大——并发度大

封锁的基本策略

宜采用多粒度封锁：
1）需常存取多个关系的大量元组时宜采用数据库级粒度；
2）需常存取单个关系大量元组时宜采用关系级；
3）需常存取单个关系少量元组时宜采用元组级；
4）一般不采用属性级；
5）物理单元一般不宜采用。

多粒度锁提供了并发度和锁开销的权衡空间。

多粒度封锁

隐式封锁：某个数据对象被显式封锁后，它在多粒度层次结构中的子孙节点被隐含的加了相同类型的锁

多粒度锁的冲突检测

  • 显式封锁和隐式封锁的效果是一样的，因此检查封锁冲突时需要对两种封锁的结果都进行检测。

    1）检查数据对象本身有无显式封锁与申请冲突；

    2）检查上级结点有无封锁与本结点冲突；

    3）检查后代结点有无封锁与本结点冲突

意向锁

对任一结点加锁时，必须先对它的上层结点加意向锁。如果对某个结点加意向锁，则表示该结点的某个子孙结点正在或拟施加相应的非意向锁。作用：提高系统并发度，减少加锁和解锁的开销。被商用产品广泛采用。

意向锁的类型：
1）IS锁：表示某个子孙结点拟加S锁
2）IX锁：表示某个子孙结点拟加X锁
3）SIX锁：表示对结点施加S锁的同时，再施加IX锁= S+IX