数据库并发控制

为什么需要并发控制？#

ACID 是数据库事务需要保证的四个特性。
从定义出发，数据库事务本身就具有原子性。
在理想的事务模型中，如果所有的数据库事务都是瞬间完成。那么他也会同时具有一致性以及隔离性，因为不会影响到其他事务。
loading...
如果任何修改都可以立即写入到存储位置，那么就具有持久性。
但是现实终究不是理想的模型。事务的完成不可能是一瞬间的事情。它可能需要大量的操作才可以进行。
那么退而求其次。
loading...
一个完全串行的事务执行流程也是正确的，也可以保证一致性和隔离性。
但问题是，它太慢了。所以会引入事务的并发执行，以提高事务执行的性能。
loading...
如果像上图一样，两个事务操作的对象完全不相关。那么事务tx1和tx2之间可以随意的乱序执行。
但是事务之间有关系才是常态，随意的并发必然会导致严重的问题，因此需要进行并发控制，使得在并发执行的同时，尽量保证事务的正确性。

并发控制需要解决什么样的问题？#

如果对事务进行抽象，那就是对一个或多个对象进行读或写的操作序列。
一个基本操作就是 R(obj) 或 W(obj)。
并发控制需要解决不同事务之间操作同一对象而产生的冲突。

Read Write Conflict(unrepeatable read)

loading...
如图，tx1 先于tx2开始执行，理论上 在 ts3 读取到的内容应当与ts1读取到的内容一致。
但是 tx2 在 ts2 处更新了 u，如果不做任何的并发控制，就会导致读取到不一致的内容。产生了读写冲突。

Write Read Conflict

loading...
如图，tx1 先于tx2开始执行，理论上，tx2 在 ts2 读取的内容，应当是tx在ts3写入后的内容。如果不做任何的并发控制，就会导致tx2读取到还没来得及更新的旧数据。产生了写读冲突。

Dirty Read

loading...

如图，tx1 先于tx2开始执行，理论上，tx2 在 ts2 读取的内容是正确的，但是因为最终tx1被回滚了，tx2 在 ts2 读取的内容是应当是tx1在ts1写入前的内容。如果不做任何的并发控制，就会导致tx2读取到错误的脏数据。产生了脏读。

Write-Write Conflict(lost update)

loading...

如图，tx1 先于tx2开始执行，理论上，tx2写入的内容会覆盖 tx1 写入的内容。如果不做任何的并发控制，就会导致tx1写入的内容覆盖 tx2 写入的内容。产生了覆盖。

并发控制的思路#

为了实现正确的并发控制，有两大类思路，悲观或乐观。
悲剧的并发控制会假设冲突是经常发生的，因此会采取措施避免冲突的发生。
乐观的并发控制则假设冲突是偶尔发生的，且不会造成太大的影响，因此会允许冲突发生，并在检测到冲突发生的时候去解决冲突。
从结果出发，并发控制就是要对并发中执行的操作进行合理的安排，使得在尽可能提高并发性的条件下，保证其正确性。我们将这样的一个安排称为：执行排期 (execution schedule，为避免与执行计划混淆使用编排一词)。
那么问题就是如何生成一个正确且高效的执行排期，让这个排期可以等效于串行执行排期。
在学术中有如下定义：

• 串行排期：不同事务间不会相互交错，事务就是串行执行。注意，串行排期可能有多种，比如 T1,T2 或者 T2,T1，尽管结果不同，但是都是正确的。
• 等价排期：对于两个排期，执行期间，两个排期中事务对数据库的状态更改都是相同的，就称为等价排期。
• 可串行化排期：一个排期等价于一个串行排期，就称其可串行化。

消除上面列举的冲突。

关于可串行化有两种类型：冲突可串行化和视图可串行化。无论是哪种定义，都不能涵盖所有可串行化的调度。实践中，DBMS 更多冲突可串行化，因为很有效。
loading...
冲突可串行化：
首先定义冲突等效：如果两个排期涉及相同事务的相同操作，且其中每对冲突操作在两个排期中的排序相同。就称为冲突等效。
如果一个排期与某个串行排期冲突等效，那它就是可串行化排期。
验证方式：

1. 尝试交换非冲突操作直到形成一个串行排期，有用，正确，但低效。
2. 使用依赖图。
   在一个排期中，将事务当作图中节点，如果 Ti 的操作的操作 Oi 与 Tj 的操作 Oj 冲突，且Oi时间上先于Oj，则将其当作一条从 Ti 到 Tj 的有向边。
   如果一个排期生成的依赖图是有向无环图，则是可串行排期。
   视图可串行化：
   相比冲突可串行化要求更弱。存在一些排期，尽管生成的依赖图不是有向无环图，但仍然是可串行排期。其中有一部分排期，其部分事务存在盲写行为（也就是事务不是先读后写，而是直接写入）。

权衡#

显然要同时提高并发速度和解决以上的事务冲突是个两难问题，而现实生活中，面对不同的场景，我们是可以有不同的容错能力的。比如对于银行事务，我门希望完全准确，不能有半点差错。但是对于社交媒体中的一个指标，比如点击量。我们可以允许一定的差错，9000 个和 9001 个差别并不大，即使漏掉一两个也是可以接受的。因此面对问题，通过定义隔离级别以适配不同的场景。比如 ANSI-92 SQL 标准定义了隔离性的四个级别。

ANSI-92 SQL Standard#

contrib.andrew.cmu.edu/~shadow/sql/sql1992.txt
隔离级别指定在并发 SQL 事务执行期间可能出现的情况。

ANSI 92 定义的现象#

脏读

loading...
如图，tx1 先于tx2开始执行，理论上，tx2 在 ts2 读取的内容是正确的，但是因为最终tx1被回滚了，tx2 在 ts2 读取的内容是应当是tx1在ts1写入前的内容。如果不做任何的并发控制，就会导致tx2读取到错误的脏数据。产生了脏读。

不可重复读，幻读

这两个现象都是读写冲突，都是读取内容前后不一致，但表现略有不同。

loading...
如图，tx1 先于tx2开始执行，理论上 在 ts3 读取到的内容应当与ts1读取到的内容一致。
但是 tx2 在 ts2 处更新了 u，如果不做任何的并发控制，就会导致读取到不一致的内容。产生了读写冲突。
如果tx2进行W(u)是删除结果集中的部分数据，则tx1第一次读取到的数据要多于第二次，则称为不可重复读。
如果tx2进行W(u)是新增结果集中的部分数据，则tx1第一次读取到的数据要少于第二次，则称为幻读。
针对

ANSI 92 定义的隔离级别#

针对这不同的三个现象，定义了四种隔离级别。要达到特定级别，必须要解决对应的问题。比如读已提交，如果一个数据库的并发控制实现可以防止脏读的情况发生，那么就称其达到了 Read Committed 级别。