一種改進的基于時間戳的分布式事務并發(fā)控制策略

李清霞

(東莞理工學院 城市學院，廣東東莞 523419)

并發(fā)控制是事務處理的核心技術之一，是指數(shù)據(jù)庫合理調(diào)度并發(fā)事務，避免并發(fā)事務之間的相互干擾造成數(shù)據(jù)的不一致性。分布式事務并發(fā)控制策略主要有封鎖和時間戳這兩種。時間戳策略是指每個事務在產(chǎn)生時，系統(tǒng)會賦予事務唯一的時間戳，越晚開始的事務將獲得越大的時間戳，當某事務與比其時間戳更大(更晚)的事務發(fā)生沖突時，它會中止。而在同樣的情況下，如果使用封鎖策略的話，事務將等待或立即繼續(xù)執(zhí)行［1］。另一方面，基于時間戳的并發(fā)控制不會造成死鎖，這對于分布式事務處理來說是一個很大的優(yōu)點，因為如果分布式事務處理存在發(fā)生死鎖的可能，那么系統(tǒng)一般只能采用死鎖檢測機制來處理死鎖問題，而在分布式環(huán)境下實現(xiàn)死鎖檢測機制是較為復雜且資源開銷比較大的，其復雜度和資源開銷還會隨著分布式規(guī)模的增大而增加。雖然基于時間戳的分布式事務并發(fā)控制能夠避免死鎖的發(fā)生，但是卻容易造成事務的回滾［2］。

針對上述問題，本文在研究分析基于時間戳的分布式事務并發(fā)控制策略的基礎上提出了一種改進策略，并通過實驗證明了改進后的并發(fā)控制策略能夠有效減少事務的回滾，降低資源的開銷。

1 基于時間戳的并發(fā)控制

1.1 時間戳

對于每個事務T，系統(tǒng)需要為其指定時間戳TS(T)。常用來生成時間戳的兩種方法是［2］:

1)使用系統(tǒng)時鐘值作為時間戳，即事務的時間戳等于該事務進入系統(tǒng)時的時鐘值。

2)使用邏輯計數(shù)器，即事務的時間戳等于該事務進入系統(tǒng)時的計數(shù)器值，每賦予一個時間戳，計數(shù)器增加一次。

事務的時間戳決定了事務的串行化順序。即若TS(Ti)＜TS(Tj)，則系統(tǒng)必須保證所產(chǎn)生的調(diào)度等價于事務Ti出現(xiàn)在事務Tj之前的某個串行調(diào)度。

1.2 時間戳排序協(xié)議

利用時間戳可以將事務進行全局排序，使較早啟動的事務(具有較小的時間戳)在沖突時擁有較高的優(yōu)先權(quán)。如果一個事務試圖去“讀/寫”一個數(shù)據(jù)項，只有當該數(shù)據(jù)項的最近一次更新是由比此事務更早的事務完成時，該“讀/寫”操作才允許進行，否則發(fā)出請求的事務將被重新啟動，并給予一個新的時間戳。時間戳法產(chǎn)生的可串行化調(diào)度表的次序等價于成功提交事務的時間戳序列。

每個數(shù)據(jù)項Q 需要與兩個時間戳相關聯(lián) :

●R－timestamp(Q):任何成功執(zhí)行Read(Q)的事務的最大時間戳。

●W－timestamp(Q):任何成功執(zhí)行Write(Q)的事務的最大時間戳。

1)假設事務Ti請求執(zhí)行Read(Q)時。

a)如果TS(Ti)＜W－timestamp(Q)，則Ti需讀入的Q 值已被覆蓋。因此，Read 操作被拒絕，Ti回滾。

b)如果TS(Ti)＞ = W－timestamp(Q)，則執(zhí)行Read 操作，R－timestamp(Q)被設為MAX(R－timestamp(Q)，TS(Ti))。

2)假設事務Ti請求執(zhí)行Write(Q)時。

a)如果TS(Ti)＜R－timestamp(Q)，則Ti產(chǎn)生的Q 值是先前所需要的值，且系統(tǒng)已經(jīng)假定該值不會發(fā)生。因此，Write 操作被拒絕，Ti回滾。

b)如果TS(Ti)＜W－timestamp(Q)，則Ti試圖寫入的Q 值已過時。因此，Write 操作被拒絕，Ti回滾。

c)否則，執(zhí)行Write 操作，將w－timestamp(Q)設為TS(Ti)。

如果事務Ti由于請求Read 或Write 操作而被并發(fā)控制機制滾回，則系統(tǒng)賦予它新的時間戳并重新啟動。

1.3 存在的不足

基于時間戳的并發(fā)控制雖然能保證沖突可串行化和無死鎖性，但是當一系列沖突的短事務引起長事務反復重啟時，可能會導致長事務餓死的現(xiàn)象［2］。另外，并發(fā)發(fā)事務頻繁讀寫同一個數(shù)據(jù)項時，很容易會造成事務的頻繁回滾，從而耗費大量的資源開銷。在分布式環(huán)境中，要實現(xiàn)全局時間戳的一致性和唯一性也是一個難題［3］。此外數(shù)據(jù)項的時間戳信息需要額外的空間來存儲，一旦遇到事務處理要涉及的數(shù)據(jù)項很多的情況，那么存儲它們的時間戳信息需要不小的空間，這無疑增加了系統(tǒng)負擔［4］。

2 改進并發(fā)控制策略

針對傳統(tǒng)策略存在的不足，我們提出了一種改進的并發(fā)控制策略，在傳統(tǒng)策略的基礎上增加了對事務操作的延遲，Tomas 寫規(guī)則，兩版本時間戳以及放棄對數(shù)據(jù)項時間戳信息的持久性保存。

2.1 事務的延遲操作

考慮分布式事務Ti的一個子事務Ti1，它要執(zhí)行Read(Q)的操作，Q 為一個數(shù)據(jù)項，然而在經(jīng)過很短的時間間隔t 后馬上又有分布式事務Tj的一個子事務Tjl要執(zhí)行Write(Q)的操作，而且TS(Ti1)＞TS(Tj1)，這就說明Ti1比Tj1要先開始，根據(jù)時間戳排序協(xié)議，TS(Ti1)＜R－timestamp(Q)，所以Tj1的操作被拒絕，Tj1不得不通過回滾獲得一個新的時間戳。但如果能延遲時間tdelay(tdelay＞t)再執(zhí)行Ti1Read(Q)的操作，那么事務Tj1的Write(Q)操作就會因為其時間戳小而先被得到執(zhí)行，從而避免了事務Tj1的回滾［5］。

改進的并發(fā)控制策略引入了事務操作延遲的概念，如圖1 所示，各種事務請求執(zhí)行的操作將會被先放入延遲隊列中，操作按時間戳的大小進行排列，時間戳越小的操作越排在前面被先執(zhí)行，每次有新的操作請求來到時，系統(tǒng)會根據(jù)其時間戳的大小將其插入到延遲隊列中相應的位置。當經(jīng)過延遲時間tdelay后或者延遲隊列中的事務操作數(shù)目超過最大延遲操作數(shù)目時，延遲隊列中的操作將會被放入執(zhí)行隊列中被執(zhí)行。這里的延遲時間和最大延遲操作數(shù)目都需根據(jù)實際環(huán)境而設置，延遲時間不能太短，最大延遲操作數(shù)目也不能太小，不然達不到減少事務回滾的目的，而相反的話就會造成事務操作延遲很久才被執(zhí)行，降低事務處理的效率。

圖1 事務操作延遲過程

2.2 Tomas 寫規(guī)則

考慮對圖2 所示的調(diào)度應用時間戳并發(fā)控制。T11是分布式事務T1的子事務，T21是分布式事務T2的子事務。由于T11先于T21開始，所以TS(T11)＜TS(T21)。T11的Read(Q)操作成功，T21的Write(Q)操作也成功。當T11試圖進行Write(Q)操作時，由于TS(T11)＜W－timestamp(Q)，因為Wtimestamp(Q)= TS(T21)，所以T11的W rite(Q)操作被拒絕且事務T11必須回滾。雖然事務T11回滾是時間戳并發(fā)控制所要求的，但這是不必要的。由于T21己經(jīng)寫入了Q，T11想要寫入的值永遠不會被讀到。滿足TS(Ti)＜TS(T21)的任何事務Ti試圖進行Read(Q)操作時都會被回滾，因為TS(Ti)＜W－timestamp(Q)。滿足TS(Ti)＞TS(T21)的任何事務Ti必須讀由T21寫入的Q 值，而不是T11寫入的值。

圖2 事務調(diào)度

根據(jù)以上所述，在改進的并發(fā)控制策略中引入了Tomas 寫規(guī)則［2］:

假設事務Ti發(fā)出Write(Q)操作請求。

1)如果TS(Ti)＜R－timestamp(Q)，則Ti產(chǎn)生的Q 值是先前所需要的值，且系統(tǒng)己經(jīng)假定該值不會發(fā)生。因此，Write 操作被拒絕，Ti回滾。

2)如果TS(Ti)＜W－timestamp(Q)，則Ti試圖寫入的Q 值己過時。因此，Write 操作可以被忽略。

3)否則，執(zhí)行W rite 操作，將W－timestamp(Q)設為TS(Ti)隔離級。

Tomas 寫規(guī)則實際上是通過刪除事務發(fā)出的過時Write 操作來實現(xiàn)可串行化的，可以避免由于過時Write 操作被拒絕而導致的事務回滾。

2.3 兩版本時間戳

在基于時間戳的并發(fā)控制策略中，每一個事務只對應唯一的時間戳，但是這樣可能會出現(xiàn)Read 操作由于相應值還未寫入而延遲，或者因為它要讀取的值己經(jīng)被覆蓋而被拒絕執(zhí)行，從而導致事務的回滾［2］。但是如果每一數(shù)據(jù)項的更新的副本都被保存在系統(tǒng)中，這些問題就可以避免了，但這樣做系統(tǒng)需要大量的額外空間來保存這些副本，而這些副本可能大多數(shù)都極少能被使用到。

針對這一點，改進策略采用了兩版本時間戳的方法，每一數(shù)據(jù)項只保存當前的版本值和最近一次更新的版本值，這樣基本可以解決Read 操作延遲讀的問題又節(jié)省了不少的副本存儲空間。

在改進策略中，對于每個數(shù)據(jù)項Q 包含以下五個數(shù)據(jù)段:

●OldC0ntent:Q 的舊版本值。

●NewC0ntent:Q 的新版本值。

●W－OldTimestam:Q 的舊版本執(zhí)行完Write(Q)的事務的最大時間戳。

●W－NewTimestamp:Q 的新版本執(zhí)行完W rite(Q)的事務的最大時間戳。

●R－Timestamp:Q 執(zhí)行完Read(Q)的最大時間戳。

圖3 給出Write(Q)操作的執(zhí)行流程，如果事務Ti請求Write(Q)操作合法，那么先將數(shù)據(jù)項Q的OldContent 設為NewContent，而Q 的NewContent 則設為最近寫入的值，再將W－OldTimestaimp 設為W－NewTimestamp，W－NewTimestamp 設為TS(Ti)，最后把R－Timestamp 設為MAX(R－Timestamp，TS(Ti))。

假設事務Ti發(fā)出Read(Q)操作，如果TS(Ti)＞= W－NewTimestamp，就讀取NewContent 的值，否則如果TS(Ti)＞= W－OldTimestamp，就讀取OldContent 的值，如果TS(Ti)＜W－NewTimestamp 而且TS(Ti)＜W－OldTimestamp 的話，Read(Q)操作被拒絕，事務Ti回滾，Read(Q)操作基本流程如圖4所示。

圖3 Write(Q)流程圖

圖4 Read(Q)流程圖

2.4 數(shù)據(jù)項時間戳的非持久保存

在基于時間戳的并發(fā)控制策略中，數(shù)據(jù)項的時間戳充當著一個相當重要的角色。傳統(tǒng)的做法都是將數(shù)據(jù)項最近一次的時間戳信息放入數(shù)據(jù)庫保存，可是一旦需要使用大量數(shù)據(jù)項的時候，則需要不小的數(shù)據(jù)庫空間來存儲這些信息［4］。

考慮到數(shù)據(jù)項的時間戳信息在并發(fā)控制策略中主要用來實現(xiàn)時間戳排序協(xié)議，更新的頻率比較高，而且對時間戳信息的使用集中在事務對數(shù)據(jù)項的操過程，一旦所有操作都己經(jīng)完成，時間戳信息也失去了其使用價值。在改進策略中，數(shù)據(jù)項Q 的時間戳信息并不需要存入數(shù)據(jù)庫，只是每次在使用到Q 之前都要先在內(nèi)存中對其時間戳信息進行初始化，將R－timestamp(Q)和W－timestamp(Q)都設置為0，因為任何需要對Q 進行事務操作的時間戳都不可能小于0，就意味對Q 進行操作的事務只需考慮初始化之后與其他事務操作發(fā)生的沖突。這樣一方面可以免去從數(shù)據(jù)庫獲取數(shù)據(jù)項時間戳信息的系統(tǒng)資源開銷和時間開銷，另一方面也可以節(jié)省存儲數(shù)據(jù)項時間戳信息的數(shù)據(jù)庫空間。

3 實驗模擬

實驗模擬主要是為了將傳統(tǒng)的基于時間戳的分布式事務并發(fā)控制策略同改進策略進行性能的比較。因為在分布式事務處理中，由于網(wǎng)絡的延遲等因素可能會造成分布式事務的處理請求并不是按照其時間戳的先后順序被送到相應的結(jié)點進行處理的，所以在實驗模擬中，對事務操作的時間戳采用邏輯計數(shù)器隨機分配和非完全隨機分配兩種方式，操作請求時間間隔則都是隨機生成的。這里的非完全隨機是指在隨機變量的基礎上再加上一個遞增變量。實驗模擬的部分參數(shù)設置如表1 所示。

表1 實驗模擬的部分參數(shù)設置

圖5 實驗結(jié)果

圖5 所示的是幾次典型的實驗結(jié)果，可以明顯看出改進策略具有比傳統(tǒng)策略更低的事務操作回滾率，特別是當參與操作的數(shù)據(jù)項數(shù)目較多并且操作的時間戳采用非完全隨機分配時，改進策略能夠更為有效地減少回滾。而且在實驗模擬中，所有參與操作的數(shù)報項的時間戳信息都在內(nèi)存中進行初始化和相關操作，并沒有存放入數(shù)據(jù)庫，這不僅節(jié)省了存儲空間，也減少了資源開銷和時間開銷，提高了執(zhí)行效率。

4 結(jié)語

本文首先介紹了基于時間戳的分布式事務并發(fā)控制策略，然后提出了一種改進策略，最后通過實驗證明了改進策略能夠有效彌補傳統(tǒng)策略上的部分不足之處。不過改進后的策略延遲了事務的操作，可能會延長部分事務的處理時間，不太適合應用到那些對實時性要求很高的事務處理中，而且在改進策略中，像如何實現(xiàn)全局時間戳的一致性等問題還沒有得到解決，這都是我們下一步工作需要研究改進的地方。

［1］Andrew S. Tanenbaum，Maarten van Steen. Distributed systems Principles and Paradigms［M］.楊劍峰，常曉波，李敏，譯. 北京:清華大學出版社，2004:9.

［2］Abraham Silberschatz，Henry F Korth Sudarshan S. DataBase System Concepts［M］. 楊冬青，唐世渭，譯. 北京:機械工業(yè)出版社，2003:3.

［3］李陶深，武燕華. 基于全局時標的網(wǎng)格事務并發(fā)機制研究［J］. 計算機工程與設計，2011，32(8):2729－2733.

［4］Hector Garcia－Molina，Jeffrey D. Ullman，Jennifer Widom. Database system Implementation［M］. 楊冬青，唐世渭，徐其鈞，等，譯. 北京:機械工業(yè)出版社，2001:3.

［5］Philip A. Bernstein，Vassos Hadzilacos，Nathan Goodman. Concurrency Control and Recovery in Database Systems［M］. Addison－Wesley Publishing Company，1987.