第22章并行與分布式數據庫

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

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

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

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

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

……

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

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

記錄按照相應的age值進行分布

0<=age<10處理機1

10<=age<20處理機2

……

……90<=age<100處理機10缺點：產生由對數據偏斜不同分片的記錄數目差別很大并行連接操作的數據流網絡合并

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

A”B”A連接連接

Ai∞BiAj∞BjAiAiAiAjAjAjAjBiBiBiBiBjBjBjBjB存儲關系A與B的處理機處理連接的處理機并行連接操作的數據流網絡（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分布式數據庫簡介分布式數據庫——數據分布存儲于若干個場地上，每個場地都由獨立運行的DBMS進行數據管理。分布式數據庫系統的特點：

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

(2)分布式事物的原子性：用戶可以提交事物訪問或者修改若干個場地上的數據，涉及多個場地的事物具有原子性。分布式數據庫系統的類型同步分布式數據庫系統——數據分布在各個場地，但各場地上運行相同的DBMS。異步分布式數據庫系統（多數據庫系統）——數據分布在各個場地，不同場地運行不同的DBMS。22.7分布式DBMS體系結構（1）客戶/服務器（2）協同服務器（3）中間件22.71客戶/服務器系統客戶/服務器系統——每個都能夠處理本地事務，擁有一個或多個客戶進程，一個或多個服務器進程，并且客戶進程可以向任一服務器進程提交查詢?？蛻暨M程負責和用戶進行交互，服務器進程負責管理數據并進行事物處理。客戶進程可運行在個人計算機上，將查詢提交給大型主機上的服務器進程執(zhí)行。缺點：不能處理涉及多個服務器的單個查詢，因此客戶進程必須將查詢分解成合適的子查詢，分別在不同場地執(zhí)行，然后將各個子查詢的結果組合起來得到最終查詢結果?？蛻暨M程將變得非常復雜。22.72協同服務器系統中的數據庫服務器，每個都能夠處理本地事務，并能協同執(zhí)行涉及多個服務器的事務。當服務器收到的查詢需要訪問其它服務器的數據時，將產生合適的子查詢，提交給其它服務器，得到結果組合產生原始查詢的最終結果。22.7.3中間件系統中間件系統允許提交涉及多個服務器的單個查詢，并且數據庫服務器不需要都具有多場地查詢執(zhí)行能力。該方法對于集成很難擴展的若干遺留系統非常有效?；旧?，只需要一個服務器有能力處理涉及多個服務器的查詢或者事物就可以了，其余的服務器只需要處理本地的查詢和事物。中間件——將協同執(zhí)行涉及多服務器的查詢或事物的特殊服務器看成一個軟件層。中間件本身并不維護數據，但能夠對來自其它服務器的數據進行連接和其他關系操作。22.8分布式DBMS的數據存儲分布式DBMS，關系可以存儲于若干場地。將經常使用的數據存儲于本地，并且將使用頻率較高的關系數據復制存儲于每個場地。22.8.1劃分劃分——將關系分離成若干個小關系或者分片，每個分片存儲于不同場地。（1）水平劃分——每個分片是原始關系所有數據行的子集合。（2）垂直劃分——每個分片是原始關系所有數據列的子集合。22.8.1劃分Idnamecityagesal001JonesMadra233000002SmithChicago254500003MaryChicago195000004JakcBombay358000005MadaBombay469800垂直劃分——可用π得到.πid，name水平劃分——可以用σ得到例：來自同一個城市的雇員位于一個分片將Chicago數據存儲于場地Chicago。相當多的查詢是本地查詢22.8.2復制復制——同時存儲關系或者關系分片的若干個版本。一個完整的關系可以在一個或多個場地進行復制與存儲。同樣，關系分片也可以復制存儲于若干場地。例：關系劃分成R1，R2，R3三個分片，可以只存儲R1的一個副本，復制存儲R2的多個副本，在所有場地復制存儲R3的副本。復制的作用：增加數據的可用性：當存儲數據的某個場地的系統發(fā)生故障時，可以在其他場地找到數據?？焖俚牟樵兲幚恚菏褂帽镜馗北敬嬖L問遠程數據，減少了訪問遠程場地的數據將導致額外的傳輸代價，能加快查詢的執(zhí)行速度。22.9分布式目錄管理跟蹤分布到多個場地的數據，保存關系進行劃分以及進行復制的信息，即關系分片如何分布到若干個場地以及分片副本存儲在哪里。22.9.1命名對象關系進行了劃分和復制后，要對之命名以唯一地識別每個分片的每個副本。<load-name,birth-site>本地名（load-name），關系所在場地生成的名字。同一場地兩個對象不能同名。產生場地名（birth-site），用于標識關系產生的場地，以及對關系的所有分片和副本的信息進行維護的場地。22.9.2目錄結構場地目錄：描述該場地存儲的所有分片和副本本場地產生的關系的副本的分布情況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）（記錄數）再利用上述信息計算AVG（age）——如果WHERE子句只有一個條件S.rating>6,只需在一個場地Tokyo查詢處理Sailors垂直劃分：場地shanghai存儲sid和rating場地Tokyo存儲sanme和age

有損分解兩個字段無公共字段兩個分片加額外標識字段（id）存儲于兩個場地，才能合并兩個分片得到原關系。22.10.1分布式DBMS中無連接的查詢Sailors同時存儲于場地shanghai和Tokyo選擇哪個場地進行查詢？取決于：將查詢結果傳輸到查詢提交場地的代價在場地shanghai或Tokyo執(zhí)行查詢的代價22.10.2分布式DBMS中的連接操作LONDONPARISSailorsReserves每條記錄50字節(jié)每頁存80條記錄總共有500頁每條記錄40字節(jié)每頁有100條記錄總共有1000頁記錄D——從磁盤讀?。▽懀╉摂祿璧臅r間

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

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

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