ѧ
JOURNAL OF SOFTWARE
1999ꡡ109ڡVol.10No.91999



һֲݿĶ̬άݷֲ*

ժҪݿϵͳݿڶദ֮ķֲ.ĿǰѾһЩݿݷֲ.ǣЩЧֶ֧̬ݿ.һֲݿĶ̬άݷֲ.÷ܹЧֶ֧̬ݿķֲжάݷֲŵ.˷ɳʼݷֲʽ̬ݷֲ.ʼֲɸݿļĳʼֲ.̬ݷֲʵֶ̬ݿݷֲĶ̬.۷ʵַʮЧֶܹ֧̬ݿϵĸֲݲ㷨.
ؼʡݿ⣬ݷֲάݷֲ.
ͼšTP311
A Dynamic and Multidimensional Declustering Method for Parallel Databases
LI Jian-zhong
(Department of Computer Science Harbin Institute of Technology Harbin 150080)
AbstractThe performance of parallel database systems is closely related to the declustering methods of databases. In the recent years, many declustering methods have been proposed. But most of them cannot support dynamic databases. A new dynamic and multidimensional declustering method called DCMD(dynamic coordinates module declustering) is proposed in this paper. DCMD not only supports dynamic databases but also has the advantages of multidimensional data declustering. DCMD consists of a component for initially declustering databases and a component for dynamically adjusting data distribution. The first component, which is a random algorithm, is to declustering databases initially among multiple processing nodes. The second component, which is composed by a splitting algorithm, a merging algorithm and two heuristic scheduling algorithms, is to support the dynamic adjusting of the database distribution among multiple processing nodes during running time. Experimental and theoretic results show that DCMD can efficiently support parallel processing of dynamic databases.
Key wordsParallel database, data declustering, multidimensional data declustering.
ݿϵͳݿڶദ֮ķֲ(¼ݷֲ).꣬һЩݷֲ1.3һάݷֲȱ2,3.Щݷֲݿһ(Ϊ)ֵڶֲ֮ݿ.ЩЧ֧ڷǻϾѡνʵĲѯ.Ϊ˽⣬HuaLeeһֻGridļĶάݷֲ4.ַֻƽ⣬ûпǰGrid䵽ַͬܳϵͳĲ.GhadeharizadehDeWittһֳΪMagicĶάݷֲ5.ַ֧־̬ݿ.˵3ֶάֲΪCMD(coordinates module declustering)6.CMDЧֲַ֧״̬Ԥ֪Ķ̬ݿ.Щ⣬һܹЧֶ֧̬ݿĶάݷֲΪDCMD(dynamic coordinates module declustering).DCMDɳʼݷֲͶ̬ݷֲ,ʼֲɸݿļĳʼֺͷֲ;̬ݷֲ̬صݿڶദ֮ķֲ.һάݿļFʼݷֲFȵطֲ.ϵͳڼ䣬̬ݷֲFı仯ʱFķֲ֤Fȷֲڶ.۷ʵ֤DCMDʮЧֶܹ֧̬ݿϵĸֲв㷨.÷ѾʵֵĲйϵݿϵͳȡ˺ܺõЧ.
Diһ򼯺(1id)D1D2...DdӼΪdάݿļdԵݿļ.ΪʧһԣļٶDi=0,1).⣬ٶмϵͳ޹Դ(shared-nothing)ṹ.
1ʼݷֲ
ʼݷֲݻ㷨ݷ㷨.һdάݿļFʼݷֲ,ʹݻ㷨FֳɶСȵĳ壬Ȼʹڶ֮ȷֲ.
1.1ݻ㷨ݷ㷨
niʾFĵiά򱻻ΪniN.niз֮һȷ ֪Fڣ0, 1)dϵķֲѡһn1,n2,...,ndʹn1:n2:...:ndڻӽs1:s2:...:sd,siFڵiάͶӰԪ(ظԪ) ֪FϸݲƵʡCPUʱ䡢I/Oʱͨʱ䣬ɰף3ݸķȷn1,n2,...,nd ٺ͢ڵ㣬n1=n2=...=nd=1.
FĻdʾÿʾһάĶĻ.,pi0=0,pi niN=1.iάΪVi=(pi0,Si0,pi1,Si1,...,pi niN-1,Si niN-1)ʾiά򱻻ΪniNpi0,pi1),pi1,pi2),...,pi niN-1,pi niN)ж1jniN-1Sij=|pi j-1,pij)0,1)d-1F|FڵiάjͶӰԪ(ظԪ).Vik.pVik.SʾVipikSik.ά0niN-1.iάĵkΪIik=lik,hik).ǣFΪniN dά.һdάdͬάĵѿ˻ l1k1,h1k1)l2k2,h2k2)...ldkd,hdkd)0kjnjN-11jd.궨Ϊ(k1,k2,...,kd).Ժڲ£Ǽ򵥵ʹáFĳ塱ʾFĽʹóʾ.
 ʼݷֲĿʹFN֮ȷֲ.Ϊˣȸһ㷨PartitionʹFΪСȵĶ.Ϊ㣬dN.㷨ƹ㵽d>N.㷨Partition.
㷨. Partition
룺Fdάݿļ洢ڴ0;n1,...,nd:ֲs.
 V1,V2,...,Vd洢ڴ0. /* 㻮Vik.pVik.SɺDA㷨 */
(1) 0ִ(2)(5).
(2) FOR i=1 TO d DO samplei:=FгȡСΪsniN
(3) FOR i=1 TO d DO sampleiڵiάϵͶӰ(ظԪ)Proj_samplei͵i
(4) FOR i=1 TO d DO (е)
(5) iProj_sampleiS:=|Proj_samplei|/(niN);
(6) FOR k=1 TO niN-1 DO /* iȷֵ㣬0Vik.pֵ */
(7) Vik.p:=sampleikS;Vik.p0
(8) 0Vik.pֵΪdVik.pֵ/* (7)(8)ִ */
ͨϸ(ƪʡ˷)Partition㷨Ĳд̶дʱO(sniN)CPUʱO(dsn0N+sn0Nlog2(sn0N)),ͨʱO(niN),.
ݷ㷨ڴPartition㷨Fĳ弯,FĻеVij.S.ʹģCMD(X1,X2,...,Xd)=(X1+X2+...+Xd) mod Nڴ֮Fĳ壬Ϊ(X1,X2,...,Xd)ĳ屻䵽CMD(X1,X2,...,Xd)NıΪ0,1,...,N-1.ݷ㷨DA(data allocation).
㷨. DA
룺 Fdάļ洢ڴ0; V1,...,VdFĻ洢ڴ0.
(1) 0ִ(2)(6).
(2) FOR FÿԪT DO;
(3) FVij.pֵ(1id,1jniN-1)T(X1...,Xd)
(4) k:=CMD(X1,...,Xd);
(5) ԪT͵k;
(6) FOR 1id DO ViXi.S:=ViXi.S+1
(7) FOR i=0 TO N-1 DO (е) iܲ洢0FԪ.
ͨϸ(ƪʡϸ)DA㷨Ĳд̶дʱO(B),CPUʱO(TniN)ͨʱO(T),BʾFĴ̿TʾFļ¼.
1.2ʼݷֲ
۳ʼݷֲ.ƪʡжʵ֤.
1. dάݿļFPartition㷨Ϊk壬iĴСΪci.ΪPartition㷨F.˵jڦЦ1ҽӽ1.
1. dάݿļFPartition㷨Ϊk壬iĴСΪci.i(1ik)j(1jk).
1˵Partition㷨Fʱ,ҽFĳһ.ҪPartition㷨ĸʵϽ磬ֻ迼㷨ĸʵϽ(¼ʵϽ).ʵϽȷPartition㷨ĴС.Partition㷨dάݿļʵϽɻd-1άݿļʵϽȷ.ΪʧһԣĽǻֶάݿļʵϽ.X={x1,x2,...,xm}һmԪһάݿļBX(s,,k,m)ʾʹôСΪksFΪkһάʱһԪĸʵϽ.
2. 
1. XY={(x1,y1),(x2,y2),...,(xm,ym)}ǶάݿļBXY(s,,v,h,m)ʾPartition㷨FΪhvʱһάеԪĸʵϽ,

1BX(s,,k,m)Partition㷨ֶάݿļʱʵϽ.һأPartition㷨dάݿļʱʵϽ仮d-1άݿļʱʵϽ.Ȼ=1ʱBX(s,,k,m)=BXY(s,,v,h,m)=1ʹݿļʱش.ǣ2Ͷ1֪Partition㷨ʵϽС.
2. dάݿļFR1R2Ϊڳ壬i(1id)ʹR1=(X1,...,Xi,...,Xd)R2(X1,...,Xi+1,...,Xd).
3. һݷֲ㷨ƽģÿͬĳ,ڳڲͬĴ.
3. ʹDA㷨Nֲ֮dάݿļFĳ壬Fڳ嶼ڲͬĴ.
4. dάļFڵiάϵj+1ڳ嶨ΪR(i,k,j+1,(x1,...,xi-1,xi+1,...,xd)){Rk,Rk+1,...,Rk+j}Rk+m(x1,...,xi-1,k+m,xi+1,...,xd)Fdά壬0mj1id0kniN-1-j.
4. AR(ikLN(X1,...,Xi-1,Xi+1,...,Xd))dάݿļFڳ弯ϣki붨4еkiͬL.ʹDA㷨Nֲ֮Fĳ壬ÿҽLAеĳ.
2. DA㷨ƽ.
1. DCMDĳʼֲһֶ̬άֲ.
2. DCMDļά϶ǲģάiIikIimǵiά,k<mIik0,1)d-1еÿԪڵiάϵֵСIim0,1)d-1еÿԪĶӦֵ.
±ߵĶ̬ݷֲԱ֤ݿʼվȵطֲڶ֮䣬212˵DCMDЧ֧άϾѡνʵѡѯӡѡͶӰȹϵ.4˵һά漰kN(k)ѯQ˵DCMDŻģÿ϶ȡͬĳ.
2̬ݷֲ
ʼݷֲܹFȵطֲN.ǣݸ²ִУFڸ֮ķֲܳƫб(ƫб)ϵͳ.£ҪFڸ֮ķֲ.ʼݷֲ·ֲF.ǣFܴ󣬷óʼݷֲĴҲ൱.ʹֲС̬ݷֲĴۣ ݷֲĸЧݷѺݺϲ㷨ʹóʼݷֲ·ֲF ڱ֤ϵͳܲǰ£СݷֲĴ.۲ݷѺͺϲ㷨Ȼ̬ݵʽ㷨.
2.1з㷨
㷨ĿǼϸռ0, 1)dܶȴĻ֣ѸFݾȵطֲN.㷨3ɣ ѡҪӻֵάƷά ڷάѡ䣬Ʒ䣻 ѡķ仮ΪN+1䣬ڴ·ֲµõĳ.ѷ仮ΪN+1䣬ԼؽʹϢ.
5. ļFiά伶ƫбǣMiǵiά,SikǵiάĻеVik.S=|Iik0, 1)d-1F|.
άѡÿάǰĻÿά伶ƫб.i,άȷΪiά.ھжͬ伶ƫбȵ£ѡСάΪά.iάѱѡΪά.ڵiάѡĲԺܼ򵥣ֻѡSikֵIikΪ伴.
dάݿļF,{V1,...,Vd}sͷӦ>0һ{V1,...,Vd}洢ڴ0ϣ㷨Split.
(1) FOR i=1 TO d DO/* 0άƫб */
(2) ;/* Miǵiάǰ */
(3) IF  THEN άΪiELSE 㷨;/*0ȷά*/
(4) ȷVik.ķk;/* 0ȷ */
(5) NеشFIik0,1)d-1ȡs(N+1)ʹ0ϵsample;
(6) 0iάֵsample;
(7) 0ViVikݷNλ; /* ѷάĵkΪN+1NΪ */
(8) FOR j=1 TO N DO
(9) Vik+j.p:=sampleijs; /* 䱻ΪN+1䣬ֵ뻮 */
(10) FOR j=0 TO N-1 DO /* ׼ڴ֮·ֲiάĵk */
(11) 0Rj:={(x1,...,xi-1,k,xi+1,...,xd)|(k+Xm) mod N=j,0xmMm-1}䵽j/* Mmǵmάǰ */
(12) FOR j=0 TO N-1 DO (е) /* ڴ֮·ֲiάĵk */
(13) FOR ÿ(x1,...,k,...,xd)Rj DO
(14) FOR k+1yk+N-1 DO
(15) j(Viy.p,Viy+1.p)(Vmxm.p,Vmxm+1.pF(y+Xj)mod N;
(16) Viy.SĲֵ͵00ۺϼViy.Sֵ.
ͼ1һά̬ݵ.ͼ1(a)ʼֲģʽN=3,n1=n2=1.㷨ѡ1άΪά1άĵ1Ϊ.ͼ1(b)㷨ִн.ͼгڵֱʾ÷ڵĴ.

ͼ1
Split㷨ݴ.ڳйصĳ⣬겻Split㷨Ӱ죬ݷֲڼ䲻ҪıЩڵĴ.Split㷨һҪص.⣬IikΪN+1Ժõĵ1»ǵk䣬ԼΪIikһΪIik+N.ݷֲУIikIik+NйصFĳڵĴҲҪı.ǣµ.
5. IikǷ.Split㷨贫䦤FԪ飬Ц=|Iik0,1)d-1F|.
ͨϸ(ƪʡ˷)Split㷨Ĳд̶дʱΪ,CPUʱΪͨʱΪ.
2.2кϲ㷨
ϲ㷨ĿǰFһʵάϡN+1ϲΪ1.ϲ㷨3ɣ ѡҪкϲά(ƺϲά) ںϲάѡN+1(ƺϲ) ϲN+1ϲΪһ䣬ڴ·ֲɺϲõĳ.һκϲN+1Լؼݴ.
6. iά伶ݸƫбǣMiǵiάSikFڵiάĵkIikϵͶӰ(ظԪس)Ԫ|Iik0,1)d-1F|.
ϲάѡÿάǰĻÿά伶ݸƫб.һi㣬ϲάȷΪiά.ͬ伶ݸƫбȣѡ໮άΪϲά.
iάѡΪϲά.ڵiάѡN+1ϲĲǣFN+1ϲͶӰ(ظԪ)ԪܺӦӽ.NI(i,k)ʾiάϴkʼN+1.NI(i,k)ĴСΪ|NI(i,k)|=Vij.S.|NI(i,k)|ľֵΪNI(i,k)ֵ.ѡֵСNI(i,k)Ϊϲ䣬NI(i,j)NI(i,j)ȷΪϲ.

dάݿļF洢ڴ0ϵĻ{V1,...,Vd}ͺϲӦ<0ϲ㷨Merge.
(1) 0ִе(2)(9).
(2) FOR 1id DO/* άĸƫб */
(3) ;
(4) IF  THEN ϲάΪi; ELSE㷨; /* ȷϲά */
(5) FOR k=0 TO Mi-N-1 DO /* ѡϲֵ */
(6) ;
(7) άiȷĺϲNI(i,j) /* ȷϲ */
(8) FOR k=0 TO N-1 DO/* ׼ڴ֮䴫ͺϲ */
(9) 0Rk:={(x1,...,xi,...,xd)|(xm mod N)=k,j+1xij+N-1,mi,0xmMm-1}͵k;
/* jΪ(9)ѡĺϲ伯NI(i,j)ĵ1ı */
(10) FOR k=0 TO N-1 DO (е) /* ڴ֮䴫ͺϲ */
(11) FOR ÿ(x1,...,xd)Rk DO
(12) kͳ(x1,...,xd)(j+xm) mod N; /* j(9)еjͬ */
(13) 0޸ĻVij.SVij.;
(14) FOR 1kN DO 0ViɾVij+k.
,NI(i,j)Ǻϲ.56.
6. Merge㷨Ҫڴ䴫FԪǦ.
ͨϸ(ƪʡ˷)Merge㷨Ĳд̶дʱΪ,CPUʱΪͨʱΪ.
2.3ݷֲĵ㷨
ĸݷֲĵ㷨,һǶ̬㷨,һڵ㷨.㷨ͨȽƫбݲĶ⿪ݷֲ㷨ĿǷݷֲĵݷֲ㷨ִдСݷֲĴ.
opһݲFһdάݿļRTU(op)ʾFȵطֲNʱFִopĲִʱ䣬RTS(op)ǵFƫбطֲNʱFִopĲִʱ.
7. FƫбopĶ⿪ECOST(op)=RTS(op)RTU(op).
8. Fһݿļ,op1,op2,...,opmFϵݲfiopiִеƵ.Fƫбֲܶ⿪.
2.3.1 ݷֲĶ̬㷨
̬㷨ÿݿļķֲ״̬ۺϿƫбĶ⿪͵ݷֲĿȷǷҪݷֲҪ,SplitMergeԼʼݷֲݷֲ.SplitMerge㷨ҪСͨ㷨ĵڳʼݷֲ.̬㷨ǶݿĲɾʵ㷨֮.,ǼҪظ㷨Ķ.ĶУIijʾiάϵĵj䣬ûʵΪݷֲ.
㷨. 㷨
: dάݿļF;洢ڴ0ϵFĻ{V1,...,Vd}ԪT(t1,...,td).
(1) ȷT(t1,...,td)Ӧòĳ(x1,...,xd)
(2) ԪT(t1,...,td)볬(x1,...,xd)
(3) FOR 1id DO (е)
(4) Vixi.S:=Vixi.S+1;
(5) TECOSTFOTECOSTF:=TECOSTF+1
(6) WHILE (TECOSTF>)(RTSplit<TECOSTF)(OTECOSTF>TECOSTF) DO
ִSplit㷨; OTECOSTF:=TECOSTF;¼TECOSTF/* RTSplitSplit㷨ִ
ʱ */
(7) IF (TECOSTF>)(RTPD<TECOSTF) THEN ִгʼݷֲ. /* RTPDPartition
DA㷨ִʱ */
㷨. ɾ㷨
룺dάݿļFFĻ{V1,...,Vd},洢ڴ0ɾԪT.
(1) ȷTڳ(x1,...,xd);
(2) CMD(x1,...,xd)ɾԪT;
(3) FOR 1id DO /* 0޸Ļ */
(4) Vixi.S:=Vixi.S1;
(5) TECOSTFOTECOSTF:=TECOSTF+1;
(6) WHILE (TECOSTF>)(RTmerge<TECOSTF)(OTECOSTF>TECOSTF) DO
ִMerge㷨; OTECOSTF:=TECOSTF; ¼TECOSTF /* RTmergeMerge㷨ִ
ʱ */
(7) IF (TECOSTF>)(RTPD<TECOSTF) THEN ִгʼݷֲ. /* RTPDPartition
DA㷨ִʱ */
2.3.2ݷֲڵ㷨
ڵ㷨ҪԤȷһֲСL.LҪݸ²Ƶȷ.ÿLʱҪݷֲһ.ΪˣֻÿLʱһڵ㷨ȷǷҪFݷֲȷһ㷨ݷֲĵ.ڵ㷨.
룺 dάݿļF洢ڴ0ϵFĻ{V1,...,Vd}.
(1) TECOSTF
(2) IF TECOSTF< THEN ;
(3) WHILE (ڿɺϲ)(RTMerge<TECOSTF) DO
ִMerge㷨TECOSTF
(4) WHILE (ڿɷ)(RTSplit<TECOSTF) DO
ִSplit㷨;TECOSTF
(5) IF (TECOSTF>)(RTPD<TECOSTF) THEN ִгʼݷֲ.
3ʵ
һ̫ӵ8̨586΢ͼȺлʵDCMDʵ˶ֻDCMDĲݲ㷨.Join㷨ӡáоĹϵ㷨ĽDCMD3ֲ㷨ܵΪĲHybrid-Hash,Grace-HashSort-Merge㷨ܱȽ.DCMD3ֲ㷨ϸڲμף7.زһԾ5Ԫ飨ÿԪ32ֽڣĹϵȻԹϵִ6㷨.ͼ2Щ㷨ִʱ.ͼDhDsmDnlֱʾDCMD3ֲ㷨HyGrSmֱʾHybrid-HashGrace-HashSort-Merge㷨.ͼ2пԿDCMDĲ㷨Чʸ㷨.ʵDCMDһʮЧĶά̬ݷֲ.

ͼ2
*оõ863߿ƼĿ𡢹ҽܳͺʡܳ.
ͨѶϵˣУ150080,ҵѧѧϵ
߼飺,1950,,ʿʦҪоΪݿϵͳм.
ߵλҵѧѧϵ150080E-mail: jzl@hlju.edu.cn
οף
1.ݿĲѯлƷ.ѧ,1994,5(10):110
(Li Jian-zhong. Parallelization techniques for query processing and data declustering methods. Journal of Software, 1994,5(10):110)
2DeWitt D J et al. GAMMA: a high performance dataflow database machine. In: Wiederhold G ed. Proceedings of the 14th International Conference on Very Large Databases. San Mateo, CA: Morgan Kaufmann Publishers, Inc., 1986. 228240
3Ghandeharizadeh S, DeWitt D J. Hybrid-range partitioning: a new declustering strategy for multiprocessor database machines. In: McLeod D, Sacks-Davis R, Hans S eds. Proceedings of the 16th International Conference on Very Large Databases. San Mateo, CA: Morgan Kaufmann Publishers, Inc., 1990. 480492
4Hua K A, Lee C. An adaptive data placement scheme for parallel database computer systems. In: McLeod D, Sacks-Davis R, Hans S eds. Proceedings of the 16th International Conference on Very Large Databases. San Mateo, CA: Morgan Kaufmann Publishers, Inc., 1990. 493506
5Ghandeharizadeh S et al. A performance analysis of alternative multi-attribute declustering. In: Stonebraker M ed. Proceedings of 1992 ACM SIGMOD International Conference on Management of Data. Baltimore, MD: ACM Press, 1992. 2938
6Li J, Srivastava J, Rotem D. CMD: a multidimensional declustering method for parallel database systems. In: Yuan Li-Yan ed. Proceedings of the 18th International Conference on Very Large Databases. San Mateo, CA: Morgan Kaufmann Publishers, Inc., 1992. 314
7,ޱ.ݿϵĲCMD-Join㷨.ѧ,1998,9(4):256261
(Li Jian-zhong, Du Wei. Parallel CMD-Join algorithms on parallel databases. Journal of Software, 1998,9(4):256261)
ոڣ1997-12-12޸ڣ1999-05-31
