多版本时间戳排序

---

多版本时间戳排序 (MVTO) 是一种流行的并发控制技术，用于数据库管理系统 (DBMS)。MVTO 允许数据项的多个版本同时共存，提供高并发性和数据一致性，同时防止冲突和死锁。

在本文中，我们将讨论 MVTO 的定义和组成部分，以及它的工作原理。

多版本时间戳排序 (MVTO)

在 MVTO 中，数据项的每个版本都有一个与之关联的唯一时间戳。访问数据项的事务也会被分配时间戳。

MVTO 有三个组成部分：时间戳、版本和排序 -

• 时间戳分配给事务和数据项版本以确定操作顺序。

• 版本在修改数据项时创建，每个版本都有一个唯一的时间戳。

• 排序确保事务仅根据其时间戳访问数据项的相应版本。

MVTO 的工作原理

读取操作

有两种类型的读取操作。它们是只读事务和读写事务。

• 只读事务可以访问数据项的任何版本。它存在于事务启动时。

• 读写事务只能访问数据项的最新版本。该版本是在事务提交之前创建的。

二、写入操作

有三种类型的写入操作：插入、删除和更新。

• 对于数据项插入的情况。它会得到一个新的时间戳。

• 对于数据项删除的情况。它被标记为已删除，但不会物理地从数据库中删除。

• 对于数据项更新的情况。将创建一个具有新时间戳的新版本，并将旧版本标记为已删除。

用于可串行化的多版本时间戳排序技术

在多版本时间戳排序技术中，为每个事务分配唯一的时间戳，并为每个数据项维护多个版本。该技术通过遵循两条规则来确保可串行化。

规则 1

如果事务 T 发出 Read(X) 请求，并且 Read_TS(Xi) < TS(T)，则系统将 Xi 的值返回给事务 T 并将 Read_TS(Xi) 更新为 TS(T)。

规则 2

如果事务 T 发出 Write(X) 请求并且 TS(T) < Read_TS(X)，则系统中止事务 T。如果 TS(T) = Write_TS(X)，则系统覆盖 X 的内容；如果 TS(T) > Write_TS(X)，则它创建 X 的新版本。

为数据项的每个版本维护的字段 -

• 该版本的价值。

• Read_TS(Xi)：Xi 的读取时间戳是成功读取版本 Xi 的任何事务的最大时间戳。

• Write_TS(Xi)：Xi 的写入时间戳是成功写入版本 Xi 的任何事务的最大时间戳。

示例

考虑以下包含事务 T1 和 T2 的调度，其中 T1 的时间戳为 5，T2 的时间戳为 10。

T1	T2
Read(X)
Write(X)
	Read(X)
	Write(X)
Read(X)
Write(X)
	Write(X)

• 最初，数据项 X 的状态为 X0，Read_TS(X0) = Write_TS(X0) = 0。

• T1 执行 Read(X)，读取 X0 的值，并将 Read_TS(X0) 设置为 TS(T1) = 5。

• T1 执行 Write(X)，创建一个新版本 X1 并设置 Read_TS(X1) = Write_TS(X1) = TS(T1) = 5。

• T2 执行 Read(X)，读取 X1 的值，并将 Read_TS(X1) 设置为 TS(T2) = 10。

• T2 执行 Write(X)，创建一个新版本 X2 并设置 Read_TS(X2) = Write_TS(X2) = TS(T2) = 10。

• T1 执行 Read(X)，读取 X1，读取成功。

• T1 执行 Write(X)，但由于 T2 已经读取了 X1，系统中止 T1。

• T1 的中止级联到 T2，T2 也中止。

多版本时间戳排序流程图

MVTO 的优点和缺点

以下是多版本时间戳排序 (MVTO) 的优点和缺点：

优点

• 高并发性

• 防止冲突和死锁

• 数据一致性

• 支持长时间运行的事务

缺点

• 存储开销

• 计算复杂度增加

• 可扩展性有限

结论

总之，多版本时间戳排序是一种并发控制技术。它允许存储和使用事务的数据项的多个版本。每个事务都分配一个唯一的时间戳。对于数据项的每个版本，系统维护值、读取时间戳和写入时间戳。

通过允许存储数据项的多个版本，多版本时间戳排序避免了不必要的事务中止。它减少了对同一数据项版本的竞争。但是，它也需要更多的存储空间，并且由于维护多个版本而可能导致开销增加。