Timestamp Ordering Concurrency Control

上节课介绍的 2PL 是悲观的并发控制策略,本节课介绍的 Timestamp Ordering (T/O) 则是一个乐观的策略,其乐观表现在事务访问数据时无需显式加锁。T/O 的核心思想就是利用时间戳来决定事务之间的等价执行顺序:如果 TS(Ti)<TS(Tj)TS(T_i) < TS(T_j) ,那么数据库必须保证实际的 schedule 与先执行 TiT_i ,后执行 TjT_j 的结果等价。要实现 T/O,就需要一个单调递增的时钟,来决定任意事务 TiT_i 发生的时间。满足条件的时钟方案有很多,如:

  • 系统单调时钟 (System Clock)

  • 逻辑计数器 (Logical Counter)

  • 混合方案 (Hybrid)

Basic T/O

Basic T/O 是 T/O 方案的一种具体实现。在 Basic T/O 中,事务读写数据不需要加锁,每条数据 X 都会携带两个标记:

  • W-TS(X):最后一次写 X 发生的时间戳

  • R-TS(X):最后一次读 X 发生的时间戳

在每个事务结束时,Basic T/O 需要检查该事务中的每个操作,是否读取或写入了未来的数据,一旦发现则中止、重启事务。

Basic T/O Reads

读取数据时的逻辑如下所示:

func read(X) val {
    if TS(T_i) < W_TS(X) {
        abort_and_restart(T_i)
    } 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
    }
}

如果事务 TiT_i 发生在 W-TS(X) 之前,即尝试读取未来的数据,则中止 TiT_i ;如果事务 TiT_i 发生在 W-TS(X) 之后,意味着它正在读取过去的数据,符合规范。 TiT_i 读取数据后,如果有必要,则更新 R-TS(X),同时保留一份 X 的副本,用来保证 TiT_i 结束之前总是能读到相同的 X。

Basic T/O Writes

写入数据时的逻辑如下所示:

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
    }
}

如果事务 TiT_i 发生在 W-TS(X) 或 R-TS(X) 之前,即尝试写入已经被未来的事务读取或写入的数据,则中止 TiT_i ;反之,意味着它正尝试修改过去的数据,符合规范。 TiT_i 写入数据后,如果有必要,则更新 W-TS(X),同时保留一份 X 的副本,用来保证 TiT_i 结束之前总是能读到相同的 X。

Basic T/O - Example #1

如下图所示:有两个事务T1T_1T2T_2,它们的时间戳分别为 1,2,即 T1T_1发生在 T2T_2 之前,它们要访问的数据为 A 和 B,假设它们是数据库预填充的数据,R-TS 和 W-TS 都为 0。

T1T_1 先读取 B,将 R-TS(B) 更新为 1

T2T_2 读取 B,将 R-TS(B) 更新为 2

T2T_2 修改 B,将 W-TS(B) 更新为 2

T1T_1 读取 A,将 W-TS(A) 更新为 1

T2T_2 读取 A,将 R-TS(A) 更新为 2

T2T_2 修改 A,将 W-TS(A) 更新为 2

由于整个过程,没有发生违背规范的操作,因此两个事务都能够成功提交。

Basic T/O - Example #2

类似地,我们可以看下面这个例子:

不难看出, T1T_1T2T_2 修改 A 后又修改了 A,该操作肯定会违反规范:

因此 T1T_1 将被数据库中止。但实际上,仔细分析上述例子,如果我们忽略掉 T1T_1的 W(A) 操作,即不更新 A 数据,也不修改 W-TS(A),那么 T1T_1T2T_2 都可以正常提交,且结果和二者先后执行等价,这便是所谓的 Thomas Write Rule (TWR):

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)
    // ...
}

example #2 符合 TWR,可以允许让两个事务顺利提交。TWR 优化了 Basic T/O 的写检查,使得一些本不必中止的事务顺利进行,提高了事务并发程度。

Basic T/O Summary

如果不使用 TWR 优化,Basic T/O 能够生成 conflict serializable 的 schedule,如果使用了 TWR,则 Basic T/O 生成的 schedule 虽然与顺序执行的效果相同,但不满足 conflict serializable。Basic T/O 的优势在于:

  1. 不会造成死锁,因为没有事务需要等待

  2. 如果单个事务涉及的数据不多、不同事务涉及的数据基本不相同 (OLTP),可以节省 2PL 中控制锁的额外成本,提高事务并发度

其缺点在于:

  1. 长事务容易因为与短事务冲突而饿死

  2. 复制数据,维护、更新时间戳存在额外成本

  3. 可能产生不可恢复的 schedule (具体见下节)

Recoverable Schedules

如果一个 schedule 能够保证每个事务提交前,修改过其读取过数据的事务都已提交,那么这个 schedule 就是 recoverable。如果不能保证 recoverable,DBMS 就无法在发生崩溃之后恢复数据,举例如下:

T2T_2T1T_1 修改 A 之后读取 A,符合规范。但是在 T2T_2 提交之后, T1T_1中止,前者依赖的数据实际上并未真实写入,数据库发生故障以后将无法恢复。因此 Basic T/O 可能产生不可恢复的 schedules。

Optimistic Concurrency Control (OCC)

OCC 是 H.T. KUNG 在 CMU 任教时提出的并发控制算法。在 OCC 中,数据库为每个事务都创建一个私有空间:

  • 所有被读取的数据都复制到私有空间中

  • 所有修改都在私有空间中执行

OCC 分为 3 个阶段:

  1. Read Phase:追踪、记录每个事务的读、写集合,并存储到私有空间中

  2. Validation Phase:当事务提交时,检查冲突

  3. Write Phase:如果校验成功,则合并数据;否则中止并重启事务

DBMS 需要维持所有活跃事务的全局视角,并将 Validation Phase 和 Write Phase 的逻辑放入一个 critical section 中。

OCC - Example

事务 T1T_1 读取 A 时,将 A 复制到自己的 workspace 中,可以看到,与 Basic T/O 相比,OCC 只需要记录一个时间戳,W-TS。

事务 T2T_2 读取 A 时,同样将 A 复制到自己的 workspace 中:

事务 T2T_2 完成数据操作,在 Validation Phase 中获得事务时间戳 1,由于没有数据写入,跳过 Write Phase

事务 T1T_1 修改 A 的值为 456,由于尚不知道自己的事务时间戳,将 W-TS(A) 设置为无穷大:

事务 T1T_1 在 Validation Phase 获得事务时间戳 2,并通过校验,将 W-TS(A) 修改为 2,并合并到数据库中

OCC - Read Phase

追踪事务的读写集合 (read/write sets),将 read set 存放在 private workspace 中用来保证 repeatable read,将 write set 存放在 private workspace 中用来作冲突检测。

OCC - Validation Phase

在进入 Validation Phase 后,每个事务都会被赋予一个时间戳,然后与其它正在运行的事务执行 Timestamp Ordering 检查,检查的方式有两种:

  1. Backward Validation

  2. Forward Validation

如下图所示,在 Backward Validation 中,需要检查待提交的事务 (txn #2) 的读写集合是否与已经提交的事务的读写集合存在交集:

与此类似,在 Forward Validation 中,需要检查待提交的事务 (txn #2) 的读写集合是否与尚未提交的事务的读写集合存在交集:

如果 TS(Ti)<TS(Tj)TS(T_i) < TS(T_j) ,那么以下 3 个条件之一必须成立:

Condition 1: TiT_i completes all three phases before TjT_j begins

如果事务 TiT_i 在事务 TjT_j 开始之前已经完成 OCC 的所有 3 个阶段,那么二者之间不存在任何冲突。

Condition 2: TiT_i completes before TjT_j starts its Write Phase, and TiT_i does not write to any object read by TjT_j

如果 TiT_iTjT_j 的 Write Phase 开始前就已提交,同时 TiT_i 没有修改任意 TjT_j 读取的数据,即 WriteSet(Ti)ReadSet(Tj)=WriteSet(T_i) \cap ReadSet(T_j) = \emptyset ,则二者之间不存在冲突。

Condition 3: TiT_i completes its Read Phase before TjT_j completes its Read Phase, and TiT_i does not write to any object that is either read or written by TjT_j

如果 TiT_iTjT_j 结束自己的 Read Phase 前结束 Read Phase,同时 TiT_i 没有修改任何 TjT_j 读取或修改的数据,即满足:

WriteSet(Ti)ReadSet(Tj)= , WriteSet(Ti)WriteSet(Tj)=WriteSet(T_i) \cap ReadSet(T_j) = \emptyset \space, \space WriteSet(T_i) \cap WriteSet(T_j) = \emptyset

时,二者之间不存在冲突。

OCC 与 Basic T/O 的思路类似,都是在检查事务之间的 WW、WR 冲突。当冲突发生的频率很低时,即:

  • 大部分事务都是读事务

  • 大部分事务之间访问的数据间没有交集

OCC 的表现很好,如在数据库体量较大,workload 比较均衡的场景下。2PC 的性能瓶颈在于锁管理,尽管 OCC 没有加锁的成本,但它也存在性能问题:

  • 在 private workspace 与 global database 之间移动、合并数据开销大

  • Validation/Write Phase 需要在一个全局的 critical section 中完成,可能造成瓶颈

  • 在 Validation Phase 中,待提交事务需要和其它事务做冲突检查,即便实际上并没有冲突,这里也有很多获取 latch 的成本 (锁住其它事务的 private workspace,对比是否有冲突,再释放锁)

  • 事务中止的成本比 2PL 高,因为 OCC 在事务执行快结束时才检查数据冲突

Partition-Based T/O

类似全局锁到分段锁的优化,我们也可以将数据库切分成不相交 (disjoint) 的子集,即 horizontal partitions 或 shards,然后在 partition 内部使用单调递增的时间戳确定各个事务的顺序,不同 partition 上的事务之间无需检测冲突。

假设数据库中存储着如下三张表:

我们可以按照 customer 的 c_id 对数据库分片:

每个 partition 使用一个锁保护:

  • 当事务需要访问多个 partitions 时,就在所需的多个 partitions 上排队

  • 如果事务的时间戳是整个 partition 中最小的,那么该事务就获得锁

  • 当事务获取其所需访问的所有 partitions 的全部锁,它就可以开始执行

Partition-Based T/O - Reads

如果事务已经获取分片上的锁,该事务就能够读取它想读取的任意数据。如果事务尝试访问一个未获取锁的分片,那么它将被中止后重启。

Partition-Based T/O - Writes

写事务直接在原地修改数据,并在内存中维护一个缓冲区,用来记录修改的数据以便事务中止后回滚。如果事务尝试修改一个未获取锁的分片,那么它将被中止后重启。

Partition-Based T/O - Example

假设有两个事务同时开启,并分别被分配了全局的时间戳 100 和 101,二者都需要获取 partition 1 上的锁,如下图所示:

由于事务 #100 的时间戳较小,它将获得 partition 1 的锁,从而执行事务:

随后事务 #101 才能够获得 partitio 1 的锁,执行事务内容

Partition-based T/O 的性能取决于以下两点:

  • DBMS 是否在事务开启前就能知道事务所需的所有 partitions

  • 是否大多数事务只需要访问单个 partition

multi-partition 的事务将使得更多其它事务陷入等待状态,取了锁而未使用的 partition 也可能陷入空转。

Dynamic Databases

到现在为止,我们都只考虑事务读取和更新数据,如果我们再考虑插入、删除操作,就会遇到新的问题。

The Phantom Problem

考虑插入操作,则可能出现 Phantom Read:

即在单个事务内部,同样的查询,读到不一样的数据。这种现象发生的原因在于,尽管 T1T_1 锁住了已经存在的记录,但新生成的记录并不会被锁住,因此实际上 conflict serializability 能保证事务可序列化的前提是数据集合是固定的,出现记录新增和删除时,这个结论就不成立了。

Predicate Locking

predicate locking 指的是通过一个逻辑表达式来为潜在的记录加锁,如:status = 'lit' 。然而,predicate locking 的成本很高,对每条新插入的数据都需要做校验。基本没有 DBMS 用这种方式实现,一种更高效的做法是 index locking。

Index Locking

同样以上文中的例子为例,如果在 status 字段上有索引,那么我们可以锁住满足 status = 'lit' 的 index page,如果尚未存在这样的 index page,我们也需要能够找到可能对应的 index page,锁住它们。

Locking Without An Index

同样以上文中的例子为例,如果在 status 字段上没有索引,那么事务就需要执行以下操作:

  • 获取 table 的每个 page 上的锁,防止其它记录的 status 被修改成 lit

  • 获取 table 本身的锁,防止满足 status = 'lit' 的记录被插入或删除

Repeating Scans

另一种比较暴力的做法是在事务提交时,扫描 status = 'lit' 的所有数据,检查这些数据是否与事务操作之前的数据相同。目前没有任何商业数据库采用这种方案。

Isolation Level

以上讨论的都是可序列化的并发控制方案。可序列化固然是一种很实用的特性,它可以将程序员从并发问题中解脱,但可序列化的方案要求比较严格,会对系统的并发度和性能造成较大的限制,因此我们也许能够用更弱的数据一致性保证去改善系统的扩展性。这也是所谓的数据库隔离级别。

更弱的数据库隔离级别将事务修改的数据暴露给其它事务,以此提高整体并发度,但这种并发度可能造成一系列问题,如 Dirty Reads/Writes (脏读、脏写)、Unrepeatable Reads (不可重复读)、Phantom Reads (幻读) 等等。

常见的数据库隔离级别从弱到强依次包括:Read Uncommitted -> Read Committed -> Repeatable Reads -> Serializable,总结如下表:

该表总结得不太完全,更详细的讨论可参考 Transactions

SQL - 92 Isolation Levels

SQL-92 中定义了数据库设置隔离级别的命令:

SET TRANSACTION ISOLATION LEVEL <isolation-level>;   // 全局设定
BEGIN TRANSACTION ISOLATION LEVEL <isolation-level>; // 单事务设定

但并非所有数据库在所有运行环境中都能支持所有隔离级别,且数据库的默认隔离级别取决于它的实现。以下是 2013 年统计的一些数据库的默认隔离级别和最高隔离级别:

SQL-92 Access Mode

SQL-92 中也允许用户提示数据库自己的事务是否会修改数据:

SET TRANSACTION <access-mode>;   // 全局设置
BEGIN TRANSACTION <access-mode>; // 单个事务设置

其中 access-mode 有两种模式:READ WRITE 和 READ ONLY。当然,即便在 SQL 语句中添加了这种提示,也不是所有数据库都会利用它来优化 SQL 语句的执行。

Conclusion

任意一种并发控制都可以被分解成前两节课中提到的基本概念。

References

slides, video

Last updated