第22章并行與分布式數(shù)據(jù)庫

第22章并行與分布式數(shù)據(jù)庫22.1簡介集中式數(shù)據(jù)庫管理系統(tǒng)——數(shù)據(jù)在獨立的站點進行管理，順序地進行事物處理。并行數(shù)據(jù)庫系統(tǒng)——通過并行實現(xiàn)各種數(shù)據(jù)操作，如數(shù)據(jù)載入、索引建立、數(shù)據(jù)查詢等，可以提高系統(tǒng)的性能。分布式數(shù)據(jù)庫系統(tǒng)——數(shù)據(jù)分布存儲于若干場地，并且每個場地由獨立于其它場地的DBMS進行數(shù)據(jù)管理。并行與分布技術(shù)特點：增強的可用性：當(dāng)存儲某個關(guān)系的場地系統(tǒng)崩潰時，可繼續(xù)使用存儲在別的場地的復(fù)本。數(shù)據(jù)的分布訪問：企業(yè)數(shù)據(jù)可以分布于若干城市，分析時可能需要訪問不同場地的數(shù)據(jù)，但通常在訪問模式中得到數(shù)據(jù)存儲的局部性（如銀行經(jīng)理通常是查詢本地支行的顧客賬戶），這種局部性可用來分布數(shù)據(jù)。分布數(shù)據(jù)的分析：企業(yè)越來越需要分析所有可用的數(shù)據(jù)，即使這些數(shù)據(jù)存儲在不同場地和不同的數(shù)據(jù)庫系統(tǒng)中。22.2并行數(shù)據(jù)庫系統(tǒng)的可用結(jié)構(gòu)（一）實現(xiàn)并行DBMS的三種硬件結(jié)構(gòu)：（1）共享內(nèi)存系統(tǒng)（2）共享磁盤系統(tǒng)（3）無共享資源系統(tǒng)（一）實現(xiàn)并行DBMS的三種硬件結(jié)構(gòu)：連接網(wǎng)絡(luò)全局共享內(nèi)存DDD（1）共享內(nèi)存系統(tǒng)：多個cpu通過連接網(wǎng)絡(luò)進行通信，并能訪問公共的主存。

MMM連接網(wǎng)絡(luò)DDD（2）共享磁盤系統(tǒng)：每個cpu擁有自己的私有內(nèi)存，并通過連接網(wǎng)絡(luò)直接訪問所有磁盤。沖突問題——隨著cpu數(shù)目的增加，由于內(nèi)存訪問的沖突增加、網(wǎng)絡(luò)通信帶寬有限，cpu性能下降。（一）實現(xiàn)并行DBMS的三種硬件結(jié)構(gòu)：連接網(wǎng)絡(luò)MMMDDD（3）無共享資源系統(tǒng)：每個cpu擁有自己的內(nèi)存和磁盤空間，并無公共區(qū)域，cpu之間所有通信通過連接網(wǎng)絡(luò)來完成。大型并行數(shù)據(jù)庫系統(tǒng)的最優(yōu)結(jié)構(gòu)(二)加速比和可擴展性每秒處理事物數(shù)cpu數(shù)目線性加速比（理想）亞線性加速比加速比曲線表明對于固定的數(shù)據(jù)庫大小，通過增加cpu數(shù)目，每秒能處理更多的事物。無共享資源的并行結(jié)構(gòu)——具有近似線性加速比（隨cpu數(shù)目增加，各種操作所需時間減少。）(二)加速比和可擴展性每秒處理事物數(shù)cpu數(shù)目數(shù)據(jù)庫大小線性可擴展性亞線性可擴展性每個事物的時間cpu數(shù)目，每秒處理事物數(shù)亞線性線性可擴展性（理想）無共享資源的并行結(jié)構(gòu)——具有線性可擴展性（cpu和磁盤數(shù)目隨著數(shù)據(jù)量的增加而按比例增加時，系統(tǒng)性能保持不變）可擴展曲線表明，通過增加系統(tǒng)資源，系統(tǒng)能處理更大規(guī)模的問題。數(shù)據(jù)庫大小與可擴展性每秒處理事務(wù)數(shù)與可擴展性22.3并行查詢處理多個查詢并行執(zhí)行單個查詢并行執(zhí)行

（1）并行處理多個操作----查詢的執(zhí)行計劃可用關(guān)系代樹表達式樹表示，其中操作都可并行執(zhí)行（2）并行處理單個操作----查詢計劃中的單個操作也能夠并行處理22.3并行查詢處理流水線并行技術(shù)——并行處理多個操作。當(dāng)一個操作需要另一個操作的輸出數(shù)據(jù)時，即在產(chǎn)生部分操作輸出數(shù)據(jù)的同時立即進行隨后的操作。阻塞操作——如果一個操作必須在得到所有輸入數(shù)據(jù)后才能產(chǎn)生輸出數(shù)據(jù)，該操作稱為阻塞操作。阻塞操作不能用流水線技術(shù)?；跀?shù)據(jù)劃分的并行處理——對查詢計劃的單個操作的并行處理。首先對并行操作所需要的數(shù)據(jù)進行劃分，然后并行地處理每個分片，最后再將結(jié)果合并。無共享資源的并行數(shù)據(jù)庫的查詢處理都使用基于數(shù)據(jù)劃分的并行查詢處理方法。22.3.1數(shù)據(jù)劃分將大數(shù)據(jù)集水平劃分到多個磁盤上，可以通過并行讀寫有效地利用多磁盤的I/O帶寬。將關(guān)系水平劃分方法：（1）輪轉(zhuǎn)劃分法——如果系統(tǒng)有n個cpu，將第i條記錄劃分到第imodn處理器的方法稱為輪轉(zhuǎn)劃分方法。（2）哈希劃分法——使用特定的哈希函數(shù)，作用于選定的屬性，將記錄劃分到不同的處理機。（3）區(qū)域劃分法——首先對記錄進行排序，然后按照排序碼將其劃分成n個區(qū)域，使每個區(qū)域中近似含有相同數(shù)目的記錄，處于第i個區(qū)域的記錄分布于處理機i。22.3.1數(shù)據(jù)劃分優(yōu)勢劣勢：（1）輪轉(zhuǎn)法可有效應(yīng)用于需要訪問整個關(guān)系的查詢處理，當(dāng)需要訪問部分記錄時，哈希法和區(qū)域法更優(yōu)。（2）區(qū)域法可能會導(dǎo)致數(shù)據(jù)偏斜，也就是不同分片含有的記錄數(shù)目差別很大。數(shù)據(jù)偏斜會造成存有大片數(shù)據(jù)分片的處理機的性能瓶頸問題。（3）哈希法優(yōu)點是：即使數(shù)據(jù)隨時間增加或減少，也能保持均勻分布。22.3.2并行化順序數(shù)據(jù)操作處理程序并行DBMS軟件結(jié)構(gòu)能夠?qū)F(xiàn)有的關(guān)系操作順序處理程序快速并行化。該方法的基本思想——使用并行數(shù)據(jù)流技術(shù)數(shù)據(jù)流（來自不同的磁盤或者其它操作的輸出）在需要時進行歸并以產(chǎn)生關(guān)系操作的輸入，并且在必要時進行分裂以便于隨后的并行處理。一個并行查詢處理計劃是關(guān)系操作以及歸并和分裂操作共同組成的數(shù)據(jù)流網(wǎng)絡(luò)。

Split- Merge 實現(xiàn)并行查詢技術(shù)22.4數(shù)據(jù)操作的并行化假設(shè)：（1）無共享資源的并行結(jié)構(gòu)（2）關(guān)系都水平劃分到若干磁盤上分布式DBMS的數(shù)據(jù)存儲水平劃分——每個分片是原始關(guān)系所有數(shù)據(jù)行的子集合垂直劃分——每個分片是原始關(guān)系所有數(shù)據(jù)列的子集合Idnameaddressagephone123…22.4.1掃描A．讀一個關(guān)系R的整個內(nèi)容B．僅讀出R中滿足謂詞的元組定位R中基本元組的方法：a.表掃描

b.索引掃描掃描并行化——如果關(guān)系被劃分到若干磁盤上，可以首先按頁并行讀入，然后歸并得到所需的記錄。2.4.2排序簡單方法：每個cpu先對本地磁盤上的記錄進行排序，然后歸并有序記錄集合，并行程度受歸并階段的影響。2.4.2排序更好方法：a.用區(qū)域劃分法先將關(guān)系的所有記錄重新分布再進行排序。例：employee按屬性salary排序，salary的取值范圍從10~210，處理機數(shù)目2010~20的所有記錄分布于處理機121~30……………2

……

……200~210…………20b.每個cpu使用排序算法對分配給它的記錄排序。每個處理機得到分配給它的所有記錄的有序序列。

c.通過按照區(qū)域劃分的對應(yīng)次序訪問處理機得到完整的有序關(guān)系。難點：如何進行區(qū)域劃分來使得每個處理機分布的記錄數(shù)目近似相等。否則，對具有大量記錄的處理機排序時將產(chǎn)生性能瓶頸，從而限制并行排序的可擴展性。2.4.3連接假設(shè)：對關(guān)系A(chǔ)和B進行劃分時，連接屬性為age，關(guān)系初始分布在若干磁盤上，但不是基于連接屬性分布的。方法：對關(guān)系A(chǔ)和B重新劃分：把連接屬性age的取值分成k個區(qū)域假設(shè)10個處理機，age取值范圍0~100

記錄按照相應(yīng)的age值進行分布

0<=age<10處理機1

10<=age<20處理機2

……

……90<=age<100處理機10缺點：產(chǎn)生由對數(shù)據(jù)偏斜不同分片的記錄數(shù)目差別很大并行連接操作的數(shù)據(jù)流網(wǎng)絡(luò)合并

Ai分離分離分離合并分離合并合并掃描掃描掃描掃描A’B’AB

A”B”A連接連接

Ai∞BiAj∞BjAiAiAiAjAjAjAjBiBiBiBiBjBjBjBjB存儲關(guān)系A(chǔ)與B的處理機處理連接的處理機并行連接操作的數(shù)據(jù)流網(wǎng)絡(luò)（1）掃描A劃分AAi 0<=age<50Aj 50<=age<100

掃描B劃分BBi0<=age<50Bj50<=age<100

（2）將第i個分片的記錄發(fā)給處理機i（3）歸并——歸并所有來自A（B）的記錄（4）每個處理機將分配給它的A和B的記錄進行連接（5）歸并22.6分布式數(shù)據(jù)庫簡介分布式數(shù)據(jù)庫——數(shù)據(jù)分布存儲于若干個場地上，每個場地都由獨立運行的DBMS進行數(shù)據(jù)管理。分布式數(shù)據(jù)庫系統(tǒng)的特點：

(1)分布數(shù)據(jù)的獨立性：用戶無需提供關(guān)系或關(guān)系副本的存儲地點，就可以對數(shù)據(jù)進行查詢。

(2)分布式事物的原子性：用戶可以提交事物訪問或者修改若干個場地上的數(shù)據(jù)，涉及多個場地的事物具有原子性。分布式數(shù)據(jù)庫系統(tǒng)的類型同步分布式數(shù)據(jù)庫系統(tǒng)——數(shù)據(jù)分布在各個場地，但各場地上運行相同的DBMS。異步分布式數(shù)據(jù)庫系統(tǒng)（多數(shù)據(jù)庫系統(tǒng)）——數(shù)據(jù)分布在各個場地，不同場地運行不同的DBMS。22.7分布式DBMS體系結(jié)構(gòu)（1）客戶/服務(wù)器（2）協(xié)同服務(wù)器（3）中間件22.71客戶/服務(wù)器系統(tǒng)客戶/服務(wù)器系統(tǒng)——每個都能夠處理本地事務(wù)，擁有一個或多個客戶進程，一個或多個服務(wù)器進程，并且客戶進程可以向任一服務(wù)器進程提交查詢?？蛻暨M程負責(zé)和用戶進行交互，服務(wù)器進程負責(zé)管理數(shù)據(jù)并進行事物處理?？蛻暨M程可運行在個人計算機上，將查詢提交給大型主機上的服務(wù)器進程執(zhí)行。缺點：不能處理涉及多個服務(wù)器的單個查詢，因此客戶進程必須將查詢分解成合適的子查詢，分別在不同場地執(zhí)行，然后將各個子查詢的結(jié)果組合起來得到最終查詢結(jié)果。客戶進程將變得非常復(fù)雜。22.72協(xié)同服務(wù)器系統(tǒng)中的數(shù)據(jù)庫服務(wù)器，每個都能夠處理本地事務(wù)，并能協(xié)同執(zhí)行涉及多個服務(wù)器的事務(wù)。當(dāng)服務(wù)器收到的查詢需要訪問其它服務(wù)器的數(shù)據(jù)時，將產(chǎn)生合適的子查詢，提交給其它服務(wù)器，得到結(jié)果組合產(chǎn)生原始查詢的最終結(jié)果。22.7.3中間件系統(tǒng)中間件系統(tǒng)允許提交涉及多個服務(wù)器的單個查詢，并且數(shù)據(jù)庫服務(wù)器不需要都具有多場地查詢執(zhí)行能力。該方法對于集成很難擴展的若干遺留系統(tǒng)非常有效。基本上，只需要一個服務(wù)器有能力處理涉及多個服務(wù)器的查詢或者事物就可以了，其余的服務(wù)器只需要處理本地的查詢和事物。中間件——將協(xié)同執(zhí)行涉及多服務(wù)器的查詢或事物的特殊服務(wù)器看成一個軟件層。中間件本身并不維護數(shù)據(jù)，但能夠?qū)碜云渌?wù)器的數(shù)據(jù)進行連接和其他關(guān)系操作。22.8分布式DBMS的數(shù)據(jù)存儲分布式DBMS，關(guān)系可以存儲于若干場地。將經(jīng)常使用的數(shù)據(jù)存儲于本地，并且將使用頻率較高的關(guān)系數(shù)據(jù)復(fù)制存儲于每個場地。22.8.1劃分劃分——將關(guān)系分離成若干個小關(guān)系或者分片，每個分片存儲于不同場地。（1）水平劃分——每個分片是原始關(guān)系所有數(shù)據(jù)行的子集合。（2）垂直劃分——每個分片是原始關(guān)系所有數(shù)據(jù)列的子集合。22.8.1劃分Idnamecityagesal001JonesMadra233000002SmithChicago254500003MaryChicago195000004JakcBombay358000005MadaBombay469800垂直劃分——可用π得到.πid，name水平劃分——可以用σ得到例：來自同一個城市的雇員位于一個分片將Chicago數(shù)據(jù)存儲于場地Chicago。相當(dāng)多的查詢是本地查詢22.8.2復(fù)制復(fù)制——同時存儲關(guān)系或者關(guān)系分片的若干個版本。一個完整的關(guān)系可以在一個或多個場地進行復(fù)制與存儲。同樣，關(guān)系分片也可以復(fù)制存儲于若干場地。例：關(guān)系劃分成R1，R2，R3三個分片，可以只存儲R1的一個副本，復(fù)制存儲R2的多個副本，在所有場地復(fù)制存儲R3的副本。復(fù)制的作用：增加數(shù)據(jù)的可用性：當(dāng)存儲數(shù)據(jù)的某個場地的系統(tǒng)發(fā)生故障時，可以在其他場地找到數(shù)據(jù)。快速的查詢處理：使用本地副本代替訪問遠程數(shù)據(jù)，減少了訪問遠程場地的數(shù)據(jù)將導(dǎo)致額外的傳輸代價，能加快查詢的執(zhí)行速度。22.9分布式目錄管理跟蹤分布到多個場地的數(shù)據(jù)，保存關(guān)系進行劃分以及進行復(fù)制的信息，即關(guān)系分片如何分布到若干個場地以及分片副本存儲在哪里。22.9.1命名對象關(guān)系進行了劃分和復(fù)制后，要對之命名以唯一地識別每個分片的每個副本。<load-name,birth-site>本地名（load-name），關(guān)系所在場地生成的名字。同一場地兩個對象不能同名。產(chǎn)生場地名（birth-site），用于標(biāo)識關(guān)系產(chǎn)生的場地，以及對關(guān)系的所有分片和副本的信息進行維護的場地。22.9.2目錄結(jié)構(gòu)場地目錄：描述該場地存儲的所有分片和副本本場地產(chǎn)生的關(guān)系的副本的分布情況22.10分布式查詢處理Sailors（sid:integer,sname:string,rating:integer,age:real）Reserves(sid:integer,bid:integer,day:date,rname:string)SELECTAVG(S.age)FROMSailorsSWHERES.rating>3ANDS.rating<722.10.1分布式DBMS中無連接的查詢Sailors水平劃分：rating<5存在shanhai>=5存在Tokyo——必須在兩個場地分別計算SUM（age），COUNIT（age）（記錄數(shù)）再利用上述信息計算AVG（age）——如果WHERE子句只有一個條件S.rating>6,只需在一個場地Tokyo查詢處理Sailors垂直劃分：場地shanghai存儲sid和rating場地Tokyo存儲sanme和age

有損分解兩個字段無公共字段兩個分片加額外標(biāo)識字段（id）存儲于兩個場地，才能合并兩個分片得到原關(guān)系。22.10.1分布式DBMS中無連接的查詢Sailors同時存儲于場地shanghai和Tokyo選擇哪個場地進行查詢？取決于：將查詢結(jié)果傳輸?shù)讲樵兲峤粓龅氐拇鷥r在場地shanghai或Tokyo執(zhí)行查詢的代價22.10.2分布式DBMS中的連接操作LONDONPARISSailorsReserves每條記錄50字節(jié)每頁存80條記錄總共有500頁每條記錄40字節(jié)每頁有100條記錄總共有1000頁記錄D——從磁盤讀取（寫）頁數(shù)據(jù)所需的時間

S——傳輸一頁數(shù)據(jù)（從一個場地到另一個場地）所需的時間不同執(zhí)行策略：（1）需要時取得數(shù)據(jù)（2）傳輸?shù)揭粋€場地（3）半連接和布魯連接不同執(zhí)行策略的執(zhí)行代價：（1）需要時取得數(shù)據(jù)在場地London做基于頁的嵌套循環(huán)連接，Sailors作為外關(guān)系，則對于Sailors的每頁數(shù)據(jù)，都需要從場地Paris得到Reserves的所有數(shù)據(jù)，并進行連接。代價：500D+500*1000（D+S）如果查詢不是在場地London提交的，查詢的處理代價還需要加上將查詢結(jié)果傳輸?shù)讲樵兲峤粓龅氐膫鬏敶鷥r，這個取決于查詢結(jié)果的大小。如果查詢場地不再London也不在Paris，傳輸查詢結(jié)果的代價將大于將關(guān)系Sailors和Reserves都傳到查詢場地的代價。所以應(yīng)將兩個關(guān)系傳輸?shù)讲樵儓龅?，再?zhí)行連接操作?？梢栽趫龅豅ondon使用索引嵌套循環(huán)連接方法，對于關(guān)系Sailors的每條記錄，只訪問關(guān)系Reserves中合適的記錄。對關(guān)系Reserves建立基于屬性sid哈希索引。都需要從遠程場地取得數(shù)據(jù)，傳輸代價所占比重大。不同執(zhí)行策略的執(zhí)行代價：（2）傳輸?shù)揭粋€場地可將Sailors從London傳到Paris，然后在Paris執(zhí)行連接。500（2D+S）+4500D可將Reservs從Paris傳到London，連接

1000（2D+S）+4500D將兩個關(guān)系都傳到查詢提交的場地，在那里連接不同執(zhí)行策略的執(zhí)行代價（3）半連接和布魯連接例：將Reserves傳到London并連接實際上Reserves的部分記錄并不能和Sailors的記錄進行連接，事先確定哪些記錄和Sailors不能進行連接，可避免傳輸這些記錄，從而可減少傳輸Reserves記錄的數(shù)目。半連接：（1）在場地London對關(guān)系Sailors進行投影得到連接字段sid，將結(jié)果傳到場地Paris（2）在場地Paris，將London傳來的投影結(jié)果和關(guān)系Peserves進行自然連接。連接的結(jié)果就稱為Reserves的一個基于關(guān)系Sailors的約減。只有約減的Reserves記錄能和Sailors的記錄進行連接。所以約減后的Reserves傳輸?shù)綀龅豅ondon（3）在場地London，對約減后的Reserves和Sailors進行連接代價：200S+6500D半連接的傳輸代價小，但總代價可能比傳輸整個關(guān)系要大布魯連接（1）傳送位向量，不是Sailors的投影。位向量長度為k，關(guān)系Sailors的每條記錄（使用屬性sid）通過哈希函數(shù)映射到區(qū)域0~k-1，如果記錄的哈希值為i，則向量的第i位設(shè)為1，否則為0。（2）對關(guān)系Reserves進行約減時，使用相同的哈希函數(shù)將Reserves的每個記錄（使用屬性sid）映射到區(qū)域0~k-1，對于哈希值為i的記錄，如果向量的第i位值為0，表示沒有哈希值為i的Sailors記錄，即沒有Sailors可進行連接，忽略該Reserves中的記錄。SailorsReservessid：sid：h（sid）=1，2……k-101234k-101100……1*位向量傳輸代價低，更有效。22.11分布式數(shù)據(jù)的更新同步復(fù)制——在更新事物提交時，同步更新數(shù)據(jù)的所有副本異步復(fù)制——關(guān)系的副本只需要定期更新;

因此一個事物讀取每個關(guān)系的不同副本結(jié)果可能不同異步復(fù)制危害了分布數(shù)據(jù)的獨立性，但比同步復(fù)制能更有效地實現(xiàn)。22.11.1同步復(fù)制1）投票技術(shù)——事物在修改每個對象時寫該對象的大多數(shù)副本，并且在讀時要讀足夠數(shù)量的副本來保證其中之一為當(dāng)前副本例：總共有10個副本，更新事物寫了其中7個副本，那么至少應(yīng)該讀4個副本。*很多應(yīng)用中，讀數(shù)據(jù)比更新數(shù)據(jù)頻繁，所以應(yīng)提高了讀的性能，所以此技術(shù)沒吸引力2）讀任意寫全部技術(shù)——事物可以讀對象的任一個副本，但寫時需要所有副本。和投票比較：讀的速度快，寫的速度慢讀操作比寫頻繁時，此技術(shù)有吸引力。通常情況使用此技術(shù)來實現(xiàn)同步復(fù)制。22.11.2異步復(fù)制