事务

发表于 分类于

数据库管理系统的并发控制和恢复机制存在于数据库管理系统设计中的各个部分。并发控制确保在多个线程写入/读取时数据的正确性，而恢复机制确保数据库管理系统在系统突然断电后数据仍然正常。基于事务的特性，并发控制和恢复机制是数据库管理系统的重要部分。

事务是在数据库上执行一系列的一个或多个操作（例如SQL查询）以执行一些更高级别的功能。事务是数据库管理系统变化的基本单位。只执行部分事务是不允许的。

比如，从小明的账户转100元给小红

  • 检查小明是否有100元
  • 小明的账户减少100元
  • 小红的账户增加100元

简易设计

可按照事务到达数据库管理系统顺序依次执行，同一时刻仅可以执行一个事务。

在事务开始之前，将整个数据库复制到一个新文件，之后的更改均在新文件上执行。

  • 写入成功时用新文件覆盖原有文件
  • 写入失败时，删除新文件

以上设计存在一定的问题，可允许相互独立的事务并发执行以提高执行效率。

任意交错的操作将会导致暂时不一致，系统必然会在某一时刻处于不一致状态。但是这样不一致的状态不可一直存在。事务的作用域仅限于数据库管理系统中，在数据库管理系统以外不可回滚，所以事务不可更改数据库系统以外的文件。

ACID特性

事务可能在从数据库中检索到的数据中执行很多操作，但是数据库管理系统仅仅关注从数据库中读入/写入的数据。

我们将数据库定义为固定的数据集合，例如A,B,C。相应地，事务定义为读/写操作的序列。例如R(A),R(B)。事务是数据库管理系统对应用程序的抽象。

在SQL中，事务以BEGIN为开始，要么以COMMIT,要么以ABORT结束。

  • COMMIT 如果提交了，数据库管理系统要么保存所有的更改，要么放弃更改
  • ABORT 如果失败，所有操作将取消，和之前并未执行这些操作一样

原子性

在事务中所有操作要么都执行，要么都不执行。

考虑以下两种情形

  1. 从小明的账户中取出了100元后，数据库管理系统在转账时失败
  2. 从小明账户中转出100元后，系统关机

以上事务执行后小明账户正确的数目应该是多少？

可通过以下两种方式来确保操作的原子性

  • 日志

    数据库管理系统记录所有的操作，在事务失败时取消失败事务的相关操作

    在内存和磁盘中均存储取消的操作记录

    目前大多数数据管理系统的方式，效率高

  • 不可见页

    数据库操作系统复制页，事务对这些页更改。仅当事务提交时这些页才对其余事务可见。

一致性

数据库表示的世界在逻辑上是正确的，所有对数据的查询也应得到正确的应答。

通过以下一致性来确保正确性：

数据库一致性

数据库准确地模拟了真实世界，符合完整性约束。

将来的事务可查看过去在数据库中提交的事务。

事务一致性

如果每个事务都是一致的，并且在事务开始时数据库是一致的，则可确保事务完成时数据库是一致的。

隔离性

用户提交事务，每个事务独立执行，互不干扰。

数据库管理系统通过交错事务的操作来实现并发。

并发模型即是如何决定从多个事务中决定合适的交错顺序。

  • 消极型 首要的一点是不让问题出现
  • 乐观型 假定冲突很少见，在发生时再对冲突处理

考虑以下情况，假定A,B中初始时刻均有1000元

T1从A的账户中转100元到B的账户，T2给两个账户6%的利息。

1
2
3
4
5
 T1                     T2
BEGIN                  BEGIN
A=A-100                A=A*1.06 
B=B+100                B=B*1.06
COMMIT                 COMMIT

执行T1和T2的结果可能是什么呢？

可能有很多执行结果，但是A+B应该是$2000*1.06=2120$

若两个事务同时提交，无法确保T1一定在T2之前执行，反之亦然。但是最后的结果必须等同于按照一定顺序串行执行的这两个事务。

合理的结果可能为：

  • $A=954,B=1166$
  • $A=960,B=1160$

结果取决于A先执行还是B先执行。

调度a

1
2
3
4
5
6
7
8
9
 T1                     T2
BEGIN                
A=A-100                
B=B+100                
COMMIT                
                       BEGIN
                       A=A*1.06 
                       B=B*1.06
                       COMMIT

执行后，$A=954,B=1166$

调度b

1
2
3
4
5
6
7
8
9
 T1                     T2
                       BEGIN
                       A=A*1.06 
                       B=B*1.06
                       COMMIT
BEGIN                
A=A-100                
B=B+100                
COMMIT

执行后，$A=960,B=1160$

交叉执行的调度同样正确，例如调度c

1
2
3
4
5
6
7
8
9
 T1                     T2
BEGIN                
A=A-100
                       BEGIN
                       A=A*1.06
B=B+100                
COMMIT
                       B=B*1.06
                       COMMIT

执行后结果为，$A=954,B=1166$

调度c和调度b最后的结果均满足$A+B=2120$，所以二者等价。

但是若T1和T2按照以下顺序执行，会得到错误的结果。

1
2
3
4
5
6
7
8
9
 T1                     T2
BEGIN                
A=A-100
                       BEGIN
                       A=A*1.06
                       B=B*1.06
                       COMMIT
B=B+100                
COMMIT

$A=954,B=1060,A+B=2014$ 损失了106元。

如何判定调度是正确的呢？

如果调度等价于某个顺序的串行执行，则该调度是正确的。

  • 串行执行调度

    不同事务的操作不交错的调度

  • 等价执行调度

    对于任何数据库状态来说，先执行前者和先执行后者的结果相同

  • 可串行化调度

    等价于某一事务串行执行的调度

如果每个事务均可持久，每个串行调度也将是持久的。

为了有效描述冲突操作之间的等价，我们给出以下定义

假如两个操作冲突，那么它们属于不同事务，对同一对象作用，至少有一个是写操作。

交错执行异常有以下几种：

  • 读写冲突
  • 写读冲突
  • 写写冲突

读写冲突

1
2
3
4
5
6
7
8
9
     T1                    T2
    BEGIN
10<-R(A)
                         BEGIN
                         R(A) ->10
                         W(A) <-19
                         COMMIT
19<-R(A)
    COMMIT

两次读结果应该是一致的，在这里却不一致。

写读冲突

1
2
3
4
5
6
7
8
9
      T1                  T2
    BEGIN
10<-R(A)
12->W(A)
                         BEGIN
                         R(A)->12
                         W(A)<-14
                         COMMIT
    ABORT

T2读取T1未提交的更改数据。

写写冲突

1
2
3
4
5
6
7
8
9
10
      T1                  T2
    BEGIN
10->W(A)

                         BEGIN
                         W(A)<-19
                         W(A)<-Andy
                         COMMIT
Bieber->W(B)
    COMMIT

T1提交的数据A被T2覆盖，T2提交的数据B被T1覆盖。

给定以上例子，串行化调度用于检查调度是否正确，而不是用于产生正确的调度。

串行性有不同级别

  • 冲突串行化

    大部分数据库管理系统支持

  • 视图串行化

    仅仅是理论

两个调度是等价的，当且仅当：

  • 由相同事务的相同操作组成
  • 每组冲突的操作都按照相同顺序执行

如果调度S与某个串行调度冲突等价，那么调度S是可串行化冲突。

可通过交换相邻的不同事务的不冲突操作得到可串行化冲突S。

1
2
3
4
5
6
7
8
9
10
11
12
 T1                   T2
BEGIN                BEGIN
R(A)
W(A)
                     R(A)
                     W(A)
R(B)
W(B)
COMMIT
                     R(B)
                     W(B)
                     COMMIT

W(A)与R(B)不冲突，可调换顺序。R(B)和R(A)也不冲突，可再次调换顺序，我们得到以下调度

1
2
3
4
5
6
7
8
9
10
11
12
 T1                   T2
BEGIN               BEGIN
R(A)
W(A)
R(B)
                     R(A)
                     W(A)
W(B)
COMMIT
                     R(B)
                     W(B)
                     COMMIT

类似地，我们也可以得到以下调度

1
2
3
4
5
6
7
8
9
10
11
12
 T1                   T2
BEGIN                BEGIN
R(A)
W(A)
R(B)
W(B)
COMMIT
                     R(A)
                     W(A)
                     R(B)
                     W(B)
                     COMMIT

仅有两个事务的时候可通过简单的交换来构造串行化的调度。

对于更多事务的操作，存在更好的算法吗？

依赖图

每个事务对应一个节点，满足

  • $T_i$中的$O_i$操作与$T_j$中的$O_j$冲突

  • $O_i$比$O_j$出现早

    那么就从$T_i$引一条到$T_j$的边。

一个调度是可串行化冲突当且仅当依赖图是无环的。

视图串行性

弱化的串行性，对于调度$S_1$和调度$S_2$，满足

  • $T_1$读入$S_1$中$A$的初始值时，$T_1$也读入$S_2$中$A$的初始值
  • $T_1$读取$S_1$中$T_2$写入到$A$的值时,$T_1$也读取$S_2$中$T_2$写入到$A$的值时
  • $T_1$写入到$S_1$中$A$的最终值时，也写入$A$的最终值到$S_2$
1
2
3
4
5
6
7
8
9
10
11
T1              T2              T3
BEGIN
R(A)
W(A)
COMMIT
               BEGIN
               W(A)
               COMMIT
                               BEGIN
                               W(A)
                               COMMIT

与以下调度视图等价。

1
2
3
4
5
6
7
8
9
10
11
12
T1              T2              T3
BEGIN
               BEGIN
               W(A)
R(A)
W(A)
COMMIT
               
               COMMIT
                               BEGIN
                               W(A)
                               COMMIT

视图串行化即所有的串行化冲突再附加上随意写的事务，即不限定写入的事务的顺序。

与冲突串行化不同，视图串行化不存在有效验证的方法，目前没有任何数据库支持视图串行化。

以上分析用文氏图表示如下

持久性

一个事务成功完成后，对数据库的更改是永久的。