第7章并行數(shù)據(jù)庫

第7章并行數(shù)據(jù)庫并行數(shù)據(jù)庫系統(tǒng)概念硬件體系結(jié)構(gòu)數(shù)據(jù)分片技術(shù)并行性種類并行連接并行排序7.1并行數(shù)據(jù)庫系統(tǒng)概念為什么并行存取數(shù)據(jù)？7.1并行數(shù)據(jù)庫系統(tǒng)概念為什么并行存取數(shù)據(jù)？數(shù)據(jù)密集型(data-intensive)應(yīng)用，如決策支持系統(tǒng)、在線處理分析(OLAP)、數(shù)據(jù)倉庫(datawarehouse)、知識(shí)和數(shù)據(jù)發(fā)現(xiàn)(KDD)等并行數(shù)據(jù)庫系統(tǒng)設(shè)計(jì)的研究問題：并行I/O、并行查詢優(yōu)化、并行性數(shù)據(jù)庫操作等7.1并行數(shù)據(jù)庫系統(tǒng)概念并行數(shù)據(jù)庫系統(tǒng)的評(píng)價(jià)參數(shù)：speedup：對(duì)于某個(gè)固定的計(jì)算任務(wù)，1倍計(jì)算資源系統(tǒng)所完成的時(shí)間與n倍計(jì)算資源所完成時(shí)間之比；理想的speedup曲線為線性加速scaleup：1倍計(jì)算任務(wù)在1倍計(jì)算資源系統(tǒng)所完成的時(shí)間與n倍計(jì)算任務(wù)在n倍計(jì)算資源系統(tǒng)所完成時(shí)間之比，理想的scaleup曲線為y=17.1并行數(shù)據(jù)庫系統(tǒng)概念影響并行數(shù)據(jù)庫系統(tǒng)性能的三個(gè)因素啟動(dòng)代價(jià)(startup)：?jiǎn)?dòng)一個(gè)并行操作的代價(jià)干擾(interference)：共享資源之間的相互干擾傾斜(skew)：一個(gè)操作或一個(gè)查詢可以被分解為若干個(gè)可并行執(zhí)行的子操作或子查詢，執(zhí)行時(shí)間最長(zhǎng)的子操作或子查詢的響應(yīng)時(shí)間決定該并行操作的響應(yīng)時(shí)間7.1并行數(shù)據(jù)庫系統(tǒng)概念實(shí)現(xiàn)并行的2種基本技術(shù)管道一個(gè)操作的輸出是另一個(gè)操作的輸入分片多臺(tái)機(jī)器在不同的數(shù)據(jù)分片上做相同的事情7.2硬件體系結(jié)構(gòu)共享內(nèi)存(SM,SE)在SM體系結(jié)構(gòu)中，處理機(jī)和磁盤可以通過一個(gè)總線或互聯(lián)網(wǎng)絡(luò)來訪問一個(gè)公共的內(nèi)存，即所有資源均是共享的處理機(jī)間通訊可通過共享內(nèi)存來進(jìn)行,比通過通訊機(jī)制進(jìn)行通訊要快得多32或64節(jié)點(diǎn)以內(nèi)并行算法speedup很好超過32或64節(jié)點(diǎn)以后scaleup很壞，因?yàn)樗匈Y源均是共享的，總線或互聯(lián)網(wǎng)絡(luò)就變成了一個(gè)瓶頸。超過這個(gè)點(diǎn)后增加處理機(jī)節(jié)點(diǎn)個(gè)數(shù)沒有任何用處，因?yàn)樘幚頇C(jī)不得不花更多的時(shí)間來等待總線并訪問內(nèi)存和磁盤PPPPPM7.2硬件體系結(jié)構(gòu)共享磁盤(SD)所有處理機(jī)可以直接通過總線或互聯(lián)網(wǎng)絡(luò)訪問磁盤,但每個(gè)處理機(jī)有自己的私有內(nèi)存由于每個(gè)處理機(jī)有自己的內(nèi)存，存儲(chǔ)器的總線不會(huì)成為瓶頸提供一定的容錯(cuò)能力，若某處理機(jī)或它的內(nèi)存出問題了，其它處理機(jī)可以接管它的任務(wù)，因?yàn)閿?shù)據(jù)庫駐留在所有處理機(jī)可以直接訪問的磁盤上。磁盤子系統(tǒng)本身的容錯(cuò)問題可以通過使用RAID來解決盡管不存在內(nèi)存共享，共享磁盤仍然成為SD系統(tǒng)可擴(kuò)展性問題的障礙，共享的磁盤子系統(tǒng)的互聯(lián)成為性能可擴(kuò)展的瓶頸。SD不能解決可擴(kuò)展性問題，僅僅緩解了SM系統(tǒng)的可擴(kuò)展性問題PMPMPMPMPM7.2硬件體系結(jié)構(gòu)無共享資源體系結(jié)構(gòu)(SN)每個(gè)節(jié)點(diǎn)由一個(gè)處理機(jī)、內(nèi)存和一個(gè)或多個(gè)磁盤構(gòu)成處理機(jī)之間通過高速互聯(lián)網(wǎng)進(jìn)行通訊SN結(jié)構(gòu)克服了SD結(jié)構(gòu)必須通過一個(gè)總線進(jìn)行I/O操作的缺點(diǎn)，僅僅是對(duì)非局部磁盤的存取才通過網(wǎng)絡(luò)來進(jìn)行。SN體系結(jié)構(gòu)具有很好的可擴(kuò)展性，有的甚至可以擴(kuò)展到成千上萬個(gè)節(jié)點(diǎn)主要缺點(diǎn)是通訊代價(jià)和非局部磁盤的存取代價(jià)比較昂貴PMPMPMPMPM7.2硬件體系結(jié)構(gòu)層次體系結(jié)構(gòu)(COW,NOW)結(jié)合了SN、SM、SD體系結(jié)構(gòu)的特點(diǎn)，在高層看是一個(gè)SN體系結(jié)構(gòu)，但每個(gè)節(jié)點(diǎn)是由一個(gè)SM體系結(jié)構(gòu)所構(gòu)成的。當(dāng)然每個(gè)節(jié)點(diǎn)也可是一個(gè)SD體系結(jié)構(gòu)在這種體系結(jié)構(gòu)中代碼的編寫是非常復(fù)雜的，降低編程復(fù)雜度的一種很好的辦法是分布式虛擬存儲(chǔ)器體系結(jié)構(gòu)PMPPPPPMPPPPPMPPPPUser節(jié)點(diǎn)AClientServer磁盤映射內(nèi)存映射共享虛擬堆客戶共享虛擬空間服務(wù)器共享虛擬空間頁面讀/寫User節(jié)點(diǎn)BClientServer磁盤映射內(nèi)存映射共享虛擬堆客戶共享虛擬空間服務(wù)器共享虛擬空間頁面讀/寫DSVM映射7.3數(shù)據(jù)分片技術(shù)Round-robin：對(duì)于關(guān)系r中的第i個(gè)元組分配到第(imodn)個(gè)磁盤上。該方法保證了每個(gè)磁盤上具有相同數(shù)目的元組數(shù)。哈希分片：關(guān)系r中的一個(gè)或多個(gè)屬性作為分片屬性，對(duì)于r中的元組rt，該元組被分配到第h(rt)(0..n-1)個(gè)磁盤上。范圍分片：對(duì)于關(guān)系r，分片屬性為A，則在A上可以定義一個(gè)分片向量：[v0,v1,…,vn-2]。分片過程如下：若t[A]<v0，則t被分配給第0個(gè)磁盤；若t[A]vn-2，則t分配給第n-1個(gè)磁盤；若vit[A]<vi+1，則t被分配給第i+1個(gè)磁盤。分片技術(shù)對(duì)比三種操作掃描整個(gè)關(guān)系點(diǎn)查詢：如employee-name=”Campbell”范圍查詢：10000<salary<20000Round-robin：對(duì)于掃描操作非常好，但對(duì)于點(diǎn)操作和范圍操作卻不是很好哈希分片：對(duì)于基于分片屬性的點(diǎn)操作是最好的。如果哈希函數(shù)能夠保持隨機(jī)性和均勻性，則哈希分片也能很好的處理掃描操作。但哈希分片方法不能很好地支持范圍查詢和基于非分片屬性的點(diǎn)查詢。分片技術(shù)對(duì)比范圍分片：能夠很好地支持基于分片屬性的點(diǎn)查詢和范圍查詢。但這種支持既具有優(yōu)點(diǎn)，也具有缺點(diǎn)。優(yōu)點(diǎn)是：當(dāng)一個(gè)范圍查詢只涉及到某幾個(gè)磁盤時(shí)，該查詢不必向其他磁盤發(fā)出查詢請(qǐng)求，這樣其他的磁盤可以響應(yīng)其他的查詢請(qǐng)求，提高了系統(tǒng)的吞吐量；缺點(diǎn)是：當(dāng)在某幾個(gè)磁盤上要存取大量的元組時(shí)，I/O成為瓶頸，造成執(zhí)行傾斜，從而使得該查詢的響應(yīng)時(shí)間過長(zhǎng)。除了round-robin分片處理以外，其他兩種分片方法均可能造成傾斜問題。傾斜的分類：屬性值傾斜：屬性值傾斜指的是很多元組在分片屬性值上具有相同的元組，這必將導(dǎo)致傾斜。屬性值分片將會(huì)導(dǎo)致分片傾斜無論采用范圍分片還是哈希分片。分片傾斜：分片傾斜指的是在每個(gè)片段中的元組個(gè)數(shù)不同，即使不存在屬性值傾斜問題也可能出現(xiàn)分片傾斜問題。7.4并行性種類操作內(nèi)并行性多臺(tái)機(jī)器同時(shí)執(zhí)行某個(gè)操作(分片技術(shù))操作間并行性多個(gè)操作并發(fā)地運(yùn)行在多臺(tái)機(jī)器上(管道技術(shù))查詢間并行性不同的查詢運(yùn)行在不同的機(jī)器上主要討論操作內(nèi)并行性7.5并行連接7.5.1分片連接7.5.2非對(duì)稱分片復(fù)制連接7.5.3對(duì)稱式分片復(fù)制連接7.5.4并行哈希連接7.5.5并行嵌套循環(huán)連接7.5.1分片連接通過范圍分片或哈希分片方法將r分片為n個(gè)片段，r->r0,r1,…,rn-1通過范圍分片或哈希分片方法將s分片為n個(gè)片段，s->s0,s1,…,sn-1在處理機(jī)pi上做子連接操作：risi僅適合于等連接操作r0r1r2s0s1s2p0p1p2rs7.5.2非對(duì)稱分片復(fù)制連接可使用任何分片方法(包括round-robin)來將r分為n片將關(guān)系s復(fù)制到所有的處理機(jī)上處理機(jī)pi執(zhí)行子連接操作ri

s適合任何形式的連接操作r0r1r2sp0p1p2r7.5.3對(duì)稱式分片復(fù)制連接將關(guān)系r分片為m1片：r->r0,r1,…,rm1-1將關(guān)系s分片為m2片：s->s0,s1,…,sm2-1n=m1*m2將分片ri發(fā)送到處理機(jī)Pi,0,Pi,1,…,Pi,m2-1將分片si發(fā)送到處理機(jī)P0,i,P1,i,…,Pm1-1,i處理機(jī)pi,j做子連接ri

sj適合任何形式的連接操作r0r1r2p0,0p1,0p2,0rs0s1s2sp0,1p1,1p2,1p0,2p1,2p2,27.5.4并行哈希連接考慮重分片r：在每個(gè)處理機(jī)pi上，對(duì)于磁盤Di上r的每個(gè)元組tr,計(jì)算h1(tr[JoinAttrs])=j，則將該元組發(fā)送到處理機(jī)Pj，并形成關(guān)系r在處理機(jī)Pj上的再分片rj。當(dāng)所有的分片操作完成后在每個(gè)處理機(jī)上就能得到一個(gè)r的再分片。用相同的哈希函數(shù)再分片關(guān)系s。重分片s：與(1)相同在每個(gè)處理機(jī)pi上哈希計(jì)算子連接ri

si7.5.5并行嵌套循環(huán)連接考慮關(guān)系s<r,對(duì)r進(jìn)行分片存儲(chǔ)，r的每一個(gè)分區(qū)上存在連接屬性上的一個(gè)索引。采用非對(duì)稱的分片-復(fù)制方法，將關(guān)系s進(jìn)行復(fù)制，利用r現(xiàn)有的分區(qū)。存放關(guān)系s的分區(qū)的每一處理器Pi對(duì)存放在Di上的關(guān)系s中的元組進(jìn)行讀取，并將其復(fù)制到其余的每一個(gè)處理器Pi中，最后，關(guān)系s被復(fù)制到存放關(guān)系r的元組的所有站點(diǎn)中。在每個(gè)處理機(jī)pi上對(duì)關(guān)系r的第i個(gè)分區(qū)做索引嵌套循環(huán)連接ri

si。通過將索引嵌套循環(huán)連接與對(duì)關(guān)系s的元組的劃分并行操作，減少將s元組寫回磁盤再讀取的代價(jià)。7.6并行排序假定被排序的關(guān)系被分放在n個(gè)磁盤上，可以采用兩種方法來進(jìn)行排序并行范圍分片排序并行外部排序7.6.1并行范圍分片排序假定用m個(gè)處理機(jī)來排序具有n個(gè)分片的關(guān)系，n>m使用一個(gè)范圍分片策略來重分片被排序的關(guān)系，使得在范圍i上的的元組被發(fā)送給處理機(jī)Pi，并將新的分片臨時(shí)保存在磁盤Di上。該步是并行執(zhí)行的，有I/O開銷和網(wǎng)絡(luò)通訊開銷處理機(jī)Pi排序存儲(chǔ)在磁盤Di上的分片Ri，合并操作：由于使用的是范圍分片，合并操作相當(dāng)簡(jiǎn)單，若i<j，則處理機(jī)Pi上的元組關(guān)鍵字值小于處理機(jī)Pj上的元組關(guān)鍵字值7.6.2并行外部排序每個(gè)處理機(jī)pi外部排序存儲(chǔ)在磁盤Di上的數(shù)據(jù)，該步是并行執(zhí)行的合并每個(gè)處理機(jī)上的局部排序結(jié)果：每個(gè)處理機(jī)上排序后的分片進(jìn)一步被范圍分片到m個(gè)處理機(jī)上，這些元組以排序序來發(fā)送。每個(gè)處理機(jī)當(dāng)收到來自其他處理機(jī)上的元組時(shí)進(jìn)行合并操作某個(gè)處理機(jī)最后合并所有處理機(jī)上的合并結(jié)果，這個(gè)合并非常簡(jiǎn)單7.7.1并行聚合操作集中式二階段并行聚合算法層次合并的并行聚合算法兩階段并行聚合算法再分布并行聚合算法7.7.1集中式二階段并行聚合算法局部聚合階段：它是在各個(gè)節(jié)點(diǎn)上進(jìn)行一個(gè)集中式聚合操作集中合并階段：各個(gè)局部聚合結(jié)果都發(fā)送到一個(gè)中央節(jié)點(diǎn)（稱為協(xié)調(diào)者）進(jìn)行最后的全局合并并生成最終的全局聚合結(jié)果優(yōu)點(diǎn)：當(dāng)GroupBy子句的選擇率比較小的時(shí)候，由于各個(gè)局部聚合結(jié)果的聚合組數(shù)較少，這樣就減少了算法的通信開銷，從而提高了算法的性能。但是隨著GroupBy子句選擇率的不斷增加，通信開銷也將隨之增加，而且由于局部聚合的聚合組數(shù)的增大，中央?yún)f(xié)調(diào)者的工作負(fù)載也就越來越重，并最終可能成為并行算法的性能瓶頸7.7.2層次合并的并行聚合算法局部聚合階段：與集中式二階段并行聚合算法相類似層次合并階段：與集中式二階段并行聚合算法不同，不是將各個(gè)節(jié)點(diǎn)的聚合結(jié)果發(fā)送到一個(gè)中央?yún)f(xié)調(diào)者，而是分層次并行地進(jìn)行部分聚合結(jié)果的合并，并得到中間合并結(jié)果，這些中間結(jié)果可能被進(jìn)一步并行地合并為新的中間結(jié)果或者合并為一個(gè)全局聚合結(jié)果。然該算法在性能上作了改進(jìn)，減輕了合并節(jié)點(diǎn)的工作負(fù)擔(dān)，但它并不能最終解決性能瓶頸問題，因?yàn)楫?dāng)GroupBy子句的選擇率足夠大時(shí)，層次合并階段亦會(huì)成為該算法的性能瓶頸，只是該算法性能瓶頸的出現(xiàn)比集中式二階段并行聚合算法來得晚些7.7.3兩階段并行聚合算法局部聚合階段：在這個(gè)階段各個(gè)局部節(jié)點(diǎn)在各自的節(jié)點(diǎn)上進(jìn)行集中式的聚合操作，并將局部聚合結(jié)果通過選擇一個(gè)哈希函數(shù)作用到GroupBy屬性上將局部聚合結(jié)果散列到各個(gè)節(jié)點(diǎn)上全局聚合階段：這個(gè)階段主要是合并被散列到該節(jié)點(diǎn)上的局部聚合結(jié)果。由于對(duì)局部聚合結(jié)果進(jìn)行了重新散列，所以全局聚合階段的聚合結(jié)果不需要進(jìn)行合并，這樣全局聚合階段是在各個(gè)節(jié)點(diǎn)上并行進(jìn)行的，避免了前兩種算法的性能瓶頸問題7.7.4再分布并行聚合算法再分布并行聚合算法的基本思想是：先將r的每個(gè)子分片通過選擇一個(gè)哈希函數(shù)并作用到GroupBy屬性值上，將這些元組再分布到不同的節(jié)點(diǎn)上，在每個(gè)節(jié)點(diǎn)上有一個(gè)聚合操作，該操作接收再分布操作符發(fā)送過來的元組并進(jìn)行聚合操作。由于對(duì)來自于聚合操作組的輸入元組直接進(jìn)行了散列，所以各個(gè)節(jié)點(diǎn)的聚合操作結(jié)果不需要進(jìn)行合并練習(xí)指出對(duì)下面每種情況，哪種并行形式（查詢并行、操作間并行、操作內(nèi)并行）可能最重要？提高一個(gè)執(zhí)行許多小查詢的系統(tǒng)的吞吐量