基于改進(jìn)樂觀兩階段鎖的移動(dòng)事務(wù)處理模型

任占廣，李叔繁，尚福華

(1.重慶文理學(xué)院 軟件工程學(xué)院，重慶 402160; 2.東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，黑龍江 大慶 163318)

0 引 言

在數(shù)據(jù)庫系統(tǒng)中，傳統(tǒng)事務(wù)處理模型很好地解決了傳統(tǒng)應(yīng)用環(huán)境下事務(wù)的并發(fā)控制問題。但在移動(dòng)互聯(lián)網(wǎng)環(huán)境中，由于事務(wù)的頻繁斷接性和長延遲性，傳統(tǒng)的事務(wù)處理機(jī)制已無法滿足移動(dòng)數(shù)據(jù)庫系統(tǒng)的事務(wù)處理要求，為此，有必要對(duì)移動(dòng)事務(wù)提交和執(zhí)行策略進(jìn)行研究。移動(dòng)事務(wù)處理可分為三類，一類是重新定義了事務(wù)的ACID(原子性、一致性、隔離線、持續(xù)性)特性[1]，如集群事務(wù)模型[1]、KANGROO模型[2]、MOFLEX模型[3]，雖然滿足了移動(dòng)環(huán)境，但無法保證事務(wù)的可串行性；第二類是將傳統(tǒng)數(shù)據(jù)庫事務(wù)處理機(jī)制引入到移動(dòng)計(jì)算環(huán)境中，如文獻(xiàn)[4-5]，要求移動(dòng)端必須一次性將完整的事務(wù)操作序列提交到數(shù)據(jù)庫服務(wù)器，一旦在提交過程中發(fā)生網(wǎng)絡(luò)中斷，移動(dòng)端只能重新提交，所以該模型不是很適合移動(dòng)數(shù)據(jù)庫系統(tǒng)；第三類是將移動(dòng)事務(wù)分成發(fā)送和樂觀提交兩階段執(zhí)行并采用不同的沖突消解機(jī)制，如文獻(xiàn)[6-7]采用時(shí)間戳解決事務(wù)沖突問題，文獻(xiàn)[8]采用結(jié)果集檢測(cè)的方式消除事務(wù)沖突,文獻(xiàn)[9]分別針對(duì)油田的特定業(yè)務(wù)，局限性較大。雖然都考慮到了移動(dòng)事務(wù)的不穩(wěn)定特點(diǎn)，但由于均采用兩階段鎖協(xié)議，數(shù)據(jù)可能被長時(shí)間封鎖，使斷接事務(wù)或長事務(wù)長時(shí)間占用資源而最終發(fā)生死鎖[10]。

鑒于以上分析，文中提出一種基于改進(jìn)樂觀兩階段鎖的移動(dòng)事務(wù)處理模型，在保證事務(wù)ACID特性的同時(shí)降低了斷接事務(wù)或者長事務(wù)對(duì)移動(dòng)數(shù)據(jù)庫系統(tǒng)的影響。

1 樂觀兩階段鎖事務(wù)處理模型

1.1 樂觀兩階段鎖機(jī)制分析

在樂觀兩階段鎖移動(dòng)事務(wù)處理模型中，移動(dòng)事務(wù)的提交和移動(dòng)事務(wù)的執(zhí)行采用不同的事務(wù)處理模式，前者采用了樂觀的并發(fā)控制機(jī)制，而后者遵循兩階段鎖事務(wù)執(zhí)行協(xié)議。移動(dòng)數(shù)據(jù)庫系統(tǒng)的整體架構(gòu)如圖1所示[11-13]。

圖1 移動(dòng)數(shù)據(jù)庫系統(tǒng)整體架構(gòu)

如圖1所示，固定網(wǎng)絡(luò)擁有多個(gè)數(shù)據(jù)庫服務(wù)器，每個(gè)數(shù)據(jù)庫服務(wù)器都有一個(gè)本地的數(shù)據(jù)庫，本地的數(shù)據(jù)庫服務(wù)器負(fù)責(zé)讀寫、預(yù)處理、提交、執(zhí)行等事務(wù)的操作[14-15]。每一個(gè)移動(dòng)支持節(jié)點(diǎn)相當(dāng)于移動(dòng)端與固定網(wǎng)絡(luò)之間的橋接器，一方面接收移動(dòng)端發(fā)送過來的移動(dòng)事務(wù)操作序列，另一方面將接收來的事務(wù)操作序列傳遞給固定網(wǎng)絡(luò)中相應(yīng)的數(shù)據(jù)庫服務(wù)器執(zhí)行，并實(shí)時(shí)監(jiān)測(cè)執(zhí)行情況。每一個(gè)移動(dòng)客戶端在任一時(shí)刻只能啟動(dòng)一個(gè)移動(dòng)事務(wù)序列，只有當(dāng)該移動(dòng)事務(wù)操作序列全部執(zhí)行完畢后才能啟動(dòng)下一個(gè)移動(dòng)事務(wù)操作序列。

1.2 存在的問題

在樂觀兩階段鎖移動(dòng)事務(wù)處理模型中，移動(dòng)事務(wù)可多次發(fā)送給移動(dòng)支持節(jié)點(diǎn)，每次可以發(fā)送一個(gè)連續(xù)的移動(dòng)事務(wù)操作序列，當(dāng)移動(dòng)客戶端接收到移動(dòng)支持節(jié)點(diǎn)返回的事務(wù)序列的執(zhí)行結(jié)果后，可以移動(dòng)到另一個(gè)網(wǎng)絡(luò)單元繼續(xù)發(fā)送下一個(gè)操作序列[7]。但該模型必須保證移動(dòng)端在移動(dòng)操作序列提交以及得到操作序列執(zhí)行結(jié)果的整個(gè)過程中始終處于強(qiáng)連接狀態(tài)，一旦發(fā)生無線網(wǎng)絡(luò)斷接，就會(huì)造成移動(dòng)事務(wù)序列的撤銷操作，只能重新提交移動(dòng)事務(wù)操作序列?；蛴捎跓o線網(wǎng)絡(luò)信號(hào)較差，使移動(dòng)端發(fā)送或接收超時(shí)，造成事務(wù)堵塞或死鎖。而無線網(wǎng)絡(luò)受環(huán)境影響較大，本身具有低帶寬、長延遲、頻繁斷接和資源有限等特性，因此該模型不能很好地支持頻繁斷接和耗時(shí)較長的移動(dòng)事務(wù)。針對(duì)這一缺點(diǎn)，文中對(duì)樂觀兩階段鎖的移動(dòng)事務(wù)處理模型進(jìn)行了有效改進(jìn)，使改進(jìn)模型更適合移動(dòng)數(shù)據(jù)庫系統(tǒng)。

2 改進(jìn)的移動(dòng)事務(wù)處理模型

2.1 模型機(jī)制

為了解決上面提到的問題，在樂觀兩階段鎖移動(dòng)事務(wù)處理模型的基礎(chǔ)上引入了移動(dòng)事務(wù)處理機(jī)制(mobile transaction processor mechanism，MTPM)和移動(dòng)事務(wù)協(xié)調(diào)機(jī)制(mobile transaction coordinator mechanism，MTCM)。MTPM負(fù)責(zé)移動(dòng)事務(wù)操作序列的編輯、生成與發(fā)送， MTCM負(fù)責(zé)識(shí)別、接收、組合移動(dòng)事務(wù)操作序列，同時(shí)將事務(wù)序列提交給數(shù)據(jù)庫服務(wù)器，將結(jié)果集返回給移動(dòng)端。改進(jìn)后的移動(dòng)事務(wù)處理模型如圖2所示。

圖2 改進(jìn)后的移動(dòng)事務(wù)處理模型

2.2 MTPM

假設(shè)移動(dòng)事務(wù)序列(mobile transaction series，MTS)由多個(gè)移動(dòng)事務(wù)子序列組成，分別記為MTSj。

RResultSet(oj)={(ψ,υ)|ψ∈ReadSet(oj)∧υ=ζ(ψ,oj)}

WResultSet(T)={(η,υ)|η∈WSet(T)∧υ=δ(η,T)}

假設(shè)，MTSi有如下操作(見表1和表2)：

表1 讀操作

表2 寫操作

設(shè)對(duì)應(yīng)的MTS的標(biāo)識(shí)MID為“M01”，所執(zhí)行的操作序?yàn)椋簉[a=50]，w[a=60]。其結(jié)果如表3所示。

表3 結(jié)果集

2.3 MTCM

MTCM有兩種協(xié)調(diào)方式。當(dāng)MTS是一個(gè)完整的事務(wù)操作序列時(shí)，整個(gè)MTS發(fā)送給MTCM時(shí)，MTCM將等待MTS全部收到后再執(zhí)行。當(dāng)MTS被分成若干個(gè)子序列，分別發(fā)送給MTCM時(shí)，MTCM根據(jù)事務(wù)識(shí)別號(hào)，將子事務(wù)序列首先存入到事務(wù)日志中，如果在這一過程中發(fā)生網(wǎng)絡(luò)中斷，那么該事務(wù)將處于掛起狀態(tài)，MTCM繼續(xù)接收和處理其他的事務(wù)。當(dāng)網(wǎng)絡(luò)恢復(fù)后，繼續(xù)接收，直到接收到以MTS_end結(jié)尾的子序列時(shí)，則說明整個(gè)移動(dòng)事務(wù)操作序列接收完成，MTCM提取事務(wù)日志子序列，合并成一個(gè)完整的事務(wù)，提交給數(shù)據(jù)庫服務(wù)器執(zhí)行。MTCM一方面負(fù)責(zé)監(jiān)聽事務(wù)執(zhí)行情況，另一方面接收數(shù)據(jù)庫服務(wù)器返回的結(jié)果集，并將結(jié)果集暫存到該事務(wù)的結(jié)果集日志中，同時(shí)MTCM根據(jù)事務(wù)標(biāo)識(shí)檢測(cè)移動(dòng)端是否處于連接狀態(tài)，如果狀態(tài)良好，就將結(jié)果集返回給MTPM，如果狀態(tài)不佳，就繼續(xù)檢測(cè)，直到網(wǎng)絡(luò)正常后再發(fā)送。具體流程如圖3所示。

圖3 MTCM處理流程

3 實(shí) 驗(yàn)

3.1 算法實(shí)現(xiàn)

該算法由兩個(gè)階段完成，第一階段MTCM接收MTPM發(fā)送過來的事務(wù)序列，進(jìn)行識(shí)別與編輯；第二階段MTCM提交組合好的事務(wù)給數(shù)據(jù)庫服務(wù)器，并將結(jié)果集返回給MTPM。

第一階段：識(shí)別與編輯。

一個(gè)移動(dòng)事務(wù)序列由n個(gè)子序列MTSi構(gòu)成，在識(shí)別階段，MTCM首先啟動(dòng)一個(gè)相應(yīng)驗(yàn)證事務(wù)VMTSi，在執(zhí)行VMTSi過程中，MTSi采用樂觀訪問并發(fā)控制機(jī)制，在訪問過程中要檢測(cè)移動(dòng)事務(wù)的寫集沖突。

(?j∈[1,n])∧(WriteSet(oj)≠Write Set(Voj))或(?j∈[1,n])∧(?Ψ∈(Set (oj)與WriteSet(Voj)))∧(ζ(Ψ,oj)≠ζ(Ψ,Voj))

定義6：對(duì)于移動(dòng)事務(wù)MTSj，當(dāng)進(jìn)行了與之對(duì)應(yīng)的一系列驗(yàn)證操作后，仍然沒有檢測(cè)到移動(dòng)事務(wù)的寫集沖突和事務(wù)的執(zhí)行時(shí)沖突，則說明驗(yàn)證事務(wù)VMTSi執(zhí)行完畢，事務(wù)調(diào)度的可串行性沒有被破壞；否則MTCM不能提交該事務(wù)。

第二階段：監(jiān)聽與提交。

在規(guī)定的時(shí)間范圍內(nèi)，如果MTCM驗(yàn)證并接收到所有移動(dòng)事務(wù)子序列后，則提交數(shù)據(jù)庫服務(wù)器；反之則通知MTPM，接收超時(shí)，終止本次提交。

3.2 實(shí)驗(yàn)結(jié)果分析

為了分析改進(jìn)后的模型在移動(dòng)計(jì)算環(huán)境下的性能，以“玩課網(wǎng)”平臺(tái)學(xué)習(xí)行為數(shù)據(jù)為基礎(chǔ)，通過Java、Android搭建了移動(dòng)數(shù)據(jù)庫系統(tǒng)。實(shí)驗(yàn)中的主要參數(shù)有：元組數(shù)為20萬條，每個(gè)移動(dòng)事務(wù)的平均操作數(shù)為7；事務(wù)處理服務(wù)器上并發(fā)的移動(dòng)事務(wù)個(gè)數(shù)為0到1萬；事務(wù)啟動(dòng)所造成的延遲為10到500毫秒。圖4為理想的移動(dòng)環(huán)境下改進(jìn)前后事務(wù)并發(fā)量與成活率的關(guān)系；圖5為連續(xù)非并發(fā)移動(dòng)事務(wù)訪問量為100時(shí)，移動(dòng)環(huán)境的變化與事務(wù)執(zhí)行情況的關(guān)系。

圖4 改進(jìn)前后移動(dòng)事務(wù)成活率

圖5 改進(jìn)前后移動(dòng)事務(wù)提交量

由圖4 可以看出，隨著移動(dòng)事務(wù)并發(fā)量的增加，移動(dòng)事務(wù)成活率隨之降低。而當(dāng)并發(fā)事務(wù)量相等時(shí)，改進(jìn)后事務(wù)提交的成功率大于改進(jìn)前的事務(wù)提交成功率。當(dāng)移動(dòng)事務(wù)的并發(fā)量越大時(shí)，改進(jìn)后的效果越明顯。由圖5所示，當(dāng)移動(dòng)端與服務(wù)器端正常連接時(shí)，改進(jìn)前后事務(wù)的成功執(zhí)行率基本相同，當(dāng)移動(dòng)網(wǎng)絡(luò)處于斷接或者弱連接的情況時(shí)，改進(jìn)后的事務(wù)的提交并執(zhí)行成功量明顯高于改進(jìn)前。因此，改進(jìn)后的模型無論是對(duì)移動(dòng)事務(wù)并發(fā)控制還是對(duì)移動(dòng)環(huán)境的適應(yīng)能力都有了明顯的提升。

4 結(jié)束語

文中提出了一種基于改進(jìn)樂觀兩階段鎖移動(dòng)事務(wù)處理模型，該模型充分考慮了移動(dòng)計(jì)算機(jī)環(huán)境弱連接性，并對(duì)頻繁斷接事務(wù)和移動(dòng)長事務(wù)有了很好的控制。實(shí)驗(yàn)表明，改進(jìn)模型能更好地適應(yīng)于移動(dòng)數(shù)據(jù)庫系統(tǒng)。