高级数据库-事务

Posted on
Words count in article: 11.4k | Reading time ≈ 41

高级数据库-事务

复习

ACID

首先，我们来复习一下事务的概念：ACID，(其实在sql中已经学过了)

  • 原子性(Atomicity): 一个事务要么没有开始，要么全部完成，不存在中间状态
  • 一致性(Consistency): 事务的执行不会破坏数据的正确性，即符合约束
  • 隔离性(Isolation): 多个事务不会相互破坏
  • 持久性(Durability): 事务一旦提交成功，对数据的修改不会丢失

事务面向的负载在于查询和更新。其主要特征是：

  • 查询：较大数据集合的计算
  • 更新：通常是小部分数据，点数据的更新

事务的实现

  • 实现并发控制：隔离性
  • 实现日志：原子性，持久性
  • 一致性：应用或其他实现保证

并发控制的主要内容

并发控制的意思就是在有多个并发的事务的情况下怎么保持数据库的一致的状态。这个状态有不同的层次，这些层次就是隔离级别。隔离级别越高，并发能力越弱；隔离级别越低，并发能力越强。比如说，可串行化是最高的隔离级别。

接下来，我们就要着重了解可序列化这个隔离等级

隔离等级

调度

首先给出调度(shedule)的定义：a sequence of (important) steps taken by one or more transactions

那么这些重要的步骤是什么？在并发控制中，往往是对于某一个值的读写操作：

1
2
read operation(Read(X))
write operations(Write(X))

我们给一个例子

现在有两个数据库中的值：A和B，它们相等

1
2
A = 25
B = 25

然后有两个事务,第一个事务负责把A和B各加上100，第二个事务负责把A和B各乘以2

那么其中的一个可能的调度如下：

当然，T1,T2可能是串行的，也就是先做完T1再做T2

串行执行

在了解可序列化之前，我们先看看顺序执行是怎么做的。顺序执行非常好理解——它是单线程调度的，做完事务1之后才能做事务2.

这是事务执行最理想的状态，但同时由于是单线程调度，其没有并发能力

可串行化(Serializable)

那么，可串行化的意思说，具有一定的并发能力，但同时让事务的调度结果和串行化是等价的。

比如说还是用上面那个例子，可串行化的调度如下：我们发现，这样的调度和串行化的调度是等价的，最终都能达到 A = B = 250的效果。

那么非可串行化的调度是怎么样的呢？我们看看下图：得到的结果是 A=250,B=150，和串行化调度不等价

可串行化对事务的执行先后没有要求，但是最后结果需要和串行化调度的结果达成一致

冲突可串行化调度(Conflict-serializable)

冲突等价

冲突操作指的是不同事务对于同一数据的读写操作与写写操作。但是有些冲突操作是可以交换次序的(non-conflicting swaps)，有些冲突操作不能交换次序(conflicting swaps)。

不能交换位置的次序为：

  • 不同事务对同一个对象的冲突操作
  • 同一事务对同一个对象的两个操作(如读写)

定义冲突等价：

如果两个Schedule S1和S2 ， S1可以通过 non-conflicting swaps 转换成 S2的话，那么S1和S2就是冲突等价的

比如说, 现在有这样一个调度，我们将其分为四个色块，分别标记为A,B,C,D

从块与块之间的角度来看，显然A和B是冲突操作，C和D是冲突操作，因为都涉及到不同事务修改同一个值。所以AB不能交换，CD不能交换

从块内角度分析：A内部$r_1(A)w_1(A)$ 是冲突的，因为这属于同一事务对同一个值的冲突操作。同理BCD也是这样，因此色块内部的顺序也不能调整

但是，我们可以打破块的束缚，从整体来看，下图绿色块跟青色块可以交换次序，因为这两个操作不冲突，不符合第三条的任意一种情况。

再看新的绿色块与青色块，如果交换它俩也不会发生冲突：

那么我们说，原调度和这些变化都是冲突等价的

冲突可串行化

一个调度Schedule1在保证冲突操作次序不变的情况下，通过交换两个事务不冲突操作的次序得到另外一个调度Schedule2，如果Schedule2与串行化等价，那么称调度Schedule1是冲突可串行化的调度。同时称Schedule1和Schedule2是冲突等价的

我们还是拿刚才那个调度为例，经过了两次交换顺序之后, 经过了如下变化：

最终结果是我们发现T1和T2被串行起来了，这和串行化是等价的。因此我们称原调度是冲突可串行化的

此外隔离等级还有Read Uncommitted，Read Commited， Repeatable Read 等

冲突可串行化的性质

然后我们要介绍冲突可串行化的一个性质：冲突可串行化永远是可串行化的. 因为如果调度是冲突可串行化的，那么必定可以通过交换non-conflicting operations的方法，得到一个新的调度，这个调度是串行化的。因此根据可串行化的定义，冲突可串行化也是可串行化的

但是要注意，可串行化的调度，不一定是冲突可串行化的，我们来举一个例子：现在有三个事务如下

有两个Schedule如下：其中S2是串行的调度

显然，S1和S2最终达到的效果是一样的，因此S1是可串行化的。但是S1却不是冲突可串行化的。因为没有办法通过non-conflicts swap将S1转换为S2

Recoverble Schedule

可恢复的调度(recoverable schedule)：是指已提交的事务不应该发生回滚的调度。我们用一张图来说明：如果$T_k$需要读取T1、T2、T3的写，那么T1、T2、T3就需要在$T_k$之前提交。

可恢复的调度分为以下几类：

  1. 层联回滚(Cascading rollback)调度：未提交的事务从未提交的(失败)事务中读取了错误的数据（Dirty Read ），必须回滚。
  2. 无层联回滚的：事务只读取已提交事务写的数据(Read Commited)。
  3. 严格调度(Strict Schedule)：在写数据项的最后一个事务提交之后事务才能开始读/写该数据项。

为什么要有这个概念呢？如果不是recovery的调度的话，一旦系统发生了故障，就无法恢复。试想，如果T1写了A，然后Tk读取了A，并先于T1提交了。那么假设在Tk提交到T1提交这个时间段出现了系统故障，那么当系统重启之后按道理来说需要回滚到T1写A之前，但是T1并没有提交，系统只会回滚到Tk读取A的那个状态。因此丢失了A原来的值。

Read Uncommitted

是最低级别的隔离等级。它什么都不会做，漏洞最多。会出现上面所说的所有问题。因为事务之间没有互相隔离，他们可以读取互相做出的未提交修改。在这种情况下不允许发生脏写，但是可能发生脏读、不可重复读、幻读。

Read Committed.

当我们使用这个隔离级别时，事务只能读取已经提交了的数据。如果我们需要在事务中进行商务上的计算，我们的决定是基于有效的、已经提交的数据。事务运行之后有数据发生了变化，事务也不会去关注这个问题。这个隔离级别可以避免Dirty Read这个问题

Repeatable Read:

在这种级别下，读取的内容是可重复的，就算是数据被其他的事务修改了也没事。我们看到的只是第一次读取时就生成的快照。这个级别可以避免 Lost Updates, Dirty Reads 和 Non-repeating Reads这三个问题

异常等级

Dirty Writes

两个事务在没提交的情况下去更新同一行数据的值

我们对一条数据进行两次更新，一次更改洲名，一次更改积分，但是这样一来，如果B是后更新的，那么B中的数据会覆盖掉A中更新的数据，造成更新丢失。我们这时候就需要Locks来规避这种情况的发生，默认情况下，Mysql使用了锁定机制以防止两个事务同时更新相同的数据，他们在一个队列中，按照顺序进行。

Dirty Reads

Dirty Reads 发生在事务读取还没有提交的数据时，比如下图。事务A想把顾客的分设置为20，在还没有提交的时候，事务B读取了表中更新过后的数据。如果每一分代表优惠一元，那么这位顾客可以优惠20元。但是事务A在提交前发生回滚。这时候事务B还没结束，所以事务B读取的数据是非法的。也就是说，在这种情况下，白给了顾客20元的优惠，因为事务B中读取了未提交的数据 。这就是 Dirty Reads，很形象。因为我们读取了污染的数据。

为了解决这个问题，我们需要围绕事务提供一定程度的隔离度。所以事务修改的数据并不会立刻被其他事务读取到。为了规避这个问题，可以使用Read Committed及以上的隔离等级。

Non-repeating Reads

如果在事务进行过程中，我们读取了两次、得到了不一样的结果怎么办.比如下图。事务A中选择了数据表中一条值为10的信息，但是这时候，B把这条信息的数据改成了0，现在A中的子查询又想读取这条信息，发现这时候其值已经变成0了。对于这种不重复读取的异常，我们可以将隔离级别从 read committed（读已提交）提升到repeatable read（可重复读）。

Phantom Reads

假设有个事务A，我们查询了所有积分大于10的客户，发给他们额外的打折券。这时候，一个事务B修改了一位顾客甲，把他的分从0修改到了20。但这时候事务A已经完成查询，甲并不在查询结果当中。这就是我们说的Phantom Read，数据有时候会像幽灵一样突然冒出来。是否解决这个问题要看我们的业务、以及把这个客户纳入我们的事务中的重要性。

不可重复读和幻读区别：不可重复读的重点是修改；同样的条件，第1次和第2次读取的值不一样。幻读的重点在于新增或者删除；同样的条件， 第1次和第2次读出来的记录数不一样。从控制角度来看，不可重复读只需要锁住满足条件的记录，幻读要锁住满足条件及其相近的记录。

事实上，隔离等级是根据异常等级的不同而划分的。我们可以用一张表来总结：

实现隔离级别

首先我们来介绍几种锁

  • 共享锁 shared lock (简称S锁) : 应用于所有读操作

    • 如果事务T1对数据对象O1加上了共享锁，那么当前事务只能对O1进行读取操作，其他事务也只能对这个数据对象加共享锁——直到该数据对象上的所有共享锁都被释放。
    • 共享锁和排他锁最根本的区别在于，加上排他锁后，数据对象只对一个事务可见，而加上共享锁后，数据对所有事务都可见。

  • 排他锁 exclusive lock(简称X锁): 应用于所有写操作

    • 如果事务 T1对数据对象 O1加上了排他锁，那么在整个加锁期间，只允许事务 T1对 O1进行读取和更新操作，其他任何事务都不能再对这个数据对象进行任何类型的操作——直到T1释放了排他锁

  • Short duration lock: 短锁，动作完成前申请，完成后立即释放锁

  • Long duration lock: 长锁, 动作完成前申请，直到Commit之后才会释放锁

我们可以用锁来定义不同的隔离级别:

Consistency Level = Locking Isolation Levo Read Locks on Data Items and Predicates Write Locks on Data Item and Predicates
Degree 0 没有要求 Well-formed Writes
Degree1
READ UNCOMMITED		 没有要求 Well-formed Writes
Long duration Write locks
Degree2
READ COMMITED(读已提交)		 Well-formed Reads
Short duration Read locks(both)		 Well-formed Writes
Long duration Write locks
REPEATABLE READ(可重复读) Well-formed Reads
Long duration data-item Read locks
Short duration Read Predicate locks(both)		 Well-formed Reads
Long duration Write locks
SERIALIZABLE(序列化) Well-formed Reads
Long duration Read locks(both)		 Well-formed Reads
Long duration Write locks

实现的原理

  • READ UNCOMMITED: 事务在读数据的时候并未对数据加锁。事务在修改数据的时候只对数据增加行级共享锁。
    • 此时，事务1读取某行记录的时候，事务2也可以对这行数据进行读取、更新(因为事务1未加锁)
    • 事务1更新某行记录时，事务2不能对这行记录做更新，直到事务1结束。（因为事务一对数据增加了共享读锁，事务二不能增加排他写锁进行数据的修改）。因此，可以避免脏写的情况。
    • 当事务2对该记录进行更新时，事务1再次读取该记录，能读到事务2对该记录的修改版本（因为事务二只增加了共享读锁，事务一可以再增加共享读锁读取数据），即使该修改尚未被提交。但是，无法避免脏读、重复读、幻读的情况，因为它对读操作并没有上锁。
  • READ COMMITED: 事务对当前被读取的数据加行级共享锁(当读到时才加锁)，一旦读完该行，立即释放该行级共享锁，(短锁)；事务在更新某数据的瞬间(就是发生更新的瞬间），必须先对其加 行级排他锁(长锁)，直到事务结束才释放。
    • 脏读发生的环境是，事务A修改了一个变量，另一个事务B刚好读取了这个变量，但事务A还没有提交的时候，就发生了回滚。因此B读取到了一个脏的数据(还没持久化的数据)。当使用READ COMMITED隔离级别的时候，在更新数据的时候加上了排它锁，因此在事务B读取特定变量的时候，无法对数据加读共享锁。事务B只能等待事务A的写操作提交以后，或者事务A回滚以后，释放了排它锁，才能读取该变量的值。
    • 但此时，由于是对读操作上了短共享锁，读取完成后立即释放。试想一下这个情景，事务A需要读取一个x的值10，读取完后释放锁，但事务A还没有结束，去忙别的事情了。这时候，事务B对x进行了更新，将其改为了20并提交了。那么，当事务A再次去读取x的时候，发现变成了20。这就是不可重复读错误
    • 再来思考一个场景，事务A筛选出积分大于10的客户，并要对其发送优惠券。此时x的积分为0，不属于A的筛选范畴，因此事务A不需要对x上锁。但是，这时候事务B修改了x的积分，到20，并成功提交。那么这时候，事务A还没结束，但是其筛选出来的值与真实的数目不符。因此，幻读还是没有办法避免的。
  • REPEATABLE READ: 事务在读取某数据的瞬间（就是开始读取的瞬间），必须先对其加 行级共享锁，直到事务结束才释放(长锁)；事务在更新某数据的瞬间（就是发生更新的瞬间），必须先对其加 行级排他锁，直到事务结束才释放(长锁)。
    • 此时来看不可重复读，当事务A开始读取变量x的时候，会对其上长共享锁，直到事务提交才会释放。那么这时候，如果B尝试对x进行更新的话，需要获取对x的排它锁,这是不被允许的。因此只有当事务A执行结束之后，事务B才可以修改x的值。
    • 但是来看幻读，当事务A只会对某一行上长共享锁，并不会对整张表上长共享锁。因此，如果事务A一开始没有选中对象x，那么也不会对其上锁，还是会蹦出来新的数据。因此也不能避免幻读的发生
  • SERIALIZABLE：事务在读取数据时，必须先对其加 表级共享锁 ，直到事务结束才释放；事务在更新数据时，必须先对其加 表级排他锁 ，直到事务结束才释放。
    • 此时，当对一张表进行读取的时候，会对读取的所有内容上长锁(共享锁)，因此事务B如果要对表中的内容进行修改，必须等事务A先提交以后，才可以获取排它锁并进行修改，因此也不会有新的内容产生、避免了幻读。
    • 这种序列化隔离条件，对并发性能的影响是很大的

思考题

下面的调度至高是在那种隔离级别下产生的调度？

R1(x)W2(x)C2 W1(x)C1

首先，不可能是Repeated Read,因为这种情况会给读操作上长锁，需要提交后才会释放锁，因此不可能在 R1(x)之后就发生W2(x)

那么可能是Read Commited吗? 在R1(x)处读上了短读锁，释放后在W2(x)上了一个长写锁，在C2结束后释放。然后在W1(x)处上了长写锁，在C1结束后释放。因此，Read Commited是可能发生的

并发控制

2PL

参考： https://zhuanlan.zhihu.com/p/480379228

引入

在事务并发的时候，我们需要找到一种机制来实现事务的冲突可串行化。那么2PL就是这样一种机制。它属于“悲观锁”，因为这个策略的核心就是：一个事务中，在拿到所有锁之前，不能释放锁。

一个朴素的加锁的方法如下：

流程如下：

  1. 在事务$T1$ 访问A之前，先通过DBMS的锁管理器（Lock Manager）获取A的锁并且注册（记录下来“A的锁当前归T1所有”）
  2. 事务T2想访问A，于是也要获得A的锁，锁管理器便会拒绝它的请求，T2之后便阻塞在这里
  3. 直到T1完成了对A的全部操作后通过锁管理器释放A的锁，T2才可以通过锁管理器获取A的锁，并且完成对A的全部操作后释放A的锁

Locks Type

事实上，数据库中有两种保护数据的方式： Locks 和 Latches 。

Latches 就是大家在学习多线程编程时接触到的锁，如 mutex、rwlock、semaphore、spinlock。用来做线程之间的并发控制。

数据库中的 locks 一般是指行锁、范围锁、表锁这些。用来做事务之间的并发控制。它保护的不是具体的数据结构，而是数据库的抽象的内容，比如说向锁管理器申请的可以是对数据库的表的某一行的锁，这个锁会保护涉及这一行的所有的索引里面关于这一行的部分

Locks Latches
Separate User Transactions(用来隔离事务) Threads(用来线程并发)
Protect Database Contents(数据库中持久化的内容) In-Memory Data Structures(内存中的数据结构)
During Entire Transactions Critical Sections
Modes Shared(共享锁), Exclusive(排他锁) Read(读锁)，Write(写锁)
Deadlock Detection & Resolution Avoidance
死锁解决方式 Waits-For, Time out, Aborts Coding Discipline
Kept in.. Lock Manager Protected Data Structure

我们在数据库中，主要用的是Lock，之前也说了Lock分为共享锁和排他锁两种：

  • S-Lock : Shared locks for reads , 和Latch中的读锁差不多
  • X-Lock : Exclusive locks for writes ，和Latch中的写锁差不多

在带有Lock的情况下，事务的执行过程如下：

  • 事务获取对应的锁
  • 锁管理器(Lock Manager) 授权或者阻塞事务
  • 事务释放锁

其中，LM内部有数据结构，记录着一张锁的表格，包括什么事务在用这个锁，是什么类型的锁，什么事务在等待用这个锁

以下场景就是用了 X/S 这两种锁，分别用来做A的读写操作：

但是仅仅通过加锁，能将原本不可串行化的执行调度的执行结果变正确吗？我们看到，在T1释放了锁以后，T2立马得到了X锁并对A进行修改，解这 T1再次获取S锁、读取A的时候，就会发现这个A并不是它最后修改的A。

这就是发生了不可重复读的错误。因此，后来的DBMS方面的学者专家们就在此之上进行改进，提出了两阶段锁来实现并发控制

Two-Phase Locking

两阶段所是一个并发控制协议，它规定了一个事务在运行的过程中如何跟其他事务之间协调锁，从而实现可串行化。使用两阶段锁不需要提前知道完整的执行调度，它会在调度进行的过程中避免不可串行化的情况发生

两阶段锁，顾名思义有两个阶段：

  • 增长阶段( Growing )
    • 在这个阶段，每个事务都只能不断的从LM那边获得锁，不能释放锁
    • LM可以根据情况给事务所需要的锁，或者阻塞事务(不给锁)
  • 缩小阶段 ( Shrinking )
    • 在这个阶段事务只能释放它之前拥有的锁，并且不能再获取新的锁

因此，在一个事务的生命周期里，它所持有的锁的数量的变化趋势如下所示，最后所有获取过的锁都被释放之后，会提交事务(Commit)

使用二阶段锁便可以使得不可串行化的执行调度的最终执行结果具有一致性，如下所示，在两阶段锁协议下，事务T1执行完W(A)后并不会立即释放A的锁，因为二阶段锁协议的规定就是“先一直获取各个锁，然后把所有获取的锁逐个释放”，直到R(A)执行完了之后T1才会释放锁（如果按照之前的策略，先获取X-Lock，再释放X-Lock，然后再获取S-Lock，之后再释放S-Lock，这就违反了两阶段锁的协议）

与此同时，在事务T1释放A的锁之前，事务T2获取A的锁的操作会被一直阻塞，直到T1把A的锁释放

在使用了二阶段锁协议后，相应的执行调度对应的依赖图（Dependency Graph）一定没有环，二阶段锁可以严格地保证冲突可串行化

级联回滚

但是二阶段锁也有一些问题：级联回滚（Cascading Aborts）

如下所示，T1释放锁之后，T2事务开始被执行，T2对A的操作是基于T1对A进行临时修改后的版本进行的，如果T1事务没有提交而是被abort了，那么T2必须跟着T1一起回滚（如果T2进行的是读操作，那么这也被称为脏读，”dirty reads”）

级联回滚本质上的原因是T2事务在T1事务更新得到的临时版本的数据上进行了操作，那我们可以通过一些手段让T2不在T1修改得到的临时版本上进行操作：

  • 可以让事务先获取各个需要获取的锁，等到它commit的时候，再一次性将这些锁释放掉，这样的话，T2就不可能再临时版本上进行操作。因为T2能获得锁并执行事务的时候，它所访问的一些数据已经被提交并持久化了。

因此，这个方法也叫做严格二阶段锁(Strong Strict 2PL,简称 SS2PL)

再严格二阶段锁协议下，事务所持有锁的数量变化，如下所示：

严格二阶段所协议的特点是事务所修改的数据在事务结束之前，其他事务都不能读写，这个协议的好处就是不会产生级联回滚。而且事务可能对数据进行了很多次更新，但在严格二阶段锁协议下，需要回滚时，直接回滚到事务开始时即可，不用管它进行过多少次更新，因为这个事务在进行数据更新时，绝对不会有其他的事务也在更新共享的数据

例子

举个例子： 事务T1是A给B转账100，事务T2是计算A和B的账户余额的和

  • 如果完全不适用二阶段锁，那么可能出现不一致的情况：

  • 如果使用二阶段锁协议

那就可以保证一致性，等效成T1事务先执行，然后T2事务执行，即冲突可串行化。但存在潜在的级联回滚问题

  • 如果使用了严格二阶段锁协议，如下所示，既可以保证一致性，也可以避免级联回滚

Venn图总结

我们可以将 视图可串行化, 冲突可串行化 , 严格二阶段锁 , 序列化 ,级联回滚 这几个概念组成一个Venn图

在全部可能发生的执行调度里, 事务串行执行是很小的子集，冲突可串行化的执行调度是更大的子集，视图可串行化的执行调度对应还要再大一点的子集

TO

TO(Timestamp Ordering)

OCC

OCC(Optimistic Concurrency Control) 是事务的乐观并发控制，乐观是说冲突没那么容易产生，因此只在事务要提交的时候去检测冲突。现在有很多内存数据库中采用这种机制，因为数据所有的操作都在内存里完成，事务的运行时间会缩短，因此出错的概率也会变小。从理论上来说，内存数据库中最佳的并发控制策略就是OCC。但是OCC也存在一些问题，比如说事务会经常重启(遇到错误时)，很多事务会一直达不到结束的条件，导致无法完成。

主要思路

OCC的基本思路是：每个事务会产生一个私有空间，并在里面维护事务中的读写集合。在事务提交的时候，验证读写集合是否与其他事务冲突，如果没有，则将写集合应用于数据;否则就把事务abort掉，再重做

另外，OCC为每个事务分配了一个时间戳，反映了事务的可串行化顺序，以方便验证

OCC的三个阶段

  • 读阶段
    • 执行事务，并在事务的私有空间生成事务的读写集合
  • 验证阶段
    • 提交之前，通过读写集合验证是否有冲突。这是整个策略的重点
  • 写阶段
    • 将写集合应用到数据，commit or abort

OCC例子

读阶段

读阶段生成读集合。 此时所有事务都是并发的

  • T1 有两步： T1.ReadSet={A}，T1.WriteSet={A}
  • T2有一步：T2.ReadSet={A}

验证阶段

在最原始的OCC中，只有读阶段是并发的，验证阶段和写阶段是阻塞的，因此当一个事务在验证或者写的时候，另外的事务是无法运作的。现在有些研究速度更快、并行度更高的验证规则。

一般来说，现在都会在验证阶段给事务分配时间戳，如下：

验证阶段的目标就是要保证事务的可串行化，即Ti需要和其他事务是否有读写冲突和写写冲突。

在验证的时候主要要关注三个时间点：事务开始(读阶段)时间、事务结束(写阶段)时间，验证阶段开始时间。由于…导致会有不同情况的出现，接下来我们来介绍几种在满足Ti<Tj之后可以提交事务Ti的情况

Case1
  • 要求：Ti在Tj事务开始之前完成写阶段

这很容易理解，时间戳示意图如下：

事务调度顺序如下：

这很容易理解，此时Ti和Tj是没有冲突的

Case2
  • 要求： $T_i$ 在 $T_j$的验证阶段开始前完成写阶段， 并且 $\text{WriteSet}(T_i)\cap \text{ReadSet}(T_j)=\empty$

第二种情况，相当于在Case1的基础上，将 tj事务左移了一段距离，如下：

注意，Ti的写集合和Tj的读集合的交集必须为空，否则会发生读写冲突。如下所示：我们看到，T1还没有提交关于B的修改，T2就开始读取B了，这时候就不是可串行化了。

那么有人要问了，如果T1的写集合是A，且在T1提交时T2才刚好读取A，看起来不会有问题，可行吗？其实这种也会被abort掉，因为毕竟是小概率事件，为了方便都会中止事务

Case3
  • 要求：$T_i $在$T_j$的读阶段结束前开始验证阶段， 并且
    • $\text{WriteSet}(T_i)\cap \text{ReadSet}(T_j)=\empty$
    • $\text{WriteSet}(T_i)\cap \text{WriteSet}(T_j)=\empty$

示意图如下：

第一个条件可以理解，和case 2是一样的，那么为什么要满足第二个条件呢？

因为如果两个事务的写集合发生重复，而且二者的写阶段也是可能发生重叠的，因此这个要求是为了避免写覆盖的发生。

OCC基本实现

事实上，在设计OCC的时候我们设计了 验证阶段+写阶段的临界区

  • 在临界区中，只能让一个事务的读阶段去和另外一个事务的读/写阶段去并行。
  • 因为临界区只能允许一个事务进入，因此所有事物之间的验证阶段和写阶段是互斥的
  • 因此，Case3实际不会出现

总结一下Case1和Case2：

  • Case1: Finish(Ti)<Start(Tj)
  • Case2: Start(Tj)<Finish(Ti)<Validation(Tj) ,且对$T_j$的读集合，需要验证他和所有满足上面范围的$T_i$的写集合是否有交集，这样就意味着只需要维护每个事物的写集合即可。
    • 这里不用写集合去和别人的读集合做验证的原因是，维护读集合的难度要比维护写集合要大得多

思考算法是如何巧妙利用时间戳实现Case1 和Case2的？

  • Case1， 事务开始获得当前时间戳start tn，在 比较时从start tn+1开始的事务去验证，因为 start tn之前的事务已经完成。
  • Case2， 事务再次获取当前时间戳finish tn, 因此所有在start tn与finish tn之间提交的事务都是满足 case2的。

伪代码如下：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
thegin = {
	create set := empty;
	read set := empty;
	write set := empty;
	delete set := empty;
	start tn := tnc //tnc是一个单调递增公共时间戳，事务一开始时就获取
}
// 临界区
tend = {
		< finish tn := tnc;
			valid := true;
			// 满足case2的条件的事务t(当前事务开始到上个事务结束这段时间)
			for t from start tn+1 to finish tn do
			// 这边用当前事务的读集合去和满足条件的t的写集合去做检查，即case2
				if(write set of transaction with transaction number t intersects read set)
						then valid := false;
				if valid
					then((write phase); tnc := tnc + 1; tn = tnc)>;
					
				if valid
						then (clean up);
				else (backup)
				
}

多版本并发控制

多版本是指：对某一数据项，数据库中存储其多个不同时间点上的状态(一次修改看做是一次状态)。不同的状态存储在链上

  • 每次写操作，创造一个新的版本
  • 每个读操作，通常事务开始时获取一个版本，读取小于等于该版本的最新数据，因此可以避免不可重复读的错误

多版本能实现读写分离(优点)：

  • 读不阻塞写
  • 写不阻塞读

SnapShot Isolation

SI既是一种实现，也是一种隔离级别(快照隔离级别)，为什么是快照？因为SnapShot读取的是数据库中的旧版本

SI流程如下：

  • 事务开始:
    • – Get snapshot 定义快照时间点
  • 事务执行:
    • Reads from snapshot 从快照中读取
    • Writes to private workspace
  • 事务提交:
    • Check for write-write conflicts
      • 如果有abort到只有一个事务提交
    • Install updates

例子：SI的版本变化

如上图，已知有三个提交: Commit T1,T2,T3，每次都会生成一个时间戳

日志

首先，我们先学习ACID与日志的关系——ACID那些性质与日志存在关系呢？显然是原子性和持久性

从单机数据库角度来说，需要使用日志的地方有很多——各种故障

  • 存储介质故障
  • 灾难性故障
  • 系统故障
    • 断电
    • 软件中止
    • 操作系统中止

不管是什么故障，有日志的存在，就能是数据库恢复到一致的状态，已经提交的事务就是持久化了,还没有提交的事务需要回滚

缓冲区策略与日志的关系

之前我们学过数据库中有个缓冲区，还写了一个BPManager的程序来进行lru调度。

现在我们来讨论一下事务、脏页、日志三者之间的关系，来看下图

  • Steal: 允许未提交事务刷入磁盘
  • Force: 只有事务的所有数据都刷入磁盘，事务才能提交

Steal/ No-Steal

现在来定义 No-Steal 策略，No-Steal是说在事务提交之前，页面不能被写入磁盘。这去报了我们不会让数据库处于一个中间状态——因为如果该事务没有完成，那么它的任何变化也不应该被持久化。但这个策略的缺陷在于它束缚了我们使用内存的方式，我们必须把每个脏页保留下来，直到一个事务完成——可能会占用大量内存空间

因此我们提出Steal策略，即允许在事务完成之前将修改过后的脏页写回到磁盘上。

Steal的例子如下，我们看到，在把A从100改为90的之后，还未提交就把A刷入了磁盘。就好像偷偷摸摸的把页给写到磁盘里去了

那么显然这种方法是有问题的，比如在这里修改了A，然后直接把A写回磁盘，这时候突然发生了系统故障。由于B还没有被修改，因此数据库需要回滚到A被修改前的状态。因此，这里需要用到Undo日志，记录修改前的状态。

Force/No Force

force是说在事务提交前强制所有修改过的数据页到磁盘， 这将确保耐久性。但是这种方法的缺点是性能不足，最终我们会做很多不必要的写操作。

因此No Force策略更加常用。这种策略是说，只在脏页要被从缓冲区删除的时候再写回磁盘。这样可以减少不必要的写入，但它是的数据库的持久性变得复杂。因为可能出现没有把脏页全刷回磁盘的情况，发生故障之后可能会导致数据丢失，因此需要Redo日志。

也就是说，日志需要记录修改后的值，这样一旦发生故障，可以通过Redo日志将数据库改为日志提交过后的状态，体现了数据库的持久性。

再回到上面那个四宫格，我们看到Force+No Steal策略是最方便的，最容易实现的。但是我们还是选择NoForce+Steal策略，虽然仅用这个策略无法满足持久性和原子性，但是可以获得最好的功能。至于如何实现原子性和持久性，我们就需要靠undo+redo日志来帮忙了

WAL日志

先写日志 WAL(write-ahead logging)，做一个操作之前先讲这件事情。

  1. 将对数据库的修改记录在单独的存储空间中（日志缓冲区） 日志缓冲区和数据缓冲区是两回事
  2. 日志只支持追加操作（顺序I/O）
  3. 修改的数据对象持久化之前，需要保证其对应的修改已记录在日志文件中(WAL)
  4. 日志落盘后事务即可提交 S2PL释放锁的时间呢？

日志生成的主要步骤：

  • 生成日志

  • 在缓冲区中占位（生成LSN）

  • 刷盘

    • 注意，在日志刷盘阶段，需要一组一组提交，因为每条日志刷盘的I/O代价比较高。因此需要多个事务的日志一起按批次刷盘。这样会减少I/O次数
  • 事务提交(可以理解为返回客户端，事务修改 对外部可见)

WAL实现

Redo引申出了WAL，即事务日志会在COMMIT或COMMIT之前写入持久化存储中，然后事务对数据本身的修改才能生效。因此就能够保证在系统故障时可以通过读取Redo日志来实现持久化操作(数据恢复)。
因此对于最终用户可以显示事务已经提交而暂时不用将所修改的数据写入持久化存储。由于数据在日志未写入持久化存储之前数据无法持久化，则需要更大的主存作为BUFFER空间，这就是为什么Redo的内存开销更大。

为了实现 WAL策略，我们需要在日志记录中添加一个字段——LSN。它代表了日志序列号，LSN是一个唯一的递增的数字，它有助于标志着操作的顺序(如果你看到一条LSN=20的日志记录，那么该操作一定是发生在LSN=10的记录之后的)。我们还将为每条日志记录添加一个prevLSN字段，该字段存储了同一事务的最后一次操作，这对撤销一个交易来说是很有用的。

数据库还将跟踪存储在RAM中的flushedLSN。flushedLSN追踪最后一条被刷入磁盘的日志记录的LSN，它意味着该页已经被写入磁盘，也意味着在内存中我们不再需要这个页了。

我们还将为每个数据页添加一段元数据，称为pageLSN。pageLSN 存储了最后修改该页的操作的LSN。我们将用它来告诉我们哪些操作的操作，以及哪些操作必须重做。

ARIES Recovery Algorithm

当数据库系统崩溃之后，我们只能获得数据库写到磁盘中去的数据页和日志。在重启之后，我们要对数据库进行恢复，达到两个目标：

  • 所有已经提交的事务，都要恢复到提交事务之后的状态(持久性)
  • 所有未提交的事务，都要恢复到事务执行之前的状态(原子性)

这个算法就是说在No Force和Steal的情况下，如何将数据库日志恢复到上面两个状态.这个算法主要分为三个阶段：

  1. Analysis Phase: 重新构建 transaction table 和 DPT

  2. Redo Phase: 重复提交后却未写回的操作，以实现持久性

  3. Undo Phase：撤销未提交但已写回的事务操作，以保证事务的持久性

首先我们来说说 transaction table 和 DPT是什么：

transaction table

Transaction table 记录了活跃的事务的相关信息，它有三个字段。活跃事务表示用来做undo的，因为

  • XID: 事务 ID
  • status: either running, committing, or aborting
  • lastLSN: the LSN of the most recent operation for this transaction

Dirty Page Table (DPT)

DPT记录了那些页是脏页(被修改过后的), 它有两个字段。脏页表主要是用来做Redo的

  • Page ID

  • recLSN: 第一个产生这个脏页的LSN

Analyse phase

Analyse phase 就是把系统crush的那一瞬间的两张表给重构出来。为了实现这个操作，我们需要扫描所有的日志记录。下面是遇到各种日志的处理方法

  • 任何只要不是END的记录，就说明该事务尚未结束，就需要将其加入到transaction Table中，同时设置LSN为当前记录的LSN
  • 如果该记录是COMMIT或者是ABORT，那么就修改相应transaction在transaction Table中的记录(修改状态)
  • 如果该记录是UPDATE，而且日志中对应的页不再DPT当中，说明发现了一个新的脏页。那么就要把这页加到DPT中并设置recLSN=该日志的LSN
  • 如果该记录是END，那就从transaction表中删除该事务

在Analyse phase的最后阶段，对于任何正在COMMIT的事务，他只是在等待提交罢了，对数据的修改、更新操作都已经做完了(相当于END)，因此我们需要把 END记录到日志中，并从transaction表中删除该事务。最终只会让ABORT或者RUNNING的事务留在transaction表中

如果我们按照上面的操作，老老实实得把数据库日志从头到尾扫描一遍，显然这样的性能很低，不切实际。因此我们可以用到checkpoint，它像一个快照一样，每隔一段时间会把transaction Table和DPT记录在日志中。

我们来举一个例子:

下面这张图是我们要恢复数据库时从磁盘中提出来的数据，左侧是日志，看到LSN50是Begin Checkpoint，说明在这一时刻开始形成一个快照，LSN50之前的transaction Table和DPT都会保存下来。检查点在LSN80处生成结束。

右侧就是从检查点提出的transaction Table和DPT，但是这两张表记录的信息是不全的，我们要从LSN60处开始复原重构两张表

  1. 首先，我们从LSN60开始构建，它记录了T3事务对P3页进行了update。因为P3已经在DPT中，因此不用改。但是它更新了transaction Table中的T3记录，需要将字段lastLSN改为当前LSN（即60)

  1. LSN70是 T3的 Aborts，因此修改 transaction Table中的T3记录，将Status改为Aborts即可

  1. LSN90是也是一条动作，就是把T3 Update P3给撤销了，因此需要更新transaction Table中的T3记录，将lastLSN改为90

  1. LSN100是T1事务对P4页做的Update操作，DPT中没有P1，因此需要把P4加入DPT；同时要更新transaction Table的T1记录，将lastLSN更新为100

  1. LSN110是T1事务的提交，因此更新transaction Table T1记录，将Status改为 Committing

  1. LSN120是T1事务的结束，因此可以从transaction Table中删除T1记录

Redo phase

Redo phase使用来保证持久化的，我们从DPT中最小的recLSN记录开始，因为那是时可能还没有进行第一个刷盘的操作。

我们将会redo所有的Update操作和CLR操作 ，如果某一个LSN符合下面三条中的一条，那么就跳过：

  • 该页不再DPT中，意味着所有对该页修改都已经持久化到磁盘了
  • 如果 recLSN > LSN， 因为正常情况下LSN是大于等于 recLSN的，如果recLSN > LSN,说明污染该页的第一个动作要比当前的LSN发生的更晚，因次当前LSN并不需要被redo
  • pageLSN(disk) >= LSN, 因为pageLSN记录了最后修改该页的操作日志，如果大于LSN的话，那说明并不需要redo当前的LSN

现在复原了两张表，transaction Table是要做Undo操作的，DPT是要做Redo的。

那么，应该从哪里开始恢复操作呢？DPT中最小的recLSN是 10，因此我们从LSN10开始看。

  • LSN10 : 更新 P3
  • LSN20 ：P1.recLSN=40 > 20, 跳过
  • LSN30: Page2不再DPT中，因此跳过
  • LSN40: P1.recLSN=40 = 40 , 执行update p1操作
  • LSN50: 跳过
  • LSN60：符合条件，更新P3
  • LSN70: 只redo Update操作和CLR操作
  • LSN80: 跳过
  • LSN90: 执行CLR操作
  • LSN100: P4.recLSN=100==LSN,因此执行更新P4操作
  • LSN110-LSN120: 跳过

Undo phase

Undo 阶段和Redo阶段的起始位置不同 ，Undo是从Transaction Table中各个事务的LastLSN往前回滚。

我们要做的是把transaction Table中没有完成的事务给回滚掉。其具体操作就是：撤销所有在transaction Table中所有事务的Update操作。使数据其从中间态恢复到事务执行前的状态

还是以上图为例，我们看到transaction Table中有T2和T3是需要回滚的。对于每个需要回滚的事务，直接从lastLSN开始。

  • 对于T2，我们可以直接从LSN30开始回滚
  • 对于T3，我们可以从LSN90 开始回滚

注意，回滚也会记录日志：

总结

-------------本文结束，感谢您的阅读-------------