面向完井的讀寫時(shí)間戳樂觀并發(fā)控制協(xié)議研究

， ，

(東北石油大學(xué) 計(jì)算機(jī)與信息技術(shù)學(xué)院，大慶 163318)

0 引言

完井，油氣井的完成，其周期從鉆井作業(yè)開始，直至投產(chǎn)作業(yè)結(jié)束[1]。由于完井工藝涉及的諸多環(huán)節(jié)需要野外作業(yè)[2]，野外移動通信信號弱，所以完井業(yè)務(wù)的移動計(jì)算環(huán)境具有頻繁斷接性、網(wǎng)絡(luò)通信不對稱性[3-5]，同時(shí)移動終端存在電池續(xù)航時(shí)間短、CPU處理能力較弱、存儲空間有限等問題[6-7]。在受到這些條件限制的情況下，在進(jìn)行事務(wù)處理時(shí)就會出現(xiàn)事務(wù)延遲、實(shí)時(shí)性差等情況，此時(shí)就會導(dǎo)致完井業(yè)務(wù)管理效率低下的問題，甚至影響整個(gè)油田信息管理的效率。因此提高移動事務(wù)處理的性能，成為了當(dāng)前急需突破的方向。

移動事務(wù)是移動設(shè)備上數(shù)據(jù)庫維護(hù)及管理的重要方法，需要在網(wǎng)絡(luò)斷開時(shí)仍然繼續(xù)數(shù)據(jù)處理，所以移動設(shè)備的數(shù)據(jù)庫具備必要的自我修復(fù)和應(yīng)急處理能力，能夠?qū)﹄x線操作的移動事務(wù)有所支持[8-9]。

事務(wù)處理的核心機(jī)制是并發(fā)控制，事務(wù)并發(fā)控制屬于事務(wù)調(diào)度的一種，出色的并發(fā)控制調(diào)度策略應(yīng)能夠有效提高系統(tǒng)的響應(yīng)速度和吞吐量，優(yōu)化資源配置。并發(fā)控制常見的有樂觀并發(fā)控制協(xié)議、悲觀并發(fā)控制協(xié)議和混合并發(fā)控制協(xié)議3種事務(wù)并發(fā)控制協(xié)議[10]，由于完井運(yùn)行信息移動服務(wù)平臺的數(shù)據(jù)操作多為數(shù)據(jù)查詢，而樂觀并發(fā)控制協(xié)議比悲觀并發(fā)控制協(xié)議更加適用于讀多寫少沖突較少的事務(wù)處理，在樂觀并發(fā)控制協(xié)議下，該平臺數(shù)據(jù)的收斂性、一致性均得到了保證。因此本文基于對完井?dāng)?shù)據(jù)移動管理、并發(fā)控制的把握，從并發(fā)控制優(yōu)化入手引入基于讀寫時(shí)間戳的樂觀并發(fā)控制協(xié)議從而提高處理事務(wù)并發(fā)的效率。

1 基于讀寫時(shí)間戳的樂觀并發(fā)控制協(xié)議

樂觀并發(fā)控制協(xié)議[11]是H.Kung等人提出的，在并發(fā)事務(wù)發(fā)生沖突可能性較低的場景下，該協(xié)議具有較高適用性，且分為3個(gè)階段，來完成整個(gè)事務(wù)的執(zhí)行。

基于時(shí)間戳的并發(fā)控制方法[12]，以預(yù)先設(shè)定的串行序次來執(zhí)行相關(guān)事務(wù)。出于確定該次序的需要，事物處理器將在時(shí)間戳和事務(wù)之間建立起一一對應(yīng)關(guān)系，同時(shí)，需確保在整個(gè)數(shù)據(jù)庫中該時(shí)間戳的唯一性。由時(shí)間戳法而來的可串行性調(diào)度表，和對事務(wù)時(shí)間戳序列的成功提交等價(jià)。這種方法不僅能有效降低死鎖問題的發(fā)生率，還能對由資源沖突造成的事務(wù)等待進(jìn)行規(guī)避。

1.1 傳統(tǒng)樂觀并發(fā)控制協(xié)議

傳統(tǒng)樂觀并發(fā)控制協(xié)議分為讀、有效性驗(yàn)證、寫 3個(gè)階段。針對具體的完井業(yè)務(wù)而言，第一階段的任務(wù)是對完井?dāng)?shù)據(jù)進(jìn)行讀取，并將數(shù)據(jù)寫入本地，并不對數(shù)據(jù)庫進(jìn)行真正的更新。第二階段的主要工作為：以協(xié)議規(guī)則為依據(jù)，校驗(yàn)在沖突可串行化方面，全部完井事務(wù)調(diào)度的合理性。在寫階段，則以校驗(yàn)結(jié)果為依據(jù)，提交數(shù)據(jù)，將其永久寫入完井?dāng)?shù)據(jù)庫。在進(jìn)行驗(yàn)證時(shí)，傳統(tǒng)的樂觀并發(fā)控制協(xié)議常用算法為BOCC，即所謂后向樂觀并發(fā)控制，也就是說，設(shè)最后兩個(gè)階段有效性驗(yàn)證階段與寫階段作為一個(gè)原子操作val-write階段，不可分割地執(zhí)行，在檢測到數(shù)據(jù)訪問沖突時(shí)，重啟正在驗(yàn)證的事務(wù)。

將完井事務(wù)ti的讀、寫數(shù)據(jù)項(xiàng)集合，分別記為RS(ti)、WS(ti)，完井事務(wù)讀階段結(jié)束后，可確定上述兩個(gè)集合，接下來，需沖突檢測、有效性驗(yàn)證全部完井事務(wù)。

定義1：完井事務(wù)tj的效力，經(jīng)BOCC驗(yàn)證得以肯定，若任意已提交完井事務(wù)ti符合下述要求之一：

條件1：提交完井事務(wù)ti后，執(zhí)行完井事務(wù)tj，也就是說，在ti執(zhí)行完畢的情況下，方可執(zhí)行tj，具體如圖1所示。

圖1 條件1示意圖

條件2：若ti的寫數(shù)據(jù)項(xiàng)集合、tj的讀數(shù)據(jù)項(xiàng)集合交集為空，即RS(tj)∩WS(ti)=φ，且在ti的val-write階段后，對完井事務(wù)tj進(jìn)行有效性檢查，具體如圖2所示。

圖2 條件2示意圖

在這種情況下，BOCC僅形成沖突可串行化調(diào)度[13]。

在BOCC模式下，完井事務(wù)的樂觀并發(fā)執(zhí)行可無障礙完成，并無錯(cuò)漏地將事務(wù)調(diào)度輸出。但是，BOCC存在一定的局限性，所涉及事務(wù)并發(fā)控制方法也是基礎(chǔ)性的。

(1) BOCC對應(yīng)用條件的要求非常嚴(yán)格。條件1可將串行化調(diào)度輸出，具體見圖1；條件2可對完井事務(wù)ti讀寫中的數(shù)據(jù)不可被完井事務(wù)tj讀取作出了規(guī)定，但這和實(shí)際調(diào)度操作存在一定出入，在完井運(yùn)行信息移動服務(wù)平臺中移動完井事務(wù)的調(diào)度中有可能出現(xiàn)條件2的情況，此時(shí)，系統(tǒng)基本處于提交保序化狀態(tài)，盡管沖突可串行化正確調(diào)度也有一定的形成幾率，但給完井事務(wù)并發(fā)度的實(shí)現(xiàn)造成了負(fù)面影響，降低了完井運(yùn)行信息移動服務(wù)平臺的資源吞吐量，效率低下。

(2) 當(dāng)完井運(yùn)行信息移動服務(wù)平臺出現(xiàn)長事務(wù)的情況時(shí)，由于若干沖突的短事務(wù)，易造成包括部分本無需重啟的完井事務(wù)的長事務(wù)的頻發(fā)重啟，具體如圖3所示。

圖3 完井事務(wù)讀寫沖突

按照BOCC協(xié)議相關(guān)要求，上圖在RS(tj)∩WS(ti)=a≠φ的情況下，發(fā)生完井事務(wù)tj的讀操作與完井事務(wù)ti的寫操作沖突，此時(shí)完井事務(wù)tj應(yīng)當(dāng)重啟。同理，當(dāng)RS(tk)∩WS(ti)=a≠φ時(shí)，完井事務(wù)tk的讀操作和完井事務(wù)ti的寫操作存在交叉，需中止并重新啟動tk。然而，進(jìn)一步分析上述操作可知，這兩種情況存在較大差異。

在完井事務(wù)tj執(zhí)行結(jié)束前，ti已經(jīng)寫回tj讀取的完井?dāng)?shù)據(jù)項(xiàng)a，a由此被更新，tj對臟數(shù)據(jù)進(jìn)行了讀取，無法為ti、tj的沖突可串行化提供保證，故tj必須回滾并重新啟動，但是，tk讀取的a是最近更新的數(shù)據(jù)項(xiàng)，盡管無法規(guī)避完井事務(wù)tj的寫操作與完井事務(wù)tk的讀操作的沖突，但沖突可串行化調(diào)度的出現(xiàn)，使得tk并無回滾重啟的必要。

(3) 作為一個(gè)臨界區(qū)處理，val-write不具備可分割性，降低了部分完井事務(wù)形成沖突的概率，但若寫操作向數(shù)據(jù)庫中寫入所有本地完井?dāng)?shù)據(jù)，則需回滾或掛起全部沖突并發(fā)的事務(wù)，進(jìn)而給系統(tǒng)的性能造成負(fù)面影響，造成許多額外重啟操作的發(fā)生，如圖4所示。不難發(fā)現(xiàn)，若將BOCC的臨界區(qū)限制消除，則有可能觸發(fā)一系列新的完井事務(wù)重啟問題。

圖4 完井事務(wù)的BOCC寫寫沖突

在WS(tj)∩WS(ti)=a≠φ的情況下，ti、tj兩個(gè)完井事務(wù)出現(xiàn)寫操作間的沖突，tj終止且重新啟動。類似的事，在WS(tk)∩WS(ti)=a≠φ的情況下，tk、tj兩個(gè)完井事務(wù)出現(xiàn)寫操作間的沖突，tk終止且重新啟動。對于上述情況的發(fā)生，BOCC協(xié)議并未進(jìn)行深入解析，但深究之下不難發(fā)現(xiàn)，上述兩種情況存在明顯差異。

ti的寫操作覆蓋了tj對a的寫操作w(a)，在ti的驗(yàn)證后，有效驗(yàn)證tj，完井事務(wù)應(yīng)形成串行序列ti,tj，但結(jié)合圖3.4可以發(fā)現(xiàn)，在所執(zhí)行的完井事務(wù)中，出現(xiàn)了tj→ti的沖突，在這種情況下，完井事務(wù)的串行化無從保證，故須終止tj，并對其進(jìn)行重新啟動。但tk發(fā)出的對完井?dāng)?shù)據(jù)項(xiàng)a的寫操作w(a)覆蓋了完井事務(wù)ti所寫的完井?dāng)?shù)據(jù)項(xiàng)a，雖然有完井事務(wù)ti與完井事務(wù)tk的寫寫沖突，但完井事務(wù)tk的有效驗(yàn)證發(fā)生在完井事務(wù)ti的有效驗(yàn)證之后，結(jié)合上一章節(jié)相關(guān)內(nèi)容可知，沖突可串行化調(diào)度的出現(xiàn)，使得tk并無回滾重啟的必要。

1.2 基于讀寫時(shí)間戳的樂觀并發(fā)控制協(xié)議

在完井運(yùn)行信息移動服務(wù)平臺的移動計(jì)算環(huán)境中，在傳統(tǒng)樂觀并發(fā)控制協(xié)議下，讀、有效性驗(yàn)證、寫，是所有完井事務(wù)均不可避免的三個(gè)階段。但優(yōu)化后的樂觀并發(fā)控制協(xié)議，對BOCC的應(yīng)用環(huán)境進(jìn)行了延伸，使val-write的臨界區(qū)限制得以消除，同時(shí)，基于對各種沖突的分析，完美解決了性能過耗、頻繁重啟等問題，促進(jìn)了完井事務(wù)調(diào)度并發(fā)度的提高?，F(xiàn)對相關(guān)概念作出規(guī)定，以更好地進(jìn)行表述：

定義2 在?ti中，將執(zhí)行ti的起始時(shí)間規(guī)定為S(ti)。

定義3 在?ti中，將ti讀階段結(jié)束，啟動有效性驗(yàn)證操作的起始時(shí)間規(guī)定為V(ti)。

定義4 在?ti中，將ti有效性驗(yàn)證結(jié)束，啟動寫操作的起始時(shí)間規(guī)定為W(ti)。

定義5 在?ti中，ti寫階段完畢的時(shí)間節(jié)點(diǎn)，規(guī)定為F(ti)。

定義6 在?ti中，以映射f指代d(opi)也就是ti的數(shù)據(jù)集，則有式(1)。

(1)

定義7 對于?ti，完井事務(wù)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兩個(gè)完井事務(wù)的沖突寫集、讀集CWW(ti,tj)、CRW(ti,tj)作出如下規(guī)定為式(4)、(5)。

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

(4)

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

(5)

定義9 在?ti中，分別以下述公式來定義ti的讀、寫點(diǎn)TDR(xi)、TDW(xi)：

TDR(xi)=事務(wù)ti讀數(shù)據(jù)項(xiàng)x的時(shí)刻

(6)

TDW(xi)=事務(wù)ti寫數(shù)據(jù)項(xiàng)x的時(shí)刻

(7)

定義10 定義隨機(jī)完井?dāng)?shù)據(jù)項(xiàng)x的讀、寫時(shí)間戳TSR(x)、TSW(x)分別為式(8)、(9)。

TSR(x)=數(shù)據(jù)項(xiàng)x被最后從數(shù)據(jù)庫讀出的時(shí)刻，并記tr(x)為讀取數(shù)據(jù)項(xiàng)x的事務(wù)

(8)

TSW(x)=數(shù)據(jù)項(xiàng)x被最后寫入數(shù)據(jù)庫的時(shí)刻，并記tw(x)為寫入數(shù)據(jù)項(xiàng)x的事務(wù)

(9)

在進(jìn)行新w(x)、r(x)操作的過程中，對TSW(x)、TSR(x)予以更新，ti所關(guān)聯(lián)時(shí)間點(diǎn)共有4個(gè)，分別是S(ti)、V(ti)、W(ti)、F(ti)，將全部活動事務(wù)存入隊(duì)列Q中，以有效驗(yàn)證起始時(shí)間的排序?yàn)橐罁?jù)，決定各活動事務(wù)從隊(duì)列中進(jìn)出時(shí)間的先后。在新協(xié)議下，val-write的臨界區(qū)限制得以消除，對比所有活動中的、有效性驗(yàn)證完畢的完井事務(wù)和所有處于有效性驗(yàn)證操作中的tj，對tj的有效性進(jìn)行檢驗(yàn)。

當(dāng)S(ti)=W(ti)時(shí)，如果完井事務(wù)ti和完井事務(wù)tj存在沖突讀集CRW(ti,tj)，那么根據(jù)完井事務(wù)ti的讀點(diǎn)TDR(xi)與完井事務(wù)tj寫點(diǎn)TDW(xj)的順序，驗(yàn)證完井事務(wù)ti和完井事務(wù)tj讀寫沖突，判斷完井事務(wù)tj是否回滾；如果完井事務(wù)ti和完井事務(wù)tj存在沖突寫集CWW(ti，tj)，那么根據(jù)完井事務(wù)tj的讀集SR(tj)和寫集SW(tj)間的關(guān)系以及V(tj)與F(ti)之間的關(guān)系，驗(yàn)證完井事務(wù)ti和完井事務(wù)tj寫寫沖突，判斷完井事務(wù)tj是否需要等待。優(yōu)化后的BOCC協(xié)議，通過將讀寫時(shí)間戳應(yīng)用于數(shù)據(jù)項(xiàng)，實(shí)現(xiàn)了性能上的突破，這也是其最大的貢獻(xiàn)，通常將其命名為基于讀寫時(shí)間戳的樂觀并發(fā)協(xié)議。

2 面向移動完井業(yè)務(wù)應(yīng)用

2.1 面向完井的讀寫時(shí)間戳樂觀并發(fā)控制協(xié)議設(shè)計(jì)

圍繞移動完井事務(wù)的處理，將基于讀寫時(shí)間戳的樂觀并發(fā)控制協(xié)議應(yīng)用到完井運(yùn)行信息移動服務(wù)平臺中，我們對讀階段、有效驗(yàn)證階段、寫階段這三個(gè)階段進(jìn)行詳細(xì)算法設(shè)計(jì)，具體讀階段算法流程如下：

步驟1：預(yù)先將一個(gè)完井事務(wù)tj作為目標(biāo)，判斷完井事務(wù)tj中是否有操作，如果有，繼續(xù)步驟2；若沒有，結(jié)束讀階段。

步驟2：如果該操作是讀操作，繼續(xù)步驟3；若不是，轉(zhuǎn)至步驟4。

步驟3：對此事務(wù)tj的讀集SR(tj)進(jìn)行讀操作，并更新讀時(shí)間戳TSR(x)以及tr(x)，轉(zhuǎn)至步驟1。

步驟4：如果該操作是寫操作，繼續(xù)步驟5；若不是，轉(zhuǎn)至步驟1。

步驟5：對事務(wù)tj的讀集SW(tj)進(jìn)行寫操作。轉(zhuǎn)至步驟1。

具體的有效驗(yàn)證階段的算法流程如下：

步驟1：存儲在隊(duì)列Q的完井事務(wù)tj出隊(duì)列，當(dāng)隊(duì)列為空的時(shí)候，結(jié)束有效驗(yàn)證階段；若不是，繼續(xù)步驟2。

步驟2：在有效性驗(yàn)證tj的同時(shí)，檢驗(yàn)ti的有效性，判斷是否S(ti)

步驟3：判斷V(tj)>=W(ti)，如果是，繼續(xù)步驟4；否則轉(zhuǎn)至步驟1。

步驟4：判斷事務(wù)ti和事務(wù)tj的沖突讀集CRW(ti,tj)是否為空，若不是，繼續(xù)步驟5；否則轉(zhuǎn)至步驟6。

步驟5：遍歷沖突讀集CRW(ti,tj)中的完井的數(shù)據(jù)項(xiàng)x，判斷是否是TDR(xj)>TDW(xi)，如果是，遍歷結(jié)束后轉(zhuǎn)至步驟9；否則，事務(wù)tj會讀臟數(shù)據(jù)，不能保證事務(wù)tj和事務(wù)ti的沖突可串行化，因此必須回滾事務(wù)tj，之后轉(zhuǎn)至步驟6。

步驟6：判斷事務(wù)ti和事務(wù)tj的沖突寫集CWW(ti,tj)是否為空，若不是，繼續(xù)步驟7；否則轉(zhuǎn)至步驟1。

步驟7：判斷事務(wù)tj的讀集SR(tj)與SW(tj)寫集SW(tj)?SR(tj)是否是，如果是，此時(shí)的情況即為步驟4的情況，已經(jīng)進(jìn)行過驗(yàn)證，因此轉(zhuǎn)至步驟1；否則繼續(xù)步驟8。

步驟8：判斷是否V(tj)>=F(ti)，若不是，完井事務(wù)tj等待直到完井事務(wù)ti結(jié)束；否則轉(zhuǎn)至步驟1。

步驟9：等待完井事務(wù)ti完成有效驗(yàn)證階段，轉(zhuǎn)至步驟1。

具體的寫階段的算法流程如下：

步驟1：將完井事務(wù)tj中的寫集SW(tj)寫入完井?dāng)?shù)據(jù)庫。

步驟2：更新寫時(shí)間戳TSW(x)。

步驟3：更新完井?dāng)?shù)據(jù)項(xiàng)x寫入的事務(wù)tw(x)。

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

為了驗(yàn)證完井運(yùn)行信息移動服務(wù)平臺應(yīng)用基于讀寫時(shí)間戳的樂觀并發(fā)控制協(xié)議后的性能，我們通過模擬實(shí)驗(yàn)程序，進(jìn)行了詳細(xì)的實(shí)驗(yàn)，在實(shí)驗(yàn)中釆用未改進(jìn)的完井運(yùn)行信息移動服務(wù)平臺和改進(jìn)的完井運(yùn)行信息移動服務(wù)平臺作為實(shí)驗(yàn)的參照對象，并對實(shí)驗(yàn)結(jié)果進(jìn)行的簡要的分析。

下述參數(shù)在進(jìn)行實(shí)驗(yàn)時(shí)具有較高使用頻率：移動事務(wù)的平均操作數(shù)為10；該平臺的節(jié)點(diǎn)數(shù)為6；數(shù)據(jù)庫共有2 000M元組數(shù)；事務(wù)截止期為100毫秒。

分別給出了在事務(wù)處理過程中，未改進(jìn)的平臺與改進(jìn)的平臺在并發(fā)移動事務(wù)數(shù)量有所調(diào)整的情況下，事務(wù)吞吐量、夭折率的波動情況。如圖5和圖6所示。

圖5 事務(wù)夭折率變化

圖6 事務(wù)吞吐量變化

由圖5可知，在事務(wù)夭折率方面，并發(fā)移動事務(wù)數(shù)量增加的同時(shí)，兩個(gè)平臺也表現(xiàn)出增長的態(tài)勢，在并發(fā)移動事務(wù)數(shù)量無限接近既定臨界點(diǎn)時(shí)，達(dá)到一個(gè)極小值并有規(guī)律地遞減。原因在于，更新數(shù)據(jù)量的提高，造成沖突發(fā)生率提高，但在無限接近某臨界點(diǎn)時(shí)，更新操作數(shù)量相對較小，所產(chǎn)生的沖突也相對較少[13]。在達(dá)到某個(gè)臨界點(diǎn)之后，改進(jìn)后的平臺在處理并發(fā)事務(wù)時(shí)的夭折率明顯比改進(jìn)前的低，這是因?yàn)楦虏僮鲾?shù)量已經(jīng)足夠使得這些沖突頻繁發(fā)生，改進(jìn)前的平臺在處理并發(fā)事務(wù)時(shí)因沖突過多導(dǎo)致事務(wù)回滾過多，因而事務(wù)夭折率高。

圖6反映的是事務(wù)吞吐量與并發(fā)移動事務(wù)數(shù)量的關(guān)系，通過實(shí)驗(yàn)可以得出這兩個(gè)平臺的事務(wù)吞吐量均隨著并發(fā)移動事務(wù)數(shù)量的增長而先升后降但波動不大。優(yōu)化前，在臨界值時(shí)，平臺吞吐量的值出現(xiàn)最高峰，并以較大幅度迅速降低，其趨勢較改進(jìn)的完井運(yùn)行信息移動服務(wù)平臺明顯。主要因?yàn)殡S著事務(wù)數(shù)量的增多，改進(jìn)后的完井運(yùn)行信息移動服務(wù)平臺利用時(shí)間戳進(jìn)行了優(yōu)化，事務(wù)撤銷率相比改進(jìn)前低，事務(wù)吞吐量比改進(jìn)前的平臺高。

綜上所述，基于讀寫時(shí)間戳的樂觀并發(fā)控制協(xié)議，對傳統(tǒng)并發(fā)控制協(xié)議的不足進(jìn)行了彌補(bǔ)，促進(jìn)了事務(wù)回滾、阻塞概率的降低及并發(fā)度的提高，從整體上對系統(tǒng)的性能進(jìn)行了改進(jìn)。

4 總結(jié)

本文基于完井運(yùn)行信息移動服務(wù)平臺，以移動計(jì)算環(huán)境為背景，對應(yīng)用樂觀并發(fā)控制協(xié)議的必要性進(jìn)行了探討，并在平臺中植入了建立在時(shí)間戳基礎(chǔ)上的樂觀并發(fā)控制協(xié)議。最后，對應(yīng)用基于時(shí)間戳的樂觀并發(fā)控制協(xié)議的完井運(yùn)行信息移動服務(wù)平臺進(jìn)行了實(shí)驗(yàn)，通過實(shí)驗(yàn)說明通過引入基于時(shí)間戳的樂觀并發(fā)控制協(xié)議，能夠有效提高平臺的性能及事務(wù)處理并發(fā)度，實(shí)現(xiàn)了對事務(wù)夭折率的有效控制。