基于優(yōu)先級的多版本兩階段鎖并發(fā)控制協(xié)議

帖 軍，馮忠雙

(中南民族大學(xué) 計(jì)算機(jī)科學(xué)學(xué)院，武漢430074)

隨著無線通信技術(shù)和便攜式設(shè)備的飛速發(fā)展，人們希望能隨時(shí)隨地獲取自己需要的數(shù)據(jù).面對這種需求，基于固定主機(jī)和有線網(wǎng)絡(luò)的分布式數(shù)據(jù)庫已經(jīng)不能適應(yīng)，移動(dòng)實(shí)時(shí)數(shù)據(jù)庫技術(shù)應(yīng)運(yùn)而生[1,2].然而移動(dòng)實(shí)時(shí)事務(wù)(MRTT)受移動(dòng)計(jì)算環(huán)境特性的影響，表現(xiàn)出弱化的ACID特性，以滿足移動(dòng)計(jì)算環(huán)境的特殊性要求[3].

1 相關(guān)協(xié)議分析

事務(wù)的并發(fā)控制協(xié)議主要包括樂觀并發(fā)控制協(xié)議、悲觀并發(fā)控制協(xié)議、多版本并發(fā)控制協(xié)議，而多版本并發(fā)控制協(xié)議在應(yīng)對移動(dòng)實(shí)時(shí)事務(wù)方面展現(xiàn)出優(yōu)勢，通過數(shù)據(jù)版本的更迭，減少了數(shù)據(jù)沖突，保證了數(shù)據(jù)的一致性[4].

MV2PL在應(yīng)對移動(dòng)實(shí)時(shí)事務(wù)時(shí)存在明顯的優(yōu)勢[5]，它將事務(wù)分為只讀事務(wù)和更新事務(wù).對于只讀事務(wù)，在任何情況下都不必等待加鎖，這大大提高了只讀事務(wù)的執(zhí)行效率；而對于更新事務(wù)則采用強(qiáng)兩階段鎖協(xié)議，以保證數(shù)據(jù)的一致性.然而，MV2PL也存在著不足，當(dāng)事務(wù)提交并寫回?cái)?shù)據(jù)庫時(shí)需要進(jìn)行兩次同步操作，這導(dǎo)致了事務(wù)運(yùn)行時(shí)間的延長.

PRMCC算法針對上述不足做了重要改進(jìn)[6]，在該算法中，通過下述2個(gè)約束，使事務(wù)提交寫回時(shí)只需一次同步操作，具體約束如下：

(1)將數(shù)據(jù)在最后一個(gè)操作完成后寫回?cái)?shù)據(jù)庫；

(2)接收某個(gè)事務(wù)請求的初始節(jié)點(diǎn)成為這個(gè)事務(wù)的協(xié)調(diào)者，負(fù)責(zé)該事務(wù)的運(yùn)行.

2 MV2PLBP協(xié)議

本文提出一種基于優(yōu)先級的多版本兩階段鎖并發(fā)控制協(xié)議(MV2PLBP)來實(shí)現(xiàn)移動(dòng)實(shí)時(shí)數(shù)據(jù)庫環(huán)境下的事務(wù)并發(fā)控制，該協(xié)議在PRMCC算法的基礎(chǔ)上進(jìn)行了改進(jìn)，通過加入優(yōu)先級的概念，對事務(wù)進(jìn)行優(yōu)先級的劃分，針對不同優(yōu)先級的事務(wù)采用不同的方式進(jìn)行考慮.

2.1 形式化定義

定義1 事務(wù)優(yōu)先級：

事務(wù)優(yōu)先級TP={W,G,E}，W表示該事務(wù)是可等待更新事務(wù)，G表示該事務(wù)為普通更新事務(wù)，E表示該事務(wù)是緊急更新事務(wù).

定義2 只讀事務(wù)：

只讀事務(wù)是一個(gè)二元組：ROT=(op,).

其中op是具有r(x)形式的多個(gè)操作步驟的有限集合，x∈D且?op×op,是在op集合上的偏序關(guān)系.

只讀事務(wù)是一種特殊事務(wù)，ROT對應(yīng)的操作集合只包含讀操作.

定義3 更新事務(wù)：

更新事務(wù)是一個(gè)三元組：UT=(op,,TPLevel).

其中op是具有r(x)或w(x)形式的多個(gè)操作步驟的有限集合，x∈D且?op×op，是在op集合上的偏序關(guān)系，TPLevel∈TP;

更新事務(wù)也是一種特殊事務(wù)，UT對應(yīng)的操作集合中既包含讀操作，又包含寫操作，TPLevel表示UT對應(yīng)的優(yōu)先級別.

定義4 預(yù)計(jì)執(zhí)行時(shí)間：

ExpectExcuteTime(T)=CPU運(yùn)行時(shí)間+磁盤訪問時(shí)間+鎖等待時(shí)間.

ExpectExcuteTime(T)分為只讀事務(wù)的預(yù)計(jì)執(zhí)行時(shí)間和更新事務(wù)的預(yù)計(jì)執(zhí)行時(shí)間兩種，由于只讀事務(wù)執(zhí)行過程中不存在加鎖過程，因此無須等待鎖，所以對于只讀事務(wù)而言，

ExpectExcuteTime(ROT)=

DataNum(ROT)*(CPUTime+IOTime)，

DataNum(ROT)表示只讀事務(wù)的數(shù)據(jù)項(xiàng)數(shù)量.

而更新事務(wù)則需要等待數(shù)據(jù)項(xiàng)處于可用狀態(tài)才能使用，因此比只讀事務(wù)多了等待鎖操作的時(shí)間，

ExpectExcuteTime(UT)=

DataNum(UT)*(CPUTime+IOTime+

LockTime)，

DataNum(UT)表示更新事務(wù)的數(shù)據(jù)項(xiàng)數(shù)量.

事務(wù)優(yōu)先級別判定規(guī)則：

通過比較事務(wù)T的截止時(shí)間(DeadLine)和事務(wù)T的預(yù)計(jì)執(zhí)行時(shí)間與當(dāng)前時(shí)間(CurrentTime)之和，決定該事務(wù)的優(yōu)先級別.

TPLevel=Compare(DeadLine(T),

ExpectExcuteTime(T)+CurrentTime).

2.2 算法描述

MV2PLBP協(xié)議將事務(wù)分為只讀事務(wù)和更新事務(wù)，更新事務(wù)又根據(jù)其不同的優(yōu)先級別分為可等待更新事務(wù)(WUT)、緊急更新事務(wù)(EUT)和普通更新事務(wù)(GUT)3種.

算法1 MV2PLBP協(xié)議算法描述Procedure MV2PLBPINPUT:T //事務(wù)OUTPUT: NULL1:if T is ROT2:if數(shù)據(jù)項(xiàng)D存在一個(gè)最新的版本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 數(shù)據(jù)項(xiàng)D存在一個(gè)最新的版本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 模擬仿真

協(xié)議的延誤率和重啟率是衡量協(xié)議的并發(fā)控制性能的兩個(gè)重要指標(biāo)，分別定義如下：

延誤率=到達(dá)截止期未完成的事務(wù)數(shù)目 / 進(jìn)入系統(tǒng)的事務(wù)總數(shù)；

重啟率=被重新啟動(dòng)的事務(wù)數(shù)目 / 進(jìn)入系統(tǒng)的事務(wù)總數(shù).

為了合理地分析MV2PLBP協(xié)議的性能優(yōu)劣，采用MV2PL協(xié)議和PRMCC協(xié)議作為MV2PLBP協(xié)議的對比實(shí)驗(yàn)協(xié)議.

通過使用Sim C++仿真軟件包[7]，基于表1給出的仿真實(shí)驗(yàn)參數(shù)進(jìn)行仿真模擬.

表1 參數(shù)設(shè)置

統(tǒng)計(jì)仿真結(jié)果得到協(xié)議的延誤率和重啟率，如圖1、圖2所示.

圖1 延誤率-到達(dá)率Fig.1 Miss rate-arrival rate

圖2 重啟率-到達(dá)率 Fig.2 Restart rate-arrival rate

分析圖1、圖2可知，事務(wù)到達(dá)率對協(xié)議性能有一定的影響.隨著事務(wù)到達(dá)率的提升，事務(wù)的延誤率和重啟率都有明顯增加.當(dāng)系統(tǒng) Arrival Rate小于15時(shí)，3種協(xié)議的延誤率和重啟率都呈緩慢上升趨勢，相比之下，MV2PLBP協(xié)議的延誤率的增長幅度要略低于MV2PL協(xié)議和PRMCC協(xié)議，在重啟率方面，MV2PLBP協(xié)議一直保持緩慢上升，而MV2PL協(xié)議和PRMCC協(xié)議卻從系統(tǒng)Arrival Rate大于10開始迅速增長；當(dāng)系統(tǒng) Arrival Rate大于15時(shí)，3種協(xié)議的延誤率和重啟率增長都很明顯，可見隨著事務(wù)數(shù)量的增加，3種協(xié)議的性能都明顯降低，出現(xiàn)這種現(xiàn)象的主要原因是事務(wù)數(shù)量增加，導(dǎo)致大多數(shù)事務(wù)將大量的時(shí)間消耗在等待隊(duì)列上，造成事務(wù)不能按時(shí)完成，在2個(gè)圖中表現(xiàn)為延誤率和重啟率的增加.

即便如此，仍可發(fā)現(xiàn)MV2PLBP協(xié)議的整體性能要略優(yōu)于MV2PL協(xié)議和PRMCC協(xié)議.

4 結(jié)語

本文提出了一種基于優(yōu)先級的多版本兩階段鎖并發(fā)控制協(xié)議，該協(xié)議結(jié)合了多版本并發(fā)控制協(xié)議和兩階段鎖協(xié)議的優(yōu)點(diǎn)，并增加了優(yōu)先級的考慮，使緊急事務(wù)能夠不受其他事務(wù)影響而正常完成.通過模擬仿真實(shí)驗(yàn)，對比了MV2PLBP協(xié)議、MV2PL協(xié)議和PRMCC協(xié)議的性能，實(shí)驗(yàn)結(jié)果顯示，在正常負(fù)載情況下，MV2PLBP協(xié)議的延誤率和重啟率都要優(yōu)于MV2PL協(xié)議和PRMCC協(xié)議，能夠有效地減少事務(wù)延誤和重啟.

參 考 文 獻(xiàn)

[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] 曾憲權(quán), 馮玉東. 移動(dòng)事務(wù)處理技術(shù)研究進(jìn)展[J]. 計(jì)算機(jī)與數(shù)字工程, 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] 徐淑颋, 孫永強(qiáng). 并行數(shù)據(jù)庫實(shí)時(shí)多版本并發(fā)控制協(xié)議性能研究[J].計(jì)算機(jī)工程，2002,25(2):173-180.

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