基于优先级的多版本两阶段锁并发控制协议

帖 军，冯忠双

(中南民族大学 计算机科学学院，武汉430074)

随着无线通信技术和便携式设备的飞速发展，人们希望能随时随地获取自己需要的数据.面对这种需求，基于固定主机和有线网络的分布式数据库已经不能适应，移动实时数据库技术应运而生[1,2].然而移动实时事务(MRTT)受移动计算环境特性的影响，表现出弱化的ACID特性，以满足移动计算环境的特殊性要求[3].

1 相关协议分析

事务的并发控制协议主要包括乐观并发控制协议、悲观并发控制协议、多版本并发控制协议，而多版本并发控制协议在应对移动实时事务方面展现出优势，通过数据版本的更迭，减少了数据冲突，保证了数据的一致性[4].

MV2PL在应对移动实时事务时存在明显的优势[5]，它将事务分为只读事务和更新事务.对于只读事务，在任何情况下都不必等待加锁，这大大提高了只读事务的执行效率；而对于更新事务则采用强两阶段锁协议，以保证数据的一致性.然而，MV2PL也存在着不足，当事务提交并写回数据库时需要进行两次同步操作，这导致了事务运行时间的延长.

PRMCC算法针对上述不足做了重要改进[6]，在该算法中，通过下述2个约束，使事务提交写回时只需一次同步操作，具体约束如下：

(1)将数据在最后一个操作完成后写回数据库；

(2)接收某个事务请求的初始节点成为这个事务的协调者，负责该事务的运行.

2 MV2PLBP协议

本文提出一种基于优先级的多版本两阶段锁并发控制协议(MV2PLBP)来实现移动实时数据库环境下的事务并发控制，该协议在PRMCC算法的基础上进行了改进，通过加入优先级的概念，对事务进行优先级的划分，针对不同优先级的事务采用不同的方式进行考虑.

2.1 形式化定义

定义1 事务优先级：

事务优先级TP={W,G,E}，W表示该事务是可等待更新事务，G表示该事务为普通更新事务，E表示该事务是紧急更新事务.

定义2 只读事务：

只读事务是一个二元组：ROT=(op,).

其中op是具有r(x)形式的多个操作步骤的有限集合，x∈D且⊆op×op,是在op集合上的偏序关系.

只读事务是一种特殊事务，ROT对应的操作集合只包含读操作.

定义3 更新事务：

更新事务是一个三元组：UT=(op,,TPLevel).

其中op是具有r(x)或w(x)形式的多个操作步骤的有限集合，x∈D且⊆op×op，是在op集合上的偏序关系，TPLevel∈TP;

更新事务也是一种特殊事务，UT对应的操作集合中既包含读操作，又包含写操作，TPLevel表示UT对应的优先级别.

定义4 预计执行时间：

ExpectExcuteTime(T)=CPU运行时间+磁盘访问时间+锁等待时间.

ExpectExcuteTime(T)分为只读事务的预计执行时间和更新事务的预计执行时间两种，由于只读事务执行过程中不存在加锁过程，因此无须等待锁，所以对于只读事务而言，

ExpectExcuteTime(ROT)=

DataNum(ROT)*(CPUTime+IOTime)，

DataNum(ROT)表示只读事务的数据项数量.

而更新事务则需要等待数据项处于可用状态才能使用，因此比只读事务多了等待锁操作的时间，

ExpectExcuteTime(UT)=

DataNum(UT)*(CPUTime+IOTime+

LockTime)，

DataNum(UT)表示更新事务的数据项数量.

事务优先级别判定规则：

通过比较事务T的截止时间(DeadLine)和事务T的预计执行时间与当前时间(CurrentTime)之和，决定该事务的优先级别.

TPLevel=Compare(DeadLine(T),

ExpectExcuteTime(T)+CurrentTime).

2.2 算法描述

MV2PLBP协议将事务分为只读事务和更新事务，更新事务又根据其不同的优先级别分为可等待更新事务(WUT)、紧急更新事务(EUT)和普通更新事务(GUT)3种.

算法1 MV2PLBP协议算法描述Procedure MV2PLBPINPUT:T //事务OUTPUT: NULL1:if T is ROT2:if数据项D存在一个最新的版本Dnew3: read Dnew4:else Error5:end if 26:else if T is UT7:TPLevel = Compare(DeadLine(T),ExpectExcuteTime(T),CurrentTime)8:if read operation9:if 数据项D存在一个最新的版本Dnew10:T 获得D上的共享锁且read Dnew11:else Error12:end if 913:end if 814:else if write operation15:if TPLevel = E16:DealEUT (T,D)17:end if 1518:else if TPLevel = W19:DealWUT (T,D)20:end if 1821:else if TPLevel = G22:DealGUT (T,D)23:end if 2124:end if 1425:end if 6

3 模拟仿真

协议的延误率和重启率是衡量协议的并发控制性能的两个重要指标，分别定义如下：

延误率=到达截止期未完成的事务数目 / 进入系统的事务总数；

重启率=被重新启动的事务数目 / 进入系统的事务总数.

为了合理地分析MV2PLBP协议的性能优劣，采用MV2PL协议和PRMCC协议作为MV2PLBP协议的对比实验协议.

通过使用Sim C++仿真软件包[7]，基于表1给出的仿真实验参数进行仿真模拟.

表1 参数设置

统计仿真结果得到协议的延误率和重启率，如图1、图2所示.

图1 延误率-到达率Fig.1 Miss rate-arrival rate

图2 重启率-到达率 Fig.2 Restart rate-arrival rate

分析图1、图2可知，事务到达率对协议性能有一定的影响.随着事务到达率的提升，事务的延误率和重启率都有明显增加.当系统 Arrival Rate小于15时，3种协议的延误率和重启率都呈缓慢上升趋势，相比之下，MV2PLBP协议的延误率的增长幅度要略低于MV2PL协议和PRMCC协议，在重启率方面，MV2PLBP协议一直保持缓慢上升，而MV2PL协议和PRMCC协议却从系统Arrival Rate大于10开始迅速增长；当系统 Arrival Rate大于15时，3种协议的延误率和重启率增长都很明显，可见随着事务数量的增加，3种协议的性能都明显降低，出现这种现象的主要原因是事务数量增加，导致大多数事务将大量的时间消耗在等待队列上，造成事务不能按时完成，在2个图中表现为延误率和重启率的增加.

即便如此，仍可发现MV2PLBP协议的整体性能要略优于MV2PL协议和PRMCC协议.

4 结语

本文提出了一种基于优先级的多版本两阶段锁并发控制协议，该协议结合了多版本并发控制协议和两阶段锁协议的优点，并增加了优先级的考虑，使紧急事务能够不受其他事务影响而正常完成.通过模拟仿真实验，对比了MV2PLBP协议、MV2PL协议和PRMCC协议的性能，实验结果显示，在正常负载情况下，MV2PLBP协议的延误率和重启率都要优于MV2PL协议和PRMCC协议，能够有效地减少事务延误和重启.

参 考 文 献

[1] Swaroop V, Shanker U. Mobile distributed real time database systems:a research challenges[J].Computer and Communication Technology (ICCCT), 2010,9: 421-424.

[2] 曾宪权, 冯玉东. 移动事务处理技术研究进展[J]. 计算机与数字工程, 2005, 33(12): 50-54.

[3] Selvarani D,Ravi T. A survey on data and transaction management in mobile databases[J].International Journal of Database Management Systems (IJDMS), 2012, 5(4):1-20.

[4] Bernstein P, Newcomer E. Principles of transaction processing[M]. Burlington:Morgan Kaufmann, 2009:73-84.

[5] Silberschatz A,Korth H, Sudarshan S. Database system concepts[M].6th ed. NY: McGraw Hill Higher Education (Asia) Co, 2006:431-432.

[6] 徐淑颋, 孙永强. 并行数据库实时多版本并发控制协议性能研究[J].计算机工程，2002,25(2):173-180.

[7] Bolier D. Sim: a C++library for discrete event simulation[D]. Amsterdam: Vrije Universiteit, 1994.