李清霞

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

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

針對(duì)上述問(wèn)題，本文在研究分析基于時(shí)間戳的分布式事務(wù)并發(fā)控制策略的基礎(chǔ)上提出了一種改進(jìn)策略，并通過(guò)實(shí)驗(yàn)證明了改進(jìn)后的并發(fā)控制策略能夠有效減少事務(wù)的回滾，降低資源的開(kāi)銷。

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

1.1 時(shí)間戳

對(duì)于每個(gè)事務(wù)T，系統(tǒng)需要為其指定時(shí)間戳TS(T)。常用來(lái)生成時(shí)間戳的兩種方法是［2］:

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

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

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

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

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

每個(gè)數(shù)據(jù)項(xiàng)Q 需要與兩個(gè)時(shí)間戳相關(guān)聯(lián) :

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

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

1)假設(shè)事務(wù)Ti請(qǐng)求執(zhí)行Read(Q)時(shí)。

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

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

2)假設(shè)事務(wù)Ti請(qǐng)求執(zhí)行Write(Q)時(shí)。

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

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

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

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

1.3 存在的不足

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

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

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

2.1 事務(wù)的延遲操作

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

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

圖1 事務(wù)操作延遲過(guò)程

2.2 Tomas 寫(xiě)規(guī)則

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

圖2 事務(wù)調(diào)度

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

假設(shè)事務(wù)Ti發(fā)出Write(Q)操作請(qǐng)求。

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

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

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

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

2.3 兩版本時(shí)間戳

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

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

在改進(jìn)策略中，對(duì)于每個(gè)數(shù)據(jù)項(xiàng)Q 包含以下五個(gè)數(shù)據(jù)段:

●OldC0ntent:Q 的舊版本值。

●NewC0ntent:Q 的新版本值。

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

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

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

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

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

圖3 Write(Q)流程圖

圖4 Read(Q)流程圖

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

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

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

3 實(shí)驗(yàn)?zāi)M

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

表1 實(shí)驗(yàn)?zāi)M的部分參數(shù)設(shè)置

圖5 實(shí)驗(yàn)結(jié)果

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

4 結(jié)語(yǔ)

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

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

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

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

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

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