上节课介绍的 2PL 是悲观的并发控制策略,本节课介绍的 Timestamp Ordering (T/O) 则是一个乐观的策略,其乐观表现在事务访问数据时无需显式加锁。
T/O 的核心思想就是利用时间戳来决定事务的可串行化执行顺序:如果 \(TS(T_i) < TS(T_j)\) ,那么数据库必须保证实际的 schedule 与先执行 \(T_i\),后执行 \(T_j\) 的结果等价。
时间戳其实就是唯一并且有固定长度的数字,有?特征,事务执行时,DBMS 会给事务分配时间戳,不同的方案会在事务处理的不同时间赋予时间戳。
- 必须单调增加 (时间戳的值必须随着时间的流逝而增加)
- 值是唯一的 (永远不能拥有两个具备相同时间戳的事务)
要实现 T/O,就需要一个单调递增的时钟来实现时间戳,来决定任意事务 \(T_i\) 发生的时间。满足条件的时钟方案有很多,如:
- 系统单调时钟 (System Clock)
- 逻辑计数器 (Logical Counter)
- 混合方案 (Hybrid)
1 Basic Timestamp Ordering (BASIC T/O)
Basic T/O 是 T/O 方案的一种具体实现。在 Basic T/O 中,事务读写数据不需要加锁,每条数据 X 都会携带两个标记:
W_TS(X)
:最后一次写 X 发生的时间戳R_TS(X)
:最后一次读 X 发生的时间戳
在每个事务结束时,Basic T/O 需要检查该事务中的每个操作,是否读取或写入了未来的数据,一旦发现则中止并重启事务。
1.1 Basic T/O - Read
读取数据时的逻辑如下所示:
func read(X) val {
if TS(T_i) < W_TS(X) {
abort_and_restart(T_i) // Abort T_i and restart it with a new TS
} else {
val := read_data(X)
R_TS(X) = max(R_TS(X), TS(T_i))
// make a local copy of X to ensure repeatable reads for T_i
return val
}
}
若事务 \(T_i\) 发生在 W_TS(X) 之前,即尝试读取未来的数据,则中止 \(T_i\),给它一个新时间戳后 restart \(T_i\);
否则,即尝试读取过去的数据,符合规范。允许 \(T_i\) 读数据 \(X\),更新 R_TS(X) ,同时保留一份 \(X\) 的副本,用来保证 \(T_i\) 结束之前总是能读到相同的 \(X\)。
1.2 Basic T/O - Write
写入数据时的逻辑如下所示:
func write(X, val) {
if TS(T_i) < R_TS(X) || TS(T_i) < W_TS(X) {
abort_and_restart(T_i)
} else {
X = val
W_TS(X) = max(W_TS(X), TS(T_i))
// make a local copy of X to ensure repeatable reads for T_i
}
}
若事务 \(T_i\) 发生在 W_TS(X) 或 R_TS(X) 之前,即尝试写入已经被未来的事务读取或写入的数据,则中止 \(T_i\),给它一个新时间戳后 restart \(T_i\);
否则,即尝试修改过去的数据,符合规范。允许 \(T_i\) 写数据 \(X\),更新 W_TS(X) ,同时保留一份 \(X\) 的副本,用来保证 \(T_i\) 结束之前总是能读到相同的 \(X\)。
先看一个正确成功提交的例子 ?
如图所示:有两个事务 \(T_1\) 和 \(T_2\),它们的时间戳分别为 1,2,即 \(T_1\) 发生在 \(T_2\) 之前,它们要访问的数据为 A 和 B,假设它们是数据库预填充的数据,R_TS 和 W_TS 都为 0。
再看一个会中止事务的例子 ?
1.3 Optimization: Thomas Write Rule (TWR)
?的例子中,Basic T/O 要求 \(T_1\) 回滚,但这是不必要的,因为 \(T_2\) 已经写过了 A,那么 \(T_1\) 想要写的数据将永远不会被读取到。所有 \(TS(T_i) < TS(T_2)\) 的事务 \(T_i\) 进行 read(A) 操作都会被回滚,因为 W_TS(A) = \(TS(T_2)\),\(TS(T_i)\) < W_TS(A);而所有 \(TS(T_i) > TS(T_2)\) 的事务 \(T_i\) 都必须读由 \(T_2\) 写的 A 值,而不是 \(T_1\) 想写的值。因此可以直接忽略 \(T_1\) 的 W(A) 操作,而不是要求 \(T_1\) 回滚。
由此,提出了 Basic T/O 的优化策略 —— Thomas 写规则
:
func write(X, val) {
if TS(T_i) < R_TS(X) {
abort_and_restart(T_i)
return
}
if TS(T_i) < W_TS(X) {
// ignore write
return
}
X = val
W_TS(X) = TS(T_i)
// ...
}
若事务 \(T_i\) 发生在 R_TS(X) 之前,即尝试写入已经被未来的事务读取的数据,则中止 \(T_i\),给它一个新时间戳后 restart \(T_i\);
若事务 \(T_i\) 发生在 W_TS(X) 之前,即尝试写入已经被未来的事务写入的数据,直接忽略此写操作;【Thomas Write Rule】
否则,即尝试修改过去的数据,符合规范。允许 \(T_i\) 写数据 \(X\),更新 W_TS(X) ,同时保留一份 \(X\) 的副本,用来保证 \(T_i\) 结束之前总是能读到相同的 \(X\)。
TWR 优化了 Basic T/O 的写检查,使得一些本不必中止的事务顺利进行,提高了事务并发程度。
若不使用 TWR 优化,Basic T/O 能够生成冲突可串行化的 schedule,若使用 TWR,则 Basic T/O 生成的 schedule 虽然与顺序执行的效果相同,但不满足冲突可串行化。
1.4 Recoverable Schedules
如果一个 schedule 能够保证每个事务提交前,修改过其读取过数据的事务都已提交,那么这个 schedule 就是可恢复的 (recoverable)。如果不能保证 recoverable,DBMS 就无法在发生崩溃之后恢复数据。
? \(T_2\) 在$ T_1$ 修改 A 之后读取 A,符合规范。但是在 \(T_2\) 提交之后,\(T_1\) 中止。故 \(T_2\) 依赖的数据实际上并未真实写入,因此数据库发生故障以后将无法恢复。
—— 不可恢复的 schedules,因为无法 restart \(T_1\)。
因此 Basic T/O 可能产生不可恢复的 schedules。
Basic T/O 的优势:
- 不会造成死锁,因为没有事务需要等待
- 如果单个事务涉及的数据不多、不同事务涉及的数据基本不相同 (OLTP),可以节省 2PL 中控制锁的额外成本,提高事务并发度
缺点:
- 长事务容易因为与短事务冲突而饿死
- 复制数据,维护、更新时间戳存在额外成本
- 可能产生不可恢复的 schedule
- 在高并发的系统中受到时间戳分配瓶颈的影响
Basic T/O 适合事务间几乎不存在冲突,且大多事务都是短事务的情况
2 Optimistic Concurrency Control (OCC)
乐观的并发控制 (OCC) 是 H.T. KUNG 在 CMU 任教时提出的并发控制算法。在 OCC 中,数据库为每个事务都创建一个私有空间:
- 所有被读取的数据都复制到私有空间中
- 所有修改都在私有空间中执行
OCC 分为 3 个阶段:
Read Phase
:追踪、记录每个事务的读、写集合,并存储到私有空间中。Validation Phase
:当事务 Commit 时,进行有效性检查。Write Phase
:若检查通过,则将事务执行的写操作结果的临时局部变量都拷贝到 database;否则 Abort 并重启事务。
(对于只读事务忽略此阶段)
DBMS 需要维持所有活跃事务的全局视角,并将 Validation Phase 和 Write Phase 的逻辑放入一个临界区 (critical section) 中。即不同事务的验证和写阶段应该原子地完成,在验证其他事务时,不允许提交任何事务。由于验证和写阶段通常比读阶段短,因此这是可以接受的妥协。
2.1 Read Phase
追踪事务的读写集合 (read/write sets),将 read set 存放在 private workspace 中用来保证可重复读,将 write set 存放在 private workspace 中用来作冲突检测 (有效性检查)。
此时的写操作都是对局部的临时变量进行的,并不对数据库进行真正的更新。
2.2 Validation Phase
当事务 Commit 时进入 Validation Phase,每个事务与其它正在运行的事务执行 Timestamp Ordering 检查。
数据库要确保生成的 schedules 是冲突可串行化的,对于每个事务来说,要确保做出的修改不会与系统的其他并发执行的事务冲突。若事务读取的某些数据已过期 or 事务的写入将覆盖在其读阶段提交的事务所写入的的某些值,则产生冲突。
检查的方式有两种:
Backward Validation:检查待与已经提交的事务是否存在冲突 (读写集合存在交集)。
Forward Validation:检查与尚未提交的事务是否存在冲突 (读写集合存在交集)。
所有事务在执行验证的时候都是沿着同一方向进行的 (要么向前,要么向后)
Backword Validation 中,对 \(T_j\) 进行 Validation,对 \(TS(T_i) < TS(T_j)\) 的所有事务 \(T_i\),可能有两种情况:
- \(T_i\) 在 \(T_j\) 读阶段开始前提交。则二者肯定不会产生冲突。
- \(T_i\) 在 \(T_j\) 读阶段开始后,写阶段开始前提交,要求 \(T_i\) 的写集合与 \(T_j\) 的读集合不相交 \(WriteSet(T_i)∩ReadSet(T_j)=∅\),否则 \(T_j\) 读到的不是最新数据。
Forward Validation 中,对 \(T_i\) 进行 Validation,对 \(TS(T_i) < TS(T_j)\) 的所有事务 \(T_j\),可能有三种情况:
- \(T_i\) 在 \(T_j\) 读阶段开始前提交。则二者肯定不会产生冲突。
- \(T_i\) 在 \(T_j\) 读阶段开始后,写阶段开始前提交,要求 \(T_i\) 的写集合与 \(T_j\) 的读集合不相交 \(WriteSet(T_i)∩ReadSet(T_j)=∅\),否则 \(T_j\) 读到的不是最新数据。
- \(T_i\) 在 \(T_j\) 写阶段开始后提交,但 \(T_i\) 的读阶段在 \(T_j\) 的读阶段先完成,要求 \(T_i\) 的写集合与 \(T_j\) 的读写集合都不相交 \(WriteSet(T_i)∩ReadSet(T_j)=∅, WriteSet(T_i)∩WriteSet(T_j)=∅\),前者是怕 \(T_j\) 读到的不是最新数据,后者是因为 \(T_i\) 尚未写入,无法保证 \(T_i\) 和 \(T_j\) 的写入顺序。
OCC 与 Basic T/O 的思路类似,都是在检查事务之间的 WW、WR 冲突。当冲突发生的频率很低时,即 ? OCC 的表现很好,如在数据库体量较大,workload 比较均衡的场景。
- 大部分事务都是读事务
- 大部分事务之间访问的数据间没有交集
2PC 的性能瓶颈在于锁管理,尽管 OCC 没有加锁的成本,但也存在性能问题:
- 在高并发的系统中受到时间戳分配瓶颈的影响
- 在 private workspace 与 global database 之间移动、合并数据开销大
- Validation/Write Phase 需要在一个全局的 critical section 中完成,可能造成瓶颈
- 在 Validation Phase 中,待提交事务需要和其它事务做冲突检查,即便实际上并没有冲突,这里也有很多获取 latch 的成本 (锁住其它事务的 private workspace,对比是否有冲突,再释放锁)
- OCC 的事务中止成本比其他协议高,因为 OCC 需要在事务 Commit 时才能在 validation phase 发现冲突,而 Basic T/O 在事务运行时就能发现冲突并终止,2PL 在事务开始时。
4 Partition-Based T/O
类似全局锁到分段锁的优化,我们也可以将数据库切分成不相交 (disjoint) 的子集,即 horizontal partitions 或 shards,然后在 partition 内部使用单调递增的时间戳确定各个事务的顺序,不同 partition 上的事务之间无需检测冲突。
根据事务到达 DBMS 的时间给它们分配时间戳,每个 partition 使用一个锁保护:
- 当事务需要访问多个 partitions 时,就在所需的多个 partitions 上排队
- 如果事务的时间戳是整个 partition 中最小的,那么该事务就获得锁
- 当事务获取其所需访问的所有 partitions 的全部锁,它就可以开始执行
Partition-Based T/O - Read
如果事务已经获取分片上的锁,该事务就能够读取它想读取的任意数据。如果事务尝试访问一个未获取锁的分片,那么它将被中止后重启。
Partition-Based T/O - Write
写事务直接在原地修改数据,并在内存中维护一个缓冲区,用来记录修改的数据以便事务中止后回滚。如果事务尝试修改一个未获取锁的分片,那么它将被中止后重启。
Partition-based T/O 的性能取决于以下两点:
- DBMS 是否在事务开启前就能知道事务所需的所有 partitions
- 是否大多数事务只需要访问单个 partition
multi-partition 的事务将使得更多其它事务陷入等待状态,取了锁而未使用的 partition 也可能陷入空转。
5 Dynamic Databases
到现在为止,我们都只考虑事务读取和更新数据,如果我们再考虑插入、删除操作,就会遇到新的问题。
The Phantom Problem
考虑插入/删除操作,则可能出现幻读 (Phantom Read):即在单个事务内部,同样的查询,读到不一样的数据。
这种现象发生的原因在于,尽管 \(T_1\) 锁住了已经存在的记录,但新生成的记录并不会被锁住,因此实际上 conflict serializability 能保证事务可序列化的前提是数据集合是固定的,出现记录新增和删除时,这个结论就不成立了。
Q:2PL 可以解决幻读问题吗?
A: 不能,因为不能对不存在的对象上锁。
解决方法:
Approach 1:Re-Execute Scans
简单粗暴,目前没有任何商业数据库采用这种方案。
DBMS 跟踪 txn 执行的所有查询的 WHERE 子句 (为 txn 中的每个范围查询保留扫描集),当事务提交时,重新执行每个查询的扫描部分 (? status = 'lit'
),检查它是否生成相同的结果。
Approach 2:Rredicate Locking
谓词锁是 System R 提出的锁定方案,指通过一个逻辑表达式来为潜在的记录加锁, ? status = 'lit'
。
- 对 SELECT 查询的 WHERE 子句中的谓词的进行共享锁。
- 对任何 UPDATE、INSERT 或 DELETE 查询的 WHERE 子句中的谓词进行排他锁。
然而,谓词锁的成本很高,对每条新插入的数据都需要做校验。基本没有 DBMS 用这种方式实现,一种更高效的做法是索引锁。
Approach 3:Index Locking
同样以上文中的例子为例,如果在 status
字段上有索引,那么我们可以锁住满足 status = 'lit'
的 index page,如果尚未存在这样的 index page,我们也需要能够找到可能对应的 index page,锁住它们。
Approach 3:Locking Without An Index
同样以上文中的例子为例,如果在 status
字段上没有索引,那么事务就需要执行以下操作:
- 获取 table 的每个 page 上的锁,防止其它记录的
status
被修改成lit
- 获取 table 本身的锁,防止满足
status = 'lit'
的记录被插入或删除
3 Isolation Levels
以上讨论的都是可串行化 (Serializability) 的并发控制方案。
可串行化固然是一种很实用的特性,它可以将程序员从并发问题中解脱。但可串行化的方案要求比较严格,会对系统的并发度和性能造成较大的限制。因此我们也许能够用更弱的数据一致性保证去改善系统的扩展性。这也是所谓的数据库隔离级别。
隔离级别
(Isolation Level) 控制一个事务将修改的数据暴露给在其他并发事务的程度。
更弱的数据库隔离级别以暴露更多事务未提交的更改为代价,提高整体并发度,但这种并发度可能造成一系列问题:
- Dirty Reads (脏读):读取未提交的数据
- Unrepeatable Reads (不可重复读):多次读取同一对象的结果不同 (侧重点在数据库的读取与更新)
- Phantom Reads (幻读):由于插入或删除操作,导致多次相同范围扫描查询的结果不同 (侧重点在数据库的插入与删除)
隔离级别 (从强到弱):
- 可串行化 (Serializable):获取所有锁,获取索引锁,实行 strict 2PL。
- 可重复读 (Repeatable Reads):同上,但没有索引锁,因此可能会有幻读问题。
- 读提交 (Read Committed):同上,但 S 锁会立即释放。因此可能多次读取同一对象的结果不同导致不可重复读。
- 读未提交 (Read Uncommitted)。同上,但允许脏读 (没有 S 锁)。因此可能读取未提交的数据。
该表总结得不太完全,更详细的讨论可参考 Transactions。
SQL - 92 Isolation Levels
SQL-92 中定义了数据库设置隔离级别的命令:
SET TRANSACTION ISOLATION LEVEL <isolation-level>; -- 全局设定 --
BEGIN TRANSACTION ISOLATION LEVEL <isolation-level>; -- 单事务设定 --
但并非所有数据库在所有运行环境中都能支持所有隔离级别,且数据库的默认隔离级别取决于它的实现。
以下是 2013 年统计的一些数据库的默认隔离级别和最高隔离级别:
Default | Maximun | |
---|---|---|
Google Spanner | Strong Serializable | Strong Serializable |
Actian Ingres | Serializable | Serializable |
CockroachDB | Serializable | Serializable |
VoltDB | Serializable | Serializable |
IBM DB2 | Cursor stability | Serializable |
YugaByte | Snapshot Isolation | Serializable |
MySQL | Repeatable Reads | Serializable |
MSFT SQL Server | Read Committed | Serializable |
PostgreSQL | Read Committed | Serializable |
SAP HANA | Read Committed | Serializable |
Oracle | Read Committed | Snapshot Isolation |
有两种额外的隔离等级。
- Cursor Stability: 在可重复读和可串行化之间,可以阻止丢失更新(Lost Update) 现象。
- Snapshot Isolation: 保证在事务读取的数据都是事务开始时存在的数据库的一致性快照。只有当事务的写入与该快照以来进行的任何并发更新不冲突时,事务才会提交。
SQL-92 Access Mode
SQL-92 中也允许用户提示数据库自己的事务是否会修改数据:
SET TRANSACTION <access-mode>; -- 全局设置 --
BEGIN TRANSACTION <access-mode>; -- 单个事务设置 --
其中 access-mode 有两种模式:READ WRITE
和 READ ONLY
。
当然,即便在 SQL 语句中添加了这种提示,也不是所有数据库都会利用它来优化 SQL 语句的执行。
参考链接
- Concurrency Timestamp Ordering Lecture Controlconcurrency timestamp ordering lecture multi-version concurrency lecture control concurrency lecture control index concurrency lecture control theory multi-version concurrency control version concurrency control project数据库 concurrency题目project control ordering filtering ordering grace-period tree_rcu ordering through