王大海,賈玉珍,靳冰

(1.新鄉(xiāng)職業(yè)技術(shù)學(xué)院,河南 新鄉(xiāng)453000;2.南陽理工學(xué)院 軟件學(xué)院,河南 南陽 473004)

數(shù)據(jù)庫集群系統(tǒng)以集群技術(shù)與數(shù)據(jù)庫系統(tǒng)相結(jié)合,是一組完整的、自治的計(jì)算處理單元,每個(gè)節(jié)點(diǎn)均有獨(dú)自的CPU、內(nèi)存以及磁盤等硬件資源,運(yùn)行獨(dú)立的操作系統(tǒng)和自治的數(shù)據(jù)庫系統(tǒng),通過高速專用網(wǎng)絡(luò)或商業(yè)通用網(wǎng)絡(luò)互連,彼此協(xié)同計(jì)算,作為統(tǒng)一的數(shù)據(jù)庫系統(tǒng)提供并行事務(wù)處理服務(wù)[1]。

近年來,集群系統(tǒng)中的負(fù)載平衡問題受到人們的關(guān)注。負(fù)載平衡包含許多因素,例如系統(tǒng)結(jié)構(gòu)[2]、算法[3]、資源管理[4]和數(shù)據(jù)分布[5]以及負(fù)載應(yīng)用類型[3]等都會(huì)影響系統(tǒng)的性能平衡。

為了保證全局事務(wù)執(zhí)行的正確性和一致性,本文在研究數(shù)據(jù)庫集群中的事務(wù)并發(fā)控制方法的基礎(chǔ)上,提出了一種多粒度的沖突判斷和死鎖檢測(cè)方法,使事務(wù)并發(fā)控制的粒度達(dá)到謂詞級(jí),并討論各種謂詞的提取方法,既提高全局事務(wù)處理效率,又不需要對(duì)局部數(shù)據(jù)庫做任何限制。本文還改進(jìn)了一種以事務(wù)提交圖為中心的并發(fā)事務(wù)調(diào)度算法來保證集群系統(tǒng)中全局事務(wù)的可串行化提交,以增加吞吐率和減少響應(yīng)時(shí)間。

1 多粒度集群數(shù)據(jù)庫并發(fā)控制算法

1.1 集群系統(tǒng)中的事物模型

數(shù)據(jù)庫集群系統(tǒng)中的事務(wù)分為兩種:全局事務(wù)和局部事務(wù),我們把只在一個(gè)站點(diǎn)上執(zhí)行的事務(wù)稱為局部事務(wù)或本地事務(wù)[6]。

定義1:一個(gè)提交到某個(gè)數(shù)據(jù)庫站點(diǎn)j上的執(zhí)行的事務(wù)Li是局部事務(wù),當(dāng)且僅當(dāng)}。其中 Dj表示局部站點(diǎn)j上的所有數(shù)據(jù)集合,Oi表示事務(wù)Li的所有讀、寫操作的數(shù)據(jù)對(duì)象的集合,而R(x)和W(x)則分別表示對(duì)數(shù)據(jù)項(xiàng)x的讀操作和寫操作。

全局事務(wù)是需要在多個(gè)站點(diǎn)上執(zhí)行的事務(wù)。

定義2:一個(gè)事務(wù)是全局事務(wù) Gi,當(dāng)且僅當(dāng)(任意 Dj∈{D1,D2,…,Dn})?Dj),Oi=。該定義表示全局事務(wù)操作的讀寫集所需訪問的數(shù)據(jù)不僅僅只包含于一個(gè)站點(diǎn)而是跨多個(gè)站點(diǎn)的。

由以上定義可知,局部事務(wù)僅在集群中一個(gè)自治的數(shù)據(jù)庫站點(diǎn)上執(zhí)行,而全局事務(wù)需要在集群系統(tǒng)中被分解為多個(gè)子事務(wù)然后發(fā)送到多個(gè)數(shù)據(jù)庫站點(diǎn)上執(zhí)行。本文把全局事務(wù)劃分為對(duì)應(yīng)站點(diǎn)上執(zhí)行的子事務(wù)稱為全局子事務(wù),每個(gè)子事務(wù)僅對(duì)應(yīng)一個(gè)數(shù)據(jù)庫站點(diǎn)操作,因此全局子事務(wù)也可以看作是僅在一個(gè)數(shù)據(jù)庫站點(diǎn)上執(zhí)行的局部事務(wù)。

由于集群中各數(shù)據(jù)庫站點(diǎn)的自治性和局部性,在每個(gè)局部站點(diǎn)的數(shù)據(jù)庫系統(tǒng)上既可以執(zhí)行由全局事務(wù)劃分的全局子事務(wù)又可以執(zhí)行不需劃分的局部事務(wù),雖然局部事務(wù)的一致性可以在單站點(diǎn)數(shù)據(jù)庫上得到保證,而作為全局事務(wù)所劃分的子事務(wù)在對(duì)應(yīng)的多個(gè)數(shù)據(jù)庫站點(diǎn)上執(zhí)行時(shí),其全局事務(wù)的原子性和一致性難以得到保證,因此這里將主要討論集群系統(tǒng)中跨多個(gè)站點(diǎn)執(zhí)行的并發(fā)全局事務(wù)間的一致性和正確性。

1.2 多粒度的并發(fā)控制

數(shù)據(jù)庫集群系統(tǒng)中并發(fā)控制的核心部件是事務(wù)管理器,如何提高事務(wù)管理器中事務(wù)執(zhí)行的并發(fā)度,提高處理效率成為研究的主要問題。集群系統(tǒng)中的事務(wù)管理器在調(diào)度全局事務(wù)的子事務(wù)在集群系統(tǒng)中的多個(gè)站點(diǎn)上執(zhí)行時(shí),由于資源競(jìng)爭(zhēng)會(huì)產(chǎn)生沖突,這些全局事務(wù)間的沖突主要可分為直接沖突和間接沖突。全局事務(wù)間的沖突歸根結(jié)底是由兩個(gè)或兩個(gè)以上的事務(wù)在相同站點(diǎn)上同時(shí)訪問相同的數(shù)據(jù)對(duì)象而引起的,因而這些事務(wù)間的沖突類型主要有讀-寫、寫-寫和寫-讀沖突三種。

首先,兩個(gè)全局事務(wù)間的直接沖突[7]定義如下:

定義3:當(dāng)且僅當(dāng)下列條件成立時(shí)稱兩操作p和q是直接沖突的,記為pCTq:

由以上定義可知,兩個(gè)或多個(gè)數(shù)據(jù)操作產(chǎn)生沖突的條件是:(1)兩個(gè)操作屬于不同的全局事務(wù);(2)兩個(gè)操作訪問相同站點(diǎn)上的同一數(shù)據(jù)項(xiàng)且其中至少有一個(gè)為寫操作,否則就不會(huì)產(chǎn)生沖突;(3)兩個(gè)操作都同時(shí)訪問數(shù)據(jù)對(duì)象,亦即兩全局事務(wù)在時(shí)間上同時(shí)發(fā)生才可能產(chǎn)生沖突。

為了保持局部站點(diǎn)數(shù)據(jù)庫的自治性,并發(fā)全局事務(wù)間的沖突檢測(cè)必須由集群系統(tǒng)中的事務(wù)管理器來執(zhí)行,而且全局事務(wù)間的沖突檢測(cè)粒度會(huì)直接影響事務(wù)執(zhí)行的并發(fā)度,在全局事務(wù)的并發(fā)控制中如果采用傳統(tǒng)的元組級(jí)封鎖,雖然可以實(shí)現(xiàn)細(xì)粒度的并發(fā)控制,但其缺點(diǎn)是開銷代價(jià)太高。本文在事務(wù)管理器中采用謂詞技術(shù)而不需封鎖元組來檢測(cè)全局事務(wù)間的直接或間接沖突,以實(shí)現(xiàn)多級(jí)粒度的沖突檢測(cè)機(jī)制,同時(shí)也進(jìn)一步減小了死鎖檢測(cè)粒度,提高了全局事務(wù)處理的并發(fā)度。

謂詞的概念及提取技術(shù)一:為了進(jìn)行全局事務(wù)間沖突的判斷,首先必須要分析出全局事務(wù)所要操作的數(shù)據(jù)粒度,而采用謂詞方法就是一種表示全局事務(wù)多級(jí)粒度操作對(duì)象的有效手段,謂詞是指全局事務(wù)的SQL語句中DML四種操作所帶的where分詞條件,這種分詞條件一般可分為謂詞常項(xiàng)(表示具體性質(zhì)和關(guān)系的詞)和謂詞變項(xiàng)(表示抽象的或泛指的謂詞)[3-4]。

根據(jù)謂詞提取及轉(zhuǎn)化的定義和規(guī)則,具體的where謂詞條件分解過程如分解算法1所示。

分解算法1:

1)if謂詞pred條件的右邊是常量:(1)獲得謂詞pred左邊的屬性定義;(2)if屬性定義中存在一個(gè)選擇子句,找到選擇子句中所涉及的關(guān)系,并將它加入條件謂詞列表中;(3)調(diào)用算法2,分解屬性定義中的查詢子句;(4)else/*屬性定義是一個(gè)簡(jiǎn)單引用*/,找到簡(jiǎn)單引用所涉及的關(guān)系,并將它加入條件謂詞列表中;end if。

2)else/*謂詞pred的右邊不是常量*/:(1)分別得到謂詞左右兩邊的屬性定義;(2)if左右兩邊的屬性定義都是查詢,for右邊屬性定義的所有選項(xiàng)r,for左邊屬性定義的所有選項(xiàng)l,找到r和l所涉及的關(guān)系,if右邊r和左邊l的關(guān)系相同加入到謂詞列表中,else發(fā)送繼續(xù)執(zhí)行,end for;/*左邊屬性定義的選擇項(xiàng)*/,調(diào)用算法2,分解左邊屬性定義中的查詢子句。end for;/*右邊屬性定義的選擇項(xiàng)*/,調(diào)用算法2,分解右邊屬性定義中的查詢子句;(3)else if;左邊的屬性定義是簡(jiǎn)單引用,右邊的屬性定義是查詢找到左邊屬性定義中對(duì)應(yīng)的關(guān)系,for右邊屬性定義的所有選項(xiàng)r,找到r所對(duì)應(yīng)的關(guān)系。if左右兩邊關(guān)系相同,加入條件謂詞列表中。end for;/*右邊屬性定義的選擇項(xiàng)*/,調(diào)用算法2,分解右邊屬性定義中的查詢子句;(4)else if;左邊的屬性定義是查詢,右邊的屬性定義是簡(jiǎn)單引用。找到右邊屬性定義中對(duì)應(yīng)的關(guān)系,for左邊屬性定義的所有選擇項(xiàng)l,找到左邊l所對(duì)應(yīng)的關(guān)系。if左右兩邊的關(guān)系相同加入條件謂詞列表中。end for;/*左邊屬性定義的選擇項(xiàng)*/,調(diào)用算法2,分解左邊屬性定義中的查詢子句;(5)else if左右兩邊的屬性定義都是簡(jiǎn)單引用。如果關(guān)系左右兩邊屬性定義中各自對(duì)應(yīng)的關(guān)系相同,則加入條件謂詞列表中;(6)end if;/*判斷左右兩邊的屬性定義是簡(jiǎn)單引用還是查詢*/。

3)end if;/*判斷謂詞pred的右邊是不是常量*/。下面是分解屬性定義中的查詢子句算法2。

分解算法2:

for q的所有查詢條件cond,找到cond左右兩邊對(duì)應(yīng)的關(guān)系;如果兩邊關(guān)系相同,則加入到條件謂詞列表中。end for;在算法1的謂詞分解流程中,當(dāng)謂詞條件在左右兩邊的屬性定義都是查詢時(shí)最復(fù)雜,假設(shè)當(dāng)左右邊各有n個(gè)屬性定義時(shí),算法1的時(shí)間復(fù)雜度為O(n2)。

謂詞的概念及提取技術(shù)二:集群系統(tǒng)中的全局事務(wù)在以SQL語句形式執(zhí)行時(shí)只有對(duì)應(yīng)的DML操作可能會(huì)產(chǎn)生讀-寫、寫-寫和寫-讀三種沖突,而DML操作主要有 4種:select、update、insert和delete,如果將select等效于讀操作,而insert、update和delete操作等效于寫操作來替代,沖突矩陣如下表1。

表1 SQL語句沖突矩陣Tab.1 SQL statements conflict matrix

在表1中,“Y”表示操作在謂詞級(jí)上沖突是相容的;“N”表示操作在謂詞級(jí)上可能是沖突相容也可能是不相容的,需要進(jìn)一步判斷是否有謂詞交集;“-”表示插入操作與其他操作在謂詞級(jí)上無法判斷是否沖突 (因?yàn)椴迦氩僮饕话銦o條件謂詞,只能加表級(jí)鎖)進(jìn)而退化到表級(jí)是沖突不相容的,另外如果允許關(guān)系中存在重復(fù)元組時(shí),insert與insert操作應(yīng)該在表級(jí)上是沖突相容的。以上直接沖突判斷的矩陣防止了數(shù)據(jù)庫中出現(xiàn)的幻象干擾。

全局事務(wù)間基于謂詞的多粒度直接沖突判斷算法流程如圖1所示,該過程不需對(duì)具體的沖突對(duì)象進(jìn)行繁瑣的上鎖操作從而減少了系統(tǒng)開銷,因此可以提高事務(wù)處理的并發(fā)度,使全局事務(wù)間直接沖突判斷的粒度能精確到謂詞級(jí)。此外,為了方便處理,當(dāng)SQL語句中沒有分詞條件時(shí),例如insert語句或不帶條件的delete、select和 update語句亦即沒有where條件和having條件時(shí),謂詞的提取粒度就直接限定在表級(jí);如果謂詞級(jí)條件不在相同屬性上并且也沒有定義不同屬性列間的相關(guān)匹配情況,就無法判斷元組是否有交集,因此也不能縮小檢測(cè)粒度,只能在表級(jí)判斷是否沖突。

兩個(gè)全局事務(wù)間的直接沖突雖然通過以上流程實(shí)現(xiàn)了多粒度的檢測(cè),但對(duì)兩個(gè)以上的并發(fā)全局事務(wù)間的間接沖突是由兩兩全局事務(wù)間的直接沖突構(gòu)成的,因此,全局事務(wù)間的間接沖突檢測(cè)比較復(fù)雜,首先需要在謂詞沖突圖中建立全局事務(wù)兩兩之間的直接沖突關(guān)系,才能進(jìn)一步檢測(cè)多個(gè)并發(fā)的全局事務(wù)間是否存在間接沖突,若謂詞沖突圖中存在一條從一個(gè)全局事務(wù)Gi到另一個(gè)全局事務(wù)Gj間的路徑,Gi和Gj存在間接沖突。此外,謂詞沖突圖還可檢測(cè)多個(gè)并發(fā)全局事務(wù)間產(chǎn)生的死鎖。

謂詞沖突中的死鎖檢測(cè):傳統(tǒng)的解決死鎖問題的方法有死鎖預(yù)防和死鎖檢測(cè)。死鎖預(yù)防要求用戶進(jìn)程事先申報(bào)所需的資源或按嚴(yán)格的規(guī)程申請(qǐng)資源,而死鎖檢測(cè)原則上應(yīng)允許死鎖發(fā)生,在適當(dāng)?shù)臅r(shí)機(jī)檢查,若發(fā)生死鎖,則設(shè)法排除之。預(yù)防死鎖與檢測(cè)死鎖相比,前者過于保守,導(dǎo)致全局事務(wù)的并發(fā)度不高。

多個(gè)并發(fā)的全局事務(wù)可能因?yàn)橹苯記_突或間接沖突而形成死鎖,借助謂詞沖突圖中全局事務(wù)間的沖突依賴關(guān)系需要進(jìn)一步檢測(cè)全局事務(wù)是否形成死鎖。

定理1:全局事務(wù)間形成死鎖,當(dāng)且僅當(dāng)謂詞沖突圖中存在環(huán)。

證明:(必要性)如果謂詞沖突圖中存在環(huán),則全局事務(wù)會(huì)產(chǎn)生死鎖。謂詞沖突圖是一個(gè)有向圖,圖中從 i指向j的邊即i→j,表明j被阻塞了并且等待i釋放沖突站點(diǎn)上的某些資源。當(dāng)存在環(huán)時(shí)表示存在一條有向路徑并且第一個(gè)節(jié)點(diǎn)和最后一個(gè)節(jié)點(diǎn)是重合的,亦即 i→j…k→i,則表明全局事務(wù)i與自己產(chǎn)生了間接沖突形成了一個(gè)資源等待環(huán),因此就產(chǎn)生死鎖。

(充分性)當(dāng)全局事務(wù)間產(chǎn)生死鎖,則謂詞沖突圖中至少存在一個(gè)有向環(huán)。當(dāng)全局事務(wù)發(fā)生死鎖時(shí),至少存在兩個(gè)或以上的事務(wù)間彼此等待對(duì)方所持有的某些資源,分兩種情況討論:當(dāng)兩個(gè)全局事務(wù)i和j間產(chǎn)生死鎖時(shí),在謂詞沖突圖中既存在i→j的有向邊也存在j→i的有向邊表示,因此在圖中形成了有向環(huán);當(dāng)兩個(gè)以上的全局事務(wù)間產(chǎn)生死鎖時(shí),例如全局事務(wù)i與k之間產(chǎn)生間接沖突時(shí),表明k間接等待i釋放某些資源,則在謂詞沖突圖中存在i→j…→k的有向邊,另由于i也在等待k所持有的某些資源,則在圖中存在k→i,因此綜合可得i→j…→k→i,圖中存在一條有向環(huán)。證畢。

全局事務(wù)在謂詞沖突圖中形成的環(huán)可分為兩類:兩個(gè)全局事務(wù)由直接沖突形成的環(huán)和兩個(gè)以上全局事務(wù)由間接沖突形成的環(huán)。對(duì)于一個(gè)全局事務(wù)只在一個(gè)站點(diǎn)上而另一全局事務(wù)卻是跨站點(diǎn)執(zhí)行情況,即如圖2所示。

在圖2所示的情況下兩個(gè)全局事務(wù)不具備成環(huán)條件,它們?cè)谡军c(diǎn)1上產(chǎn)生的沖突可由該站點(diǎn)數(shù)據(jù)庫處理。

兩個(gè)全局事務(wù)由直接沖突產(chǎn)生死鎖條件:(1)至少存在兩對(duì)或以上的直接沖突。(2)必須存在兩個(gè)不同時(shí)序關(guān)系的沖突對(duì),這樣才可能在謂詞沖突圖中形成環(huán)。此外,兩個(gè)全局事務(wù)間產(chǎn)生的沖突環(huán)可分為在同一站點(diǎn)和不在同一站點(diǎn)上兩種情況,如圖3所示。

對(duì)于全局事務(wù)在同一站點(diǎn)上可能形成環(huán)的沖突圖,如圖4左分圖不必由集群系統(tǒng)中的事務(wù)管理器處理,因?yàn)槿质聞?wù)的子事務(wù)都是局部化到一個(gè)站點(diǎn)上執(zhí)行的,而本地站點(diǎn)上的DBMS有相應(yīng)的并發(fā)控制機(jī)制。由于本地站點(diǎn)的自治性而無法知道其他站點(diǎn)全局事務(wù)間的關(guān)系,所以事務(wù)管理器需要處理的是在跨站點(diǎn)的全局事務(wù)產(chǎn)生的環(huán),而這種環(huán)可能是兩個(gè)全局事務(wù)由直接沖突產(chǎn)生的如圖4右分圖,也可能是由下面將要提到的間接沖突產(chǎn)生的。對(duì)于兩個(gè)以上的全局事務(wù)由間接沖突產(chǎn)生的環(huán),需要檢測(cè)謂詞沖突圖中的每個(gè)全局事務(wù)G是否通過間接沖突與自己沖突即G→Ο→G,那么在兩個(gè)以上的全局事務(wù)間存在間接死鎖,如圖5所示。圖5對(duì)應(yīng)的間接謂詞沖突如圖6。

集群系統(tǒng)中的事務(wù)管理器只處理跨站點(diǎn)的全局事務(wù)形成的死鎖,當(dāng)在謂詞沖突圖中檢測(cè)到?jīng)_突的全局事務(wù)形成環(huán)(包括本身形成的間接環(huán)如G→…→G和兩個(gè)全局事務(wù)形成的直接環(huán)如G1→G2和G2→G1)時(shí),就需要立即解除死鎖的發(fā)生,這里事務(wù)管理器采取回滾(rollback)最近加入環(huán)的一個(gè)全局事務(wù),保證資源利用的最大化。如果事務(wù)管理器調(diào)度的沖突全局事務(wù)在謂詞沖突圖中沒有形成環(huán)或無沖突時(shí),就可以繼續(xù)發(fā)送到底層集群數(shù)據(jù)庫站點(diǎn)上執(zhí)行。

2 試驗(yàn)分析

集群系統(tǒng)中的事務(wù)管理器所采用的基于謂詞的多粒度沖突檢測(cè)機(jī)制不需要對(duì)底層數(shù)據(jù)庫上的數(shù)據(jù)進(jìn)行上鎖操作,保證了局部數(shù)據(jù)庫站點(diǎn)的自治性,從而減少了系統(tǒng)開銷,提高了全局事務(wù)處理的并行度。謂詞沖突圖也有效防止了全局事務(wù)形成的死鎖,其控制粒度也比事務(wù)等待圖更精確,更靈活。另外,事務(wù)等待圖只適合單站點(diǎn)數(shù)據(jù)庫的死鎖檢測(cè),而謂詞沖突圖在基于數(shù)據(jù)庫集群的多站點(diǎn)間事務(wù)全局死鎖檢測(cè)中性能表現(xiàn)優(yōu)良,兩者之間的性能比較如圖7所示。

圖7中的模擬結(jié)果表明,當(dāng)采用兩種不同的方式檢測(cè)到死鎖時(shí),都采用回滾最近加入圖中的事務(wù)方法來解除死鎖,因此死鎖的效率體現(xiàn)在事務(wù)的回滾率上,事務(wù)間發(fā)生的死鎖越多,回滾率也就越高,事務(wù)間的并發(fā)度越低。由于兩種方式檢測(cè)死鎖的粒度不同從而導(dǎo)致事務(wù)的回滾率也不同,從圖中可以看出事務(wù)等待圖的執(zhí)行效率比謂詞沖突圖低,多次試驗(yàn)表明事務(wù)等待圖的事務(wù)回滾率都在40%以上,而謂詞沖突圖的回滾率較低,由此導(dǎo)致運(yùn)行相同時(shí)間內(nèi),采用謂詞沖突圖成功執(zhí)行和提交的事務(wù)數(shù)量較多。此外,本文在集群系統(tǒng)的事務(wù)管理器中實(shí)現(xiàn)了三級(jí)粒度的并發(fā)控制:站點(diǎn)級(jí)→表級(jí)→謂詞級(jí),并對(duì)比了只到表級(jí)具有兩級(jí)粒度的并發(fā)控制性能。試驗(yàn)結(jié)果對(duì)比可知,表級(jí)并發(fā)控制的粒度相對(duì)于謂詞級(jí)的大,體現(xiàn)在事務(wù)的回滾率上表級(jí)粒度平均在44.11%,而謂詞級(jí)則平均為26.01%。由此可見,在運(yùn)行時(shí)間相同的條件下,后者(謂詞級(jí)粒度)成功執(zhí)行和提交的事務(wù)數(shù)量較多,所以謂詞級(jí)多粒度控制的事務(wù)并發(fā)控制效率比表級(jí)有了較大的提高。因此,基于謂詞級(jí)的多粒度事務(wù)并發(fā)控制方法有效提高了全局事務(wù)執(zhí)行的并行度。

3 結(jié)束語

集群中各局部站點(diǎn)數(shù)據(jù)庫的自治性和局部性只能對(duì)本地站點(diǎn)上的事務(wù)并發(fā)控制,而無法保證并發(fā)全局事務(wù)執(zhí)行的一致性和正確性,無法防止全局事務(wù)間的沖突和死鎖發(fā)生,因此在集群系統(tǒng)的事務(wù)管理器中實(shí)現(xiàn)了全局事務(wù)間沖突檢測(cè)的多級(jí)粒度依次為:站點(diǎn)級(jí)→表級(jí)→謂詞級(jí)。另外,還通過檢測(cè)謂詞沖突圖中是否存在環(huán)的方法來避免沖突的全局事務(wù)可能會(huì)產(chǎn)生的全局死鎖。該并發(fā)控制方法不需具體的上鎖操作使并發(fā)控制粒度達(dá)到謂詞級(jí),不僅減小了死鎖檢測(cè)粒度而且還提高了全局事務(wù)處理的并發(fā)度,同時(shí)也不需要對(duì)局部數(shù)據(jù)庫做任何限制。

[1] THAKKAR S S,SWEIGERM.Performance of anOLTP application on symmetry multiprocessor system[C] .American:IEEE Computer Society,1990,228-238.

[2] NISHIKAWA H,STEENKISE P.A general architecture for load balancing in a distributed-memory environment[C] .American:IEEE Computer Society,1993,47-54.

[3] DU X,ZHANG X.Coordinating parallel processes on networks ofworkstations[J] .Journal of Parallel and Distributed Computing,1997,46(2):125-135.

[4] LEE J L,SCHEAUERMANN P,VINGRALEK R.File assignment in parallelI/O systems withminimal variance of service time[J] .IEEE Transactions on Computers,2000,49(2):127-140.

[5] LITWIN W,NEIMAT M A,SCHNEIDER D A.LH*-a scalable,distributed data structure[J] .T ODS,1996,21(4):480-525.

[6] KEN BARKER,TAMER M OZSU.Concurrent transaction execution in multidatabase systems[C] .American:IEEE Computer Society,1990,282-288.

[7] ZHANG A,ELMAGARMID A K.On global transaction scheduling criteria in multidatabase systems[C] .American:IEEE Compurter Society,1993,117-124.