Timestamp Ordering Concurrency Control

  • 系统单调时钟 (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
    }
}

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

Basic T/O - Example #1

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

Basic T/O - Example #2

类似地，我们可以看下面这个例子：

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 就无法在发生崩溃之后恢复数据，举例如下：

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

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) 的读写集合是否与尚未提交的事务的读写集合存在交集：

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

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：

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

PreviousTwo Phase LockingNextMulti-Version Concurrency Control

Last updated