分布式數(shù)據(jù)庫及相關問題課件

1、第六部分 分布式數(shù)據(jù)庫及相關技術的討論（第8-11章內容）一 分布式數(shù)據(jù)庫概述產(chǎn)生和發(fā)展概念和分類體系結構模式結構及獨立性。二 分布式數(shù)據(jù)庫系統(tǒng)中存在的技術問題分布式DB的設計分布式DB的查詢分布式DB的事務管理及并發(fā)。第1頁，共85頁。一 分布式數(shù)據(jù)庫概述I 分布式數(shù)據(jù)庫的產(chǎn)生及發(fā)展a 經(jīng)濟的發(fā)展b 計算機硬件環(huán)境及網(wǎng)絡的發(fā)展發(fā)展歷程：產(chǎn)生于20世紀70年代末期，成長于80年代 第一個分布式數(shù)據(jù)庫系統(tǒng)SDD-1是美國計算機公司（CAA）于1976年-1978年設計，79年在DEC-10/20上實現(xiàn)。德國斯圖加特大學研制的porel系統(tǒng)美國IBM的R*和system R美國加大學伯克利分校的I

2、ngres法國INRA研制的SIRIUS-DELTA。第2頁，共85頁。1987年：C.J Date提出了完全的，真正的分布式DBS應遵循的12條規(guī)則：本地自治性不依賴于中心站點可連續(xù)操作位置獨立性數(shù)據(jù)分片獨立性數(shù)據(jù)復制獨立性分布式查詢獨立性分布式事務管理硬件獨立性操作系統(tǒng)獨立性網(wǎng)絡獨立性DBMS獨立性第3頁，共85頁。II 分布式數(shù)據(jù)庫系統(tǒng)的定義及分類1 分布式數(shù)據(jù)庫的定義： 分布式數(shù)據(jù)庫是一個數(shù)據(jù)集合，這些數(shù)據(jù)分布在由計算機網(wǎng)絡連接起來的若干節(jié)點上，每個節(jié)點可以管理本地的數(shù)據(jù)應用，也可以參與全局數(shù)據(jù)應用。同時這些數(shù)據(jù)在邏輯上形成一個整體，由統(tǒng)一的數(shù)據(jù)庫管理系統(tǒng)進行管理。（DDBMS）注：幾

3、個基本的概念站點：計算機連接的一個邏輯單位，稱為一個站點。本地（或稱：局部）用戶、本地應用：一個用戶或應用只訪問他所注冊的那個站點。全局用戶、全局應用：一個用戶訪問涉及兩個或兩個以上的站點中的數(shù)據(jù)。全局數(shù)據(jù)庫（GDB）、局部數(shù)據(jù)庫（LDB）：。第4頁，共85頁。2.分布式數(shù)據(jù)庫系統(tǒng)的基本特點：A 結構特點：物理分布，邏輯相關。B 應用特點：站點自治。第5頁，共85頁。多處理機系統(tǒng)C.數(shù)據(jù)分布透明性：數(shù)據(jù)的物理獨立性內容更豐富，增加了數(shù)據(jù)分布透明性。-數(shù)據(jù)的邏輯分片、數(shù)據(jù)的物理位置分布、數(shù)據(jù)的復制，對用戶透明。D.集中與自治兼?zhèn)涞臄?shù)據(jù)庫系統(tǒng)控制機制.-兩個層次的數(shù)據(jù)共享：局部/全局數(shù)據(jù)共享。第6

4、頁，共85頁。E.增加數(shù)據(jù)冗余度。-利用數(shù)據(jù)冗余提高系統(tǒng)可靠性、可用性和系統(tǒng)性能。F.事務管理的分布性。-分布環(huán)境下，維護事務的原子性、一致性、隔離性和持久性。第7頁，共85頁。3.分布式數(shù)據(jù)庫系統(tǒng)的模式結構第8頁，共85頁。4.分布式數(shù)據(jù)庫系統(tǒng)的分類A 按局部DBMS的數(shù)據(jù)模型分類：-同構型：數(shù)據(jù)模型相同 *同質同構：數(shù)據(jù)模型相同且局部DBMS相同。 *異質同構：數(shù)據(jù)模型相同外交部局部DBMS不同。 SDD-1和DDM 美國CCA公司 SYSTEM R* 美國IBM公司 POREL 德國斯圖加特大學 -異構型 ：數(shù)據(jù)模型不同 MULTIBASE 美國CCA1981研制 IMADAS:H 佛羅

5、里達大學1984研制 DDTS HONEYWELL公司1980年研制。第9頁，共85頁。B 按全局控制系統(tǒng)類型分類：-全局控制集中型DDBS DDBS的全局控制機制及數(shù)據(jù)字典位于一個中心站點，由中心站點完成全局事務的協(xié)調和局部數(shù)據(jù)庫的轉換等所有控制功能。-全局控制分散型DDBS DDBS的全局控制機制及數(shù)據(jù)字典分散在網(wǎng)絡的各個站點上，每個站點都能完成全局事務的協(xié)調和局部數(shù)據(jù)轉換。-全局控制可變型（主從型） 將站點分成兩組，一組都包含全局控制機制和數(shù)據(jù)字典，另一組為輔助站點，只包含自己的數(shù)據(jù)應用。第10頁，共85頁。4.分布式數(shù)據(jù)庫管理系統(tǒng)的功能結構：除了具有集中式DBMS具有的功能外，還要有如

6、下附加 的功能： * 數(shù)據(jù)跟蹤 * 分布式查詢處理能力 * 分布式事務管理的能力 * 復制數(shù)據(jù)的能力 * 安全性 * 分布式目錄管理第11頁，共85頁。二.分布式數(shù)據(jù)庫系統(tǒng)中存在的技術問題： 1 分布式數(shù)據(jù)庫系統(tǒng)的設計 -全局模式的設計 -數(shù)據(jù)分片，分布 2 分布式數(shù)據(jù)庫的查詢處理 3 分布式數(shù)據(jù)庫的事務管理及并發(fā)控制 4 分布式數(shù)據(jù)庫的可靠性 5 異構數(shù)據(jù)庫的連接 6 安全性 7 目錄管理第12頁，共85頁。1.分布式數(shù)據(jù)庫設計一 方法：根據(jù)設計是基于現(xiàn)存的數(shù)據(jù)系統(tǒng)還是構造一個全新的數(shù)據(jù)庫系統(tǒng)，有兩種方法創(chuàng)建分布式數(shù)據(jù)庫： 組合法：基于現(xiàn)有的系統(tǒng)，建立一個協(xié)調管理系統(tǒng)。 -采用自底向上的方式

7、構建 重構法：創(chuàng)建全新的數(shù)據(jù)庫系統(tǒng) -自頂向下的方式構建二 分布式數(shù)據(jù)庫設計的內容： 1. 數(shù)據(jù)庫設計基礎-需求分析 1）數(shù)據(jù)需求 2）應用需求 應用的原發(fā)站點：發(fā)出應用請求的站點 應用在站點被激活的頻率 應用對數(shù)據(jù)對象訪問次數(shù)、類型和分布統(tǒng)計第13頁，共85頁。2. 數(shù)據(jù)庫設計（設計的核心任務） 全局模式設計 局部數(shù)據(jù)庫設計 數(shù)據(jù)分片設計 片段的位置分配設計三 分布式數(shù)據(jù)庫設計的目標： 確保數(shù)據(jù)庫數(shù)據(jù)和應用具有最大程度的本地性。 分布式數(shù)據(jù)的可用性和可靠性 工作負荷分布 存儲的能力和費用第14頁，共85頁。四 自頂向下的方式構建分布式數(shù)據(jù)庫需求分析全局概念模型全局邏輯模型分片設計系統(tǒng)實現(xiàn)試運

8、行及維護分布設計局部邏輯設計物理設計1 設計的步驟：第15頁，共85頁。2 數(shù)據(jù)庫的分片設計（1）. 什么叫“片段”？ 指在分布式數(shù)據(jù)庫系統(tǒng)中，某一站點上存儲的數(shù)據(jù)集合。（2）.分片設計的目的？ 產(chǎn)生全局數(shù)據(jù)的一個合理的劃分，從而使每個站點只獲得它所需要的數(shù)據(jù)，最大可能保證應用的本地性。（3）分片應遵循的一般規(guī)則：設：R = R1, R2, , Rn 1）完整性 即，tR, 則，必有t Ri ( i = 1,2, , n ) 2）可重構性 即，R = Ri ( i = 1,2, , n ) 或R = Ri ( i = 1, , n ) 3）不相交性 即，Ri Rj = (i,j= 1, , n

9、,且i j） 或Ri Rj = 主碼屬性(i ,j= 1, , n,且i j）第16頁，共85頁。（4）分片的基本類型和方法 水平分片，垂直分片，混合分片A 水平分片：對全關系進行選擇操作，把具有相同性質的元組進行分組，構成若干不相交的子集。初級分片和導出分片 初級分片：以關系自身屬性性質分組例1 S( S#, Sname, Age, Sex )define fragment S1 asselect * from S where Sex = M ；define fragment S2 asselect * from S where Sex = F；第17頁，共85頁。 導出分片：用其它關系的屬

10、性對某一全關系進行分組例2 設：全局關系 SC( S#, C#, Grade ) S( S#, Sname, Age, Sex )設計需求：按S的“性別”屬性（Sex）去劃分SCDefine fragment SC1 as select SC.S#, C#, Grade from SC, S where SC.S# = S.S# and S.Sex = MDefine fragment SC2 as select SC.S#, C#, Grade from SC, S where SC.S# = S.S# and S.Sex = F第18頁，共85頁。 B 垂直分片：利用投影操作把全關系的屬性

11、分成若干組，目標是把頻繁使用的屬性聚集在一起，且各片段只在鍵屬性下重疊。例3 設：全局關系EMP(E#,Name,Dept,Job,Sal,tel)Key = E# 垂直分片： EMP1(E#, Name, Sal, tel) EMP2(E#, Dept, Job)第19頁，共85頁。3 數(shù)據(jù)庫片段位置分配的設計兩種方式： 非冗余分配：一個片段映射到一個站點 冗余分配：一個片段映射到多個站點非冗余“最佳適應”分配法： 計算：Bij = k( Fkj * Nki ) 即，計算所有的應用在站點j上訪問片段i 的總次數(shù)。 對所有站點j確定j, 使得Bij = max( Bij )即，把片段Ri分配到

12、有最大訪問次數(shù)的站點j。i-片段序號j-站點序號k-應用序號Fkj-應用k在站點j上激活的頻率Rki-應用k對片段i 進行檢索訪問的次數(shù)(Read)Uki-應用k對片段i 進行更新訪問的次數(shù)Nki = Rki + Uki -應用k對片段i進行訪問的總次數(shù)第20頁，共85頁。冗余分配比較復雜，一般采用下列方法之一進行估算：-所有得益站點法：-附加復制法（1）“所有得益站點”法對所有站點確定非冗余分配方案。從全部結點中選擇一組站點，使得給這組站點分配片段Ri的一個拷貝所得到的檢索效益，大于從其它站點對Ri實施更新的代價。把片段Ri拷貝分配給該組站點第21頁，共85頁。（2）附加拷貝法對所有站點確定

13、非冗余分配方案。計算把片段Ri分配給所有站點所能得到的總效益fi（以及一個站點分得Ri所得到的效益）從分得片段Ri能夠獲取最大益處的站點起，對各站點依次附加片段Ri的一個拷貝，直到增加片段Ri不能使系統(tǒng)得到明顯效益（或者說效益增大“接近”fi ）為止。總結：數(shù)據(jù)庫片段及位置分配的設計所需要 的參數(shù)均從應用需求中得來，總結這些參數(shù)可用如下三個表表達：A 頻率表：各站點每一應用激活的次數(shù)B 劃分表：各實體的潛在水平分片規(guī)則C 極化表：給定站點發(fā)出一給定應用訪問一給定片段的概率第22頁，共85頁。需求分析全局概念模型全局邏輯模型分片設計系統(tǒng)實現(xiàn)試運行及維護分布設計局部邏輯設計物理設計頻率表劃分表極化

14、表第23頁，共85頁。分布式數(shù)據(jù)庫設計的一個例子訂票系統(tǒng)維護分布在三個網(wǎng)絡站點（與機場1，2，3處于同一地理區(qū)域）上的數(shù)據(jù)庫。數(shù)據(jù)庫存儲機場規(guī)程、班機起降和旅客訂票等數(shù)據(jù)。（1）概念設計-全局概念模式（E-R圖）第24頁，共85頁。（2）收集數(shù)據(jù)與其最相關的應用知識-用操作模式表示a 訂票: 用于旅客預訂機票。第25頁，共85頁。b 登記: 用于旅客登機登記任務記錄。第26頁，共85頁。c 起飛應用:查詢即將從一個機場起飛的30個班機信息。第27頁，共85頁。（3）在操作模式的基礎上，對每一實體估算應用的定量數(shù)據(jù)，建立邏輯訪問表例“班機”實體邏輯訪問表第28頁，共85頁。（4）分布需求分析a.

15、 頻率表：調研并給出在三個站點上使用各個應用的頻率（激活的次數(shù)）第29頁，共85頁。b.劃分表：分析各個實體各種可能的分片方式及其選擇性*基本劃分第30頁，共85頁。*導出劃分注釋表：第31頁，共85頁。c.極化表：調研并給出從一個站點發(fā)出一個應用所需要訪問某片段的概率。第32頁，共85頁。（5）飛機訂票系統(tǒng)的分布式設計a.為各個實體選擇合適的分片,原則:滿足本地性，不造成應用困難。對本例來予，各個實體采用水平分片： “機場” 由基于區(qū)域的基本水平分片（片段(F1F3)：機場1，機場2，機場3） “班機” 由基于起飛機場區(qū)域的導出水平分片（片段(A1A3) ：班機1，班機2，班機3） “旅客”

16、 由基于旅客訂票涉及的班機起飛機場所在區(qū)域的導出水平分片（片段(P1P7)：旅客1，旅客2，旅客3，旅客7）第33頁，共85頁。b.進行片段的非冗余分配：1）站點1：機場1，班機1，旅客12）站點2：機場2，班機2，旅客2 旅客4，旅客6，旅客73）站點3：機場3，班機3，旅客3 旅客5根據(jù)頻率表和極化表c.進行片段的冗余分配： 根據(jù)應用可以將旅客4.5.6分配在兩個站點上，旅客7分配在三個站點上。第34頁，共85頁。（6）重構局部模式第35頁，共85頁。第36頁，共85頁。第37頁，共85頁。本節(jié)要點1. 理解分布式數(shù)據(jù)庫系統(tǒng)的基本概念及特征，總結分布式數(shù)據(jù)庫分片設計方法。熟練掌握使用SQL

17、語句，定義全局關系模式的分片方法。2. 總結“自頂向下”設計分布式數(shù)據(jù)庫的方法。掌握從設計全局設計模式到各站點上局部模式的分布設計方法。3. 理解分布式數(shù)據(jù)庫片段分配設計方法的思想。第38頁，共85頁。2.分布式數(shù)據(jù)庫查詢處理一、分布式查詢處理的步驟查詢分析若該查詢屬于局部查詢，則執(zhí)行局部查詢處理后，即可結束。查詢分解把全局查詢或遠程查詢轉換成定義在全局關系上的關系代數(shù)表達式，并優(yōu)化該表達式。查詢本地化把一個全局關系上的查詢，轉化為對片段的局部查詢。全局查詢優(yōu)化：找出對各個片段局部查詢結果之間的最佳操作次序，使得代價最小。其重點在連接運算和并運算的優(yōu)化局部優(yōu)化：由確定的片段所在站點執(zhí)行第39頁

18、，共85頁。二、分布式查詢處理的代價QC估算： QC=I/O+通信代價T*通信代價T估算T = 傳輸次數(shù)（每次傳輸延遲時間+ 每次傳輸數(shù)據(jù)量/ 數(shù)據(jù)傳輸速率）= 傳輸次數(shù)（C0 + X / D）第40頁，共85頁。三、分布式查詢策略的重要性：例設：教學數(shù)據(jù)庫中：S(S#, Sname, Age, Sex) 10,000個元組， 存放在A站點（男/女各一半）SC(S#, C#, Grade) 1,000,000個元組， 存放在A站點（每人選課100門）C(C#, Cname, Teacher) 100,000個元組， 存放在B站點假設：每個元組的長度為100 bit; 通信系統(tǒng)傳輸速率為10,0

19、00bit / 秒；每次通信延遲時間為1秒。查詢：選修課名Maths 的男生的學號和姓名對于本例， C0 = 1秒，D = 10,000 bit / 秒第41頁，共85頁。解：SQL語句是： SELECT S.S#, Sname FROM S, SC, C WHERE S.S# = SC.S# AND SC.C# = C.C# AND SEX = M AND Cname = Maths策略1：把關系C傳到A站點；在A站點進行處理。T1 = 1 + (100,000 *100) / 10,000 16.7(分)第42頁，共85頁。策略2：先在A站點找出男生選課情況（每人平均選100門課），再根據(jù)

20、C#向B站點核查這些男生的選課是否是Maths。(結果在A站點)T3 = 2 * 500,000 *1秒 11.6 (天)策略3：先在B站點找出Maths元組（假設最多有10門），再把查找結果傳到A站點，在A站點繼續(xù)執(zhí)行查詢處理。T6 = 1 + 10* 100/10,000 1秒第43頁，共85頁。四、基于關系代數(shù)等價變換的查詢優(yōu)化例1 S(S#, Sname, Age, Sex) SC(S#, C#, Grade)其中，S 和SC都采取水平分片：用戶查詢：SELECT distinct Sname FROM S, SC WHERE S.S# = SC.S# and Sex = M and

21、Grade 90轉成關系代數(shù)表達式：Sname ( Sex = M Grade 90 ( S.S#=SC.S#( S SC ) ) )第44頁，共85頁。把關系代數(shù)表達式轉換成查詢樹并優(yōu)化從全局查詢到片段查詢的轉換第45頁，共85頁。優(yōu)化片段查詢樹a. 對于水平分片，檢查選擇運算（）與水平分片的條件（謂詞）。b. 對于垂直分片，注意消去不提供連接運算后所需要屬性的分支。第46頁，共85頁。例2 設：全局關系:EMP(E#, Ename, Sal, Dept, Dname)現(xiàn)采取垂直分片：查詢問題：SELECT Ename, SalFROM EMP查詢關系代數(shù)表達式Ename, Sal( EMP

22、 )第47頁，共85頁。第48頁，共85頁。五 基于半連接算法的全局查詢優(yōu)化1、半連接運算:由投影和連接操作導出的一種關系代數(shù)操作。設：關系R和S在屬性R.A=S.B上的半連接操作記為：RA=BS=R ( RA=BS )(B (S)=RA=BSA=BR=S ( SA=BR )(A (R)=SA=B或者:2、利用半連接運算實現(xiàn)連接運算S=RA=B(RA=BS)A=BS(SA=BR)A=BR或者:S=RA=B第49頁，共85頁。3.采用半連接運算實現(xiàn)連接運算的代價及優(yōu)化令：tuple(R) 表示關系R的元組數(shù) size(B) 表示屬性B的數(shù)據(jù)長度現(xiàn)假設，用戶希望在站點2上得到R 與 S自然連接的結

23、果RS網(wǎng)絡站點1站點2RS網(wǎng)絡站點1站點2(1)B(S)(2)傳送B(S)(3)R=RB(S)B(4)傳送R(5)RSB第50頁，共85頁?？偞鷥r：T半= 2C0 + C1 *size(B) * tuple(B(S) +size(R) * tuple(R) 采用半連接操作優(yōu)化的原理：兩個關系進行連接操作之前，去掉無用的無組，減少數(shù)據(jù)傳輸量。采用直接連接運算的總代價：T = C0 + C1 * size(R) * tuple(R)選擇半連接實現(xiàn)連接運算的原則：經(jīng)半連接操作產(chǎn)生少量元組。4. 查詢優(yōu)化策略1）計算各種半連接運算的代價。2）計算直接連接運算的代價。3）比較并選出最優(yōu)者。第51頁，共8

24、5頁。六 基于直接連接算法的查詢優(yōu)化1、利用站點依賴信息的連接算法R1R2=F11F21(F12F22)其成立的條件是什么?第52頁，共85頁。條件： A(F11) A(F12) = A(F21) A(F22) = A(F11) A(F22) = A(F12) A(F21) = 站點依賴：設：RiA、RjA、SiA 、SjA分別表示關系R、S在站點i、j的A屬性上的取值。若對于i j ,有： RiA SjA = ,則稱關系R和S在屬性A上站點依賴。性質：若關系R和S在屬性A上站點依賴，則：iRS=(RiSi)第53頁，共85頁。推論：* 如果R和S在屬性A上站點依賴，B A,則，R和S在屬性B

25、上站點依賴。* 如果R和S在屬性A上站點依賴， S和T在屬性B上站點依賴，則：RS=(RiSiTiTi）使用站點依賴算法實現(xiàn)直接連接運算的優(yōu)點:1）無數(shù)據(jù)傳送2）可進行并行計算3）可利用本地索引在查詢優(yōu)化過程中，可以判斷什么時候使用站點依賴算法（P87）第54頁，共85頁。2、分片和復制算法當查詢不能在無數(shù)據(jù)傳送方式下處理，可采用分片和復制算法，算法的原理： 選擇一組站點，將查詢中的某一個關系的所有片段分布到這些站點上，然后把查詢中的其余關系復制到每一個選定的站點上。優(yōu)點：1）可進行并行計算 2）在一定程度上可利用本地索引選擇方法：從假定某一關系分片，其余關系復制，計算代價，然后再選擇另一關系

26、為分片，最后從中選擇代價最小的方案。第55頁，共85頁。本節(jié)重點1. 總結分布式數(shù)據(jù)庫查詢優(yōu)化的主要步驟，并與集中式數(shù)據(jù)庫查詢優(yōu)化相比較。2. 總結利用半連接算法實現(xiàn)直接連接運算的全局查詢優(yōu)化方法特點。在什么條件下可以利用半連接算法實現(xiàn)直接連接運算？第56頁，共85頁。3.分布式事務管理及恢復的討論一、分布式事務概述1.事務的特點分布式數(shù)據(jù)庫的事務稱為全局事務。一個全局事務在執(zhí)行時分解為由若干與相應站點有關的操作序列組成的“子事務”。1. 原子性 2. 一致性（或可串行性）3. 隔離性 4. 持久性 5. 系統(tǒng)效率6. 系統(tǒng)可用性：分布式事務既不能影響本站點上事務的執(zhí)行，也不能影響其它站點上事

27、務的執(zhí)行第57頁，共85頁。Begin Transaction 開始事務T1T2TnCommit / Abort (或Rollback) 結束事務子事務或操作序列全局事務3 分布式事務代理執(zhí)行機制2. 分布式事務的結構事務代理的概念：一個事務代理就是一個站點上的一個進程第58頁，共85頁。應用請求（源站點總代理根代理）RollbackCommit總代理（根代理）子事務1失敗子事務1成功子事務代理n子事務代理1Begin Transaction子事務n失敗子事務n成功第59頁，共85頁。例銀行轉帳事務：把帳號FROM_ACC上數(shù)量為AMOUNT的資金，轉入帳號TO_ACC。全局應用事務：read

28、(AMOUNT, FROM_ACC, TO_ACC);begin transactionselect BALANCE into FROM_AMOUNTfrom ACCOUNT_TABLEwhere ACCOUNT_NO = FROM_ACC;if FROM_AMOUNT - AMOUNT 0then abortelse beginupdate ACCOUNT_TABLEset BALANCE = BALANCE - AMOUNTwhere ACCOUNT_NO = FROM_ACC;update ACCOUNT_TABLEset BALANCE = BALANCE + AMOUNTwhere

29、ACCOUNT_NO = TO_ACC;commitend第60頁，共85頁。設：轉出帳戶在源站點上。ROOT_AGENT:read(AMOUNT, FROM_ACC, TO_ACC);begin transactionselect BALANCE into FROM_AMOUNTfrom ACCOUNT_TABLEwhere ACCOUNT_NO = FROM_ACC;if FROM_AMOUNT - AMOUNT 0then abortelse beginupdate ACCOUNT_TABLEset BALANCE = BALANCE - AMOUNTwhere ACCOUNT_NO =

30、 FROM_ACC;create AGENT;send to AGENT(AMOUNT, TO_ACC);waittingcommit / abortend第61頁，共85頁。AGENT（子代理）:begin transactionreceive from ROOT_AGENT( AMOUNT,TO_ACC );update ACCOUNT_TABLEset BALANCE = BALANCE + AMOUNTwhere ACCOUNT_NO = TO_ACC;send to ROOT_AGENT(SUCCESS / FAIL)waittingcommit / abort第62頁，共85頁。二

31、. 分布式事務的兩階段提交協(xié)議2-PC:Two-Phase Commitment Protocal協(xié)調者日志參與者。參與者參與者日志日志日志兩階段提交協(xié)議的活動機制：第63頁，共85頁。初始協(xié)調者寫end of trans到日志初始參與者寫begin transaction等待準備提交寫ready到日志有要求撤消的？寫abort到日志提交撤消就緒消息類型?撤消提交準備撤消提交全局撤消全局提交寫abort到日志no寫commit到日志no寫abort到日志abort寫commit到日志commit第64頁，共85頁。兩階段提交協(xié)議的執(zhí)行過程：1）表決階段：對當前事務形成一個決定。 協(xié)調者： 寫“

32、開始事務”日志； 向各個參與者發(fā)出“準備”命令； 進入等待狀態(tài)。 對于每一個參與者 參與者接收“準備”消息； 參與者檢查子事務，確定是否提交子事務： Case1:可以提交子事務： 參與者寫“就緒”日志； 向協(xié)調者發(fā)“建議提交”消息； 參與者進入“就緒”狀態(tài)。 Case2:不可以提交子事務： 參與者寫“撤消”日志； 向協(xié)調者發(fā)“建議撤消”消息； 參與者進入“撤消”狀態(tài)。第65頁，共85頁。 協(xié)調者接收到所有參與者的回答后，作出決定：Case1: 若所有參與者發(fā)出“建議提交”的消息，則，協(xié)調者作出提交全局事務的決定。 協(xié)調者寫提交日志； 協(xié)調者發(fā)出“全局提交”消息； 協(xié)調者進入“提交”狀態(tài)。Cas

33、e2: 若發(fā)現(xiàn)某參與者發(fā)出“建議撤消”的消息，則，協(xié)調者作出撤消全局事務的決定。 協(xié)調者寫撤消日志； 協(xié)調者發(fā)出“全局撤消”消息； 協(xié)調者進入“撤消”狀態(tài)。 “一票否決”制！2）執(zhí)行階段 對于每一個處于“就緒”狀態(tài)的參與者： 參與者根據(jù)協(xié)調者發(fā)出的全局事務處理指令，或者撤消子事務，或者提交子事務第66頁，共85頁。 參與者發(fā)出“確認”(ACK)收到全局事務處理指令消息。 參與者進入“撤消”或“提交”狀態(tài)。 協(xié)調者寫“結束事務”日志。兩階段提交協(xié)議的特點： 參與者有權單方面撤消事務。 參與者作出“建議提交” 或“建議撤消”決定之后，不能“翻悔”。 處于“就緒”狀態(tài)的參與者可能進入提交狀態(tài)，或撤消

34、狀態(tài)。 協(xié)調者和參與者可能進入互相等待狀態(tài)。第67頁，共85頁。1. 試比較集中式、分布式事務的特點。2. 總結分布式數(shù)據(jù)庫2-PC的特點，并指出它所存在的問題。本節(jié)重點第68頁，共85頁。4.分布式數(shù)據(jù)庫并發(fā)控制機制一、分布式并發(fā)控制概述1 分布式并發(fā)控制的目的：為并發(fā)執(zhí)行的全局事務，產(chǎn)生一個可串行化調度。2 局部調度：每個站點上的調度稱為局部調度3 全局調度：數(shù)據(jù)庫系統(tǒng)全局事務的調度。4全局調度的可串行性局部調度的可串行性！局部調度的可串行性：全局調度的可串行性？問題：一個數(shù)據(jù)對象x，可能存在多個副本x1, x2, , xn。第69頁，共85頁。T1: Read(y);y := y 15;

35、Write(y);Commit;T2: Read(y);y := y * 2;Write(y);Commit;站點1 調度S1 = R1, W1, C1, R2, W2, C2 站點2 調度S2 = R2, W2, C2 , R1, W1, C1 設：站點1，站點2上都有y的副本，且都執(zhí)行事務T1, T2。全局調度不可串行！5. 全局調度的沖突可串行性應滿足的條件:單副本控制協(xié)議1) 每一個局部調度是沖突可串行化的。2) 任意兩個沖突操作在它們同時出現(xiàn)的各個局部調度中，必須有相同的執(zhí)行順序。第70頁，共85頁。二、并發(fā)控制法并發(fā)控制算法悲觀法樂觀法封鎖法時標排序法混合法加鎖法時標排序法集中式加

36、鎖主副本加鎖分布式加鎖基本時標排序法多版本時標排序保守時標排序第71頁，共85頁。1）集中式加鎖法:網(wǎng)絡中某一個站點被指定為主站點，用于存放整個分布式數(shù)據(jù)庫的加鎖表，負責整個系統(tǒng)事務的加鎖.2）主副本加鎖法：每個數(shù)據(jù)對象指定一個主副本，不同數(shù)據(jù)對象的主副本放在不同站點上。算法：對主副本加鎖；執(zhí)行更新操作；開鎖3）分布式加鎖算法：鎖的管理由各個站點調度器參與、協(xié)調，本地調度器負責本站數(shù)據(jù)加鎖。算法：對全部副本加鎖；執(zhí)行更新操作；開鎖第72頁，共85頁。三、分布式數(shù)據(jù)庫并發(fā)控制的加鎖技術1. 分布式數(shù)據(jù)庫加鎖準則 讀，鎖一個；寫，鎖全部(ROWA協(xié)議)。 遵守鎖的相容性規(guī)則 遵守兩段鎖協(xié)議（Two

37、 Phase Locking-2PL) 持有X鎖的事務，必須到結束事務才能開鎖。2、死鎖管理1）全局死鎖：分布式數(shù)據(jù)庫中，涉及多個站點的死鎖稱為全局死鎖。第73頁，共85頁。站點A站點B事務T1持有對X的鎖事務T2持有對Y的鎖事務T2請求對X的鎖事務T1請求對Y的鎖T2等待T1完成釋放對X的鎖T1等待T2完成釋放對Y的鎖第74頁，共85頁。2）全局等待圖（GWFG）站點A:擁有x 、y的副本；T1: read(x), write(y)站點B:擁有y 、z的副本；T2: read(y), write(z)站點C:擁有z 的副本； T3: read(z), write(x)T1T2T3Xyz第75

38、頁，共85頁。3）死鎖的檢測A 集中式死鎖檢測法 指定某站點上的鎖管理器作為全局死鎖檢測器 其余站點周期地向全局死鎖檢測器發(fā)送LWFG 全局死鎖檢測器產(chǎn)生GWFG，并檢測有無回路B 分布式死鎖檢測法 每個站點都有死鎖檢測器，負責檢測本地可能的死鎖。 每個站點按照一定規(guī)則，向相關站點發(fā)送潛在的死鎖回路圖。4）死鎖的解決原則：撤消并恢復代價最小的事務。 撤消并恢復年輕的事務。 撤消并恢復占用資源較少的事務。 撤消并恢復具有最短運行時間的事務。第76頁，共85頁。四 并發(fā)控制的時標技術1. 時標:唯一識別一個事務，并用于對事務進行排序的標識符。2. 時標的構成：“本地計數(shù)器值， 站點標識符3. 時標

39、的創(chuàng)建：一個事務Ti 初始化時，事務管理器給該事務分配一個時標ts(Ti )4. 時標排序（TO）規(guī)則：已知Qi和Qj是分別屬于事務Ti和Tj沖突操作。若ts(Ti) ts(Tj) , 則Qi在Qj之前執(zhí)行。5、基本時標法第77頁，共85頁。規(guī)則：1）每個事務在本地站點開始時被賦以一個全局唯一的時標。3）事務的每個讀或寫操作都有該事務的時標。2）如果事務被重新啟動，則被賦予新的時標。4）在事務結束之前，不對數(shù)據(jù)庫進行物理操作。5）對于數(shù)據(jù)庫每個數(shù)據(jù)對象x，記錄對它進行讀操作和寫操作的最大時標RTM(x)和WTM(x)基本時標法的執(zhí)行過程：1）設TS是對數(shù)據(jù)對象x進行讀操作的當前時標。若TS WTM(x)， 則， 拒絕該操作；并使發(fā)出該操作的事務用新時標重新啟動；否則， 執(zhí)行讀操作，且使： RTM(x) = max（