分布式實(shí)時(shí)事務(wù)調(diào)度

分布式實(shí)時(shí)事務(wù)調(diào)度

1分布式數(shù)據(jù)庫(kù)的并行發(fā)展根據(jù)字符串方法的配置，數(shù)據(jù)庫(kù)狀態(tài)的一致性通常可以通過(guò)確保數(shù)據(jù)庫(kù)狀態(tài)的一致性來(lái)實(shí)現(xiàn)。然而,串行調(diào)度時(shí),系統(tǒng)運(yùn)行效率可能會(huì)降低,所以實(shí)行有關(guān)操作時(shí),應(yīng)該著重強(qiáng)調(diào)那些執(zhí)行正確的可串行化調(diào)度,提高并發(fā)處理度。在分布式數(shù)據(jù)庫(kù)中,還可以提高各站點(diǎn)的并行處理度。在討論事務(wù)的并發(fā)控制時(shí),很多參考文獻(xiàn)都只是局部地以n個(gè)事務(wù)為前提加以考慮,在事務(wù)串行調(diào)度時(shí),又只是著重強(qiáng)調(diào)使用鎖來(lái)實(shí)現(xiàn)。文章針對(duì)分布式實(shí)時(shí)事務(wù)流中每一個(gè)全局事務(wù)分解后,在每個(gè)站點(diǎn)根據(jù)短子事務(wù)動(dòng)作優(yōu)先以及出現(xiàn)寫(xiě)-讀沖突、讀-寫(xiě)沖突、寫(xiě)-寫(xiě)沖突時(shí)按事務(wù)請(qǐng)求的先后次序方式處理,生成執(zhí)行效率比較高的可串行調(diào)度子事務(wù)動(dòng)作序列,從而提高并發(fā)度和并行處理度。2事務(wù)ti的操作定義1如有一組事務(wù){(diào)T1,T2,…,Ti,…,Tn},假設(shè)事務(wù)Ti的操作都先于Tj,記為T(mén)i<Tj。如一個(gè)調(diào)度S,其每個(gè)事務(wù)的執(zhí)行均有Ti<Tj(i,j的序號(hào)無(wú)關(guān)),記為S={…<Ti<Tj<…},稱S是一串行調(diào)度。2.2分布式事務(wù)模式定義2一個(gè)事務(wù)是一個(gè)偏序集:Ti=(∑i∠i),其中(3)ai或ci是∑i中的最后一個(gè)操作符;(4)如果ri[x],wi[x]∈∑i,則它們必滿足ri[x]<wi[x]或wi[x]<ri[x]。這里只給出了事務(wù)一個(gè)簡(jiǎn)單的定義。事實(shí)上,事務(wù)可能不止以上幾種操作符,如以鎖方式實(shí)現(xiàn)并發(fā)控制時(shí),事務(wù)包含加鎖、解鎖操作,分布式事務(wù)還包含通訊原語(yǔ)等。定義3事務(wù)的一個(gè)操作指組成事務(wù)Ti操作符序列中的任一個(gè)ri[x],wi[x],ci或ai或公式。定義4如果兩個(gè)操作p和q對(duì)同一數(shù)據(jù)項(xiàng)x進(jìn)行操作,其中一個(gè)是寫(xiě)操作w[x],則p和q稱為沖突操作。定義5對(duì)于一組并發(fā)事務(wù)T1,T2,…,Tn,一個(gè)調(diào)度S,S是一個(gè)偏序集S(∑,∠),其中:定義7在調(diào)度中,使得數(shù)據(jù)庫(kù)從一個(gè)一致的狀態(tài)改變到另一個(gè)數(shù)據(jù)一致?tīng)顟B(tài)的調(diào)度,稱為一致性調(diào)度。定義8兩個(gè)調(diào)度S1和S2是等價(jià)的,當(dāng)且僅當(dāng):定義9與串行調(diào)度等價(jià)的調(diào)度,稱之為可串行化調(diào)度。定義10兩個(gè)調(diào)度是沖突等價(jià)的,如果通過(guò)一系列相鄰動(dòng)作的非沖突交換能將它們中的一個(gè)轉(zhuǎn)換為另一個(gè),如果一個(gè)調(diào)度沖突等價(jià)于一個(gè)串行調(diào)度,稱之為沖突可串行化。例1考慮如下調(diào)度:2.3沖突可串行化的定義已知調(diào)度S,其中涉及事務(wù)T1和T2,可能還有其他事務(wù),說(shuō)T1優(yōu)先于T2,寫(xiě)做T1<sT2,如果有T1的動(dòng)作A1和T2的動(dòng)作A2,滿足:(1)在S中A1在A2前;這正是不能交換A1和A2順序的情況。因此,在任何沖突等價(jià)于S的調(diào)度中,A1將出現(xiàn)在A2前。所以,如果這些調(diào)度中有一個(gè)串行調(diào)度,那么該調(diào)度必然使T1在T2前。定義11優(yōu)先圖的結(jié)點(diǎn)是調(diào)度S中的事務(wù)。當(dāng)這些事務(wù)是具有不同的i的Ti時(shí),僅用整數(shù)i來(lái)表示Ti的結(jié)點(diǎn)。如果Ti<sTj,則有一條從結(jié)點(diǎn)i到結(jié)點(diǎn)j的弧。例2下面的調(diào)度S涉及3個(gè)事務(wù)T1、T2和T3。類(lèi)似地,如果看關(guān)于B的動(dòng)作,同樣可以找到T1<sT2的多個(gè)原因。調(diào)度S是否沖突可串行化的簡(jiǎn)單規(guī)則:構(gòu)造S的優(yōu)先圖,并判斷其中是否有環(huán)。如果有,那么S不是沖突可串行化的。但如果該圖是無(wú)環(huán)的,那么S是沖突可串行化的,而且結(jié)點(diǎn)的任一個(gè)拓?fù)漤樞蚨际且粋€(gè)沖突等價(jià)的串行順序。例3考慮調(diào)度2.4子事務(wù)動(dòng)作參考時(shí)間戳ts用時(shí)間戳的方法實(shí)現(xiàn)事務(wù)的并發(fā)控制時(shí),給每一個(gè)事務(wù)賦予一個(gè)唯一的時(shí)間戳,事務(wù)的執(zhí)行等價(jià)于按時(shí)間戳的先后次序串行執(zhí)行,即事務(wù)的沖突操作按時(shí)間的次序進(jìn)行調(diào)度。定義12時(shí)間戳是事務(wù)在某一站點(diǎn)激活時(shí)由系統(tǒng)賦予的全系統(tǒng)唯一的且能夠標(biāo)識(shí)事務(wù)激活的先后次序的一個(gè)標(biāo)識(shí)。參考時(shí)間戳是該文有關(guān)算法中生成實(shí)時(shí)事務(wù)流可串行調(diào)度隊(duì)列時(shí)的參考。當(dāng)沒(méi)有寫(xiě)-讀沖突、讀-寫(xiě)沖突、寫(xiě)-寫(xiě)沖突時(shí)就參考時(shí)間戳的次序來(lái)調(diào)度。子事務(wù)動(dòng)作參考時(shí)間戳(TS)的計(jì)算方法:其中:TN為事務(wù)請(qǐng)求處理時(shí)的序號(hào);TIME為估算該子事務(wù)分解后的某個(gè)具體動(dòng)作時(shí)所需的機(jī)器時(shí)間。在分布式數(shù)據(jù)庫(kù)中,事務(wù)分解為子事務(wù)在相應(yīng)的場(chǎng)地上執(zhí)行。對(duì)一組分布事務(wù)T1,T2,…,Tn,在m個(gè)場(chǎng)地上的一次執(zhí)行,是由每個(gè)場(chǎng)地上的調(diào)度序列S1,S2,…,Sm來(lái)安排。而每個(gè)場(chǎng)地的調(diào)度序列由LTM調(diào)度,其可串行性由前面的可串行化理論進(jìn)行判斷。當(dāng)然,僅對(duì)局部進(jìn)行可串行化調(diào)度是不夠的,還需考慮全局的串行執(zhí)行,因?yàn)槿植淮袝r(shí),沖突操作可能互相鎖住對(duì)方的資源,從而造成分布式死鎖。下面,在分布式環(huán)境中就源源不斷的實(shí)時(shí)事務(wù)流提出一種動(dòng)態(tài)可串行調(diào)度算法。3子事務(wù)動(dòng)作的生成(1)有全局事務(wù)請(qǐng)求處理;(2)全局事務(wù)分解,生成各站點(diǎn)事務(wù),如:TA,TB,…,TM(設(shè)有M個(gè)場(chǎng)地);下面幾個(gè)步驟可以同時(shí)在M個(gè)場(chǎng)地間并行處理:(3)各站點(diǎn)局部事務(wù)分解,生成相應(yīng)的子事務(wù)動(dòng)作,以站點(diǎn)A為例:TA1,TA2,…,TAn,并估算各子事務(wù)動(dòng)作完成所需的機(jī)器時(shí)間;(4)計(jì)算各子事務(wù)動(dòng)作的參考時(shí)間戳;(5)根據(jù)該子事務(wù)動(dòng)作按參考時(shí)間戳的先后次序,將其加入到站點(diǎn)內(nèi)的可串行調(diào)度的隊(duì)列中。加入隊(duì)列時(shí)若有寫(xiě)-讀沖突、讀-寫(xiě)沖突、寫(xiě)-寫(xiě)沖突時(shí)按事務(wù)號(hào)的先后次序優(yōu)先加入隊(duì)列中;4算法流程描述4.1.1每個(gè)站點(diǎn)都可以在團(tuán)隊(duì)結(jié)構(gòu)中組建隊(duì)列結(jié)構(gòu)4.1.2每個(gè)站點(diǎn)劃分后，處理準(zhǔn)備的事務(wù)和操作序列4.2算法流程的具體描述4.2.1在每個(gè)站點(diǎn)中生成動(dòng)態(tài)集群方案的算法5沖突轉(zhuǎn)化處理由于3個(gè)數(shù)據(jù)結(jié)構(gòu)都是改造過(guò)的雙向鏈表,是一種線性結(jié)構(gòu),其存儲(chǔ)空間復(fù)雜性為O(n),程序處理過(guò)程也只是進(jìn)隊(duì)、出隊(duì)的普通算法,其時(shí)間復(fù)雜性為O(n)。在論文的基本概念及有關(guān)定義描述中,只要生成的每個(gè)子事務(wù)動(dòng)作序列都能保持全局事務(wù)的請(qǐng)求次序,則可以保證其優(yōu)先圖是無(wú)環(huán)的,即沖突可串行調(diào)度是正確的。而該文算法正是能保證這一關(guān)鍵。6作子點(diǎn)點(diǎn)點(diǎn)。據(jù)硬件環(huán)境:P42.4GHz,內(nèi)存512MB,5臺(tái)(其中1臺(tái)作主場(chǎng)地,4臺(tái)作子站點(diǎn))。網(wǎng)絡(luò)環(huán)境:100Mbit以太網(wǎng)。軟件平臺(tái):Windows2000Server+VC6.0。6.2環(huán)境試驗(yàn)的設(shè)計(jì)6.2.1刪除同一全局事務(wù)號(hào)線程12.讀出其中事務(wù)號(hào),各站點(diǎn)信息5.延時(shí)一個(gè)隨機(jī)產(chǎn)生的暫短時(shí)間,返回1線程22.若各站點(diǎn)把同一全局事務(wù)號(hào)都處理完成,從全局事務(wù)刪除該事務(wù)號(hào)結(jié)點(diǎn)3.返回16.2.2子事務(wù)動(dòng)作與線程3無(wú)沖突的估計(jì)線程14.返回1線程2線程33.返回1線程42.若該元素中的子事務(wù)動(dòng)作與線程3無(wú)沖突,則按原估計(jì)完成時(shí)間模擬執(zhí)行;否則本線程進(jìn)入等待狀態(tài),讓線程3優(yōu)先執(zhí)行3.返回16.3生成執(zhí)行效率較高的短子事務(wù)動(dòng)作序列重點(diǎn)考慮分布式實(shí)時(shí)事務(wù)流中每一個(gè)全局事務(wù)分解后,在每個(gè)站點(diǎn)根據(jù)短子事務(wù)動(dòng)作優(yōu)先以及出現(xiàn)寫(xiě)-讀沖突、讀-寫(xiě)沖突、寫(xiě)-寫(xiě)沖突時(shí)按事務(wù)請(qǐng)求的先后次序方式處理,生成執(zhí)行效率比較高的可串行調(diào)度子事務(wù)動(dòng)作序列,實(shí)驗(yàn)數(shù)據(jù)表明該算法有更高并發(fā)度及并行處理度。2.1其他同函數(shù)b(1)∑i是操作符集,包含{ri[x],wi[x]|x是數(shù)據(jù)項(xiàng)}∪{ai|ci};(2)∑i中ai與ci兩者只出現(xiàn)一個(gè);(3)對(duì)于任意兩種沖突操作p和q∈S,則有p<q或q<p。(1)調(diào)度S1和S2在同一事務(wù)上定義,且具有相同的操作集。(2)對(duì)于有沖突的操作的事務(wù),有:r1(A);w1(A);r2(A);w2(A);r1(B);w1(B);r2(B);w2(B);說(shuō)這個(gè)調(diào)度是沖突可串行化。圖1給出了將這一調(diào)度轉(zhuǎn)換為串行調(diào)度(T1,T2)的一系列交換,在此串行調(diào)度中,T1的所有動(dòng)作都調(diào)度到T2的所有動(dòng)作之前。在每一步中要交換的相鄰動(dòng)作上加了下劃線。(2)A和A都涉及同一數(shù)據(jù)庫(kù)元素;(3)A1和A2中至少有一個(gè)寫(xiě)動(dòng)作。S:r2(A);r1(B);w2(A);r3(A);w1(B);w3(A);r2(B);w2(B)如果看關(guān)于A的動(dòng)作,可以找到T2<sT3的多個(gè)原因。例如,在S中,r2(A)在w3(A)前,而w2(A)既在r3(A)前又在w3(A)前。S′:r2(A);r1(B);w2(A);r2(B);r3(A);w1(B);w3(A);w2(B);查看關(guān)于A的動(dòng)作,仍然只能得到先后次序T2<S′T3。但是,當(dāng)檢查B時(shí),不僅有T1<S′T2(因?yàn)閞1(B)和w1(B)出現(xiàn)在w2(B)前),還得到T2<S′T1(因?yàn)閞2(B)出現(xiàn)在w1(B)前)。因此,得到圖3調(diào)度S′優(yōu)先圖。由于該圖有環(huán),斷定S′不是沖突可串行化的。(6)將已經(jīng)完成的子事務(wù)動(dòng)作從可串行調(diào)度隊(duì)列中刪除;(7)返回步驟(1),不斷處理全局事務(wù)的請(qǐng)求。4.1主要數(shù)據(jù)結(jié)構(gòu)注:每個(gè)待處理事務(wù)的頭結(jié)點(diǎn)的TS域內(nèi)記錄的是該全局待處理的事務(wù)編號(hào)。4.1.3全日制事務(wù)的分解序列4.2.2每個(gè)站點(diǎn)都可以使用團(tuán)隊(duì)模型動(dòng)態(tài)線程事務(wù)序列來(lái)執(zhí)行團(tuán)