數據庫原理與技術第十四章new.ppt

1、第十四章 分布式數據庫,概述,分布式數據庫系統(tǒng)是數據庫技術和網絡技術兩者相互滲透和有機結合的結果,分布式數據庫和分布式數據庫系統(tǒng),定義 分布式數據庫是由一組數據組成的，這組數據分布在計算機網絡的不同計算機上，網絡中每個結點具有獨立處理的能力（稱為場地自治），可以執(zhí)行局部應用（只對本結點數據進行存取的應用），同時每個結點也能通過網絡通訊支持全局應用（指存取兩個或兩個以上的結點的數據庫應用）。 分布式數據庫強調場地自治性（局部應用）以及自治場地之間的協(xié)作性（全局應用）。,分布式數據庫和分布式數據庫系統(tǒng),分布式數據庫具有以下兩個特點： 分布性 分布性有兩層含義，一是指數據庫中的數據不是都存儲在同一結

2、點（更確切的講，不存儲在同一計算機的存儲設備上），而是分布在多個結點上；二是指各結點具有獨立的數據庫處理能力，能夠有效地支持局部應用。 邏輯整體性 分布在各結點的數據不是孤立的，而是相互聯(lián)系的，是一個邏輯整體，能夠支持存取多個結點數據的全局應用。,分布式數據庫和分布式數據庫系統(tǒng),分布式數據庫系統(tǒng)是在集中式數據庫系統(tǒng)技術的基礎上發(fā)展起來的，但不是簡單地把集中式數據庫分散的實現，它豐富和發(fā)展了集中式數據庫的許多概念和技術，具有自己獨特的特征和性質。具體來說，它具有以下特點： 數據獨立性 數據獨立性在分布式數據庫系統(tǒng)中具有了更多的含義，它不僅包括數據的邏輯獨立性和物理獨立性以外，還包括數據的分布獨立

3、性（也稱分布透明性）。分布透明性指用戶不必關心數據的邏輯分片，不必關心數據物理位置分布的細節(jié)，不必關心重復副本（冗余數據）一致性問題，也不必關心局部結點上數據庫支持哪種數據模型。,分布式數據庫和分布式數據庫系統(tǒng),集中與自治相結合的控制機構 在分布式數據系統(tǒng)中，數據的共享有兩個層次：一是局部共享，即在局部數據庫中存儲局部結點各用戶的共享數據；二是全局共享。即在分布式數據庫系統(tǒng)的各個結點也存儲供其他結點的用戶共享的數據，支持系統(tǒng)的全局應用。因此，相應的控制機構也具有兩個層次：集中和自治。分布式數據庫系統(tǒng)常常采用集中和自治相結合的控制機構。各局部的DBMS可以獨立的管理局部的數據庫，具有自治功能。同

4、時系統(tǒng)又設有集中控制機構，協(xié)調各局部DBMS的工作，執(zhí)行全局應用。,分布式數據庫和分布式數據庫系統(tǒng),適當增加數據冗余 在分布式數據庫系統(tǒng)中適當的增加了冗余數據，在不同的結點存儲同一數據的多個副本，其原因是：一提高系統(tǒng)的可靠性、可用性，當某一結點出現故障時，系統(tǒng)可以對另一結點的相同副本進行操作，不會因為一處故障而造成整個系統(tǒng)的癱瘓；二是提高系統(tǒng)性能，系統(tǒng)可以選擇用戶最近的數據副本來進行操作，減少通信代價，改善整個系統(tǒng)的性能。,分布式數據庫和分布式數據庫系統(tǒng),全局的一致性、可串行性和可恢復性 分布式數據庫系統(tǒng)中各局部數據庫應滿足集中式數據庫的一致性、并發(fā)事務的可串行性和可恢復性。除此之外還應保證數

5、據庫的全局一致性、全局并發(fā)事務的可串行性和系統(tǒng)全局的可恢復性。這是因為在分布式數據庫系統(tǒng)中全局應用要涉及兩個以上結點的數據，全局事務可能由不同結點上的多個操作組成。,分布式數據庫和分布式數據庫系統(tǒng),分布式數據庫系統(tǒng)的目標 適應部門分布的組織結構，降低費用 使用數據庫的單位在組織上常常是分布的，在地理上也是分布的。分布式數據庫系統(tǒng)的結構符合上述分布的組織結構，允許各個部門將自己常用的數據存儲在本地，降低了通信代價，提高了響應速度。 提高系統(tǒng)的可靠性和可用性 將數據分布于多個結點，并適當增加冗余度，可以提供更好的可靠性。,分布式數據庫和分布式數據庫系統(tǒng),充分利用數據庫資源，提高現有集中式數據庫的利

6、用率 當在一個大企業(yè)內部和大部門中已經建成若干個數據庫后，為了利用相互的資源，開發(fā)全局應用可以在現有各局部數據庫的基礎上做一定的修改和重構，建立一個分布式數據庫系統(tǒng)。 逐步擴展處理能力和系統(tǒng)規(guī)模 相對于集中式數據庫系統(tǒng)，分布式數據庫系統(tǒng)能夠方便地將一個新結點納入系統(tǒng)，而不影響現有系統(tǒng)的結構和系統(tǒng)的正常運行，提供了逐步擴展系統(tǒng)能力的較好途徑。,分布式數據庫的體系結構,映像1,映像2,映像3,映像4,分布式數據庫的體系結構,全局外模式 全局應用的用戶視圖，是全局概念模式的子集。 全局概念模式 定義分布式數據庫中數據的整體邏輯結構，使得數據如同沒有分布一樣。 分片模式 每一個全局關系可以分為若干互不

7、相交的部分，每一部分稱為一個片段。分片模式定義片段以及全局關系到片段的映像。 分布模式 定義片段的存放結點。,分布式數據庫的體系結構,分布（網絡）透明性 分片透明性 用戶或應用程序只對全局關系進行操作而不必考慮關系的分片。如果分片模式改變了，通過調整全局模式與分片模式之間的映象關系來保持全局模式不變。 位置透明性 用戶或應用程序不必了解片段的存儲位置。 局部數據模型透明性 用戶或應用程序不必了解局部場地上使用的是哪種數據模型。,分布式數據庫的體系結構,示例：設有全局關系S，它被劃分為兩個片段S-A（本科生），S-B（研究生），S-B有兩個副本。,分布式數據庫設計,數據在分布式數據庫中的存儲途徑

8、 數據的重復存儲 系統(tǒng)在兩個或兩個以上結點維護關系R的幾個完全相同的副本。如果系統(tǒng)的每個結點都存儲R的一個副本，則稱這種重復存儲為完全重復存儲。數據重復存儲具有以下幾個優(yōu)點： 可用性強 如果某個存儲R的結點出了故障，系統(tǒng)仍然可以使用其它結點上的副本繼續(xù)處理用戶查詢，使系統(tǒng)正常運行。 增強并行性 由于R的重復存儲，可以使更多的用戶并行地查詢R。 數據的重復存儲也會帶來一些問題，如增加了更新操作的開銷，加大了并行控制的難度,分布式數據庫設計,分片存儲 關系被劃分為幾個片段，各個片段存儲在不同的結點上。將數據分片，使數據存放的單位不是關系而是片段，這既有利于按照用戶的需求較好地組織數據的分布，也有利

9、于控制數據的冗余度。分片時必須遵循以下原則： 完全性：被劃分關系中的每個元組必須屬于一個片段。 不相交性：同一個關系的片段互不相交。 可重構性：如果R被劃分為片段R1、R2、Rn，則R能從R1、R2、Rn恢復出來。,分布式數據庫設計,分片方式 水平分片 垂直分片 導出分片 混合分片,分布式數據庫設計,水平分片 將關系r依照一定條件按行分為不相交的若干子集r1，r2，rn，每個子集ri稱為一個水平片段。 一個水平片段可以看成是關系上的一個選擇。 ri =P（i）（r） 如C_S=DNO=D06（S） 關系的重構可以通過并運算來實現。 r= r1 r2rn,分布式數據庫設計,垂直分片 將關系r按列

10、分為若干屬性子集r1，r2，rn，每個子集ri稱為一個垂直片段。 一個垂直片段可以看成是關系上的一個投影。 ri =Ri（r） 其中Ri是r的一個屬性子集。 如P_S = PNO，SAL（P） 關系的重構可以通過連接運算來實現。 r= r1 r2 rn 所有分片都包括關系的碼,分布式數據庫設計,導出分片 導出水平分片，分片的條件不是關系本身屬性條件，而是其它關系的屬性條件。 如SC（SNO，CNO，G）按學生系別分片。 混合分片 關系按某種方式分片后，得到的片段再按另一種方式繼續(xù)分片。 如SC（SNO，CNO，G）按學生系別分片，再對每個片段按成績（及格，不及格）分片。,分布式數據庫設計,組合

11、存儲 這種方法是重復存儲和分片存儲相結合的方法。關系被劃分為幾個片段，系統(tǒng)為每個片段維護幾個副本，每個副本存放于不同的結點上。,分布式數據庫設計,命名和局部自治性 每個數據項（關系、副本、片段）必須有唯一的名字，在分布式數據庫系統(tǒng)中必須保證在不同的結點上不會用同一個名字來代表不同的數據項。 途徑1：名字服務器 所有名字都在名字服務器中注冊，每個名字對應一個數據項。 缺陷：名字服務器成為名字解析的瓶頸；其故障將影響整個系統(tǒng)的運行；局部自治性降低。,分布式數據庫設計,途徑2：將結點標識作為前綴加到該結點數據項的名字前面。使用這一方法，能夠保證名字的唯一性，不須中央控制，局部自治性提高；但不能保證網

12、絡透明性。,分布式數據庫管理系統(tǒng)概述,D-DBMS由四個部分組成： LDBMS，局部場地上的DBMS，主要功能是建立和管理局部數據庫，提供場地自治能力，執(zhí)行局部應用以及全局查詢的子查詢。 GDBMS，全局數據庫管理系統(tǒng)，主要功能是提供分布透明性，協(xié)調全局事務的執(zhí)行，協(xié)調各局部DBMS以完成全局應用，保證數據庫的全局一致性，執(zhí)行并發(fā)控制，實現更新同步，提供全局恢復等功能。,分布式數據庫管理系統(tǒng)概述,全局數據字典，存放全局概念模式、分片模式、分布模式等的定義，以及各模式之間的映像定義，存放有關用戶存取權限的定義、完整性約束的定義等。 通信管理，在分布式數據庫各場地之間傳送消息和數據，完成通信功能。

13、,分布式數據庫管理系統(tǒng)概述,D-DBMS的分類 按全局控制發(fā)生分類 全局控制集中的DDBMS 全局數據庫器和全局數據字典集中于某一結點，其優(yōu)點是控制簡單，容易實現更新一致性，但該結點容易成為系統(tǒng)的瓶頸，系統(tǒng)也較脆弱。,分布式數據庫管理系統(tǒng)概述,全局控制分散的DDBMS 全局數據庫器和全局數據字典分散在網絡上的每一個結點上，每個結點都能完成全局事務的協(xié)調和局部數據庫事務的控制功能。每個結點既是全局事務的參與者，也是全局事務的協(xié)調者。其優(yōu)點是結點獨立，自治性強，但全局控制的協(xié)調機制和一致性維護都比較困難。 全局控制部分分散的DDBMS 介于上述兩者之間，根據應用的需要將全局數據庫管理器和全局數據字

14、典分散在某些結點上。,分布式數據庫管理系統(tǒng)概述,按局部DBMS的類型分類 同構型DDBMS 每個結點的局部數據庫具有相同的DBMS。 異構型DDBMS 各結點的局部數據庫具有不同的DBMS,分布式查詢處理,在分布式數據庫系統(tǒng)中，數據分布在網絡上的多個結點之中，其查詢需要由多個結點利用網絡協(xié)作完成。在集中式數據庫中，查詢優(yōu)化的目標是產生最小磁盤I/O數，在分布式數據庫中還要考慮網絡的傳輸時間和各結點的并發(fā)執(zhí)行。因此，分布式查詢處理較集中式數據庫復雜。,分布式查詢處理,在分布式數據庫系統(tǒng)中，查詢可分為三類：局部查詢，遠程查詢，全局查詢。局部查詢和遠程查詢只涉及單個結點的數據（本地的或遠程的），可以

15、采用集中式數據庫的處理技術；二全局查詢涉及到多個結點的數據，因此相對復雜的多。,分布式查詢處理,分布式查詢處理的過程包括： 查詢變換 將用戶查詢轉換為析取范式或合取范式，并進行語義分析，檢查查詢的正確性等工作。,分布式查詢處理,數據定位 數據定位的目的是把用戶定義在全局概念模式上的查詢轉換為定義在局部概念模式上的查詢。由于它定義在片段上，也稱為片段查詢。設查詢Q中包含關系R1、R2、Rn，而且對于1in，Ri已經被劃分為m個片段Ri1、Ri2、Rim， Ri=F(Ri1、Ri2、Rim)。Q的數據定位包括兩步。第一步，對于1in，用Ri=F(Ri1、Ri2、Rim)代替Q中的Ri ，得到一個等

16、價的片段查詢FQ。第二步，進一步加工FQ，產生一個與FQ等價并且效率更高的片段查詢。,分布式查詢處理,全局查詢優(yōu)化 無論是集中式數據庫還是分布式數據庫其查詢策略的選擇都是以執(zhí)行查詢的預期代價為依據的。在集中式數據庫中，查詢執(zhí)行的開銷主要是：I/O+CPU代價。而在分布式數據庫中查詢執(zhí)行的開銷為：I/O+CPU代價+通信代價。因此在全局查詢優(yōu)化時需要選擇執(zhí)行操作的順序，降低網絡通信的開銷。,分布式查詢處理,局部查詢優(yōu)化 局部查詢優(yōu)化的目的是為每個局部查詢選擇優(yōu)化的執(zhí)行計劃，其方法與集中式數據庫的查詢優(yōu)化策略和方法相同。,分布式查詢處理,假定每條元組100bit大小 求供應紅色零件的、北京的供應商

17、號碼 select S.S# from S, P, SP where S.CITY = 北京 and S.S# = SP.S# and SP.P# = P.P# and P.COLOR = 紅色,分布式查詢處理,傳送時間T=總傳輸延遲+總數據量/傳輸速度 1.把關系P從B站傳送到A站，在A站進行查詢 傳送時間T=1+105 100 /104=103s,分布式查詢處理,2.把關系S，SP從A站傳送到B站，在B站進行查詢 傳送時間T=2+(104+106)100/104104s,分布式查詢處理,在A站連接S與SP，選出城市為北京的元組（假定有105個），然后對其中每個元組的P#，詢問B站，看其是否

18、為紅色。 傳送時間T=2 105s,分布式查詢處理,在B站選出紅色零件（假定有10個），然后對每個元組詢問A站，看北京的供應商是否供應此零件。 傳送時間T=2 10=20s,問,分布式查詢處理,5.在A站選出北京的供應商（105個），傳送到B站，在B站完成查詢。 傳送時間T=1+ 105100/104=103s,分布式查詢處理,在B站選出紅色零件（10個），把結果傳送到A站，在A站完成查詢。 傳送時間T=1+ 10100/104=1.1s,分布式查詢處理,半連接運算 定義 半連接R S=R（R S）,=,分布式查詢處理,半連接作用 找出R中能夠與S中元組相連接的元組來，類似于在連接之前先做選擇

19、和投影。 R S = （R S） S R S = （S R） R 半連接的非對稱性 R S S R,分布式查詢處理,半連接在分布式數據庫中的應用 R與S位于不同結點S1，S2上，其屬性組分別為R1，R2，要在S1結點求R和S的連接結果。 在S1結點對R做投影，將R縮減為R， R=R1R2（R） 將R 送往結點S2。 在S2結點完成S與R的半連接操作，將S縮減為S， S = S R 將S送回結點S1 。 在S1結點完成R與S的連接操作， R S = R S,分布式查詢處理,通訊代價模型 TC（X）= C0+X*C1 其中X為數據傳輸量。 C0為兩結點初始化一次傳輸所花費的開銷。 C1為傳輸率，即

20、單位數據傳輸所花費的時間。 采用半連接的通訊代價： CSJ=2C0+(size(R)*card(R)+size(S)*card(S)*C1 不采用半連接的通訊代價： CJN=C0+size(S)*card(S) *C1 當S中參與連接的元組足夠少時采用半連接策略是有利的。,分布式數據庫系統(tǒng)的事務處理,分布式事務 數據的分布導致事務具有了分布性。一個全局事務的執(zhí)行被劃分為在許多結點上子事務的執(zhí)行。系統(tǒng)不但要保證每個子事務的原子性，還要保證全局事務的原子性。這不是哪一個局部DBMS能夠完成的，而是需要在結點間進行協(xié)調。,分布式數據庫系統(tǒng)的事務處理,示例：銀行在兩個帳戶之間轉帳。 對集中式數據庫，單

21、個事務T： A：=A - 100，B：=B+100 對于分布式數據庫，假定A在S1,S2各有一副本，B在S3,S4各有一副本，用戶請求在S5發(fā)出，則分布事務T由T1,T2,T3,T4,T5構成： T1, T2： A：=A - 100 T3, T4 ：B：=B + 100 T5 ： 結果返回給用戶,分布式數據庫系統(tǒng)的事務處理,分布式事務處理器 事務管理器TM：管理那些訪問存儲在一個局部結點中的數據的事務。事務可以是局部事務，也可以是全局事務的一部分。 事務協(xié)調器TC：協(xié)調該結點上發(fā)起的各事務（局部的或全局的）的執(zhí)行。,分布式數據庫系統(tǒng)的事務處理,事務管理器功能 維護一個用于恢復的日志。 參與適當

22、的并發(fā)控制模式，以協(xié)調在該結點上執(zhí)行的事務的并發(fā)執(zhí)行。 事務協(xié)調器功能 啟動事務的執(zhí)行。 將事務分解為若干子事務，并將子事務分派到適當的結點上去執(zhí)行。 協(xié)調事務的終止，保證事務在所有的結點上都提交或都中止。 一個全局事務的各個子事務要么全部執(zhí)行，要么全部中止。,分布式數據庫系統(tǒng)的事務處理,事務兩階段提交協(xié)議 假定事務T在結點Si發(fā)起， 階段1： 事務協(xié)調器TCi向日志中加入一條記錄，并強制該日志寫入穩(wěn)定存儲器中。 TCi將消息發(fā)送到執(zhí)行T的所有結點上。 當某結點接受到上述消息時，該結點的TM回答確定是否提交T中屬于它的那部分，若否，則TM將記錄加入到日志中，并向TCi發(fā)送消息。若是，則TM將記

23、錄加入到日志中，并將日志強制寫入穩(wěn)定存儲器中，并向TCi發(fā)送消息。,分布式數據庫系統(tǒng)的事務處理,階段2： 當TCi收到所有結點對消息的回答時，或等待響應的時間已過，TCi決定事務T是提交還是中止。 如果TCi 收到的都是消息，事務就可以提交，否則事務必須被中止。根據結果的不同向日志中寫入 或者，并強制將日志寫入穩(wěn)定存儲器中。 向所有參與的結點發(fā)送消息或。 結點收到此消息后，就把該消息記入日志中。（向TCi發(fā)送消息； TCi收到該消息后，將記錄加入到日志中）。,分布式并發(fā)控制技術,分布式鎖技術 若分布式數據庫中沒有重復存儲的數據，可以采用如下的分布式鎖技術：每個結點保留一個局部鎖管理器，處理對存

24、儲在本地的數據加鎖和釋放鎖的請求。當事務T希望對結點Si上的數據項Q加鎖時，T簡單的向結點上的鎖管理器發(fā)出一個加鎖請求。分布式鎖技術具有實現簡單的特點，它處理一個加鎖請求需要兩次通信，處理釋放鎖請求需要一次通信。但其死鎖處理較為復雜。,分布式并發(fā)控制技術,集中式鎖技術 集中式鎖技術僅有一個鎖管理器，這個鎖管理器位于唯一一個結點（如Si）上。所有的加鎖和釋放鎖的請求都在該結點上處理。集中式鎖技術具有以下優(yōu)點： 實現簡單 加鎖請求需要兩次通信，釋放鎖請求需要一次通信。 死鎖處理簡單 可按照集中式數據庫的方法進行處理 集中式鎖技術具有以下缺點： 瓶頸問題 Si是一個鎖管理瓶頸 脆弱性 如果Si出現故

25、障，系統(tǒng)無法正常運行。,分布式并發(fā)控制技術,混合鎖技術 混合鎖技術是集中式和分布式鎖技術的折中。這種技術設置多個鎖管理器，每個鎖管理器管理一組數據的加鎖和釋放鎖的請求。每個鎖管理器位于不同的結點上。,分布式并發(fā)控制技術,以多為主的鎖協(xié)議 系統(tǒng)在每個結點上有一個鎖管理器。在任何結點Si上的鎖管理器管理存儲在Si上的所有數據項副本的加鎖和釋放鎖的請求。當事務T請求對數據項Q加鎖時，如果n個結點存儲Q的副本，則T要向n/2以上的存儲Q副本的結點發(fā)出加鎖請求。,分布式并發(fā)控制技術,區(qū)分鎖類型的鎖協(xié)議 每個結點上有一個鎖管理器。每個鎖管理器管理所在結點上存儲的數據的加鎖和釋放鎖的請求。共享鎖和互斥鎖采用不同的方式進行處理。當事務T需要在數據項加共享鎖時，T直接向一個存儲該數據項副本的結點的鎖管理器發(fā)出加