# Transactions

## 概要

事务是数据库提供给应用层的一层抽象，这层抽象将所有的并发问题和软硬件的其它各种可能的错误隐藏，只暴露出两种状态，要么成功 (commit)、要么中止 (abort)。有了事务支持，应用的逻辑变得十分简单 --- 发现事务 abort 重试即可。

没有事务抽象，应用可能面临的一系列问题。若应用读写数据的逻辑简单，没有事务也可正确运行；若应用有比较复杂的数据读写逻辑，有事务的支持能够大大帮助应用开发者减少思维负担和犯错的几率。

不同的事务可能同时执行，事务之间可能存在共享的数据，这时如果随意让事务并发执行可能产生各种意料之外的数据状态。因此，本节接着通过以多种竞争条件 (race conditions) 为例，讨论常见的事务的三种隔离级别 (isolation levels)，即 read committed、snapshot/repeatable read 以及 serializable。相关竞争条件罗列如下：

| 竞争条件                           | 描述                                                                                                 | 最低有效隔离级别                |
| ------------------------------ | -------------------------------------------------------------------------------------------------- | ----------------------- |
| Dirty Read                     | clientA 读到 clientB 写入但还未 commit 的数据                                                                | Read Committed          |
| Dirty Writes                   | clientA 覆盖 clientB 写入但还未 commit 的数据                                                                | Read Committed          |
| Read Skew/Non-repeatable Reads | client 在事务进行的不同时间点上读取不同状态的数据                                                                       | Snapshot Isolation      |
| Lost Updates                   | clientA 和 clientB 同时执行一个 read-modify-write 事务，clientA 在 clientB 不知情的情况下覆盖了 clientB 写入的数据，数据丢失且失去记录 | Snapshot Isolation      |
| Phantom Reads                  | clientA 根据某种搜索条件读取一组数据，同时 clientB 正执行的写操作改变着 clientA 读取的数据集合                                       | Snapshot Isolation      |
| Write Skew                     | clientA 读取某数据，并根据该数据的值做出另一个写数据的决定，然而在 clientA 写数据时，它读取的数据被 clientB 写入新的值，这使得 clientA 之前的决定的假设不成立   | Serialization Isolation |

弱事务隔离级别只能保护应用不受以上竞争条件中的部分情况影响，因此应用开发者需要对数据库提供的保证有正确的了解，只有 serializable isolation 可以防止以上所有竞争条件带来的影响。

最后，本节将讨论三种实现 serializable isolation 的方法：

* Serial Execution
* Two-phase locking (2PL)
* Serializable snapshot isolation (SSI)

尽管本节以关系型数据模型为例，但实际上不论使用什么样的数据模型，事务都是应用开发者迫切需要的一种特性。

## 引入

现实的数据系统需要面对许多问题：

* 数据库软件、硬件可能在任何时候故障 (包括在写操作进行到一半的时候)
* 应用可能在任何时候崩溃
* 网络扰动可能在任何时候阻隔应用与数据库、数据库节点与节点之间的连接
* 多个 clients 之间可能发生各种竞争条件，导致相应的 bugs 出现

为变得更可靠，系统需要正确地处理这些故障，保证它们不给整个系统带来灾难性的问题。但由于故障的情形太多，测试太复杂、思维负担过高，数据库系统普遍通过事务 (transactions, txns) 的抽象来简化问题。应用可以通过事务将一组读写操作打包成一个逻辑单元。从理论上说，一个事务内的所有读写操作可以被看作是一个大的操作，这个操作不可被分割，要么成功 (commit)、要么失败 (abort/rollback)。如果失败，应用可以安全地重试。于是，对于应用来说逻辑变得十分简单，无需考虑多个操作执行到一半时失败 (partial failure) 的问题。

值得一提的是，并非所有应用都需要事务，事务会增加数据库的运行成本，降低性能，有时候使用更弱的事务保证或者抛弃事务本身，能够获得更好的结果。在此之前，你需要充分了解不同数据库的事务功能提供的保证，从而正确地使用它。

## 事务的含义

在市面上，几乎所有的关系型数据库、以及部分的非关系型数据库支持事务。大多数关系型数据库的事务都根源于 IBM 在 1975 年推出的第一个关系型数据库 System R，包括 MySQL、PostgreSQL、Oracle 以及 SQL Server。虽然现在实现可能有所不同，但基本原理不会改变。

在 20 世纪末，非关系型数据库开始流行，它们的出现旨在提供新的数据数据模型支持，同时默认支持数据库的复制与分区 (分库分表)。在这场运动中，事务成了最大的牺牲者，许多新一代数据库抛弃或弱化对事务的支持。一种观点在开发者之间流行起来：”事务是系统扩展性的障碍，大型系统必须抛弃事务来保证性能和高可用“。这种看法过于极端，事实上，事务有自己的优势和局限性，为了更好的理解这其中的利弊权衡，我们首先需要了解事务能够向开发者提供什么样的保证。

### ACID

事务提供的安全保证通常描述为 ACID，即原子性 (Atomicity)、一致性 (Consistency)、隔离性 (Isolation) 和持久性 (Durability)。然而，不同数据库的 ACID 实现并不等价，比如隔离性在不同数据库中的含义不同。宏观上看，ACID 让人觉得安全可靠，但坑都埋在细节中等你去踩。我们无法将 ACID 看作是一种标准，而只能将它看作是市场营销的术语。一些无法提供 ACID 保证的数据库系统通常描述为 BASE，即基本可用 (Basically Available)、状态不定 (Soft State) 和最终一致 (Eventual Consistency)，然而 BASE 的定义比 ACID 更加模糊，几乎三个关键词都不是确定性描述。

#### 原子性

广泛地说，原子性指的是某个东西无法被分解成更小的部分。但具体到每个领域，它的含义可能略有不同。比如在多线程编程中，如果一个线程 A 执行一个原子操作 OP，这意味着其它线程无法看到 OP 执行到一半的中间结果，对于系统来说，OP 要么执行，要么不执行。\
而在 ACID 背景下的原子性与多线程并发并无关系，后者的行为由隔离性来描述。ACID 中的原子性通常是站在应用开发者的角度上看，如果应用想执行一系列写操作，但如果其中某次写操作失败，对于应用开发者来说将是灾难。如果可以将这些写操作打包成一个原子操作，要么成功，要么失败，一切都变得简单。

#### 一致性

一致性的概念出现在许多地方：

* 数据库复制中异步复制的一致性
* 负载均衡中的一致性哈希
* CAP theorem 中的 C
* ACID 中的 C

ACID 中的 C 指的是存储在数据库中的数据的内在不变性 (invariants)，比如在会计系统中，债务和债权必须相等。如果一个事务在执行前数据库的状态是合法的，那么在事务执行后它的状态也必将合法。实际上，数据库只能提供最基本的不变性检查，如唯一性、外键等，因此这里的一致性实际上需要由应用本身来保证，数据库无法阻止应用写入不合法的数据。因此在 ACID 中，实际上只有 A、I、D 是完全属于数据库本身。

#### 隔离性

大部分数据库都支持同时处理多个 clients 的请求。如果这些 clients 读写的分别都是数据库的不同部分，则无需担忧；但如果 clients 读写同一部分数据，就可能遇到并发问题，即不同的竞争条件。举例如下：

![](/files/-LfvyN0lV2fPWMKUAZ0I)

假设 user1 和 user2 同时想给数据库中的某个值增加 1，就有可能出现上图中的现象。

隔离性意味着并发执行的事务之间不可见，它们无法坑到对方。在经典数据库书籍中，隔离性指的是可序列化 (serializability)，即所有事务可以被认为是数据库中唯一执行的事务，数据库能够保证所有事务执行的结果跟它们按照某种顺序排列后顺序执行的效果一致。然而在实践中，出于性能考量，可序列化的隔离性很少被使用。

#### 持久性

数据库系统是数据安全存放的地方，不论是否出现硬件故障、软件故障甚至断电等各种意外。只要数据已经写入数据库中，数据库就应当保证它的持久性。

在单节点数据库中，持久性通常意味着数据已被写入非易失性存储设备，如 drive 或 SSD。实现上通常需要引入预写日志 (WAL) 或类似的模块来帮助数据库在故障发生后能够恢复。在多节点数据库集群中，持久性意味着数据已经成功被复制到指定数量的节点中，为了保证持久性，数据库需要等待数据成功复制到指定数量的节点后才能返回事务成功的消息给 clients。

完美的持久性并不存在，一旦所有节点、以及备用节点的硬盘同时损坏，显然这时持久性无法保证。

### 单对象/多对象操作

ACID 中介绍的原子性和隔离性，通常是针对多对象操作而言，即涉及到多个对象的事务读写相同数据。假设在某个邮箱应用中有这样一条查询语句，查询某个用户未读消息总数：

```sql
SELECT COUNT(*) FROM emails WHERE recipient_id=2 AND unread_flag = true;
```

**场景1**：在查询过程中可能有新的邮件进入收件箱，也有可能有邮件被标记成已读，如下图所示：

![](/files/-Lg0Al7apPL2R3YAg2e-)

这时，user2 可能在收件箱中看到一封未读邮件，但是页面中未读邮件的数量显示为 0（dirty reads）。这就需要隔离性来保证对于其它事务来说，user1 的事务要么全部执行，要么全部未执行。

场景2：如果在 user1 事务发生的过程中，出现错误，如下图所示：

![](/files/-Lg0Bq6m7XQm8YTrOxHg)

就可能出现数据不一致现象，这就需要原子性来保证错误发生前的写入操作全部回滚。

#### 单对象写

实际上，原子性和隔离性对单对象写操作同样适用。比如当你将 20KB 的 JSON 文档写入数据库，有可能出现以下问题：

* 网络扰动，只有前 10KB 发送成功，数据库要存吗（原子）
* 在数据库将文档写入硬盘的过程中断电了，新老数据在硬盘中各存一半（原子）
* 另外一个 client 在写入的过程读取这个文档，会读到部分数据吗（隔离）

显然上面的数据半成品不应当被保留或展示，这时候就需要原子性和隔离性的保证。一些数据库甚至提供原子性自增、compare-and-set 操作来避免 read-modify-write 的并发问题。

尽管在单对象写上，原子性和隔离性至关重要，但通常意义上的 ACID 是对多对象操作而言。

#### 多对象事务的重要性

由于实现上可能影响到数据库服务的高可用和性能，许多分布式数据库放弃对多对象事务的支持，然而这并不能成为放弃事务的理由。尽管某些情形下，我们可以只使用 key-value 数据模型和单对象操作，但在许多其它的场景下，写多个对象很难避免：

* 在关系型数据模型 (relational data model) 中，某表中的某行可能有外键链接到另一张表。多对象事务能够保证这些引用持续有效
* 在文档型数据模型 (document data model) 中，需要更新的多个字段可能在单个文档中，而单个文档可以被看作是一个对象，此时不需要多对象事务支持。然而在文档型数据模型中，通常鼓励用户将模型反规范化 (denormalization)，这个过程中就可能出现邮箱应用中的问题，未读邮件的数量和邮件分开两个 collections 存储，这时就需要多对象事务支持。
* 在支持二级索引 (secondary indexes) 的数据库中，多个索引需要同时被更新。这在某种程度上也是一种多对象事务，否则可能出现某些数据在索引 A 上能找到，而在索引 B 上找不到的现象。

即便上述应用中，也有可能在没有事务支持的前提下构建，但应用层需要自己处理操作错误和并发问题。

#### 错误处理和中止

ACID 数据库的设计都遵循这样一个哲学：如果数据库的状态违背了原子性、隔离性和持久性的保证，就应当将当前事务回滚，不允许中间状态的出现。

事务被中止后，应用程序可以通过简单地重试，但这种机制并非完美：

* 如果事务实际上已经成功，但网络中断，客户端超时重试，就可能导致事务被执行两次。那么应用层需要额外做一层去重，或者保证事务具备幂等的性质。
* 如果错误的原因是服务器负载过高，重试事务将使得问题变得更严重。为了避免这种问题，可以限制重试的次数，使用 exponential backoff 策略，甚至将负载过高的错误与其它错误分开单独处理。
* 重试只有在发生临时故障的情况下有效，如死锁、违反隔离性、网络中断、故障转移等；而在永久故障面前则没有意义，如数据不符合要求等。
* 如果事务进行过程中还发生在数据库之外的副作用，那么数据库中止事务时对这些副作用无能为力。比如发送 email，你当然不希望每次重试都发送一封 email。如果你希望保证多个系统要么一起 commit、要么一起 abort，可以使用 two-phase commit。
* 如果 client 在重试的过程中崩溃，即将写入的数据就会丢失。

## 弱隔离级别 (Weak Isolation Levels)

在实践中，支持事务隔离并不简单。由于可序列化隔离 (Serializable Isolation) 会影响性能，大部分数据库不愿意为此付出代价，因此常见的数据库会选择支持更弱的隔离级别，保证部分并发问题不会发生，通常这些弱隔离级别更难理解，稍有不慎就可能陷入更微妙的 bugs 中。本节将介绍，在没有事务隔离支持的条件下，一些常见的并发问题，以此引出不同的弱隔离级别。

### Read Committed

read committed 隔离提出两项保证：

1. no dirty reads：从数据库读取的数据都是 committed 的数据
2. no dirty writes：将数据写入数据库，只会覆盖已经被 committed 的数据

#### No Dirty Reads

假设事务 A 正向数据库中写入数据，但 A 尚未 commit 也未 abort，事务 B 能读到 A 写入的数据吗？如果能看到，就称为 dirty read。还有一种 dirty read 场景，如果事务 A abort，需要回滚数据，事务 B 就有可能看到数据出现又消失。Read Committed 隔离级别可以防止 dirty read 的发生，即 B 只能在 A commit 之后才能看见 A 写入的值，如下图所示：

![](/files/-Lg5Fw8B1Lk7HVzzrTS1)

在 user1 的事务 commit 之前，user2 读到的永远是 2。

#### No Dirty Writes

假设事务 A 正向数据库写入数据，但 A 尚未 commit 也未 abort，事务 B 同样写入数据，它能覆盖事务 A 写入的数据吗？如果能覆盖，就称为 dirty write。Read Committed 隔离级别可以防止 dirty write 的发生，即 B 只能在 A commit 之后才能覆盖 A 写入的值，通常事务 B 会被推迟到 A commit 或 abort 之后执行。实际场景如下图所示：

![](/files/-Lg5HtvaM-Wat6ZW16bO)

Alice 和 Bob 同时下单购买一辆车，买一辆车涉及到两次数据库写：

* 网站车辆列表需要更新买家
* 发货单需要发送给买家

在图中，Bob 在网站上更新为买家，但发货单却发给了 Alice。这是 dirty read 问题所致，可以在 Read Committed 隔离级别上阻止。

想象另外一个场景，两个事务同时将一个字段 +1，如之前提到的邮箱应用，收到邮件后更新未读邮件的计数，假设事务 A 读取 70，写入 71，事务 B 也读取 70 写入 71，由于事务 B 的写入发生在事务 A commit 之后，这并不是脏写，因此 Read Committed 隔离级别无法阻止这种现象发生。

#### 实现 Read Committed 隔离

Read Committed 是非常流行的隔离级别，是 Oracle、PostgreSQL、SQL Server2012、MemSQL 的默认选项。

*prevent dirty writes*

最常见的阻止脏写的方法就是使用行级别锁 (row-level locks)：当事务 A 想要修改 table 中的一行或者 collection 中的一个文档，它需要先获得相应的锁，然后持有这个锁直到事务结束。由于只有一个事务能够持有锁，其它想要写入数据的事务就只能等待事务 A 释放锁。

*prevent dirty reads*

我们可以依样画葫芦，当事务 A 想要读取 table 中的一行或者 collection 中的一个文档，也要先获取行级别锁，这种方式可以解决问题，但假如有一个事件很长的写事务正在进行，所有的数据读取事务都将被阻塞，从而降低的数据库的响应时间，应用的一个部分阻塞可能导致整个应用的雪崩。因此通常数据库不会用这种方式阻止脏读。\
实践中的典型做法是，当写事务 A 正在进行时，数据库会自动保存一份旧的数据供其它事务读取直到 A 结束，在此期间其它事务可以放心地读，无需加锁。当 A 结束时，数据库才将读请求转移到新数据上，清理旧数据。

### Snapshot Isolation and Repeatable Read

想象以下场景：

![](/files/-Lg64-6q2iH1We-AbiaO)

Alice 在银行存着 1000 元，分成两个账户 A、B，每个账户各 500 元。这时候她从 A 账户转 100 元到 B 账户，如果恰好当这个转账事务执行的过程中，Alice 分别查询两个账户中的钱，就可能出现如上所示的问题，A 账户中只有 500 元，B 账户中有 400 元，总量少于 1000 元。这种现象称为 nonrepeatable read/read skew。read skew 现象在 Commited Read 隔离级别可能出现。当然，本例在现实场景中是可以被容忍的，Alice 只要再刷新一次网页就能够看到正确的账户余额，但有些场景不能容忍这种短暂的数据不一致现象，如：

* 备份：备份数据库的时间通常比较长，在这个过程中数据库会持续接收写入请求，假设备份进程是上图中的 Alice，就可能导致备份进程读取到两个版本的数据。一旦从这样的备份中恢复数据，这种短暂的数据不一致就可能变成永久的不一致。
* 分析查询及数据完整性检查：分析和完整性检查的过程中如果读取到两个版本的数据，就会导致分析有误及完整性检查无法通过。

Snapshot Isolation 是 read skew 现象最常见的解决方案。其核心思想就是每个事务都从数据库的一个 consistent snapshot 中读取数据，如事务 A 过程中读取的数据是事务 A 开始时刻数据库中所有已经 commit 的数据，即便在事务 A 执行过程中，其它事务已经写入新的数据，A 读取到的数据仍然是其开始时刻快照的数据。Snapshot Isolation 在许多数据库中都支持，包括 PostgreSQL，MySQL (InnoDB)，Oracle，SQL Server 等。

#### 实现 Snapshot Isolation

Snapshot Isolation 的是：

> readers never block writers, and writers never block readers

由于不同的事务在同一时刻可能需要看到数据的不同版本，因此数据库需要同时保持同一条数据的多个版本，这种技术被称为多版本并发控制（multi-version concurrency control, MVCC）。如果数据库只需要支持 Read Committed 隔离，那么同时保持一条数据的两个版本即可，即 committed 和 overwritten-but-not-yet-committed，因此 Snapshot Isolation 可以说是 Read Committed 的进阶版，它包含了 Read Committed 的特性。

下图展示 PostgreSQL 如何实现 MVCC-based Snapshot Isolation：

![](/files/-LgAPAOwP2lUB-seR3n5)

每个事务在启动后都被赋予一个单调递增的事务 id，即 txid。当该事务向数据库中写数据时，数据被标记上 txid，数据表中的每一行都有一个内置的 created\_by，和一个 deleted\_by 字段。该行被插入时，created\_by 记录相应事务的 txid；该行被删除时，deleted\_by 记录相应事务的 txid。当数据库可以确定没有事务会访问被删除的数据时，后台垃圾收集进程会将标记删除的数据清除，释放磁盘空间。当更新操作发生时，在数据库内部会被转化为一次删除和一次插入。

#### 可见性规则 (Visibility Rules)

每当事务从数据库中读取数据时，txid 都会作为参数被传入，数据库可以依次来判定数据的可见性。只要合理地定义可见性规则，数据库就能够向应用提供符合一致性要求的数据库 snapshot：

* 在每个事务启动前，数据库扫描一遍正在进行的其它事务，任何这些事务写入的数据都将被忽略，不论其是否已经 commit
* 任何 aborted 事务写入的数据都被忽略
* 任何拥有更大 txid 事务写入的数据都被忽略，不论它是否已经 commit
* 其余写入的数据对该事务可见

一个长期执行的事务可能需要持续读取一些早就被覆盖或者删除的数据，通过创建数据的新版本，取代原地修改数据的方式，数据库能够在较低的成本下向应用提供多个符合一致性要求版本的数据。

#### Snapshot Isolation 中的索引

方法1：直接让索引指向多个版本的数据，然后在检索的时候过滤掉不可见的版本；当 GC 进程清理不再使用的旧版本数据时，将索引中相应的引用也删除。这种方法在 PostgreSQL 中被使用。

方法2：使用 append-only/copy-on-write 的 B+ 树变体，即保持多个版本的 B+ 树，类似地会有一个 GC 进程清理不再使用的 B+ 树数据。这种方法在 CouchDB、Datomic 以及 LMDB 中被使用。

#### Snapshot Isolation 的命名问题

尽管 Snapshot Isolation 很受欢迎，但不同的数据库对它的称呼不同：

* Oracle：serializable
* PostgreSQL/MySQL：repeatable read

出现这种命名混乱的现象，主要原因在于 SQL 标准并未对 Snapshot Isolation 作出定义。

### Preventing Lost Updates

讨论 Read Committed 和 Snapshot Isolation 隔离级别时，我们主要讨论的是一个只读事务，在其它并发写事务存在的情况下，读取到数据的保证；但对于一个写事务，在其它并发写事务存在的情况下，写入数据的保证，我们只讨论了 dirty writes 的情况。

并发写场景下，还有一个很著名的问题 --- 更新丢失问题，经典场景就是并发自增操作，如下图所示：

![](/files/-LgGoVs4AET5nd03gY4o)

由于 user2 在 user1 的事务 commit 之后才写入数据，因此这种情况不是脏写。

只要应用程序存在 read-modify-write 操作，并且可能存在多个这样的事务同时执行，就很容易出现更新丢失的现象：

* 更新账户收支记录
* 多个用户同时修改 wiki，每个用户在保存的时候都将完整的文档发送到服务器

正因为这种问题很常见，人们想出了很多方法。

#### 原子写操作

比如许多数据库提供原子更新操作，使得应用程序不必实现 read-modify-write 操作，如果你的应用逻辑能够按照这种方式实现，通常这是最佳解法，如：

```sql
UPDATE counters SET value = value + 1 WHERE key = 'foo'
```

类似的，MongoDB 等非关系型数据库、Redis 等键值数据库也提供类似的包括原子自增操作在内的系列原子写操作。但并不是所有 read-modify-write 逻辑都可以被这些数据库提供的原子写操作表达，如 wiki 页面更新，涉及到文字的部分改动。

原子操作有两种方法实现：

* 每条数据（object/document）加锁
* 单线程执行

#### 显式加锁 (Explicit Locking)

假如数据库提供的原子写操作不足以表达应用的逻辑，应用程序可以直接通过数据库提供的底层工具，直接获取相关的数据的锁，使得更新期间其它事务无法读取该数据。举例如下：

```sql
BEGIN TRANSACTION;

SELECT * FROM figures
 WHERE name = 'robot' AND game_id = 222
 FOR UPDATE;

UPDATE figures SET position = 'c4' WHERE id = 1234;
COMMIT;
```

这里的 FOR UPDATE 语句就是告诉数据库，这条查询涵盖的所有数据都要锁定，在事务结束之前不能被其它事务读写。

这种方案的缺点很明显：开发者需要仔细思考应用程序的逻辑，有时候很容易忘记应当对某些数据加锁，导致出现竞争条件。

#### 自动检测更新丢失

前两种解决方案都是应用程序强制要求 read-modify-write 操作顺序执行。另一种思路是允许这些操作并发执行，让事务管理模块 (trasaction manager) 负责检测更新丢失的情况，然后中止相关的事务并强迫它重试。

自动检测更新丢失的好处在于，数据库可以利用 snapshot isolation 方便地实现自动检测。如 PostgreSQL 的 repeatable read、Oracle 的 serializable 以及 SQL Server 的 snapshot isolation 都能够自动检测更新丢失，然而 MySQL/InnoDB 的 repeatable read 并不会自动检测更新丢失。

*自动检测更新丢失能够帮助应用开发者减少思考负担，更不容易犯错。*

#### Compare-and-Set

在不提供事务支持的数据库中，你有时候可以找到一个原子的 compare-and-set 操作，这个操作只在数据与之前读取的数据一致时才写入新的数据。

#### 冲突解决和数据库复制

在多领导复制及无领导复制场景下，通常的方案是允许数据存在多个版本，然后在应用程序级别上解决或合并这些冲突的数据。原子写操作在多节点数据库中依然适用。另外需要注意的是，许多复制数据库都使用 last write win (LWW) 策略来解决冲突，这种做法容易产生更新丢失。

### Write Skew & Phantoms

除了 dirty write 和 lost update 问题，并发写事务还可能出现其它的竞争条件。

想象这样一个场景：假设你在写一个医院的值班管理系统，要求每次必须有至少一名医生值班，只要有一名医生值班，其它医生可以选择请假。假设 Alice 和 Bob 同时按下请假按钮：

![](/files/-LgH6MXt1hHWfyMXuOmp)

Alice 和 Bob 同时查询当前值班的医生人数，确认人数大于 2，于是两人都认为自己可以请假，最终没有人值班。这个现象就是 write skew。

#### Write Skew

在上面的医生值班系统案例中，Alice 和 Bob 更改的是不同的数据，因此它既不是脏写，也不是更新丢失。但我们可以将 write skew 看作是更新丢失的加强版：**在并发写场景下，两个事务先读取相同的数据，再更新某些数据，**如果这里更新的是相同的数据，就是更新丢失现象；如果更新的是不同的数据，就是 write skew 现象。我们可以从更新丢失的解决方案出发看看是否可以利用：

* 单条数据的原子写操作：write skew 涉及到多条数据，因此不适用
* 自动检测更新丢失：前面提到继续 snapshot isolation 的方案都不适用，PostgreSQL 的 repeatable read、MySQL/InnoDB 的 repeatable read、Oracle 的 serializable 以及 SQL Server 的 snapshot isolation，都无法解决 write skew 问题。自动检测 write skew 需要真正的 serializable isolation 支持。
* 显示加锁可以解决 write skew 问题，以值班系统为例：

```sql
BEGIN TRANSACTION;

SELECT * FROM doctors;
 WHERE on_call = true
   AND shift_id = 1234 FOR UPDATE;
 
UPDATE doctors
   SET on_call = false
 WHERE name = 'Alice'
   AND shift_id = 1234;

COMMIT;
```

你可能会感觉 write skew 很少见，但一旦你注意到它，你就会发现它实际上很常见：

*会议室预定系统*

会议室预定系统需要保证两个预定相同时间相同会议室的请求不能同时成功。任何人在预定会议室之前，都要确认该会议室在该时间内是否与其它预定存在冲突，若不存在就允许预定：

```sql
BEGIN TRANSACTION;

SELECT COUNT(*) FROM bookings
 WHERE room_id = 123 AND
   end_time > '2015-01-01 12:00' AND start_time < '2015-01-01 13:00';

INSERT INTO bookings (room_id, start_time, end_time, user_id)
     VALUES (123, '2015-01-01 12:00', '2015-01-01 13:00', 666);

COMMIT;
```

不幸的是，snapshot isolation 无法阻止两个相互冲突的预定同时发生，如果想要这样的保证，就必须拥有 serializable isolation。

*多人即时游戏*

比如游戏中两个人同时将某个东西移动到一个地方，但这个地方只允许放置一个东西。

*创建账户*

用户创建账号的时候，需要：

1. 检查账号是否存在
2. 若存在则创建失败，若不存在则允许创建

幸运的是，这种场景下可以直接使用数据库的 unique constraint。

*多次支付*

假设用户同时触发两笔支付，两笔支付的数额都小于账户余额，但总和大于账户余额。

#### Write Skew & Materializing Conflicts

可以看出，write skew 的现象有固定的模式：

1. 查询一些数据，检查是否满足之后写入数据的前提条件
2. 根据查询的结构，应用代码决定是否继续
3. 如果继续，则执行写操作，INSERT、UPDATE 或者 DELETE

由于我们无法同时对步骤 1 的查询对象和步骤 3 的写入对象同时加锁，write skew 才借机造孽。于是也有一种解法是将这种冲突具象化为数据，然后在操作前加锁。以会议室预定系统为例：新建一张表，记录会议室与时间段的所有组合，每当一个事务想要预定会议室，先在这张表上的对应数据上加锁。这种方案被称为 materializing conflicts。但这种方案有两个缺点：

* 具象化的过程容易犯错，增加系统理解、维护成本
* 将并发控制的数据与数据本身存放在一起，很 jugaad。

## 可序列化隔离 (Serializability)

在前面的章节中，可以看到一些并发读写造成的竞争问题可以在 read-committed 和 snapshot 隔离级别下避免，但仍然有许多漏网之鱼，更沮丧的是：

* 不同的隔离很难被理解，而且不同数据库的实现结果并不一致
* 在大型应用中，即使很了解隔离级别，也很难确保每一段代码都遵循隔离级别下的规则
* 市面上没有好的工具帮助我们检测竞争条件，测试并发问题本身就是一个难题

这些问题并不新颖，早在 19 世纪 70 年代，弱隔离级别就已经被提出，而解决剩下的并发问题的答案也一直存在，就是使用 ***serializable*** isolation。该隔离级别通常被认为是最强的隔离级别，它保证：即使所有事务可能并行执行，但执行的结果一定和它们按某个顺序执行的结果完全一致。换句话说，数据库保证所有竞争条件都能被避免。但在一个地方得到的，必将在另一个地方失去，serilizable isolation 虽然能解决并发问题，但它在其它方面做出了牺牲与让步，我们需要进入到它的实现中去，就能理解个中缘由。本节将介绍 3 种实现技术：

* 顺序执行事务 (Actual Serial Execution)
* 两部加锁 (Two-phase Locking)
* 乐观并发控制技术 (Optimistic concurrency control techniques)

### 顺序执行事务

避免并发问题最简单的方式就是不让并发发生，只用一个线程处理事务，每次只执行一个事务。这种方式下所有的事务本身就是按某个顺序执行，因此符合 serializable isolation 的语义。但数据库设计者素来认为多线程并发能够提高数据库的性能，因此摒弃了这种方式，但近几年有部分数据库设计者开始重新思考这一方式的合理性，主要缘于两个变化：

* RAM 变得更便宜，容量更大，数据库甚至可以将数据全部读进内存。
* OLTP 事务通常很短，只做少量的读写；而 OLAP 事务通常很长，需要大量的读写。可以将给 OLTP 查询提供 serializable isolation，为 OLAP 查询提供 snapshot isolation。

顺序执行事务的方式在 VoltDB/H-Store、Redis 以及 Datomic 中被使用。有始终，单线程执行事务的系统能获得比多线程事务的系统更好的性能，因为前者没有维护锁机制的成本。然而，前者的性能受限于单核的性能上线。

#### Encapsulating Transactions in Stored Procedures

在实践中，应用程序往往有许多 read-modify-write 的逻辑，这其中可能包含与数据库多次通信，如果这些操作需要放在一个事务中执行，这个事务将存在较长的时间，而对于多线程数据库这意味着可能需要同时维持大量的并发事务；对于单线程数据库来说，这是无法接受的。于是，基于顺序执行事务的数据库往往支持用户定义 stored procedures，将 read-modify-write 的逻辑放入其中，使得一个事务必须在一次通信中完成，这样单线程数据库才可能有其用武之地。

传统数据库的 stored procedures 实现有许多弊端：

* 每种数据库都有自己专有的语言来定义 stored procedures，由于这些语言不是 general-purpose 的语言，通常它们的语法比较丑，且进化缓慢。
* 在数据库中的代码很难做测试、版本管理。
* 数据库通常是许多应用程序的依赖，一个劣质的 stored procedure 可能影响所有应用程序。

为了克服这些缺点，现代数据库通常使用一门 general-purpose 的编程语言作为定义 stored procedure 的语言，如 VoltDB 使用 Java/Groovy，Datomic 使用 Java/Clojure，Redis 使用 Lua。stored procedure 和 in-memory data 是顺序执行事务的数据库的两块基石。除此以外，VoltDB 还使用 stored procedures 来作数据复制。

#### Partitioning

顺序执行事务让并发控制变得小菜一碟，但这也使得数据库的吞吐量受限于单台机器的单个 CPU 核的处理性能上。只读的事务可以在其它地方执行，只需要支持 snapshot isolation 即可。不过对于写入量大的应用来说，单线程事务处理可能成为严重的瓶颈。

为了利用到多节点、多核 CPU，你可以将数据分片，每个数据分片内部仍然遵循单线程事务处理的模式，但不同数据分片之间可以并行。完美的情况下，吞吐量可以随着核数的增多而线性增长。然而，对于那些需要访问多个分片的事务，数据库必须付出额外的成本，使得执行速度变慢多个数量级。

数据是否能够分片通常取决于应用程序的数据模型，简单的 key-value 数据模型很容易分片。其它复杂的数据模型则容易遇到跨分片事务的场景。

### Two-Phase Locking (2PL)

在弱隔离级别中，我们介绍了避免脏写问题的方法：事务写入数据必须先获得相应的锁，假设事务 A 已经进入写数据的过程，事务 B 取锁失败，必须等到事务 A commit 或者 abort 才能继续事务。2PL 的做法与这种方式类似，但更加苛刻：

* 如果事务 A 已经读取一个数据对象，而事务 B 想要修改该对象，B 必须等待 A commit 或 abort 之后才能继续。这保证 B 无法背着 A 偷偷修改 A 读取的数据。
* 如果事务 A 已经修改一个数据对象，而事务 B 想要读取那个数据对象，B 必须等待 A commit 或 abort 之后才能继续。与此同时，在 2PL 中，让 B 在 A 尚未结束时读取旧版本的数据对象也被禁止。

在 2PL 中：

> writers don't just block other writers, they also block readers and vice versa

通过这句话可以看出 2PL 与 snapshot isolation 的区别。

#### 2PL 的实现

2PL 在 MySQL (InnoDB) 以及 SQL Server 中的 serializable isolation level 中使用。它的实现依赖于在单个数据对象的粒度上加锁，锁类似读写锁，有 shared mode 和 exclusive mode：

* 如果事务 A 想要读取一个数据对象，它必须获取读锁。读锁允许多个事务同时获取锁，但如果事务 B 事先以及获取了写锁，那么包括 A 在内的其它想要读取该数据的事务必须等待。
* 如果事务 A 想要修改一个数据对象，它必须获取写锁。其它任何事务都不能在这时候获取读锁或写锁，它们必须等待 A 释放锁后才能继续。
* 如果事务 A 先读或写某一数据对象，它可以将自己已经拥有的读锁升级为写锁，升级过程类似于直接获取写锁。
* 一旦事务 A 获取了锁，它必须持有该锁直到最后结束。这也是 2PL 名字中的 two-phase 的来历：
  * Phase 1：获取锁，这个阶段未结束前不会释放锁
  * Phase 2：释放锁，这个阶段开始后不会再获取锁

由于系统中存在许许多多的锁，不同的事务很容易因为互相等待锁而陷入死锁。数据库会自动检测事务之间的死锁，然后 abort 其中一个，保证另一个可以继续进行，aborted 事务需要应用程序自行重试。

#### 2PL 的性能

2PL 的最大缺点就是性能的损耗，无论是事务的吞吐量还是响应时间都比在弱隔离级别下差很多。因为它阻止了许多并发的可能性，所有可能产生竞争条件的事务都必须一个一个执行。而且传统数据库对每个事务的执行时间没有限制，因此实行 2PL 的数据库的事务延迟无法保证。除此之外，由于 2PL 更加严格，死锁发生的频率更高，重试失败的频率更高，也就浪费了更多的资源。

#### Predicate Locks

在前面的章节中我们介绍了 phantom 和 write skew，即事务 A、B 的 read-modify-write 操作之间可能存在 B 的 write 修改了 A read 的结果，导致 A 的 modify-write 操作逻辑错误。但支持 serializable isolation 的数据库可以解决这个问题。

在会议室预定系统的例子中，要避免 write skew 问题，如果事务 A 已经检索了特定时间、特定会议室的预定记录，就不能允许其它事务修改在该时间段内、该会议室的相关预定数据。如何实现呢？我们可以使用 predicate lock，这种锁不是加在单个数据记录上，而是加在所有符合 predicate 条件的数据上，如：

```sql
SELECT * FROM bookings
 WHERE room_id = 123 AND
       end_time > '2018-01-01 12:00' AND
       start_time < '2018-01-01 13:00';
```

一个 predicate lock 通过以下方式限制数据访问：

* 如果事务 A 想要读取符合某条件的数据，如上面的 SELECT 查询，它必须获取一个加在所有符合该条件数据上的 shared-mode predicate lock。此时如果事务 B 已经获取符合该条件的任何数据上的互斥锁，那么 A 必须等待 B 释放这个锁
* 如果事务 A 想要修改符合某条件的数据，它必须先确认新插入的数据获得即将修改的旧数据是否符合其他事务持有的 predicate locks，若存在，则 A 必须等待这些 predicate locks 被释放。

值得注意的是，predicate lock 不仅适用于存在于数据库中的数据，也适用于符合条件的未进入数据库中的数据。因此在 2PL 的前提下，数据库加入 predicate locks 就可以防止 write skew 以及其它竞争条件出现，符合 serialization isolation 的要求。

#### Index-range Locks

在实践中，predicate locks 的性能并不理想，如果当前活跃的事务持有很多锁，那么检查锁的过程将很耗时，因此大部分实现 2PL 的数据库实际上实现的是 index-range locking，predicate locking 的简化版。这种简化锁基于的思想是：如果对于一部分符合条件的数据加锁很困难，而对这部分数据的超集加锁比较简单，那么也可以使用后者。

当查询使用某索引时，数据库可以对查询访问过的数据的索引入口加锁，一旦别的事务想在锁未释放前修改这条数据，都必须阻塞，等待相关的锁被释放。由于对索引加锁相当于给所有符合单一过滤条件的数据加锁，而通常查询包含多个条件，因此这种加锁方式可能加了一些不必要的锁，但实践证明，这种方式是实践与理论的折衷，因此被采用。

### Serializable Snapshot Isolation (SSI)

目前介绍的两种 serializable isolation 实现，要么性能不佳 (2PL)，要么扩展性差 (serial execution)，那么是否存在性能不错且扩展性好的实现呢？也许 SSI 能成为这样的实现。现在 SSI 已经在 PostgreSQL (>= 9.1) 以及 FoundationDB 中被使用。与其它并发控制机制相比，SSI 仍然十分年轻，它的性能与扩展性仍然还在验证之中。

#### Pessimistic Versus Optimistic Concurrency Control&#x20;

2PL 是典型的悲观 (pessimistic) 并发控制机制，它的核心思想就是：消除问题发生的可能性，让系统的运行永远处于安全的状态中，如果当前操作可能造成问题，就等待系统变安全后再运行。而 Serial Execution 是极致的悲观并发控制机制，因为它等价于让每个事务在执行之前都锁住整个数据库。

与二者相对，SSI 是一种乐观的并发控制机制，即先让事务进行，在事务将要 commit 时，数据库需要检查是否违背了隔离的要求，如果违背了，就将事务 abort。乐观并发控制并不是一个新观点，它的优点和缺点也一直被大家拿出来讨论。系统负载较高时，事务竞争的可能越大，abort 的比例越大，如果系统已经接近它的最大吞吐量，不断重试还会继续使得情况进一步恶化，这时乐观的并发控制机制不是一种好的选择；当系统负载适中时，乐观并发控制通常要表现地比悲观并发控制好。

SSI 在 snapshot isolation 之上加了一层检测事务读写冲突的检测逻辑，从而判断哪些事务应该 abort，保证隔离性达到 serialization 的要求。

## 参考

DDIA chapter 7


---

# Agent Instructions: Querying This Documentation

If you need additional information that is not directly available in this page, you can query the documentation dynamically by asking a question.

Perform an HTTP GET request on the current page URL with the `ask` query parameter:

```
GET https://zhenghe.gitbook.io/open-courses/ddia-bi-ji/transactions.md?ask=<question>
```

The question should be specific, self-contained, and written in natural language.
The response will contain a direct answer to the question and relevant excerpts and sources from the documentation.

Use this mechanism when the answer is not explicitly present in the current page, you need clarification or additional context, or you want to retrieve related documentation sections.