数据库事务处理技术

数据库数据库

Created At : 2021-08-30 20:57

Views 👀 :

第22讲数据库事务处理技术

为了更好的性能，我们需要并行处理数据库事务

什么是并发控制？

就比如我们买票

如果大家同时买起点终点、日期、车次相同的车票，会否买到座位相重复的车票？

很显然如果服务不能很好的进行并发控制，就会导致一张票被卖了两次，进而出现我们不想要的结果

常见的三种并发问题：

丢失修改（同一数据被两个事务同时操作，其中一个事务的结果被另一个事务的结果覆盖）
不可重复读（第一次读和第二次读结果不一样）
脏读（读到了已被回滚的数据）

什么是事务

事务是数据库管理系统提供的控制数据操作的一种手段，通过这一手段，应用程序员将一系列的数据库操作组合在一起作为一个整体进行操作和控制，以便数据库管理系统能够提供一致性状态转换的保证。

一个事务可处理一个数据或一条记录（从帐户A过户5000到帐户B上），也可能处理一批数据或一批记录

例如：下面的操作即为一个事务

read(A);
A := A – 5000;
write(A);
read(B);
B := B + 5000;
write(B);

所以说

并发控制就是通过事务微观交错执行次序的正确安排，保证事务宏观上的独立性、完整性和正确性

事务的ACID特性

原子性Atomicity : DBMS能够保证事务的一组更新操作是原子不可分的，即对 DB而言，要么全做，要么全不做
一致性Consistency⭐: DBMS保证事务的操作状态是正确的，符合一致性的操作 规则，不能出现三种典型的不一致性。它是进一步由隔离性来保证的。
隔离性Isolation: DBMS保证并发执行的多个事务之间互相不受影响。例如两个 事务T1和T2, 即使并发执行，也相当于或者先执行了T1,再执行T2;或者先执行了T2,再执行T1。
持久性Durability: DBMS保证已提交事务的影响是持久的，被撤销事务的影响是可恢复的。

并发调度

什么是事务调度(schedule)：

一组事务的基本步(读、写、其他控制操作如加锁、解锁等)的一种执行顺序称为对这组事务的一个调度。

并发(或并行)调度：多个事务从宏观上看是并行执行的，但其微观上的基本操作(读、写)则是交叉执行的。

事务调度之正确性

当且仅当在这个并发调度下所得到的新数据库结果与分别串行地运行这些事务所得的新数据库完全一致，则说调度是正确的。

事务调度之可串行性

如果不管数据库初始状态如何，一个调度对数据库状态的影响都和某个串行调度相同，则我们说这个调度是可串行化的 (Serializable)或具有可串行性(Serializability)。

可串行化调度一定是正确的并行调度，但正确的并行调度，却未必都是可串行化的调度
并行调度的正确性是指内容上结果正确性，而可串行性是指形式上结果正确性，便于操作。
可串行化的等效串行序列不一定唯一

事务调度之冲突

调度中一对连续的动作，它们满足：如果它们的顺序交换，那么涉及的事务中至少有一个事务的行为会改变。

有冲突的两个操作是不能交换次序的，没有冲突的两个事务是可交换的

同一个事务的任何两个操作都是冲突的

不同事务对同一元素的两个写操作是冲突的
不同事务对同一元素的一读一写操作是冲突的

事务调度之冲突可串行性

一个调度，如果通过交换相邻两个无冲突的操作能够转换到某一个串行的调度，则称此调度为冲突可串行化的调度。

冲突可串行性是比可串行性要严格的概念
满足冲突可串行性，一定满足可串行性；反之不然

冲突可串行性判别算法

构造一个前驱图(有向图)
结点是每一个事务Ti。如果Ti的一个操作与Tj的一个操作发生冲突，且Ti在 Tj前执行，则绘制一条边，由Ti指向Tj, 表征Ti要在Tj前执行。
测试检查: 如果此有向图没有环，则是冲突可串行化的

一道习题：冲突可串行的判定

基于封锁的并发控制方法

锁的概念

锁是控制并发的一种手段，是数据库元素上的并发控制标志

关于锁的基本知识点

每一数据元素都有唯一的锁
每一事务读写数据元素前，要获得锁
如果被其他事务持有该元素的锁，则要等待
事务处理完成后要释放锁
锁本身并不能保证冲突可串行性，只是为调度提供了控制的手段，具体如何使用锁需要说明——不同协议

封锁协议之锁的类型

排他锁X

只有一个事务能读和写，其他任何事务都不能读、写

共享锁S

所有事务都可以读，但任何事务都不能写

更新锁U

初始读，以后可以升级为写

增量锁I

区分增量更新和其他类型的更新

封锁协议0级到3级协议（加锁的时机）

0级协议 有写要求的数据对象A加排他锁，不再访问后即刻解锁。可防止丢失修改，但允许脏读，允许重复读错误
1级协议 有写要求的数据对象A加排他锁，事务提交时刻解锁。可防止丢失修改，可恢复,防止脏读，允许重复读错误
2级协议 有写要求的数据对象A加排他锁，事务提交时刻解锁。有读要求的数据对象B加共享锁，不再访问后即刻解锁。可防止丢失修改，防止脏读，防止重复读错误，但是不能解决幻读
3级协议 有写要求的数据对象A加排他锁，事务提交时刻解锁。有读要求的数据对象B加共享锁，事务提交时刻解锁。防止所有不一致性

脏读、不可重复读、幻读：

脏读：

所谓的脏读，其实就是读到了别的事务回滚前的脏数据。比如事务B执行过程中修改了数据X，在未提交前，事务A读取了X，而事务B却回滚了，这样事务A就形成了脏读。

也就是说，当前事务读到的数据是别的事务想要修改成为的但是没有修改成功的数据。

不可重复读：

事务A首先读取了一条数据，然后执行逻辑的时候，事务B将这条数据改变了，然后事务A再次读取的时候，发现数据不匹配了，就是所谓的不可重复读了。

也就是说，当前事务先进行了一次数据读取，然后再次读取到的数据是别的事务修改成功的数据，导致两次读取到的数据不匹配，也就照应了不可重复读的语义。

幻读：

事务A首先根据条件索引得到N条数据，然后事务B改变了这N条数据之外的M条或者增添了M条符合事务A搜索条件的数据，导致事务A再次搜索发现有N+M条数据了，就产生了幻读。

也就是说，当前事务读第一次取到的数据比后来读取到数据条目少。

SQL之隔离性级别

读未提交(read uncommitted) —相当于0级协议

读已提交 (read committed) —相当于1级协议

可重复读(repeatable read)—相当于2级协议

可串行化(serializable) —相当于3级协议

详细说明

两段封锁协议

是一种基于锁的并发控制方法。读写数据之前，每个事务中所有封锁请求先于任何一个解锁请求。

两阶段：加锁段和解锁段。加锁段不能有解锁操作，解锁段不能有加锁操作。

作用

两段封锁协议是可以保证冲突可串行性的。

注意：两段封锁协议是可能产生死锁的协议

基于时间戳的并发控制方法

基于时间戳的并发控制方法：借助于时间戳，强制使一组并发事务的交叉执行，等价于一个特定顺序的串行执行

具体操作就是执行时判断冲突，如无冲突，予以执行；如有冲突，则撤销事务，并重启该事务，此时该事务获得了一个更大的时间戳，表明是后执行的事务。

有哪些冲突：

读-读无冲突；
读-写或写-读冲突；
写-写冲突

具体规则：

对DB中的每个数据元素x，系统保留其上的最大时间戳

RT(x): 即R-timestamp(x) 读过该数据事务中最大的时间戳，即最后读x的事务的时间戳。

WT(x): 即W-timestamp(x)写过该数据事务中最大的时间戳，即最后写x的事务的时间戳。

事务的时间戳

TS(T) 即TimeStamp

读-写并发：(读-写、写-读)
若T事务读x，则将T的时间戳TS与WT(x)比较:
若TS大(T后进行)，则允许T操作，并且更改RT(x)为max{RT(x),TS}；
否则，有冲突，撤回T，重启T。
若T事务写x，则将T的时间戳TS与RT(x)比较：
若TS大(T后进行)，则允许T操作，并且更改WT(x)为max{WT(x),TS}；
否则，有冲突，撤回T重做。

写-写并发

若T事务写x，则将T的时间戳TS与WT(x)比较：
若TS大，则允许T写，并且更改WT(x)为T的时间戳；
否则有冲突，T撤回重做。

前述规则可以解决事务T过晚的读和过晚的写

但是这两种“事实上不可实现的”冲突可以避免了，实用性很有限

因此引入另一种调度规则

对DB中的每个数据元素x，系统保留其上的最大时间戳

RT(x): 即R-timestamp(x)

读过该数据事务中最大的时间戳，即最后读x的事务的时间戳。

WT(x): 即W-timestamp(x)

写过该数据事务中最大的时间戳，即最后写x的事务的时间戳。

C(x): x的提交位。

该位为真，当且仅当最近写x的事务已经提交。

C(x)的目的是避免出现事务读另一事务U所写数据然后U终止或者被撤销这样的情况。

对来自事务T的读写请求，调度器可以：

同意请求
撤销/终止T，并重启具有新时间戳的T(终止+重启，被称回滚)
推迟T，并在以后决定是终止T还是同意请求(如果请求是读，且此读可能是脏的)

调度规则

假设调度器收到请求rT(X)

(1)如果TS(T)>=WT(x), 此读是事实上可实现的

如C(x)为真，同意请求。如果TS(T)>RT(x), 置RT(x):=TS(T); 否则不改变RT(x).

如C(x)为假，推迟Ｔ直到C(x)为真或写x的事务终止。

(2)如果TS(T)<WT(x), 此读是事实上不可实现的

回滚T(终止并重启T)；(过晚的读)

假设调度器收到请求wT(X)

(1)如果TS(T)>=RT(x), 且TS(T)>=WT(x), 此写是事实上是可实现的

为x写入新值；置WT(x):=TS(T)；置C(x):=false.

(2)如果TS(T)>=RT(x),但是TS(T)<WT(x)，此写是事实上可实现的。但x 已经有一个更晚的值

如果C(x)为真，那么前一个x的写已提交；则忽略T的写；继续进行。(托马斯写规则)
如果C(x)为假，则我们需推迟T，直到C(x)为真或写x的事务终止。

(3)如果TS(T)<RT(x), 此写是事实上不可实现的
T必须回滚。(过晚的写)

假设调度器收到提交T的请求。

它必须找到T所写的所有数据库元素x, 并置C(x):=true。

如果有任何等待x被提交的事务，这些事务就被允许继续进行。

假设调度器收到终止T的请求

像前述步骤一样确定回滚T。

那么任何等待T所写元素x的事务必须重新尝试读或写，看这一动作现在T的写被终止后是否合法。

基于时间戳的并发控制的思想

事务在启动时刻被赋予唯一的时间戳，以示其启动顺序。
为每一数据库元素保存读时间戳和写时间戳，以记录读或写该数据元素的最后的事务。
通过在事务读写数据时判断是否存在冲突(读写冲突、写读冲突、写写冲突) 来强制事务以可串行化的方式执行。

基于有效性确认的并发控制方法

基于有效性确认的并发控制的思想

事务在启动时刻被赋予唯一的时间戳，以示其启动顺序。
为每一活跃事务保存其读写数据的集合，RS(T)：事务T读数据的集合； WS(T)：事务T写数据的集合。
通过对多个事务的读写集合，判断是否有冲突(存在事实上不可实现的行为)，即有效性确认，来完成事务的提交与回滚，强制事务以可串行化的方式执行

基于有效性确认的调度器

事务在启动时刻被赋予唯一的时间戳，以示其启动顺序。
每一事务读写数据的集合

RS(T)：事务T读数据的集合；
WS(T)：事务T写数据的集合。

事务分三个阶段进行

读阶段。事务从数据库中读取读集合中的所有元素。事务还在其局部地址空间计算它将要写的所有值；
有效性确认阶段。调度器通过比较该事务与其它事务的读写集合
来确认该事务的有效性。
写阶段。事务往数据库中写入其写集合中元素的值。
每个成功确认的事务是在其有效性确认的瞬间执行的。
并发事务串行的顺序即事务有效性确认的顺序。

调度器维护三个集合

START集合。已经开始但尚未完成有效性确认的事务集合。对此
集合中的事务，调度器维护START(T)，即事务T开始的时间。
VAL集合。已经确认有效性但尚未完成第3阶段写的事务。对此集
合中的事务，调度器维护START(T)和VAL(T)，即T确认的时间。
FIN集合。已经完成第3阶段的事务。对这样的事务T,START(T), VAL(T)和FIN(T)，即T完成的时间。

有效性确认规则

-(1)对于所有已经过有效性确认, 且在T开始前没有完成的U（U已经过有效性确认）, 即对于满足 FIN(U)>START(T)（U在T开始前没有完成。）的U,检测:

RS(T) ∩WS(U)是否为空。

若为空，则确认。否则，不予确认。

其含义是：如果一个较早的事务U现在正在写入T应该 读过的某些对象，则T的有效性不能确认

(2)对于所有已经过有效性确认，且在T有效性确认前没有完成的U（U有效性已经成功确认）, 即对于满足FIN(U)>VAL(T)的U（U在T进入其有效性确认阶段以前没有完成）, 检测：WS(T) ∩WS(U)是否为空。