Chapter 17 Timestamp Ordering Concurrency Control

CONCURRENCY CONTROL APPROACHES

• Two-Phase Locking (2PL)
  • Determine serializability order of conflicting operations at runtime while txns execute.
• Timestamp Ordering (T/O)
  • Determine serializability order of txns before they execute.

T/O Control

Use timestamps to determine the serializability order of txns.

If TS(\(T_i\)) < TS(\(T_j\)), then the DBMS must ensure that the execution schedule is equivalent to a serial schedule where \(T_i\) appears before \(T_j\).

Timestamp Allocation

Each txn \(T_i\) is assigned a unique fixed timestamp that is monotonically increasing.

• Let TS(\(T_i\)) be the timestamp allocated to txn \(T_i\).
• Different schemes assign timestamps at different times during the txn.

Multiple implementation strategies:

• System/Wall Clock.
• Logical Counter.
• Hybrid.

这里涉及分布式系统或数据库系统中事务（Transaction, txn）管理的时间戳分配策略。在分布式系统中，时间戳用于确保事务的顺序性、一致性和隔离性。

1. System/Wall Clock (系统时钟/墙上时钟)

   • 概念: 使用系统的物理时钟（通常是操作系统提供的当前时间）为每个事务分配一个时间戳。
   • 特点: 每个事务的时间戳是系统当前的时间，保证了时间戳的唯一性和单调递增性。
   • 优点: 简单直接，易于实现。
   • 缺点:
     • 在分布式系统中，时钟不同步可能会导致时间戳的不一致，导致问题如“时钟回拨”。
     • 依赖物理时钟的精确性，如果时钟同步不精确，会导致问题。

2. Logical Counter (逻辑计数器)

   • 概念: 使用一个全局的逻辑计数器来为事务分配时间戳。每当有新事务开始时，计数器的值会递增并分配给该事务作为时间戳。
   • 特点: 时间戳并不依赖物理时间，而是根据事务的顺序分配，确保了时间戳的唯一性和单调递增性。
   • 优点:
     • 不依赖物理时钟，因此避免了时钟同步问题。
     • 可以确保事务的全局顺序。
   • 缺点:
     • 在分布式系统中，维护全局计数器的开销较大，尤其是需要确保所有节点一致。
     • 如果系统有较高的事务并发性，可能会导致计数器成为瓶颈。

3. Hybrid (混合策略)

   • 概念: 结合物理时钟和逻辑计数器的策略。通常，这种策略使用物理时钟作为基础，并使用逻辑计数器来解决物理时钟的精度或同步问题。
   • 特点:
     • 时间戳的主要部分来自物理时钟，确保基本的时间顺序。
     • 逻辑计数器用于解决物理时钟不精确或多节点系统中的冲突问题。
   • 优点:
     • 能够在分布式环境中提供较高的时间戳精度和顺序性。
     • 解决了物理时钟同步问题，同时避免了逻辑计数器的单点瓶颈问题。
   • 缺点:
     • 实现较复杂，需要同时处理物理时钟和逻辑计数器。
     • 需要合理设计逻辑计数器的机制，以避免时间戳冲突。

Today's Agenda:

• Basic Timestamp Ordering (T/O) Protocol
• Optimistic Concurrency Control
• Isolation Levels

BASIC T/O

数据库中时间戳排序（Timestamp Ordering, T/O）协议的基本概念。这个协议用于确保事务的并发控制，避免冲突，从而保证数据一致性。

基本概念

• 事务（Transaction, T\(_i\)）: 一个操作序列，被视为一个独立的单位，它要么完全执行，要么完全不执行。
• 时间戳（Timestamp, TS(T\(_i\))）: 分配给每个事务的唯一标识符，用于标识事务的执行顺序。时间戳通常是单调递增的。
• W-TS(X): 对象 \(X\) 的最后一次写操作的时间戳。
• R-TS(X): 对象 \(X\) 的最后一次读操作的时间戳。

基本T/O规则

在基本T/O协议中，每个事务在读或写对象时，系统会根据时间戳来决定是否允许该操作，或者需要中止并重启事务。

1. 读操作 (Basic T/O - Reads)

   • 当事务 \(T_i\) 读取对象 \(X\) 时，系统会检查时间戳：
     • 如果 \(TS(T_i) < W-TS(X)\)：这意味着事务 \(T_i\) 的时间戳比对象 \(X\) 的最后一次写操作的时间戳早。允许这种操作会导致读取过时的数据，这违反了时间戳排序规则，因此事务 \(T_i\) 会被中止并重启。
     • 否则，允许 \(T_i\) 读取 \(X\)，并将 \(R-TS(X)\) 更新为 \(\max(R-TS(X), TS(T_i))\)，以确保后续事务读取的数据是一致的。

2. 写操作 (Basic T/O - Writes)

   • 当事务 \(T_i\) 写入对象 \(X\) 时，系统会检查时间戳：
     • 如果 \(TS(T_i) < R-TS(X)\) 或 \(TS(T_i) < W-TS(X)\)：这意味着事务 \(T_i\) 的时间戳比对象 \(X\) 的最后一次读或写操作的时间戳早。允许这种操作会导致数据的不一致，因此事务 \(T_i\) 会被中止并重启。
     • if 比最后一次读的时间戳早，那就会导致此时(最后一次读)“读”的并不是原始内容，而是原始+修改ing混杂的内容，不行！
     • if 比最后一次写的时间戳早，那会导致此时(最后一次写)“写”的并不是基于原始内容，而是基于修改ing混杂的内容，不行！
     • 否则，允许 \(T_i\) 写入 \(X\)，并将 \(W-TS(X)\) 更新为 \(TS(T_i)\)，同时做一个本地副本以保证可重复读。

用一段伪代码表示：

if (opt == READ)
    if (TS(Ti) >= W-TS(X)):
        Ti READ X # write
        R-TS(X) = max(R-TS(X), TS(Ti)) # update timestamp
        COPY X # local copy
    else:
        ABORT X
        RESTART X
else # opt == WRITE
    if (TS(Ti) >= R-TS(X) and TS(Ti) >= W-TS(X)):
        Ti WRITE X # write
        W-TS(X) = TS(Ti) # update timestamp
        COPY X # local copy
    else:
        ABORT X
        RESTART X

示例

假设系统中有两个事务 \(T_1\) 和 \(T_2\)，分别获得了时间戳 TS(\(T_1\)) = 5 和 TS(\(T_2\)) = 10。现在有一个对象 \(X\)，其初始状态为：

• W-TS(\(X\)) = 3（上一次写操作是在时间戳为3的事务中执行的）
• R-TS(\(X\)) = 3（上一次读操作也是在时间戳为3的事务中执行的）

情景1：\(T_1\) 试图读取 \(X\)

• 检查: 因为 TS(\(T_1\)) = 5 并且 W-TS(\(X\)) = 3, 满足条件，所以允许 \(T_1\) 读取 \(X\)。
• 更新: 更新 R-TS(\(X\)) = max(3, 5) = 5。

情景2：\(T_2\) 试图写入 \(X\)

• 检查: 因为 TS(\(T_2\)) = 10，并且 TS(\(T_2\)) > R-TS(\(X\)) = 5 和 TS(\(T_2\)) > W-TS(\(X\)) = 3，满足条件，允许 \(T_2\) 写入 \(X\)。
• 更新: 更新 W-TS(\(X\)) = 10。

情景3：\(T_1\) 试图写入 \(X\)（写操作在读操作之后）

• 检查: TS(\(T_1\)) = 5 现在小于 R-TS(\(X\)) = 5，所以 \(T_1\) 的写操作会被拒绝，\(T_1\) 会被中止并重启。

这个过程确保了所有事务都按照时间戳的顺序进行操作，避免了数据不一致和冲突。

THOMAS WRITE RULE

特定于 "opt==WRITE" 的一种简单的优化方式

Thomas Write Rule 是一个用于处理事务并发控制的规则，尤其是在时间戳排序协议中。这条规则主要用于避免不必要的事务中止，从而提高系统性能。

Thomas Write Rule 的主要作用是在某些情况下忽略写操作，从而避免事务中止，这样可以提高并发系统的性能，同时仍然保持数据一致性。

1. 检查读取时间戳 (R-TS(X)):

   • 如果 \(TS(T_i) < R-TS(X)\):
     • 说明事务 \(T_i\) 的时间戳比对象 \(X\) 的最后一次读操作的时间戳还要早。这种情况下，如果允许写操作，会违反时间戳顺序，导致数据不一致。因此，\(T_i\) 必须中止并重启。

2. 检查写入时间戳 (W-TS(X)):

   • 如果 \(TS(T_i) < W-TS(X)\):
     • 按照常规的时间戳排序规则，这种情况通常会导致事务中止，因为它会违反时间戳顺序。然而，Thomas Write Rule 提出了一种优化策略：
     • 忽略写操作：直接忽略 \(T_i\) 的写操作，允许事务继续执行，而不是中止。尽管这违反了时间戳顺序，但它不会影响数据的一致性，因为 \(X\) 的值不会被更早的事务覆盖。相当于说，事务写入的是“过时的数据”，直接忽略就好。

3. 允许写操作:

   • 如果上面的条件都不满足，即 \(TS(T_i) \geq W-TS(X)\)，则允许 \(T_i\) 对 \(X\) 进行写操作，并更新 \(W-TS(X)\)。

用一段伪代码表示：

if (opt == READ)
    if (TS(Ti) >= W-TS(X)):
        Ti READ X # write
        R-TS(X) = max(R-TS(X), TS(Ti)) # update timestamp
        COPY X # local copy
    else:
        ABORT X
        RESTART X
else # opt == WRITE: Thomas write rule
    if (TS(Ti) < R-TS(X)):
        ABORT X
        RESTART X
    else if (TS(Ti) < W-TS(X)):
        Ti WRITE X # write
        # write but do not update W-TS(X)
    else:
        Ti WRITE X # write
        W-TS(X) = TS(Ti) # update timestamp
        COPY X # local copy

Generates a schedule that is conflict serializable if you do not use the Thomas Write Rule.

• No deadlocks because no txn ever waits.
• Possibility of starvation for long txns if short txns keep causing conflicts.

Andy is not aware of any DBMS that uses the basic T/O protocol described here.

• It provides the building blocks for OCC / MVCC.

OPTIMISTIC CONCURRENCY CONTROL (OCC)

Intro

High overhead from copying data to txn's workspace and from updating timestamps.

• Every read requires the txn to write to the database.

Long running txns can get starved.

• The likelihood that a txn will read something from a newer txn increases.

If you assume that conflicts between txns are rare and that most txns are short-lived, then forcing txns to acquire locks or update timestamps adds unnecessary overhead.

OCC

A better approach is to optimize for the no-conflict case.

The DBMS creates a private workspace for each txn.

• Any object read is copied into workspace.
• Modifications are applied to workspace.

When a txn commits, the DBMS compares workspace write set to see whether it conflicts with other txns.

If there are no conflicts, the write set is installed into the "global" database.

乐观并发控制（OCC）是一种假设大多数事务不会发生冲突的并发控制机制，因此它优化了无冲突情况下的操作流程。

1. 创建私有工作区:

   • 当一个事务（txn）开始时，数据库管理系统（DBMS）为其创建一个私有工作区，这是一个事务专属的内存空间，用于存储事务过程中读取或修改的数据。
   • 在事务执行过程中，任何被读取的对象都会被复制到这个工作区中。
   • 对数据的所有修改都只应用到这个工作区，而不是直接修改全局数据库中的数据。

2. 事务提交（Commit）:

   • 当事务执行完毕并准备提交时，DBMS 会比较工作区中的写集合（write set），即事务在工作区中修改的所有数据，与其他正在进行的事务的写集合进行比较。
   • 如果没有检测到冲突（即工作区中的修改不会与其他事务的修改冲突），则将工作区中的修改应用到全局数据库中，完成提交。

3. 处理冲突:

   • 如果检测到冲突（例如，另一个事务已经修改了工作区中事务准备提交的数据），则当前事务可能会被中止，并需要重新开始。

OCC 的关键思想是乐观地假设大部分事务在提交时不会发生冲突，因此在执行过程中不会对事务进行锁定。只有在提交时，系统才会检查是否有冲突，从而决定是否应用修改。这种方法在高并发的场景下特别有效，因为它减少了事务之间的等待时间和锁争用的开销。

其实这个思想非常简单，就是对每个事务进行对应的缓冲区维护，所有更改都在缓冲区内进行，全部弄完以后再“提交”，检查是否有冲突

1. Read Phase:

   • Track the read/write sets of txns and store their writes a private workspace.

2. Validation Phase:

   • When a txn commits, check whether it conflicts with other txns.

3. Write Phase:

   • If validation succeeds, apply private changes to database. Otherwise abort and restart the txn.

OCC – READ PHASE

Track the read/write sets of txns and store their writes in a private workspace.

The DBMS copies every tuple that the txn accesses from the shared database to its workspace ensure repeatable reads.

• We can ignore for now what happens if a txn reads/writes tuples via indexes.

OCC – VALIDATION PHASE

When txn \(T_i\) invokes COMMIT, the DBMS checks if it conflicts with other txns.

• The DBMS needs to guarantee only serializable schedules are permitted.
• Checks other txns for RW and WW conflicts and ensure that conflicts are in one direction (e.g., older→younger).

Approach:

1. Backward Validation
2. Forward Validation

OCC – BACKWARD VALIDATION

Check whether the committing txn intersects its read/write sets with those of any txns that have already committed.

OCC – FORWARD VALIDATION

Check whether the committing txn intersects read/write sets with any active txns that have yet committed.

Each txn's timestamp is assigned at the beginning of the validation phase.

Check the timestamp ordering of the committing txn with all other running txns.

If TS(\(T_i\)) < TS(\(T_j\)), then one of the following three conditions must hold:

当事务 \(T_i\) 进入验证阶段时，它会被分配一个时间戳 \(TS(T_i)\)。这个时间戳用来确定事务的相对执行顺序。验证阶段的一个重要步骤就是检查当前提交的事务 \(T_i\) 和其他正在运行的事务之间的时间戳关系。

• TS(\(T_i\)): 表示事务 \(T_i\) 的时间戳。
• TS(\(T_j\)): 表示正在运行的其他事务 \(T_j\) 的时间戳。

假设 \(T_i\) 的时间戳小于 \(T_j\) 的时间戳（即 \(TS(T_i) < TS(T_j)\)），那么 OCC 协议要求以下三种条件中的至少一种必须成立，以确保事务顺序的正确性和数据的一致性。

三个条件

1. \(T_i\) 在其整个生命周期内都没有读取过 \(T_j\) 修改的数据:

   • 这意味着 \(T_i\) 和 \(T_j\) 没有发生读写冲突（Read-Write Conflict）。如果 \(T_i\) 读取了 \(T_j\) 修改的数据，而 \(T_j\) 的时间戳比 \(T_i\) 晚，可能会导致数据不一致。

2. \(T_j\) 在其整个生命周期内都没有读取过 \(T_i\) 修改的数据:

   • 这意味着 \(T_j\) 和 \(T_i\) 没有发生写读冲突（Write-Read Conflict）。如果 \(T_j\) 读取了 \(T_i\) 修改的数据，而 \(T_j\) 的时间戳比 \(T_i\) 早，可能会导致 \(T_j\) 读取了不一致的数据。

3. \(T_i\) 在 \(T_j\) 之前完成了所有的写操作:

   • 这意味着 \(T_i\) 的写操作已经在 \(T_j\) 开始之前完成，从而避免了写写冲突（Write-Write Conflict）。即 \(T_i\) 和 \(T_j\) 都试图写入相同的数据对象，但 \(T_i\) 应该在 \(T_j\) 之前完成写操作，以保持正确的事务顺序。

具体可以看下面的例子，这里有例子和讲解辅助：

\(T_i\) completes all three phases before \(T_j\) begins its execution.

This just means that there is serial ordering.

In this example above, Timestamp(T2-Read) < Timestamp(T1-Write), namely:

\(WriteSet(T_i) \cap ReadSet(T_j) \neq \emptyset\)

Hence, T1 must abort even though T2 will never write to the database :(

In this example, \(WriteSet(T_i) \cap ReadSet(T_j) = \emptyset\)

So it's safe to commit T1 :)

OCC – WRITE PHASE

Propagate changes in the txn's write set to database to make them visible to other txns.

Serial Commits:

• Use a global latch to limit a single txn to be in the Validation/Write phases at a time.

Parallel Commits:

• Use fine-grained write latches to support parallel Validation/Write phases.
• Txns acquire latches in primary key order to avoid deadlocks.

这段内容描述了乐观并发控制（Optimistic Concurrency Control, OCC）协议中的写阶段（Write Phase），特别是如何将事务的修改传播到数据库中，并使这些修改对其他事务可见的过程。具体来说，内容涉及了两种提交方式：串行提交（Serial Commits）和并行提交（Parallel Commits）。以下是详细解释：

在 OCC 协议中，事务在验证阶段通过验证后，进入写阶段。在这个阶段，事务的修改（即事务的写集合，Write Set）会被写入数据库，从而使得这些修改对其他事务可见。

串行提交 (Serial Commits)

• 单一事务限制: 在串行提交中，为了确保事务的正确性，系统会使用一个全局的锁（global latch）来限制在同一时间内只有一个事务可以处于验证（Validation）或写入（Write）阶段。
• 安全性: 这种方式确保了没有两个事务在同一时间内进行写操作，从而避免了并发问题。这种模式下，事务是串行地依次提交的，虽然安全性高，但可能会导致性能瓶颈，因为同时只能处理一个事务的提交。

并行提交 (Parallel Commits)

• 细粒度写锁: 在并行提交中，为了提高并发性，系统会使用细粒度的写锁（fine-grained write latches），使得多个事务能够同时处于验证和写入阶段。
• 主键顺序: 为了避免死锁问题（多个事务相互等待彼此释放锁），事务会按照主键顺序（primary key order）来获取这些锁。这意味着每个事务按照一定顺序来获取锁，确保不会出现循环等待，从而避免死锁。

其实可以很简单的理解为：原子级别的latch

SUMMARY && REFLECTION

OCC works well when the # of conflicts is low:

• All txns are read-only (ideal). Txns access disjoint subsets of data.
• If the database is large and the workload is not skewed, then there is a low probability of conflict, so again locking is wasteful.

OCC 在冲突较少的情况下非常有效，尤其在以下两种情况下表现优异：

1. 所有事务都是只读的:

   • 在这种情况下，事务之间不会有任何冲突，因为没有写操作，数据不会被修改。事务只读取数据，这使得并发控制变得非常简单和高效。

2. 数据库很大且工作负载不偏斜:

   • 如果数据库非常庞大，而事务的工作负载比较均匀（即各事务访问的数据子集彼此独立，没有重叠），那么发生冲突的概率就很低。在这种情况下，使用锁定机制（如两阶段锁定协议，2PL）显得不必要且浪费资源。

Performance Issues

• High overhead for copying data locally.
• Validation/Write phase bottlenecks.
• Aborts are more wasteful than in 2PL because they only occur after a txn has already executed.

尽管 OCC 在低冲突环境中表现良好，但它在某些情况下可能会遇到性能瓶颈：

1. 高开销的本地数据复制:

   • 在 OCC 中，每个事务会在本地创建一个工作空间，并将从数据库读取的数据复制到这个空间。这个数据复制过程可能会带来较高的开销，尤其是在事务需要处理大量数据时。

2. 验证/写入阶段的瓶颈:

   • OCC 的验证和写入阶段可能会成为性能瓶颈，特别是在多个事务需要同时提交时。如果有许多事务进入验证/写入阶段，系统可能无法有效处理，导致性能下降。

3. 事务回滚的浪费:

   • 在 OCC 中，事务的回滚通常比在两阶段锁定协议（2PL）中更加浪费资源。这是因为事务是在执行完毕后才进行验证，如果在验证阶段检测到冲突，整个事务必须回滚并重新开始，这意味着之前的执行都浪费了。

OCC 是一种适用于低冲突环境的并发控制协议，在数据库大且工作负载分散的情况下表现出色。然而，在高冲突场景下，它的性能问题可能会凸显出来，尤其是在本地数据复制、验证/写入阶段以及事务回滚的开销上。如果系统中的事务冲突较多，使用 OCC 可能会导致较高的资源浪费和性能瓶颈。

DYNAMIC DATABASES

Recall that so far, we have only dealt with transactions that read and update existing objects in the database.

But now if txns perform insertions, updates, and deletions, we have new problems...

Note

Conflict serializability on reads and writes of individual items guarantees serializability only if the set of objects is fixed.

THE PHANTOM PROBLEM

phantom 幻影

Approach #1: Re-Execute Scans

• Run queries again at commit to see whether they produce a different result to identify missed changes.

Approach #2: Predicate Locking

• Logically determine the overlap of predicates before queries start running.

Approach #3: Index Locking

• Use keys in indexes to protect ranges.

Note

幻影问题（Phantom Problem）主要在数据库并发控制（动态数据库）中产生，尤其是在使用多事务并发执行时。

产生原因

1. 范围查询与插入/删除的并发操作:

   • 范围查询: 一个事务（如事务A）执行一个范围查询，比如读取某个年龄段的所有员工信息 SELECT * FROM employees WHERE age BETWEEN 30 AND 40。
   • 插入/删除操作: 在事务A执行范围查询后，但在事务A提交之前，另一个事务（如事务B）插入、删除或修改了符合该范围的新记录。例如，事务B插入了一名年龄为35岁的员工。
   • 结果: 当事务A再次读取相同范围的数据时（例如在提交前的检查中），会发现比最初查询时多了一条（或少了一条）记录，这个新记录就是幻影问题中的“幻影”。

2. 事务隔离级别不足:

   • 在较低的事务隔离级别（如读已提交或可重复读）下，数据库系统可能无法完全隔离不同事务对同一数据集的操作，这导致幻影问题的产生。
   • 可重复读: 在“可重复读”隔离级别下，事务A可以多次读取相同的记录集而不会看到已存在的记录被修改。然而，幻影问题可能仍然存在，因为“可重复读”级别通常无法防止其他事务在查询范围内插入新记录。

3. 不适当的锁定机制:

   • 当数据库系统仅锁定已存在的行，而没有锁定查询范围（如表中的一个区间或条件），就会导致幻影问题。没有锁定整个查询范围，允许其他事务插入新的符合条件的记录，这就是导致幻影问题的一个常见原因。
   • 行级锁: 通常行级锁（Row-Level Locking）仅锁定已经存在的行，而不会锁定尚未存在但可能符合查询条件的新行。因此，当一个事务只获取行锁时，另一个事务仍然可以插入新行，导致幻影现象。

幻影问题的产生主要是因为事务在执行范围查询时，其他并发事务在该范围内插入、删除或修改了数据，导致查询结果在事务执行期间不一致。通常的解决方法包括使用适当的锁定机制（如谓词锁或范围锁），或在更高的事务隔离级别（如可序列化）下执行事务以避免此类问题。

RE - EXECUTE SCANS

这一段描述了在数据库管理系统（DBMS）中解决“幻影问题”（Phantom Problem）的一种方法，即重新执行扫描（Re-Execute Scans）。这种方法用于确保事务在提交时没有遗漏任何数据修改，特别是避免在范围查询中出现幻影行。

含义

在事务执行期间，DBMS 会记录所有查询的 WHERE 子句，即每个查询所涉及的条件或范围。这些条件定义了事务在数据库中检索数据的方式，特别是对于范围查询（例如 SELECT * FROM table WHERE condition）而言，DBMS 需要确保在事务提交之前，查询结果的完整性和一致性。

工作流程

1. 记录扫描集:

   • 对于事务执行的每个范围查询，DBMS 会保存这些查询的“扫描集”（即符合 WHERE 子句条件的数据集）。
   • 这意味着在事务提交之前，DBMS 会保留这些查询的结果集，以便在事务结束时进行验证。

2. 重新执行扫描:

   • 当事务准备提交时，DBMS 会重新执行这些范围查询，但仅限于重新扫描数据（而不是执行修改操作）。
   • 这意味着，DBMS 将再次运行每个查询的扫描部分，并检查其结果是否与最初的扫描结果一致。

3. 检查一致性:

   • 如果重新执行的扫描结果与最初的扫描集一致，那么可以确认在事务执行期间，没有新的数据插入或被删除，从而确保没有出现幻影问题。
   • 例如，如果一个 UPDATE 查询更新了符合某个条件的行，在事务提交时，DBMS 将重新扫描这些行，确认所有符合条件的行与最初扫描时一样，而不进行实际的更新操作。

假设有一个事务执行了以下 UPDATE 查询：

UPDATE employees SET salary = salary * 1.1 WHERE age BETWEEN 30 AND 40;

- 在执行这条查询时，DBMS 会记录所有符合 age BETWEEN 30 AND 40 条件的员工记录（即扫描集）。 - 当事务准备提交时，DBMS 将重新执行这个扫描过程，再次检查所有 age BETWEEN 30 AND 40 的记录，确认这些记录仍然存在且与初次扫描时一致。 - 但在重新扫描时，DBMS 不会实际修改 salary 字段，只是检查查询结果是否一致。

操作前看一眼，操作完再看一眼，如果完全一样，就说明没有干扰

PREDICATE LOCKING

这段描述的是一种用于解决并发控制问题的锁定机制（Locking Scheme），该机制最早由 System R 提出。具体来说，它描述了在数据库系统中如何使用锁来确保查询和修改操作的安全性和一致性。

含义

System R 是一种早期的关系数据库管理系统，它提出了一种锁定机制来管理并发事务，以确保数据的一致性和正确性。这种机制的关键在于在执行查询（如 SELECT）和修改操作（如 UPDATE、INSERT、DELETE）时，根据 WHERE 子句中的条件（谓词，Predicate）来加锁，从而防止并发冲突。

锁定机制

1. 共享锁（Shared Lock, S-Lock）：

   • 当一个 SELECT 查询执行时，会在 WHERE 子句中涉及的谓词上加一个共享锁。
   • 共享锁允许多个事务同时读取相同的数据，但不允许修改。
   • 例如，若有查询 SELECT * FROM employees WHERE age > 30，系统会在 age > 30 这个条件上加一个共享锁，允许其他查询同时访问这部分数据。

2. 独占锁（Exclusive Lock, X-Lock）：

   • 当执行 UPDATE、INSERT 或 DELETE 查询时，会在 WHERE 子句中涉及的谓词上加一个独占锁。
   • 独占锁不允许其他事务同时读取或修改相同的数据，确保只有一个事务能对这些数据进行更改。
   • 例如，若有更新操作 UPDATE employees SET salary = salary * 1.1 WHERE age > 30，系统会在 age > 30 这个条件上加一个独占锁，以阻止其他事务读取或修改这些记录。

实施情况

• 系统实现：
  • 虽然这种锁定机制在 System R 中被提出，但并未在实际系统中广泛实现。
  • 唯一的例外是 HyPer，这是一种现代内存数据库系统，它实现了所谓的“精确锁定（Precision Locking）”机制，该机制在某种程度上实现了 System R 提出的锁定策略。

这里似乎非常显然，跟我们之前提到的S-Lock和X-Lock一模一样

INDEX LOCKING SCHEMES

• Key-Value Locks
• Gap Locks
• Key-Range Locks
• Hierarchical Locking

Key-Value Locks

Gap Locks

Key-Range Locks

A txn takes locks on ranges in the key space.

• Each range is from one key that appears in the relation, to the next that appears.
• Define lock modes so conflict table will capture commutativity of the operations available.

Hierarchical Locking

ISOLATION LEVELS

LOCKING WITHOUT AN INDEX

If there is no suitable index, then the txn must obtain:

• A lock on every page in the table to prevent a record’s status='lit' from being changed to lit.
• The lock for the table itself to prevent records with status='lit' from being added or deleted.

如果数据库中没有适合的索引来加速查询或更新操作，那么事务必须通过锁定 更大的数据范围 来确保数据操作的安全性和一致性。具体来说，事务需要执行以下两个操作：

1. 锁定表中每一页：

   • 页面锁（Page Lock）：页面是数据库文件中的基本存储单元，它包含了多个记录（也称为行）。当没有索引可用时，事务需要获取表中每一页的锁，以防止其他事务更改某些记录的状态。例如，如果你正在执行一个涉及 status='lit' 条件的查询，锁定每一页可以防止其他事务将某个记录的 status 更改为 'lit'（或从 'lit' 改为其他状态），从而保持查询结果的一致性。

2. 锁定整个表：

   • 表级锁（Table Lock）：为了防止在操作进行期间有新的记录插入到表中或者已有的记录被删除，事务需要锁定整个表。这种锁可以确保在事务执行期间，没有新的符合 status='lit' 条件的记录被添加，也没有现有的记录被删除，保证了查询的稳定性和一致性。

假设有一张 Books 表，其中 status 列表示书籍的状态。现在你要查询所有 status='lit' 的书籍并进行一些操作（如更新或删除），但由于没有适合的索引，无法快速定位这些记录。

• 锁定每一页：你必须锁定表中的每一页，以防止其他事务在你操作期间更改某本书的 status 为 'lit' 或从 'lit' 改为其他状态。这样可以确保你查询到的结果在操作期间不会发生变化。
• 锁定整个表：同时，你还需要锁定整个 Books 表，以防止其他事务在操作期间插入新的 status='lit' 记录或删除现有的 status='lit' 记录。这样可以确保你处理的记录是完整且稳定的。

在没有适合索引的情况下，通过锁定表中每一页和整个表，事务可以防止在操作期间数据发生变化，从而确保数据操作的一致性。这种方法虽然可以保证安全性，但可能会降低并发性能，因为它阻止了其他事务在同一时间对表的访问。

WEAKER LEVELS OF ISOLATION

Serializability is useful because it allows programmers to ignore concurrency issues.

But enforcing it may allow too little concurrency and limit performance.

We may want to use a weaker level of consistency to improve scalability.

ISOLATION LEVELS

Controls the extent that a txn is exposed to the actions of other concurrent txns.

Provides for greater concurrency at the cost of exposing txns to uncommitted changes:

• Dirty Reads
• Unrepeatable Reads
• Phantom Reads

含义

隔离级别 决定了一个事务（txn）在多大程度上 可以"看到"其他事务的操作结果

• 隔离级别越高，事务之间的隔离程度越强，数据一致性越好，但并发性可能会降低
• 反之，隔离级别越低，系统允许更多的并发操作，但这可能导致事务暴露于未提交的更改，从而带来一致性问题

较低的隔离级别可能会导致以下三种常见的问题：

1. 脏读（Dirty Reads）：

   • 这是指一个事务读取了另一个未提交事务所做的更改。如果该更改的事务最终回滚，那么读取到的数据将是无效的，这就是“脏”的数据。
   • 例如，事务A更新了某行数据，但尚未提交，而事务B读取了该数据。如果事务A后来回滚，事务B读取到的数据就是脏读。

2. 不可重复读（Unrepeatable Reads）：

   • 这是指在同一个事务中，重复读取某一数据时，结果不同。这可能是因为在两次读取之间，另一个事务修改了该数据并提交了更改。
   • 例如，事务A两次读取同一行数据，第一次读到的是x=5，而在第二次读取时，事务B已将x修改为x=10并提交，因此事务A在第二次读取时看到的结果与第一次不同。

3. 幻读（Phantom Reads）：

   • 这是指在同一个事务中执行相同的查询时，结果集的行数发生了变化。通常发生在其他事务插入或删除了与查询条件匹配的行之后。
   • 例如，事务A第一次查询数据库，结果包含3行符合条件的数据。随后，事务B插入了一行新的符合条件的数据并提交。事务A再次执行相同查询时，发现结果变成了4行，这种情况被称为幻读。

隔离级别通过控制事务之间的可见性来平衡数据一致性和并发性。较高的隔离级别可以避免脏读、不可重复读和幻读，但会降低并发性能。较低的隔离级别允许更高的并发性，但可能会导致这些问题的发生。在实际应用中，选择合适的隔离级别取决于应用的需求和对数据一致性的容忍度。

Note

幻读主要契合的是“动态数据库”，这个我们在本节刚刚提到；脏读 and 不可重复读在我们之前反复提到的“静态数据库”中已强调，相信大家并不陌生