并行數(shù)據(jù)庫(kù)系統(tǒng)

PAGE3并行數(shù)據(jù)庫(kù)系統(tǒng)1并行數(shù)據(jù)庫(kù)概述并行數(shù)據(jù)庫(kù)系統(tǒng)是在并行機(jī)上運(yùn)行的具有并行處理能力的數(shù)據(jù)庫(kù)系統(tǒng)，是數(shù)據(jù)庫(kù)技術(shù)與并行計(jì)算技術(shù)結(jié)合的產(chǎn)物。1.1并行數(shù)據(jù)庫(kù)系統(tǒng)的目標(biāo)：1．高性能。通過(guò)將數(shù)據(jù)庫(kù)在多個(gè)磁盤(pán)上分布存儲(chǔ)，利用多個(gè)處理機(jī)對(duì)磁盤(pán)數(shù)據(jù)進(jìn)行并行處理，解決I/O瓶頸問(wèn)題。通過(guò)開(kāi)發(fā)查詢(xún)間并行性、查詢(xún)內(nèi)并行性以及操作內(nèi)并行性，提高查詢(xún)效率。2．高可用性?？赏ㄟ^(guò)數(shù)據(jù)復(fù)制來(lái)增強(qiáng)數(shù)據(jù)庫(kù)的可用性，當(dāng)一個(gè)磁盤(pán)損壞時(shí)，該盤(pán)上的數(shù)據(jù)在其他磁盤(pán)上的副本仍可供使用。3．可擴(kuò)充性。系統(tǒng)通過(guò)增加處理和存儲(chǔ)能力而平滑地?cái)U(kuò)展性能的能力。線形伸縮比：是指任務(wù)擴(kuò)大N倍、系統(tǒng)處理和存儲(chǔ)能力也擴(kuò)大N倍時(shí)系統(tǒng)性能不變，即：小任務(wù)在小系統(tǒng)上的運(yùn)行時(shí)間與大（N倍）任務(wù)在大系統(tǒng)上的運(yùn)行時(shí)間之比為1。線形加速度比：是指任務(wù)不變、系統(tǒng)處理和存儲(chǔ)能力擴(kuò)大N倍時(shí)系統(tǒng)性能也提高N倍，即：小系統(tǒng)上執(zhí)行一個(gè)任務(wù)的時(shí)間與大（N倍）系統(tǒng)上執(zhí)行同一個(gè)任務(wù)的時(shí)間之比為N。1.2支持并行數(shù)據(jù)庫(kù)的并行結(jié)構(gòu)1.2.1共享內(nèi)存（SM）并行結(jié)構(gòu)處理機(jī)處理機(jī)處理機(jī)處理機(jī)處理機(jī)處理機(jī)…互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)…共享存儲(chǔ)器共享存儲(chǔ)器磁盤(pán)磁盤(pán)磁盤(pán)磁盤(pán)磁盤(pán)磁盤(pán)…圖1.1SM結(jié)構(gòu)并行計(jì)算機(jī)（負(fù)荷比較均衡、成本高、可用性不是很好）1.2.2共享磁盤(pán)（SD）并行結(jié)構(gòu)處理機(jī)處理機(jī)處理機(jī)處理機(jī)處理機(jī)處理機(jī)…存儲(chǔ)器存儲(chǔ)器存儲(chǔ)器存儲(chǔ)器存儲(chǔ)器存儲(chǔ)器…互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)磁盤(pán)磁盤(pán)磁盤(pán)磁盤(pán)磁盤(pán)磁盤(pán)圖1.2SD結(jié)構(gòu)并行計(jì)算機(jī)（成本低、可擴(kuò)充性好、可用性強(qiáng)。實(shí)現(xiàn)起來(lái)比復(fù)雜）1.2.3無(wú)共享資源（SN）并行結(jié)構(gòu)互連網(wǎng)絡(luò)互連網(wǎng)絡(luò)處理機(jī)處理機(jī)處理機(jī)…處理機(jī)處理機(jī)處理機(jī)存儲(chǔ)器存儲(chǔ)器存儲(chǔ)器存儲(chǔ)器存儲(chǔ)器存儲(chǔ)器…磁盤(pán)磁盤(pán)磁盤(pán)磁盤(pán)磁盤(pán)磁盤(pán)…圖1.3SN結(jié)構(gòu)并行計(jì)算機(jī)（成本低、可伸縮性與可用性高。實(shí)現(xiàn)復(fù)雜、節(jié)點(diǎn)負(fù)荷難均衡）GROUPBYDEPTNUMORDERBYDEPTNUM；可以分解為掃描DEPT表和EMP表，對(duì)兩表進(jìn)行結(jié)合，對(duì)結(jié)合結(jié)果排序以及分組和輸出五個(gè)子任務(wù)。前一操作的輸出即是下一操作的輸入。如果后一操作等待前一操作產(chǎn)生一定量的輸出后（而不必等待前一操作執(zhí)行完畢）即可在另一處理機(jī)上開(kāi)始執(zhí)行，這種并行方式稱(chēng)為垂直并行或流水線并行。操作內(nèi)（intra-Operation）并行性操作內(nèi)并行性的粒度最細(xì)，它將同一操作（如掃描操作、合并操作、排序操作等）分解成多個(gè)獨(dú)立的子操作，由不同的處理機(jī)同時(shí)執(zhí)行。事務(wù)（Transation）事務(wù)內(nèi)事務(wù)間查詢(xún)（Query）查詢(xún)內(nèi)查詢(xún)間操作（Operation）操作內(nèi)操作間并行粒度細(xì)粗圖2.1四種并行粒度2.1.1并行化形式水平并行化（獨(dú)立并行化，IndependentParallelism）和垂直并行化（流水線并行化，PipeliningParallelism）OP1OP1OP2OP2(a)水平并行化（b）垂直并行化圖2.2.并行化的兩種形式如果兩個(gè)操作OP1、OP2無(wú)相互依賴(lài)關(guān)系，則稱(chēng)這兩個(gè)操作相互獨(dú)立。水平并行化指的是互相獨(dú)立的多個(gè)操作或者一個(gè)操作內(nèi)互相獨(dú)立的多個(gè)子操作分別由不同的處理機(jī)并行執(zhí)行的形式。如果操作OP2直接依賴(lài)于OP1，并且OP2必須等待OP1處理完所有元組后方可開(kāi)始執(zhí)行，則稱(chēng)OP2以阻塞方式直接依賴(lài)于OP1；如果OP2無(wú)需等待OP1執(zhí)行完畢即可在另一處理機(jī)上開(kāi)始執(zhí)行，則稱(chēng)OP2以流水線方式直接依賴(lài)于OP1。垂直并行化則是指存在流水線方式依賴(lài)關(guān)系的操作分別由不同處理機(jī)并行執(zhí)行的形式。例如，排序操作、掃描操作由不同的處理機(jī)并行執(zhí)行就是水平并行化的實(shí)例。排序排序排序……↓↓↓掃描掃描掃描……↓↓↓例如：掃描操作、排序操作、連接操作、分組操作由不同的處理機(jī)并行執(zhí)行就是垂直并行優(yōu)化的實(shí)例。掃描↓排序↓連接↓分組由于關(guān)系代數(shù)的封閉性和數(shù)據(jù)操作的相對(duì)獨(dú)立性，關(guān)系查詢(xún)具有三種固有并行性，即操作間的流水線并行性、操作間的獨(dú)立并行性以及操作內(nèi)的獨(dú)立并行性，這為關(guān)系代數(shù)的并行化提供了現(xiàn)實(shí)基礎(chǔ)。2.1.2并行操作算法并行數(shù)據(jù)庫(kù)操作算法的研究已經(jīng)成為并行數(shù)據(jù)庫(kù)系統(tǒng)近幾年一個(gè)非常活躍的研究領(lǐng)域。并行操作算法有并行結(jié)合算法、并行掃描算法、并行排序算法等。由于結(jié)合操作是關(guān)系數(shù)據(jù)庫(kù)系統(tǒng)中最耗時(shí)且最常用的操作，對(duì)并行結(jié)合操作的研究最多。提出了基于嵌套循環(huán)的并行結(jié)合算法、基于合并掃描的并行結(jié)合算法、基于HASH的并行結(jié)合算法、基于索引的并行結(jié)合算法等?；谇短籽h(huán)的并行結(jié)合算法（S>>R）輸入：R，S：待結(jié)合的兩個(gè)關(guān)系；A：連接屬性；P：處理機(jī)數(shù)輸出：關(guān)系R和S的結(jié)合結(jié)果（結(jié)合屬性為A）方法：（1）把S均勻地分布到P個(gè)處理機(jī)，設(shè)Si是S在結(jié)點(diǎn)i上的子集合；（2）FORI=1TOpDO（并行地）處理機(jī)i按照結(jié)合屬性值排序SiENDDO；（3）在R所在的處理機(jī)上，對(duì)R按結(jié)合的屬性排序，再以流水線方式向P個(gè)處理機(jī)廣播R的元組；（4）FORi=1TOpDO（流水線方式并行的）處理機(jī)i以流水線方式接收R的元組；對(duì)磁盤(pán)上的S中元組和內(nèi)存中R的元組結(jié)合、輸出；ENDFOR；該算法適合于S的元組數(shù)遠(yuǎn)遠(yuǎn)大于R的元組數(shù)（R元組數(shù)較少）R1S1S1S2RR1S1S1S2RS3R2R2S21R3S3R3S3┇┇RP1SP1SRP1SP1SP圖2.3R與S基于嵌套循環(huán)的并行結(jié)合示意圖圖2.4一次哈希與排序并行結(jié)合圖二、基于排序的并行結(jié)合算法基于排序的并行結(jié)合算法由兩個(gè)階段組成：排序階段和結(jié)合階段。在排序階段，它按照結(jié)合屬性的值排序每個(gè)結(jié)合關(guān)系；在結(jié)合階段，完成兩個(gè)排序關(guān)系的結(jié)合。輸入：R，S：待結(jié)合的兩個(gè)關(guān)系。A：連接屬性P：處理機(jī)數(shù)H：HASH函數(shù)輸出：關(guān)系R和S的結(jié)合結(jié)果（結(jié)合屬性為A）方法：（1）使用HASH函數(shù)在P個(gè)處理結(jié)點(diǎn)間分布R和S的元組，設(shè)Si和Ri是S和R在結(jié)點(diǎn)i上的子集：（2）FORi=1TOpDO（水平并行地），處理機(jī)i排序Ri和SiENDFOR；（3）i=1TOpDO（水平并行地），結(jié)點(diǎn)i完成Ri和Si的結(jié)合輸出R和S的結(jié)合結(jié)果ENDFOR；理論和實(shí)驗(yàn)結(jié)果表明，當(dāng)兩個(gè)結(jié)合關(guān)系的元組數(shù)相差較小時(shí)，該算法的效率高于前一個(gè)算法?；诙蜨ASH的并行連接算法通過(guò)一個(gè)定義在結(jié)合連接屬性上的HASH函數(shù)把兩個(gè)結(jié)合關(guān)系分解為P個(gè)子集合，然后使用P個(gè)處理機(jī)并行地完成結(jié)合操作。輸入：關(guān)系R和S：HASH函數(shù)H1和H2，結(jié)點(diǎn)數(shù)P，子集合數(shù)M。輸出：關(guān)系R和S的連接結(jié)果。使用H1把R劃分為M個(gè)子集合，HASH值為i的元組送入子集合Ri，并存儲(chǔ)到所有可用的磁盤(pán)；使用H1把S劃分為M個(gè)子集合，HASH值為i的元組送入子結(jié)合Si，并存儲(chǔ)到所有可用的磁盤(pán)；FORI=1TOMDO（并行地）使用H2把Ri分布到p個(gè)處理結(jié)點(diǎn)，在每個(gè)結(jié)點(diǎn)的內(nèi)存中建立Ri元組的HASH表；使用H2以流水線方式向p個(gè)處理結(jié)點(diǎn)發(fā)送Si的元組；FORJ=1TOpDO（并行地）結(jié)點(diǎn)j用收到的Si的元組匹配Ri的HASH表，進(jìn)行Si和Ri的結(jié)合；輸出R和S的結(jié)合結(jié)果。算法中的M應(yīng)該充分大，以減少R的子集合對(duì)應(yīng)的HASH表超過(guò)可用內(nèi)存容量的概率。實(shí)驗(yàn)表明，使用并行數(shù)據(jù)操作算法實(shí)現(xiàn)查詢(xún)的并行處理可以充分地發(fā)揮多處理機(jī)的并行性，從而改善關(guān)系運(yùn)算的效率，提高查詢(xún)處理的速度。RSHASH1HASH1R1R2R3…RmS1S2S3…SmHASH2HASH2P1P2P3…PpP1P2P3…PpR1R11R12…R1pS1S11S12…S1pR2R21R22…R2pS2S21S22…S2p┇┇RiRi1Ri2…RipSiSi1Si2…Sip┇┇RmRm1Rm2…RmpSmSm1Sm2…Smp在站點(diǎn)P1，對(duì)R的每一個(gè)M足夠大，以保證每條鏈不太長(zhǎng)。子集R均有一個(gè)鍵值表值。2.1.并行數(shù)據(jù)庫(kù)查詢(xún)優(yōu)化問(wèn)題與順序數(shù)據(jù)庫(kù)查詢(xún)問(wèn)題有所不同。在順序數(shù)據(jù)庫(kù)系統(tǒng)中，給定一個(gè)查詢(xún)Q，查詢(xún)優(yōu)化算法只需找到Q的一個(gè)具有最小工作量的執(zhí)行計(jì)劃。Q的最小工作量的執(zhí)行計(jì)劃可能具有很強(qiáng)的固有順序性，難以并行化，因而不具有最小響應(yīng)時(shí)間，在并行數(shù)據(jù)庫(kù)系統(tǒng)中，查詢(xún)優(yōu)化的目標(biāo)是尋找Q的具有最小響應(yīng)時(shí)間的執(zhí)行計(jì)劃，執(zhí)行計(jì)劃的工作量不是第一重要的。于是，在并行數(shù)據(jù)庫(kù)系統(tǒng)中，需要新的查詢(xún)處理算法和新的查詢(xún)優(yōu)化技術(shù)。并行查詢(xún)優(yōu)化面臨的兩大困難：執(zhí)行計(jì)劃搜索空間的龐大。設(shè)SPLAN（Q）是查詢(xún)Q的順序執(zhí)行計(jì)劃空間，P是一個(gè)順序執(zhí)行計(jì)劃，PARALLEL（P）是該計(jì)劃的所有并行化方案，那么查詢(xún)Q的并行執(zhí)行計(jì)劃空間PARALLEL（P）則可以由下述公式來(lái)表示：PPLAN（Q）=∪PARALLEL（P）P∈SPLAN（Q）由此可見(jiàn)，依靠傳