面向完井的读写时间戳乐观并发控制协议研究

， ，

(东北石油大学 计算机与信息技术学院，大庆 163318)

0 引言

完井，油气井的完成，其周期从钻井作业开始，直至投产作业结束[1]。由于完井工艺涉及的诸多环节需要野外作业[2]，野外移动通信信号弱，所以完井业务的移动计算环境具有频繁断接性、网络通信不对称性[3-5]，同时移动终端存在电池续航时间短、CPU处理能力较弱、存储空间有限等问题[6-7]。在受到这些条件限制的情况下，在进行事务处理时就会出现事务延迟、实时性差等情况，此时就会导致完井业务管理效率低下的问题，甚至影响整个油田信息管理的效率。因此提高移动事务处理的性能，成为了当前急需突破的方向。

移动事务是移动设备上数据库维护及管理的重要方法，需要在网络断开时仍然继续数据处理，所以移动设备的数据库具备必要的自我修复和应急处理能力，能够对离线操作的移动事务有所支持[8-9]。

事务处理的核心机制是并发控制，事务并发控制属于事务调度的一种，出色的并发控制调度策略应能够有效提高系统的响应速度和吞吐量，优化资源配置。并发控制常见的有乐观并发控制协议、悲观并发控制协议和混合并发控制协议3种事务并发控制协议[10]，由于完井运行信息移动服务平台的数据操作多为数据查询，而乐观并发控制协议比悲观并发控制协议更加适用于读多写少冲突较少的事务处理，在乐观并发控制协议下，该平台数据的收敛性、一致性均得到了保证。因此本文基于对完井数据移动管理、并发控制的把握，从并发控制优化入手引入基于读写时间戳的乐观并发控制协议从而提高处理事务并发的效率。

1 基于读写时间戳的乐观并发控制协议

乐观并发控制协议[11]是H.Kung等人提出的，在并发事务发生冲突可能性较低的场景下，该协议具有较高适用性，且分为3个阶段，来完成整个事务的执行。

基于时间戳的并发控制方法[12]，以预先设定的串行序次来执行相关事务。出于确定该次序的需要，事物处理器将在时间戳和事务之间建立起一一对应关系，同时，需确保在整个数据库中该时间戳的唯一性。由时间戳法而来的可串行性调度表，和对事务时间戳序列的成功提交等价。这种方法不仅能有效降低死锁问题的发生率，还能对由资源冲突造成的事务等待进行规避。

1.1 传统乐观并发控制协议

传统乐观并发控制协议分为读、有效性验证、写 3个阶段。针对具体的完井业务而言，第一阶段的任务是对完井数据进行读取，并将数据写入本地，并不对数据库进行真正的更新。第二阶段的主要工作为：以协议规则为依据，校验在冲突可串行化方面，全部完井事务调度的合理性。在写阶段，则以校验结果为依据，提交数据，将其永久写入完井数据库。在进行验证时，传统的乐观并发控制协议常用算法为BOCC，即所谓后向乐观并发控制，也就是说，设最后两个阶段有效性验证阶段与写阶段作为一个原子操作val-write阶段，不可分割地执行，在检测到数据访问冲突时，重启正在验证的事务。

将完井事务ti的读、写数据项集合，分别记为RS(ti)、WS(ti)，完井事务读阶段结束后，可确定上述两个集合，接下来，需冲突检测、有效性验证全部完井事务。

定义1：完井事务tj的效力，经BOCC验证得以肯定，若任意已提交完井事务ti符合下述要求之一：

条件1：提交完井事务ti后，执行完井事务tj，也就是说，在ti执行完毕的情况下，方可执行tj，具体如图1所示。

图1 条件1示意图

条件2：若ti的写数据项集合、tj的读数据项集合交集为空，即RS(tj)∩WS(ti)=φ，且在ti的val-write阶段后，对完井事务tj进行有效性检查，具体如图2所示。

图2 条件2示意图

在这种情况下，BOCC仅形成冲突可串行化调度[13]。

在BOCC模式下，完井事务的乐观并发执行可无障碍完成，并无错漏地将事务调度输出。但是，BOCC存在一定的局限性，所涉及事务并发控制方法也是基础性的。

(1) BOCC对应用条件的要求非常严格。条件1可将串行化调度输出，具体见图1；条件2可对完井事务ti读写中的数据不可被完井事务tj读取作出了规定，但这和实际调度操作存在一定出入，在完井运行信息移动服务平台中移动完井事务的调度中有可能出现条件2的情况，此时，系统基本处于提交保序化状态，尽管冲突可串行化正确调度也有一定的形成几率，但给完井事务并发度的实现造成了负面影响，降低了完井运行信息移动服务平台的资源吞吐量，效率低下。

(2) 当完井运行信息移动服务平台出现长事务的情况时，由于若干冲突的短事务，易造成包括部分本无需重启的完井事务的长事务的频发重启，具体如图3所示。

图3 完井事务读写冲突

按照BOCC协议相关要求，上图在RS(tj)∩WS(ti)=a≠φ的情况下，发生完井事务tj的读操作与完井事务ti的写操作冲突，此时完井事务tj应当重启。同理，当RS(tk)∩WS(ti)=a≠φ时，完井事务tk的读操作和完井事务ti的写操作存在交叉，需中止并重新启动tk。然而，进一步分析上述操作可知，这两种情况存在较大差异。

在完井事务tj执行结束前，ti已经写回tj读取的完井数据项a，a由此被更新，tj对脏数据进行了读取，无法为ti、tj的冲突可串行化提供保证，故tj必须回滚并重新启动，但是，tk读取的a是最近更新的数据项，尽管无法规避完井事务tj的写操作与完井事务tk的读操作的冲突，但冲突可串行化调度的出现，使得tk并无回滚重启的必要。

(3) 作为一个临界区处理，val-write不具备可分割性，降低了部分完井事务形成冲突的概率，但若写操作向数据库中写入所有本地完井数据，则需回滚或挂起全部冲突并发的事务，进而给系统的性能造成负面影响，造成许多额外重启操作的发生，如图4所示。不难发现，若将BOCC的临界区限制消除，则有可能触发一系列新的完井事务重启问题。

图4 完井事务的BOCC写写冲突

在WS(tj)∩WS(ti)=a≠φ的情况下，ti、tj两个完井事务出现写操作间的冲突，tj终止且重新启动。类似的事，在WS(tk)∩WS(ti)=a≠φ的情况下，tk、tj两个完井事务出现写操作间的冲突，tk终止且重新启动。对于上述情况的发生，BOCC协议并未进行深入解析，但深究之下不难发现，上述两种情况存在明显差异。

ti的写操作覆盖了tj对a的写操作w(a)，在ti的验证后，有效验证tj，完井事务应形成串行序列ti,tj，但结合图3.4可以发现，在所执行的完井事务中，出现了tj→ti的冲突，在这种情况下，完井事务的串行化无从保证，故须终止tj，并对其进行重新启动。但tk发出的对完井数据项a的写操作w(a)覆盖了完井事务ti所写的完井数据项a，虽然有完井事务ti与完井事务tk的写写冲突，但完井事务tk的有效验证发生在完井事务ti的有效验证之后，结合上一章节相关内容可知，冲突可串行化调度的出现，使得tk并无回滚重启的必要。

1.2 基于读写时间戳的乐观并发控制协议

在完井运行信息移动服务平台的移动计算环境中，在传统乐观并发控制协议下，读、有效性验证、写，是所有完井事务均不可避免的三个阶段。但优化后的乐观并发控制协议，对BOCC的应用环境进行了延伸，使val-write的临界区限制得以消除，同时，基于对各种冲突的分析，完美解决了性能过耗、频繁重启等问题，促进了完井事务调度并发度的提高。现对相关概念作出规定，以更好地进行表述：

定义2 在∀ti中，将执行ti的起始时间规定为S(ti)。

定义3 在∀ti中，将ti读阶段结束，启动有效性验证操作的起始时间规定为V(ti)。

定义4 在∀ti中，将ti有效性验证结束，启动写操作的起始时间规定为W(ti)。

定义5 在∀ti中，ti写阶段完毕的时间节点，规定为F(ti)。

定义6 在∀ti中，以映射f指代d(opi)也就是ti的数据集，则有式(1)。

(1)

定义7 对于∀ti，完井事务ti的读集SR(ti)和写集SW(ti)分别定义为式(2)(3)

SR(ti)=∪d(opi), if ∀opi∈ti,opiis read operation

(2)

Sw(ti)=∪d(opi), if ∀opi∈ti,opiis write operation

(3)

定义8 对于∀ti和tj，对tj、ti两个完井事务的冲突写集、读集CWW(ti,tj)、CRW(ti,tj)作出如下规定为式(4)、(5)。

CRW(titj)=SR(ti)∩SW(tj)

(4)

CWW(titj)=SW(ti)∩SW(tj)

(5)

定义9 在∀ti中，分别以下述公式来定义ti的读、写点TDR(xi)、TDW(xi)：

TDR(xi)=事务ti读数据项x的时刻

(6)

TDW(xi)=事务ti写数据项x的时刻

(7)

定义10 定义随机完井数据项x的读、写时间戳TSR(x)、TSW(x)分别为式(8)、(9)。

TSR(x)=数据项x被最后从数据库读出的时刻，并记tr(x)为读取数据项x的事务

(8)

TSW(x)=数据项x被最后写入数据库的时刻，并记tw(x)为写入数据项x的事务

(9)

在进行新w(x)、r(x)操作的过程中，对TSW(x)、TSR(x)予以更新，ti所关联时间点共有4个，分别是S(ti)、V(ti)、W(ti)、F(ti)，将全部活动事务存入队列Q中，以有效验证起始时间的排序为依据，决定各活动事务从队列中进出时间的先后。在新协议下，val-write的临界区限制得以消除，对比所有活动中的、有效性验证完毕的完井事务和所有处于有效性验证操作中的tj，对tj的有效性进行检验。

当S(ti)=W(ti)时，如果完井事务ti和完井事务tj存在冲突读集CRW(ti,tj)，那么根据完井事务ti的读点TDR(xi)与完井事务tj写点TDW(xj)的顺序，验证完井事务ti和完井事务tj读写冲突，判断完井事务tj是否回滚；如果完井事务ti和完井事务tj存在冲突写集CWW(ti，tj)，那么根据完井事务tj的读集SR(tj)和写集SW(tj)间的关系以及V(tj)与F(ti)之间的关系，验证完井事务ti和完井事务tj写写冲突，判断完井事务tj是否需要等待。优化后的BOCC协议，通过将读写时间戳应用于数据项，实现了性能上的突破，这也是其最大的贡献，通常将其命名为基于读写时间戳的乐观并发协议。

2 面向移动完井业务应用

2.1 面向完井的读写时间戳乐观并发控制协议设计

围绕移动完井事务的处理，将基于读写时间戳的乐观并发控制协议应用到完井运行信息移动服务平台中，我们对读阶段、有效验证阶段、写阶段这三个阶段进行详细算法设计，具体读阶段算法流程如下：

步骤1：预先将一个完井事务tj作为目标，判断完井事务tj中是否有操作，如果有，继续步骤2；若没有，结束读阶段。

步骤2：如果该操作是读操作，继续步骤3；若不是，转至步骤4。

步骤3：对此事务tj的读集SR(tj)进行读操作，并更新读时间戳TSR(x)以及tr(x)，转至步骤1。

步骤4：如果该操作是写操作，继续步骤5；若不是，转至步骤1。

步骤5：对事务tj的读集SW(tj)进行写操作。转至步骤1。

具体的有效验证阶段的算法流程如下：

步骤1：存储在队列Q的完井事务tj出队列，当队列为空的时候，结束有效验证阶段；若不是，继续步骤2。

步骤2：在有效性验证tj的同时，检验ti的有效性，判断是否S(ti)

步骤3：判断V(tj)>=W(ti)，如果是，继续步骤4；否则转至步骤1。

步骤4：判断事务ti和事务tj的冲突读集CRW(ti,tj)是否为空，若不是，继续步骤5；否则转至步骤6。

步骤5：遍历冲突读集CRW(ti,tj)中的完井的数据项x，判断是否是TDR(xj)>TDW(xi)，如果是，遍历结束后转至步骤9；否则，事务tj会读脏数据，不能保证事务tj和事务ti的冲突可串行化，因此必须回滚事务tj，之后转至步骤6。

步骤6：判断事务ti和事务tj的冲突写集CWW(ti,tj)是否为空，若不是，继续步骤7；否则转至步骤1。

步骤7：判断事务tj的读集SR(tj)与SW(tj)写集SW(tj)⊆SR(tj)是否是，如果是，此时的情况即为步骤4的情况，已经进行过验证，因此转至步骤1；否则继续步骤8。

步骤8：判断是否V(tj)>=F(ti)，若不是，完井事务tj等待直到完井事务ti结束；否则转至步骤1。

步骤9：等待完井事务ti完成有效验证阶段，转至步骤1。

具体的写阶段的算法流程如下：

步骤1：将完井事务tj中的写集SW(tj)写入完井数据库。

步骤2：更新写时间戳TSW(x)。

步骤3：更新完井数据项x写入的事务tw(x)。

2.2 实验结果分析

为了验证完井运行信息移动服务平台应用基于读写时间戳的乐观并发控制协议后的性能，我们通过模拟实验程序，进行了详细的实验，在实验中釆用未改进的完井运行信息移动服务平台和改进的完井运行信息移动服务平台作为实验的参照对象，并对实验结果进行的简要的分析。

下述参数在进行实验时具有较高使用频率：移动事务的平均操作数为10；该平台的节点数为6；数据库共有2 000M元组数；事务截止期为100毫秒。

分别给出了在事务处理过程中，未改进的平台与改进的平台在并发移动事务数量有所调整的情况下，事务吞吐量、夭折率的波动情况。如图5和图6所示。

图5 事务夭折率变化

图6 事务吞吐量变化

由图5可知，在事务夭折率方面，并发移动事务数量增加的同时，两个平台也表现出增长的态势，在并发移动事务数量无限接近既定临界点时，达到一个极小值并有规律地递减。原因在于，更新数据量的提高，造成冲突发生率提高，但在无限接近某临界点时，更新操作数量相对较小，所产生的冲突也相对较少[13]。在达到某个临界点之后，改进后的平台在处理并发事务时的夭折率明显比改进前的低，这是因为更新操作数量已经足够使得这些冲突频繁发生，改进前的平台在处理并发事务时因冲突过多导致事务回滚过多，因而事务夭折率高。

图6反映的是事务吞吐量与并发移动事务数量的关系，通过实验可以得出这两个平台的事务吞吐量均随着并发移动事务数量的增长而先升后降但波动不大。优化前，在临界值时，平台吞吐量的值出现最高峰，并以较大幅度迅速降低，其趋势较改进的完井运行信息移动服务平台明显。主要因为随着事务数量的增多，改进后的完井运行信息移动服务平台利用时间戳进行了优化，事务撤销率相比改进前低，事务吞吐量比改进前的平台高。

综上所述，基于读写时间戳的乐观并发控制协议，对传统并发控制协议的不足进行了弥补，促进了事务回滚、阻塞概率的降低及并发度的提高，从整体上对系统的性能进行了改进。

4 总结

本文基于完井运行信息移动服务平台，以移动计算环境为背景，对应用乐观并发控制协议的必要性进行了探讨，并在平台中植入了建立在时间戳基础上的乐观并发控制协议。最后，对应用基于时间戳的乐观并发控制协议的完井运行信息移动服务平台进行了实验，通过实验说明通过引入基于时间戳的乐观并发控制协议，能够有效提高平台的性能及事务处理并发度，实现了对事务夭折率的有效控制。