Chapter 18 Multi-Version Concurrency Control

WHY WE NEED MVCC

The DBMS maintains multiple physical versions of a single logical object in the database:

• When a txn writes to an object, the DBMS creates a new version of that object.
• When a txn reads an object, it reads the newest version that existed when the txn started.

Writers do not block readers. Readers do not block writers.

Read-only txns can read a consistent snapshot without acquiring locks.

• Use timestamps to determine visibility.

Easily support time-travel queries.

1. 多个版本的物理对象:
   • 在多版本并发控制下，数据库系统会维护同一逻辑对象的多个物理版本。
   • 事务写入：当一个事务（txn）写入一个对象时，数据库会为这个对象创建一个新的版本。原有的版本不会被覆盖，而是保留起来。
   • 事务读取：当一个事务读取一个对象时，它读取的是在事务开始时 已经存在的最新版本。这确保了事务在执行期间看到的数据是一致的，不会被其他事务的更改所影响。
2. 读写操作互不阻塞:
   • 在MVCC中，写操作不会阻塞读操作，读操作也不会阻塞写操作。
   • 写操作不会阻塞读操作：因为 写操作会创建新版本，而读操作读取的是已存在的版本 ，所以读写操作可以同时进行而互不干扰。
   • 读操作不会阻塞写操作：因为 读操作不会锁定数据的版本 ，所以写操作可以自由创建新版本而不被读操作阻止。
3. 只读事务的快照读取:
   • 只读事务可以读取一个一致的快照，而不需要获取锁。
   • 时间戳用于可见性判断：系统使用时间戳来判断哪些数据版本在事务开始时是可见的。通过这种方式，只读事务能够看到数据在它开始执行时的状态。
4. 时光旅行查询（Time-travel Queries）
   • 由于数据库保留了对象的多个版本，所以可以轻松支持“时光旅行”查询。这种查询允许用户查看某个数据对象在过去某个时间点的状态。

Note

多版本并发控制通过保留数据对象的多个版本，使得不同事务可以并发地、安全地访问数据库，而不会相互干扰。这不仅提高了数据库的并发性，还支持 历史查询 功能。

Example-1

Example-2

SNAPSHOT ISOLATION (SI)

When a txn starts, it sees a consistent snapshot of the database that existed when that the txn started.

• No torn(撕裂) writes from active txns.
• If two txns update the same object, then first writer wins.

SI is susceptible(易受影响的) to the Write Skew Anomaly.

1. 事务开始时的快照一致性: 当一个事务（txn）开始时，它会看到一个一致的数据库快照。这意味着事务在执行过程中，看到的数据库状态是它开始时的状态，即使其他事务同时在对数据库进行更新。

   • 无撕裂写入（No Torn Writes from Active Txns）：这是指正在进行的事务不会看到部分写入的、不完整的数据。由于事务在开始时会看到一个一致的快照，所以不会遇到“撕裂写入”问题（即数据部分更新的情况）。
   • 第一个写者胜出：如果两个事务尝试更新同一个对象，那么第一个成功提交更新的事务的更改会被保留，而后一个事务的更改可能会被回滚或拒绝。这是一种确保数据一致性的机制，防止多个事务同时修改数据导致不一致。

2. SI（快照隔离）和写入偏差异常（Write Skew Anomaly）

   • 快照隔离（Snapshot Isolation, SI） 是一种事务隔离级别，允许每个事务在开始时看到数据库的一个快照。这种隔离级别避免了大多数并发冲突，但它有一个潜在的问题：写入偏差异常。
   • 写入偏差异常（Write Skew Anomaly）：这是在快照隔离下可能发生的一种并发异常。在某些情况下，如果两个事务读取相同的数据，并基于这些数据做出决定，然后分别写入更新，可能导致数据不一致。虽然每个事务在单独执行时看似都是正确的，但并发执行时，它们的组合操作可能会导致意外的结果。

• skew 倾斜；偏差
• anomaly 异常

Example:

假设有两个医生（Dr. A 和 Dr. B）查看同一个病人的病历，然后分别决定对病人进行不同的治疗。Dr. A 看到病人的状况需要一种治疗，而 Dr. B 看到的状况需要另一种治疗。如果这两个决定基于相同的病历快照（即在同一时间点读取），并且他们分别更新病历，则最终的结果可能会导致病人同时接受两种不兼容的治疗。这就是写入偏差异常的一个例子。

Note

在快照隔离下，事务在开始时会看到一个一致的数据库快照，避免了“撕裂写入”等问题。然而，它也可能导致写入偏差异常，这是一种需要小心处理的并发问题。

这里以一个例子讲解针对同一份数据，采用A/B 序列化执行 与 并行化执行 的差异：

针对下列两个操作:

• Txn #1: Change white marbles to black
• Txn #2: Change black marbles to white

如果并行化执行:

如果序列化执行:

Note

MVCC is more than just a concurrency control protocol. It completely affects how the DBMS manages transactions and the database.

MVCC DESIGN DECISIONS

• Concurrency Control Protocol
• Version Storage
• Garbage Collection
• Index Management
• Deletes

CONCURRENCY CONTROL PROTOCOL

Approach #1: Timestamp Ordering

• Assign txns timestamps that determine serial order.

Approach #2: Optimistic Concurrency Control

• Three-phase protocol from last class.
• Use private workspace for new versions.

Approach #3: Two-Phase Locking

• Txns acquire appropriate lock on physical version before they can read/write a logical tuple.

很显然，这就是我们之前在chapter15/16/17中介绍的CC PROTOCOL

VERSION STORAGE

The DBMS uses the tuples' pointer field to create a version chain per logical tuple.

• This allows the DBMS to find the version that is visible to a particular txn at runtime.
• Indexes always point to the "head" of the chain.

Different storage schemes determine where/what to store for each version:

• Approach #1: Append-Only Storage
  • New versions are appended to the same table space.
• Approach #2: Time-Travel Storage
  • Old versions are copied to separate table space.
• Approach #3: Delta Storage
  • The original values of the modified attributes are copied into a separate delta record space.

APPEND - ONLY STORAGE

All the physical versions of a logical tuple are stored in the same table space. The versions are inter-mixed.

On every update, append a new version of the tuple into an empty space in the table.

这个想法非常简单直接：我们采用main table这张大表，里面存有A/B/C/D...所有的信息

对于每一类，不同的更新使用index进行维护，不同的版本之间使用指针进行链接 即可 :)

那么很显然，有个问题需要考虑——指针维护的顺序：

Approach #1: Oldest-to-Newest (O2N)

• Append new version to end of the chain.
• Must traverse chain on look-ups.

Approach #2: Newest-to-Oldest (N2O)

• Must update index pointers for every new version.
• Do not have to traverse chain on look-ups.

TIME -TRAVEL STORAGE

1. On every update, copy the current version to the time-travel table. Update pointers.
2. Overwrite master version in the main table and update pointers.

每次更新前的准备工作是：将当前需要的内容从main table直接复制到time-travel table中；并对应的改写指针关系

然后，在main table中直接覆盖当前的内容，并更新指针关系

DELTA STORAGE

On every update, copy only the values that were modified to the delta storage and overwrite the master version.

只记录并维护“改动关系”

In this scenario,

• txns can recreate old versions by applying the delta in reverse order
• the DBMS would have to read the delta record and the master version to find the current value of the attribute.

GARBAGE COLLECTION

The DBMS needs to remove reclaimable physical versions from the database over time.

• No active txn in the DBMS can "see" that version (SI).
• The version was created by an aborted txn.

Two additional design decisions:

• How to look for expired versions?
• How to decide when it is safe to reclaim memory?

Approach:

• Tuple-level
  • Find old versions by examining tuples directly.
  • Background Vacuuming vs. Cooperative Cleaning
• Transaction-level
  • Txns keep track of their old versions so the DBMS does not have to scan tuples to determine visibility.

这段讲解了数据库管理系统（DBMS）中与多版本并发控制（MVCC）相关的垃圾回收机制。垃圾回收的主要目的是从数据库中移除那些不再需要的物理版本，从而释放存储空间。

数据库系统为了“时间回溯”功能，会保留多个数据版本，但这些版本会随着时间的推移累积，占用大量存储空间。为了优化资源使用，DBMS需要定期清理这些不再需要的旧版本。

需要清理的版本有两种情况：

• 没有活动事务能“看到”的版本：即在所有正在执行的事务中，这些版本都已经变得不可见，因此可以被回收。
• 由中止的事务创建的版本：如果某个事务在中途被中止，它创建的任何数据版本都被视为无效，应该被清理。

为了有效地执行垃圾回收，DBMS需要做出两个关键的设计决策：

• 如何查找过期版本？

  • DBMS需要一种方法来==查找已经过期的、不再需要的数据版本==。

• 何时可以安全地回收内存？

  • DBMS需要决定在 何时可以安全地删除这些版本并释放相关的存储 空间。

有两种常见的垃圾回收方法：元组级别和事务级别。

1）元组级别的垃圾回收

• 直接检查元组：DBMS通过直接检查每个元组来查找旧版本。
• 背景清理与协作清理：
  • 背景清理（Background Vacuuming）：系统会在 后台定期运行一个进程来扫描数据库，并删除那些不再需要的旧版本。
  • 协作清理（Cooperative Cleaning）：事务在执行过程中，可以帮助清理 它们发现的旧版本。这种方法可以分散垃圾回收的负担，避免集中清理带来的性能瓶颈。

2）事务级别的垃圾回收

• 事务跟踪旧版本：每个事务在运行过程中记录自己生成的旧版本。当事务完成时，DBMS可以根据这些记录来清理不再需要的版本。这样，DBMS无需扫描整个数据库来查找哪些版本已经过期。

TUPLE - LEVEL GC

Background Vacuuming

Separate thread(s) periodically scan the table and look for reclaimable versions. Works with any storage.

Cooperative Cleaning

Worker threads identify reclaimable versions as they traverse version chain. Only works with O2N.

TRANSACTION - LEVEL GC

Each txn keeps track of its read/write set. On commit/abort, the txn provides this information to a centralized vacuum worker.

The DBMS periodically determines when all versions created by a finished txn are no longer visible.

更新A类：

再更新B类：

现在形成了这样的“终态”：

Vacuum来清理，整个过程全部结束：

INDEX MANAGEMENT

Primary key indexes point to version chain head.

• How often the DBMS must update the pkey index depends on whether the system creates new versions when a tuple is updated.
• If a txn updates a tuple's pkey attribute(s), then this is treated as a DELETE followed by an INSERT.

Secondary indexes are more complicated...

SECONDARY INDEXES

Logical Pointers

• Use a fixed identifier per tuple that does not change.
• Requires an extra indirection layer.
• Primary Key vs. Tuple Id

Physical Pointers

• Use the physical address to the version chain head.

MVCC INDEXES

• MVCC DBMS indexes (usually) do not store version information about tuples with their keys.
  • Exception: Index-organized tables (e.g., MySQL)

• Every index must support duplicate keys from different snapshots:

  • The same key may point to different logical tuples in different snapshots.

• 索引通常不存储版本信息

  • 在MVCC数据库中，索引通常不会与键一起存储具体的版本信息。
  • 不存储版本信息：通常，MVCC DBMS中的 索引只存储与键相关的位置信息，而不存储版本信息。这意味着索引只是指向某个数据的位置，而不直接区分该数据是哪个版本。
  • 例外情况：索引组织表：在某些数据库系统（例如MySQL）的特定实现中，索引组织表（Index-Organized Tables, IOTs）是一个例外。在这些表中，索引本身可能会包含版本信息，因为索引与数据是紧密结合的。IOTs中的数据存储方式与普通表不同，数据的物理排序与索引顺序一致，因此索引需要更详细地管理版本信息。

• 索引必须支持不同快照中的重复键

  • 在MVCC环境下，同一个键可能在不同的事务快照中指向不同的逻辑元组。这种情况要求索引具备处理重复键的能力。
  • 支持重复键：由于在不同的事务快照中，同一个键可能指向不同的版本，因此索引需要能够管理这些重复键。这意味着，当你在不同的快照中查询同一个键时，可能会得到不同的结果（因为这些结果对应的是不同的逻辑元组）。
  • 不同快照的不同逻辑元组：例如，事务A和事务B可能都更新了一个包含相同键的元组。事务A看到的是自己更新的版本，而事务B看到的是另一个版本。索引必须支持这些情况，并正确地指向在特定快照下可见的版本。

在MVCC数据库中，索引通常不会与键一起存储具体的版本信息，除非是像MySQL中的索引组织表这种特殊情况。同时，索引必须支持在不同事务快照中出现的重复键，因为同一个键在不同快照中可能指向不同的逻辑元组。这种机制确保了事务在并发执行时，能够正确地访问自己对应的版本数据。

Each index's underlying data structure must support the storage of non-unique keys.

Use additional execution logic to perform conditional inserts for pkey / unique indexes.

• Atomically check whether the key exists and then insert.

Workers may get back multiple entries for a single fetch. They then must follow the pointers to find the proper physical version.

MVCC DELETES

The DBMS physically deletes a tuple from the database only when all versions of a logically deleted tuple are not visible.

• If a tuple is deleted, then there cannot be a new version that tuple after the newest version.
• No write-write conflicts / first-writer wins

We need a way to denote that tuple has been logically delete at some point in time.

Approach #1: Deleted Flag

• Maintain a flag to indicate that the logical tuple has been deleted after the newest physical version.
• Can either be in tuple header or a separate column.

Approach #2: Tombstone Tuple

• Create an empty physical version to indicate that a logical tuple is deleted.
• Use a separate pool for tombstone tuples with only a special bit pattern in version chain pointer to reduce the storage overhead.

1）MVCC中的删除操作

在MVCC系统中，当删除一个元组时，DBMS不会立即从数据库中物理删除该元组。这是因为其他事务可能仍然在访问该元组的不同版本。

• 物理删除时机：DBMS只有在确认 所有版本的逻辑上已删除元组都不可见后，才会物理删除该元组。这意味着，只有当没有任何活动的事务能够看到这个元组的任何版本时，DBMS才会真正从数据库中移除它。
• 版本管理：当一个元组被删除后，不会再有新的版本出现。也就是说，删除操作是最终的，新的写操作不会针对已经逻辑删除的元组创建新版本。
• 避免写写冲突：由于删除操作意味着元组不再接受新的版本，所以不会发生写写冲突的情况。如果两个事务试图删除同一个元组，通常第一个提交的事务将会成功删除该元组。

2）标记逻辑删除的方法

为了标识一个元组已经被逻辑删除，DBMS通常会使用以下两种方法之一：

方法 1：删除标志（Deleted Flag）

• 删除标志：DBMS会维护一个标志（flag），用于指示某个元组在其最新版本之后已经被逻辑删除。
• 标志位置：这个标志可以放在元组的头部（header）或者作为一个独立的列来存储。当标志被设置时，它表示这个元组的所有版本已经被删除。

方法 2：墓碑元组（Tombstone Tuple）

• 墓碑元组：墓碑元组是一种特殊的物理版本，用于指示某个逻辑元组已经被删除。墓碑元组本身没有实际数据，只是一个占位符，表示该元组在逻辑上已不存在。
• 存储优化：墓碑元组通常存储在一个单独的池（pool）中，并使用一个特殊的位模式（bit pattern）来指示在版本链指针中的位置。这样可以减少存储开销，因为墓碑元组不需要存储实际的数据内容。

Note

1. 在MVCC系统中，删除操作不会立即物理删除元组，而是等待所有版本不可见时才进行物理删除。
2. 为了标识逻辑上已删除的元组，DBMS通常使用删除标志或墓碑元组。
   • 删除标志通过在元组头部或独立列中设置一个标志来表示删除，而墓碑元组则是一个特殊的空版本，用来指示元组已被逻辑删除。
   • 这些机制有助于管理删除操作，并确保数据库的一致性。

CONCLUSION

MVCC is the widely used scheme in DBMSs. Even systems that do not support multi-statement txns (e.g., NoSQL) use it.