用于主存储器数据库的高效的多版本锁定

摘要

本发明涉及用于主存储器数据库的高效的多版本锁定。事务创建对实现多版本并发控制方案的主存储器数据库中的版本的等待依赖性。等待依赖性允许该事务在其他事务正读取版本的同时更新该版本。多版本并发控制方案还允许与等待依赖性并发地实现提交依赖性。提交依赖性允许事务在提交更新的版本之前读取该更新的版本。

说明书

技术领域

本发明涉及数据库管理，尤其涉及数据的并发控制。

背景技术

主存储器正变得足够的大，从而大部分在线事务处理数据库的工作集可被存 储在存储器中。为存储器内存储而优化的数据库系统与当前系统相比可支持高得多 的事务率。然而，标准并发控制方法无法缩放至这样的系统可实现的高事务率。

为存储器内存储而优化且在多核处理器上运行的数据库系统可支持非常高的 事务率和并发水平。在这样的环境中，高效地确保并发执行的事务之间的隔离变得 具有挑战性。当前的数据库系统通常通过锁定来实现隔离。然而，传统的单版本锁 定遭受可缩放性约束，从而使得传统的锁定不适用于具有非常高的事务率的系统。

发明内容

本发明涉及用于通过主存储器数据库中的高效的多版本锁定来实现并发控制 的方法、系统和计算机程序产品，其中锁是非阻塞的且事务的正确排序是由依赖性 机制来实施的。

在一个实施例中，第一事务将读取标记(也称为读取锁)放置在数据库中的 记录的一版本上。该读取标记指示第一事务正读取该记录的该版本，但不阻止另一 事务并发地读取或更新该记录。在第一事务终止之前，第二事务获取该记录的该版 本上的写锁定。写锁定阻止另一事务更新该记录的该版本。第二事务还创建对该版 本的等待依赖性。第二事务继续处理，但等待直到第一事务终止并移除该版本上的 读取记录才开始它的提交。

在另一实施例中，一个或多个第一事务各自将扫描标记放置在散列表中的桶 上。第二事务随后试图将记录的新的版本添加到该桶。第二事务在检测到该桶上的 一个或多个扫描标记之后创建对该一个或多个第一事务中的每一个的等待依赖性。 第二事务继续处理，但等待直到一个或多个第一事务中的每一个终止才开始它的提 交。

在另一实施例中，第一事务获取记录的一版本的写锁定。当该版本被第一事 务写锁定的同时，第二事务试图将读取标记放置在该版本上。在确定该版本由第一 事务写锁定之后，第二事务创建针对第一事务对该版本的等待依赖性，并将读取标 记放置在该版本上。等待依赖性使得第一事务等待直到第二事务终止之后才开始它 的提交。

提供本发明内容以便以简化形式介绍将在以下具体实施方式中进一步描述的 一些概念。本发明内容并非旨在标识所要求保护的主题的关键特征或必要特征，也 不旨在用于帮助确定所要求保护的主题的范围。

本发明的附加特征和优点将在以下描述中叙述，且其一部分根据本描述将是 显而易见的，或可通过对本发明的实践来获知。本发明的特征和优点可通过在所附 权利要求书中特别指出的工具和组合来实现和获得。本发明的这些和其他特征将通 过以下描述和所附权利要求书变得更加显而易见，或可通过对下文中所述的本发明 的实践来领会。

附图说明

为了描述可获得本发明的上述和其他优点和特征的方式，将通过参考附图中 示出的本发明的具体实施例来呈现以上简要描述的本发明的更具体描述。可以理 解，这些附图仅描述本发明的典型实施例，从而不被认为是对其范围的限制，本发 明将通过使用附图用附加特征和细节来描述和说明，在附图中：

图1示出根据一个或多个实施例的如何设置版本的时间戳的示例。

图2示出根据一个或多个实施例的表示记录锁的示例性数据结构。

图3示出根据一个或多个实施例的表示事务对象的示例性数据结构。

图4示出根据一个或多个实施例的表示扫描标记的示例性数据结构。

图5示出用于当事务获取对当前向其发放读取标记的一版本的写锁定时创建 对等待依赖性的方法的流程图。

图6示出用于当事务将新版本添加到被一个或多个其他事务锁定的桶时创建 对等待依赖性的方法的流程图。

图7示出用于当事务获取对已经被另一事务写锁定的版本上的读取标记时创 建对等待依赖性的方法的流程图。

图8示出根据一个或多个实施例的表示事务对象的示例性数据结构。

具体实施方式

本发明涉及用于在主存储器数据库中实现多版本并发控制的方法、系统和计 算机程序产品，其中锁是非阻塞的且事务的正确排序是由依赖性机制来实施的。本 发明还包括可同时实现乐观和悲观事务的多版本并发控制数据库的各实施例。

在一个实施例中，第一事务将读取标记放置在数据库中的记录的一版本上。 该读取标记指示第一事务正读取该记录的该版本，但不阻止另一事务并发地读取或 更新该记录。在第一事务终止之前，第二事务获取该记录的该版本上的写锁定。写 锁定阻止另一事务更新该记录的该版本。第二事务还创建对该版本的等待依赖性。 第二事务继续处理，但等待直到第一事务终止并移除其在该版本上的读取记录才开 始它的提交。

在另一实施例中，一个或多个第一事务中的每一个将扫描标记放置在散列表 中的桶上。第二事务随后试图将记录的新的版本添加到该桶。第二事务在检测到该 桶上的一个或多个扫描标记之后创建对该一个或多个第一事务中的每一个的等待 依赖性。第二事务继续处理，但等待直到一个或多个第一事务中的每一个终止才开 始它的提交。

在另一实施例中，第一事务获取记录的一版本的写锁定。当该版本被第一事 务写锁定的同时，第二事务试图将读取标记放置在该版本上。在确定该版本由第一 事务写锁定之后，第二事务创建针对第一事务的对该版本的等待依赖性，并将读取 标记放置在该版本上。等待依赖性使得第一事务等待直到第二事务终止之后才开始 它的提交。

本发明的各实施例可包括或利用专用或通用计算机，该专用或通用计算机包 括诸如例如一个或多个处理器和系统存储器等计算机硬件，如以下更详细讨论的。 本发明范围内的各实施例还包括用于承载或存储计算机可执行指令和/或数据结构 的物理和其他计算机可读介质。这样的计算机可读介质可以是可由通用或专用计算 机访问的任何可用介质。存储计算机可执行指令的计算机可读介质是物体计算机存 储介质(设备)。承载计算机可执行指令的计算机可读介质是传输介质。由此，作 为示例而非限制，本发明的各实施例可包括至少两种显著不同的计算机可读介质： 计算机存储介质(设备)和传输介质。

计算机存储介质(设备)包括RAM、ROM、EEPROM、CD-ROM、DVD或 其他光盘存储、磁盘存储或其他磁存储设备、或可用于存储计算机可执行指令或数 据结构形式的所需程序代码装置(软件)且可由通用或专用计算机中的一个或多个 处理器访问并执行以实现本发明的各方面的任何其他介质，以使得它们不仅仅是瞬 态载波或传播信号。

“网络”被定义为允许在计算机和/或模块和/或其他电子设备之间传输电子数 据的一个或多个数据链路。当信息通过网络或另一个通信连接(硬连线、无线、或 者硬连线或无线的组合)传输或提供给计算机时，该计算机将该连接适当地视为传 输介质。传输介质可包括可用于携带计算机可执行指令或数据结构形式的所需程序 代码装置且可由通用或专用计算机访问的网络和/或数据链路。上述的组合也应被 包括在计算机可读介质的范围内。

此外，在到达各种计算机系统组件之后，计算机可执行指令或数据结构形式 的程序代码装置可从传输介质自动转移到计算机存储介质(设备)(或者相反)。 例如，通过网络或数据链路接收到的计算机可执行指令或数据结构可被缓存在网络 接口模块(例如，“NIC”)内的RAM中，然后最终被传送到计算机系统RAM 和/或计算机系统处的较不易失性的计算机存储介质(设备)。因而，应当理解， 计算机存储介质(设备)可被包括在同样(或甚至主要)利用传输介质的计算机组 件中。

计算机可执行指令例如包括，当在一个或多个处理器处执行时使通用计算机、 专用计算机、或专用处理设备执行某一功能或某组功能的指令和数据。计算机可执 行指令可以是例如二进制代码、诸如汇编语言之类的中间格式指令、或甚至源代码。 尽管用结构特征和/或方法动作专用的语言描述了本主题，但可以理解，所附权利 要求书中定义的主题不必限于上述特征或动作。相反，上述特征和动作是作为实现 权利要求的示例形式而公开的。

本领域的技术人员将理解，本发明可以在具有许多类型的计算机配置的网络 计算环境中实践，这些计算机系统配置包括个人计算机、台式计算机、膝上型计算 机、消息处理器、手持式设备、多处理器系统、基于微处理器的或可编程消费电子 设备、网络PC、小型计算机、大型计算机、移动电话、PDA、寻呼机、路由器、 交换机等等。本发明也可以在通过网络链接(或者通过硬连线数据链路、无线数据 链路，或者通过硬连线和无线数据链路的组合)的本地和远程计算机两者都执行任 务的分布式系统环境中实践。在分布式系统环境中，程序模块可位于本地和远程存 储器存储设备中。

在讨论使用悲观事务来实现本发明的多版本并发控制方案之前，将描述可在 本发明中使用的示例性多版本并发控制方案的各基本概念。在这一示例性多版本并 发控制方案中，事务被给予分别指示事务的开始和结束事件的逻辑时间的两个唯一 的时间戳。这些时间戳用于定义事务事件之间的总体顺序。时间戳，如此处所使用 的，可以是从单调递增计数器接收的值，且不限于时钟值。

例如，当事务开始时，它可通过读取并递增时间戳计数器来接收时间戳。该 开始时间戳唯一地标识了该事务并因此在某些实施例中可充当事务id。当事务终止 时，它还可通过读取时间戳计数器并递增该计数器来接收结束时间戳。如果事务通 过提交而终止，则这一结束时间戳还可充当其提交时间戳。时间戳的这一使用使得 多版本化方案能够保留并发事务之间的可串行化。

主存储器数据库中的记录被版本化以允许多个事务的并发访问。时间戳还用 于标识记录的各版本以及它们的有效时间。例如，记录的提交版本包含两个时间戳， 开始时间戳和结束时间戳。提交版本的开始时间戳等于创建该版本的事务的提交时 间。例如，如果事务T1在其处理期间创建记录的一版本(诸如通过修改现有的记 录或创建新的记录)，则所创建的版本将接收与事务T1的提交时间戳相同的开始 时间戳。

版本的结束时间戳最初被设为指示该时间戳尚未确定的值，诸如无穷大。然 而，当另一事务T2提交对该版本的修改时(无论是对该版本的更新(因此创建新 的版本)、还是对该版本的删除)，该版本的结束时间戳被设为事务T2的提交时 间戳。换言之，一旦T2提交(并因此使得它的该记录的新版本或对该记录的删除 是持久的)，该记录的前一版本就不再有效。

在T2提交之前，该版本的结束时间戳被设为T2的事务ID，因为T2的提交 时间尚未可知。出于相同原因，这一相同的事务ID最初还用作新版本的开始时间 戳。因此，当事务创建新版本时，它将其事务ID分配给正被修改的版本的结束时 间戳和新版本的开始时间戳。一旦T2提交，它写入其提交时间戳作为旧版本的结 束时间戳以及作为新版本的开始时间戳。为对包含有效时间戳的版本以及具有临时 事务ID被分配为其时间戳的版本之间进行区分，可以使用标志。

图1示出版本V2的示例性生存期以及如何设置其时间戳。在时间t1，事务 T1通过更新在先版本来创建版本V2。T1将V2的开始时间戳设为其自己的事务ID 而将V2的结束时间戳设为诸如无穷大之类的值以指示该结束时间戳是尚未确定 的。因为V2的开始时间戳被设为T1的事务ID，其他事务可发现T1的事务对象 并因此确定T1的状态。T1还将版本V1(被更新以创建V2的版本)的结束时间 戳设为T1的事务ID，以向其他事务指示V1已被更新且被写锁定。

在时间t2，T1预先提交。预先提交涉及在提交之前T1获得结束时间戳并进 入有效阶段。这一时间t2是V2的有效时间的开始。然而，因为T1尚未提交并仍 然可能中止，所以V2的存在性仍然存疑。因此，V2的开始时间戳保留为T1的事 务ID。

在时间t3，T1完成有效阶段并提交。在时间t4，T1随后将V2的开始时间戳 从其事务ID更新为其结束时间戳t2。因此，V2的开始时间戳指示T1一提交(这 使得V2变得持久)V2的开始时间戳就变得有效(从其他事务的角度)。V2的开 始和结束时间戳此时分别是t2和无穷大。同时，T1还将V1的结束时间戳更新为 t2(未在图中示出)，它指示V1的有效时间在t2结束。

在稍后的某一时间t5，事务T2更新V2以创建新版本V3。T2采取与如上所 述的T1作出的用于设置V2和V1的时间戳类似的步骤来设置V2和V3的时间戳。 例如，T2将V2的结束时间戳设为T2的事务ID。在时间t6，T2预先提交并接收 t6作为其结束时间戳。如果T2继续提交，则t6将是V2的有效时间的结束。一旦 提交，T2就将V2的结束时间戳设为t6。

为概括以上示例，V2的开始时间戳采用了两个值。首先，它在被创建时用T1 的事务ID来初始化，且随后一旦T1提交就被设为T1的结束时间戳。这指示一旦 T1作出的改变是持久的则V2就变得有效。相反，V2的结束时间戳采用了三个值。 首先，它被初始化为无穷大，随后被设为T2的事务ID，最后一旦T2提交它就被 设为T2的结束时间戳。这指示一旦在T2提交时V3(由T2创建)变得持久，V2 就不再有效。

并发运行的事务可互相干扰从而产生不正确的结果。如果并发控制技术依赖 于抢先地阻止这样的有害干扰使其从不发生，则这种并发控制技术被称为悲观的。 这通常使用锁定来实现。另一方面，乐观并发控制技术不试图抢先地试图阻止干扰， 相反依赖于在允许事务提交之前确认没有发生有害干扰。类似地，取决于事务所依 赖的并发控制技术的类型，事务被称为悲观的或乐观的。

本发明允许悲观事务和乐观事务共存。悲观事务使用读取标记、扫描标记和 写锁定来实现本发明的多版本并发控制方案。悲观事务通过放置标记来阻止其读取 变得无效。在本发明中，可使用两种不同类型的标记来实现悲观事务：读取标记和 扫描标记。读取标记被放置在各版本上以确保读取稳定性，而扫描标记被放置在各 桶上以阻止幻影(phantom)。桶可以指代散列索引，然而本发明不限于使用散列 索引的数据库；扫描标记可等价地适用于经排序的索引等。

事务在开始对桶中的记录的扫描之前将扫描标记放置在散列表桶上。这不阻 止新的记录被添加到该桶，但直到扫描标记被移除才可提交新的版本。如果经排序 的索引由树结构来实现，则节点上的扫描标记保护以该节点为根的子树。同样，如 果经排序的索引由跳过列表来实现，则塔上的扫描标记保护从该塔到同一高度的下 一塔的范围。当在事务开始时由查询返回的版本集与在事务结束时由同一查询返回 的版本集不同时发生幻影。

事务通过递增版本V的读取标记计数来将读取标记放置在版本V上。在某些 实施例中，版本可被限于读取标记的最大数，并且还可包括一标志以阻止任何其他 读取标记被放置。因此，在任何给定时间，版本可具有多个读取标记。相反，版本 在任何给定时间只可具有单个写锁定。

图2示出根据本发明的某些实施例的表示读取标记的示例性数据结构200。如 上所述，每一版本包含结束时间戳字段201a，它可包含时间戳。图2还描述了本 发明可如何使用这一字段来记录读取标记。

如图2所示，为使得能够将结束时间戳字段201a用于时间戳以及读取标记两 者，第一位被指派为内容类型位，它定义了该字段包含的内容的类型。在图2所示 的示例性数据结构中，该字段的第一位被定义为这种内容类型位。当内容类型位被 设为第一值(例如0)时，该字段的其余63位是时间戳字段201a，如上所述。然 而，当内容类型位被设为第二值(例如1)时，该字段的其余63位被不同地解释。 例如，如图2所示，63位可在不再有读取标记标志202a、读取标记计数202b和写 锁定字段202c之间划分。不再有读取标记标志202a可被设为阻止任何进一步的读 取标志被放置在该版本上。读取标记计数202b记录该版本上的读取标记的当前数 量。写锁定字段202c包含持有该版本上的写锁定的事务(如果有的话)的事务ID， 或者如果该版本如上所述并未被锁定则为无穷大。

使用图2的示例性数据结构，事务可通过将其事务ID写入版本的写锁定字段 202c来对该版本写锁定。类似地，事务可通过递增版本的读取标记计数202b来将 读取标记放置在该版本上。本发明中的读取标记与典型的数据库实现中的读锁定不 同，因为版本上的读取标记不阻止另一事务更新该版本，如现在将进一步描述的。

在数据库的传统锁定实现中，当事务试图更新被读锁定的版本时，它将被迫 阻塞。相反，在本发明中，如果一个或多个事务已经将读取标记放置在版本上，则 另一事务可对该版本写锁定以更新该版本。换言之，作出更新的事务不会被迫阻塞 直到读取标记被移除。作出更新的事务可继续处理，包括更新该版本，然而，作出 更新的事务直到该版本上的所有读取标记都被移除之后才可提交。

类似地，在本发明中，如果一版本被一个事务写锁定，则另一事务可并发地 将读取标记放置在该版本上。在这一场景中，作出更新的事务(具有写锁定的事务) 直到该读取标记被移除之后才可提交。读取标记可通过进行读取的事务或提交或中 止来移除。由此，在上述场景中的每一个场景中，作出更新的事务被迫等待直到该 版本上的所有读取标记都被移除之后才提交，无论作出更新的事务是在一个或多个 读取标记被放置之前还是之后对该版本进行写锁定。

类似的规则适用于扫描标记。例如，如果第一事务在桶上放置了扫描标记， 则第二事务被允许将新的版本插入到该桶中。然而，第二事务不被允许提交，直到 第一事务移除其在该桶上的扫描标记。

为了在使用这些方案时便于正确的串行化，本发明实现等待依赖性。等待依 赖性迫使更新事务在它可获取结束时间戳并开始提交处理之前进行等待。为实现这 些等待依赖性，事务跟踪它的传入和传出的等待依赖性。传入依赖性是事务对其进 行等待的依赖性，而如果某一其他事务等待一事务完成，则该事务具有传出依赖性。

如图3所示，每一事务包括要跟踪依赖性的字段。该字段可被包含在事务对 象中，如图3所示，或者位于其他位置。对于传入等待依赖性，可维护两个字段： 等待计数301以及对不再有等待依赖性标志302。等待计数301指示一事务正在等 待多少传入等待依赖性。不再有等待依赖性标志302可被设为阻止任何更多的传入 依赖性的创建。例如，这一标志可用于阻止持续地添加新的传入依赖性而导致的资 源缺乏(starvation)。对于传出等待依赖性，维护等待事务列表303。这一列表包 含等待该事务完成的任何其他事务的事务ID。

下面的段落描述图2和3中示出的两个示例性数据结构可如何用于利用本发 明的多版本并发控制方案来实现等待依赖性。当事务TU更新版本V时，它通过 将其事务ID复制到V的写锁定字段202c来获得V上的写锁定。如果V的读取标 记计数202b大于0，则TU通过递增TU的等待计数301来采取对V的等待依赖 性。在该示例中，可以这么认为，TU创建了自己的等待依赖性。

TU也可以用另一方式来获得等待依赖性。如果TU获得V上的写锁定而V 的读取标记计数202b是0，则TU最初将不会取得对V的等待依赖性。当V被TU 锁定的同时，另一事务TR可能试图将读取标记放置在V上。TR将检测到V的读 取标记计数202b是0，但V被写锁定。TR随后读取TU的不再有等待依赖性标志 302，以确定TU是否将允许创建等待依赖性。如果TU的不再有等待依赖性标志 302未设置，则TR通过递增V的读取标记计数来将读取标记放置在V上，并通过 递增TU的等待计数301来给予TU对V的等待依赖性。出于这一原因，可以这么 认为，在该示例中TR给了TU等待依赖性。

为移除版本V上的读取标记，事务TR取决于各种因素而执行不同的步骤， 该各种因素包括V是否具有尚待解决的读取标记以及另一事务TU是否对V具有 写锁定。在第一场景中，如果V未被写锁定，TR简单地递减V的读取标记计数 202b并继续。在第二场景中，如果V被写锁定，但一个或多个其他事务已经将读 取标记放置在V上(即，V的读取标记计数大于1)，则TR同样简单地递减V的 读取标记计数202b并继续。

然而，在第三场景中，如果V被写锁定且V的读取标记计数等于1(这意味 着TR是具有V上的读取标记的唯一事务)，则TR打算移除V上的最后一个读取 标记。在该第三场景中，TR必须释放TU对V的等待依赖性。为此，TR将V的 读取标记计数202b设为0并将V的不再有读取标记标志202a设为真，因而阻止 在V上获得任何其他读取标记。随后，TR(通过读取V的写锁定字段202c中的 它的事务ID)来定位TU并递减TU的等待计数301。

在释放TU对V的等待依赖性之前将V的不再有读取标记标志202a设为真， 以确保在TU提交V的更新版本之前没有其他事务将读取标记放置在V上。这是 必要的，因为一旦TU对等待依赖性被移除，TU就可以继续提交。因此，通过由 TU所创建的更新的版本V’来代替V，V将变得无效。

图4示出在本发明的某些实施例中的用于实现扫描标记的示例性数据结构 400。同扫描标记有关的等待依赖性与同读取标记有关的等待依赖性类似地运作。 事务TR通过递增桶B的标记计数401并将其事务ID添加到B的标记列表402来 将扫描标记放置在桶B上。扫描标记的目的不是阻止版本被添加到桶，而是相反 的，阻止在扫描标记在原位的同时所添加的任何版本在其处理期间变得对TR可见。 换言之，另一事务TU可向B添加版本，但TU直到TR移除了它在B上的标记之 后才能提交。这通过TU获得对TR的等待依赖性来实施。

注意，在该扫描标记场景中，这一规范指的是对另一事务的等待依赖性，而 在记录锁定场景中，这一规范指的是对版本的等待依赖性。这是为了区分：在扫描 标记场景中等待依赖性取决于释放其扫描标记的一个或多个事务(即，多个版本上 的标记而非如在读取标记场景中的单个版本上的标记)。

事务TU可通过两种方式来获取由扫描标记引起的等待依赖性。第一，如果 TU正试图将新的版本V添加到具有一个或多个扫描标记的桶B，TU取得对B的 标记列表402中列出的每一事务(即，具有B上的扫描标记的每一事务)的等待 依赖性。为此，TU将它自己的事务ID添加到B的标记列表402中列出的每一事 务的等待事务列表303。TU还为B的标记列表402中列出的每一事务递增它自己 的等待计数301。

第二，如果事务TR扫描桶B并发现版本V，该版本V满足TR的搜索谓词 但因为V被仍然活动的事务TU写锁定而对TR不可见，则TR通过将TU的事务 ID添加到TR的等待事务列表303并递增TU的等待计数301来为TU注册对TR 的等待依赖性。创建此类等待依赖性以阻止TU在TR之前提交，TU在TR之前提 交会使得V变成TR的幻影。

图5示出用于在主存储器数据库的多版本并发控制方案中创建等待依赖性的 方法500的流程图。方法500将参照图2和3中的示例性数据结构来描述。在方法 500中，第一事务将读取标记放置在数据库中的记录的一版本上(动作501)。该 读取标记指示第一事务正读取该记录的该版本，但不阻止另一事务并发地读取或更 新该记录。例如，第一事务可通过递增该版本的读取标记计数202b来获取读取标 记。在第一事务终止之前，第二事务获取该记录的该版本上的写锁定(动作502)。 写锁定阻止另一事务更新该记录的该版本。例如，第二事务可通过将其事务ID写 入该版本的写锁定字段202c来获取写锁定。第二事务还创建对该版本的等待依赖 性(动作503)。例如，第二事务可递增其等待计数301，等待计数301可被存储 在其事务对象中。第二事务继续处理，但等待直到第一事务终止并移除该版本上的 读取记录才进行提交(动作504)。

方法500还可包括，第二事务在创建等待依赖性之前，通过读取版本的读取 标记计数202b并确定该读取标记计数202b大于0来确定该版本具有尚待解决的读 取标记。

在某些实施例中，方法500还可包括，第一事务确定其读取标记是该版本上 的最后一个读取标记(诸如通过确定在第一事务终止之前该版本的读取标记计数 202b等于1)。该方法还包括，第一事务递减该版本的读取标记计数202b，设置 该版本的不再有读取标记标志202a以及递减第二事务的等待计数301。第一事务 可通过读取该版本的写锁定字段202c中的第二事务的事务ID来标识第二事务。

在其他实施例中，方法500还可包括，第一事务确定一个或多个其他读取标 记已经被放置在该版本上，并且第一事务通过递减该版本的读取标记计数202b来 移除其读取标记。在某些实施例中，该版本的不再有读取标记标志202a、读取标 记计数202b和写锁定字段202c被存储在该版本中。

图6示出用于当事务将新版本添加到具有一个或多个扫描标记的桶时创建等 待依赖性的方法600的流程图。方法600将参照图3和4中的示例性数据结构来描 述。在方法600中，一个或多个第一事务将扫描标记放置在桶上(动作601)。例 如，一个或多个第一事务通过递增标记计数401并将它们的事务ID添加到标记列 表402来放置扫描标记。第二事务随后试图将记录的新的版本添加到该桶(动作 602)。第二事务在检测到该桶上的一个或多个扫描标记之后创建对该一个或多个 第一事务中的每一个的等待依赖性(动作603)。例如，第二事务可通过读取该桶 的标记计数401来检测该桶上的一个或多个标记。第二事务随后可通过将其事务 ID添加到锁定列表402中列出的每一事务的等待事务列表303来创建一个或多个 等待依赖性。第二事务继续处理，但等待直到一个或多个第一事务中的每一个终止 才进行提交(动作604)。例如，在终止时，一个或多个第一事务中的每一个都可 递增第二事务的等待计数301。一旦第二事务的等待计数301达到0，这指示第二 事务不再有等待依赖性，则第二事务可继续以进行提交。

图7示出用于当事务将读取标记放置在已经被另一事务写锁定的版本上时创 建等待依赖性的方法700的流程图。方法700将参照图2和3中的示例性数据结构 来描述。在方法700中，第一事务获取记录的一版本的写锁定(动作701)。例如， 第一事务可通过将其事务ID写入该版本的写锁定字段202c来获取写锁定。当该版 本被第一事务写锁定的同时，第二事务试图将读取标记放置在该版本上(动作 702)。在确定该版本被第一事务写锁定之后，第二事务创建针对第一事务的对该 版本的等待依赖性，并将读取标记放置在该版本上(动作703)。例如，第二事务 可通过确定该版本的写锁定字段202c包含第一事务的事务ID来确定该版本被写锁 定。第二事务可通过递增第二版本的等待计数301来创建第一事务对该版本的等待 依赖性，并且可通过递增该版本的读取标记计数202b来放置读取标记。等待依赖 性使得第一事务等待直到第二事务已终止并且移除了它在版本上的读取标记之后 才进行提交。例如，第一事务可继续处理，但直到等待计数301等于0之后才进行 提交。

除了如上所述的等待依赖性，本发明的各实施例还可与等待依赖性同时实现 提交依赖性。

与等待依赖性类似，提交依赖性可以是传入或传出依赖性，如下文将进一步 描述的。类似地，事务仅需要知道传入提交依赖性的数量，并因此维护传入提交依 赖性计数。此外，事务必须跟踪其传出提交依赖性中的每一个，并因此维护传出提 交依赖性集合。

再次参照图1，尽管V2从t2到t6是有效的，但是存在V2的有效性存疑的时 间段。换言之，因为在创建了记录的新版本之后事务可能中止，所以直到事务提交 之后才可能知道新版本将是有效的。具体地，V2在t1被创建，但其有效时间间隔 的起始直到T1在时间t2预先提交之后才知道。在这一时间(t1-t2)期间，V2仅对 T1可见。

此外，虽然一旦T1在t2预先提交就知道了V2的有效时间的起始，但直到 T1在t3实际地进行提交，V2才稳定，因为T1在它已预先提交之后仍然可能中止。 然而，使用根据本发明的提交依赖性，另一事务可被允许在这一间隔(t2-t3)期间 读取V2。提交依赖性允许进行读取的事务假定T1将提交，从而允许进行读取的 事务在T1已提交之前读取更新的版本V2。提交依赖性可由悲观和乐观事务两者 使用。

在该场景中，进行读取的事务TR可向T1注册提交依赖性。提交依赖性的实 现将参照图8来描述。图8与图3类似，因为它包括与图3中示出的字段类似的字 段。参照图8，为向T1注册提交依赖性，TR递增它自己的传入提交依赖性计数 804，并在T1的传出提交依赖性集合805中注册它的事务ID。随后，当T1已提交 之后，它在其传出提交依赖性集合805中定位TR的事务ID(以及已向T1注册了 提交依赖性的其他事务的任何其他事务ID)，并递减TR的提交依赖性计数804。

如果TR的唯一的依赖性是关于T1的，则它的提交依赖性计数804现在将为 0，这指示它不再等待任何其他事务进行提交。因此，TR现在可以进行提交。如可 以见到的，使用这一方法，TR能够在它确定版本将是有效的之前从该版本读取值。 如果T1中止而非提交，则T1将向TR通知该中止，从而导致TR也中止(因为它 已经读取了将永远不会变得有效的值)。这可以是通过在每一事务中使用中止标志 806来实现的，当中止标志被设置时致使事务中止。进行中止的事务(在该情况下 是T1)可在TR中设置这一标志。

因为大部分事务都提交了，所以使用提交依赖性的这一推测性的读取方法是 非常高效的。另外，在许多情况下，进行读取的事务将不会等待，因为在进行读取 的事务准备好提交之前，进行读取的事务所取决的事务完成了处理。

本发明包括可通过利用读取标记、扫描标记和写锁定、以及提交依赖性和等 待依赖性两者来实现如上所述的乐观和悲观事务两者的多版本并发控制技术的各 实施例。附图中示出的且在上文中描述的示例性数据结构允许两种依赖性对读取标 记、扫描标记和写锁定的并发使用。

本发明可具体化为其它具体形式而不背离其精神或本质特征。所描述的实施 例在所有方面都应被认为仅是说明性而非限制性的。因此，本发明的范围由所附权 利要求书而非前述描述指示。落入权利要求书的等效方案的含义和范围内的所有改 变被权利要求书的范围所涵盖。