CigaCase
0%

CMU15-445-2022Fall-Lecture-15

发表于

Lecture 15: Concurrency Control Theory

主要介绍了并发控制的原理

Transaction Managment

首先是一些常见的数据库事务上会出现的并发问题：

比如对于以下一系列操作：

1
2
3
4
5
Read(A)
Check(A > 25)
Pay(25)
A = A - 25
Write(A)
  • 如果执行到A = A - 25的时候，突然发生了断电，那么很有可能银行就收不到钱（这个其实和恢复系统有关系）
  • 如果某个人同时执行了两个相同的该操作，则如果他们同时从数据库中读取了A=100，最终A会变成75（即少扣了25）

最基础最笨拙的解决这些问题的方式就是让数据库将所有的事务排成一个队列依次执行，只有当前一个事务执行完毕、数据写会，再执行下一个事务，但是这样就会丧失数据库的并发性，还会占用大量的存储（因为我们需要把整个数据库文件进行复制）

因此我们需要数据库支持并发控制，并且在此基础上要保证数据的正确性和公平性

Transaction

在正式开始之前，需要明确一下事务的定义。从正式一点的定义上来说，数据库是由一组组固定的命名对象A、B、C组成的，而事务就是对这些对象的一系列处理（比如说读写、插入、删除）

以Sql语言为例，事务的起点会显式地用BEGIN来表示，而结束一般由成功的提交（COMMIT）或者报错（ABORT），如果事务提交，数据库会保存事务所做的所有修改（或者引发报错）；而如果事务报错，那么所有修改都将不复存在，数据库会进行回滚操作

Correctness Criteria：ACID

事务的正确性标准被称为ACID

  • 原子性（Atomicity）：事务是一个不可分割的工作单位，事务中的操作要么全部成功，要么全部失败
  • 一致性（Consistency）：事务必须使数据库从一个一致性状态变换到另外一个一致性状态
  • 隔离性（Isolation）：多个事务并发执行就像事务单独执行一样并不会相互影响
  • 持久性（Durability）：持久性是指一个事务一旦被提交，它对数据库中数据的改变就是永久性的，接下来即使数据库发生故障也不应该对其有任何影响

Atomicity

事务只有两种可能的输出：提交和报错，要么完成所有的修改，要么所有的修改都不执行

那么该如何保证原子性：

Logging

日志技术几乎在所有的DBMS中都会被使用到，其中有UndoLog（回滚未提交的操作）和RedoLog（执行已经提交的操作）

DBMS在日志中按照顺序记录了事务所作出的所有修改，然后Undo所有报错事务已经执行了的操作

Shadow Paging

在事务执行之前，DBMS首先复制相关的page，让事务修改其中的数据，当且仅当事务正确提交之后，这些page才会对外可见

Consistency

如果 DBMS 在事务开始之前是 consistent，那么在事务执行完毕后也应当是 consistent

比如对于一个银行所使用的数据库，至少钱的数值不能小于100，如果a有90块钱，他想转100给b，此时，事务提交之前符合数据库的规则，但是在提交之后就不符合了，那么此时事务就不能够提交，这就是所谓的一致性

  • 数据库一致性：数据库中的数据是对现实世界中的模拟，并且满足约束的规则

  • 事务一致性：事务执行前后数据库均满足一致性

Isolation

用户提交事务，不同事务执行过程应当互相隔离，互不影响，每个事务都认为只有自己在执行

并发控制协议

为了达到并发执行事务的目的，我们需要并发控制协议，包含两种锁

  • 乐观锁：假设事物之间的冲突是罕见的，当冲突发生之后再进行处理
  • 悲观锁：事务执行时获取需要的锁，这样不会导致冲突的发生

事务并发顺序的正确性

为了保证结果的正确性，并发执行的顺序必须等同于某种串行的顺序

  • Serial Schedule：不同事务之间没有重叠，串行执行
  • Equivalent Schedules：对于任意数据库起始状态，若两个调度分别执行所到达的数据库最终状态相同，则称这两个调度等价
  • Serializable Schedule：如果一个 schedule 与事务之间的某种 serial execution 的效果一致，则称该 schedule 为 serializable schedule

事务冲突

两个不同的事务指向了同一个对象，如果其中一个对对象有写操作，则会产生冲突

  • 读写冲突：事务先A读取某行数据、事务B后修改该行数据，和事务B先修改某行事务、事务A后读该行记录两种schedule。事务A读到的结果不同。这种冲突可能会导致Unrepeatable Read（不可重复读，两次读取的数据可能不一样）和Dirty Read（脏读，一个事务读取了另一个事务还没有提交的数据）
  • 写读冲突：读未提交（脏读）
  • 写写冲突：Lost Update（更新丢失，一个事务将另一个事务的未提交的数据覆盖）

冲突串行化

冲突的串行化执行可以通过一定的转换为某种串行化的结果

  • 两个 schedules 在 transactions 中有相同的 actions，且每组 conflicting actions 按照相同顺序排列，则称它们为 conflict equivalent
  • 一个 schedule S 如果与某个 serial schedule 是 conflict equivalent，则称 S 是 conflict serializable
  • 如果通过交换不同 transactions 中连续的 non-conflicting operations 可以将 S 转化成 serial schedule，则称 S 是 conflict serializable