， ，

(東北石油大學 計算機與信息技術學院，大慶 163318)

0 引言

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

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

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

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

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

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

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

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

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

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

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

圖1 條件1示意圖

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

圖2 條件2示意圖

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

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

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

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

圖3 完井事務讀寫沖突

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

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

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

圖4 完井事務的BOCC寫寫沖突

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

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

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

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

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

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

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

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

定義6 在?ti中，以映射f指代d(opi)也就是ti的數(shù)據(jù)集，則有式(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)作出如下規(guī)定為式(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讀數(shù)據(jù)項x的時刻

(6)

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

(7)

定義10 定義隨機完井數(shù)據(jù)項x的讀、寫時間戳TSR(x)、TSW(x)分別為式(8)、(9)。

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

(8)

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

(9)

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

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

2 面向移動完井業(yè)務應用

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

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

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

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

步驟3：對此事務tj的讀集SR(tj)進行讀操作，并更新讀時間戳TSR(x)以及tr(x)，轉至步驟1。

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

步驟5：對事務tj的讀集SW(tj)進行寫操作。轉至步驟1。

具體的有效驗證階段的算法流程如下：

步驟1：存儲在隊列Q的完井事務tj出隊列，當隊列為空的時候，結束有效驗證階段；若不是，繼續(xù)步驟2。

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

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

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

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

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

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

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

步驟9：等待完井事務ti完成有效驗證階段，轉至步驟1。

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

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

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

步驟3：更新完井數(shù)據(jù)項x寫入的事務tw(x)。

2.2 實驗結果分析

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

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

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

圖5 事務夭折率變化

圖6 事務吞吐量變化

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

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

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

4 總結

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