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

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

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

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

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

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

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

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

8、行及維護分布設(shè)計局部邏輯設(shè)計物理設(shè)計1 設(shè)計的步驟：第15頁，共85頁。2 數(shù)據(jù)庫的分片設(shè)計（1）. 什么叫“片段”？ 指在分布式數(shù)據(jù)庫系統(tǒng)中，某一站點上存儲的數(shù)據(jù)集合。（2）.分片設(shè)計的目的？ 產(chǎn)生全局?jǐn)?shù)據(jù)的一個合理的劃分，從而使每個站點只獲得它所需要的數(shù)據(jù)，最大可能保證應(yīng)用的本地性。（3）分片應(yīng)遵循的一般規(guī)則：設(shè)：R = R1, R2, , Rn 1）完整性 即，tR, 則，必有t Ri ( i = 1,2, , n ) 2）可重構(gòu)性 即，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 水平分片：對全關(guān)系進行選擇操作，把具有相同性質(zhì)的元組進行分組，構(gòu)成若干不相交的子集。初級分片和導(dǎo)出分片 初級分片：以關(guān)系自身屬性性質(zhì)分組例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頁。 導(dǎo)出分片：用其它關(guān)系的屬

10、性對某一全關(guān)系進行分組例2 設(shè)：全局關(guān)系 SC( S#, C#, Grade ) S( S#, Sname, Age, Sex )設(shè)計需求：按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 垂直分片：利用投影操作把全關(guān)系的屬性

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

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

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

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

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

16、 由基于旅客訂票涉及的班機起飛機場所在區(qū)域的導(dǎo)出水平分片（片段(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ù)應(yīng)用可以將旅客4.5.6分配在兩個站點上，旅客7分配在三個站點上。第34頁，共85頁。（6）重構(gòu)局部模式第35頁，共85頁。第36頁，共85頁。第37頁，共85頁。本節(jié)要點1. 理解分布式數(shù)據(jù)庫系統(tǒng)的基本概念及特征，總結(jié)分布式數(shù)據(jù)庫分片設(shè)計方法。熟練掌握使用SQL

17、語句，定義全局關(guān)系模式的分片方法。2. 總結(jié)“自頂向下”設(shè)計分布式數(shù)據(jù)庫的方法。掌握從設(shè)計全局設(shè)計模式到各站點上局部模式的分布設(shè)計方法。3. 理解分布式數(shù)據(jù)庫片段分配設(shè)計方法的思想。第38頁，共85頁。2.分布式數(shù)據(jù)庫查詢處理一、分布式查詢處理的步驟查詢分析若該查詢屬于局部查詢，則執(zhí)行局部查詢處理后，即可結(jié)束。查詢分解把全局查詢或遠(yuǎn)程查詢轉(zhuǎn)換成定義在全局關(guān)系上的關(guān)系代數(shù)表達式，并優(yōu)化該表達式。查詢本地化把一個全局關(guān)系上的查詢，轉(zhuǎn)化為對片段的局部查詢。全局查詢優(yōu)化：找出對各個片段局部查詢結(jié)果之間的最佳操作次序，使得代價最小。其重點在連接運算和并運算的優(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è)：教學(xué)數(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站點假設(shè)：每個元組的長度為100 bit; 通信系統(tǒng)傳輸速率為10,0

19、00bit / 秒；每次通信延遲時間為1秒。查詢：選修課名Maths 的男生的學(xué)號和姓名對于本例， 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：把關(guān)系C傳到A站點；在A站點進行處理。T1 = 1 + (100,000 *100) / 10,000 16.7(分)第42頁，共85頁。策略2：先在A站點找出男生選課情況（每人平均選100門課），再根據(jù)

20、C#向B站點核查這些男生的選課是否是Maths。(結(jié)果在A站點)T3 = 2 * 500,000 *1秒 11.6 (天)策略3：先在B站點找出Maths元組（假設(shè)最多有10門），再把查找結(jié)果傳到A站點，在A站點繼續(xù)執(zhí)行查詢處理。T6 = 1 + 10* 100/10,000 1秒第43頁，共85頁。四、基于關(guān)系代數(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轉(zhuǎn)成關(guān)系代數(shù)表達式：Sname ( Sex = M Grade 90 ( S.S#=SC.S#( S SC ) ) )第44頁，共85頁。把關(guān)系代數(shù)表達式轉(zhuǎn)換成查詢樹并優(yōu)化從全局查詢到片段查詢的轉(zhuǎn)換第45頁，共85頁。優(yōu)化片段查詢樹a. 對于水平分片，檢查選擇運算（）與水平分片的條件（謂詞）。b. 對于垂直分片，注意消去不提供連接運算后所需要屬性的分支。第46頁，共85頁。例2 設(shè)：全局關(guān)系:EMP(E#, Ename, Sal, Dept, Dname)現(xiàn)采取垂直分片：查詢問題：SELECT Ename, SalFROM EMP查詢關(guān)系代數(shù)表達式Ename, Sal( EMP

22、 )第47頁，共85頁。第48頁，共85頁。五 基于半連接算法的全局查詢優(yōu)化1、半連接運算:由投影和連接操作導(dǎo)出的一種關(guān)系代數(shù)操作。設(shè)：關(guān)系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) 表示關(guān)系R的元組數(shù) size(B) 表示屬性B的數(shù)據(jù)長度現(xiàn)假設(shè)，用戶希望在站點2上得到R 與 S自然連接的結(jié)

23、果RS網(wǎng)絡(luò)站點1站點2RS網(wǎng)絡(luò)站點1站點2(1)B(S)(2)傳送B(S)(3)R=RB(S)B(4)傳送R(5)RSB第50頁，共85頁。總代價：T半= 2C0 + C1 *size(B) * tuple(B(S) +size(R) * tuple(R) 采用半連接操作優(yōu)化的原理：兩個關(guān)系進行連接操作之前，去掉無用的無組，減少數(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) = 站點依賴：設(shè)：RiA、RjA、SiA 、SjA分別表示關(guān)系R、S在站點i、j的A屬性上的取值。若對于i j ,有： RiA SjA = ,則稱關(guān)系R和S在屬性A上站點依賴。性質(zhì)：若關(guān)系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、分片和復(fù)制算法當(dāng)查詢不能在無數(shù)據(jù)傳送方式下處理，可采用分片和復(fù)制算法，算法的原理： 選擇一組站點，將查詢中的某一個關(guān)系的所有片段分布到這些站點上，然后把查詢中的其余關(guān)系復(fù)制到每一個選定的站點上。優(yōu)點：1）可進行并行計算 2）在一定程度上可利用本地索引選擇方法：從假定某一關(guān)系分片，其余關(guān)系復(fù)制，計算代價，然后再選擇另一關(guān)系

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

27、務(wù)的執(zhí)行第57頁，共85頁。Begin Transaction 開始事務(wù)T1T2TnCommit / Abort (或Rollback) 結(jié)束事務(wù)子事務(wù)或操作序列全局事務(wù)3 分布式事務(wù)代理執(zhí)行機制2. 分布式事務(wù)的結(jié)構(gòu)事務(wù)代理的概念：一個事務(wù)代理就是一個站點上的一個進程第58頁，共85頁。應(yīng)用請求（源站點總代理根代理）RollbackCommit總代理（根代理）子事務(wù)1失敗子事務(wù)1成功子事務(wù)代理n子事務(wù)代理1Begin Transaction子事務(wù)n失敗子事務(wù)n成功第59頁，共85頁。例銀行轉(zhuǎn)帳事務(wù)：把帳號FROM_ACC上數(shù)量為AMOUNT的資金，轉(zhuǎn)入帳號TO_ACC。全局應(yīng)用事務(wù)：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頁。設(shè)：轉(zhuǎn)出帳戶在源站點上。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、. 分布式事務(wù)的兩階段提交協(xié)議2-PC:Two-Phase Commitment Protocal協(xié)調(diào)者日志參與者。參與者參與者日志日志日志兩階段提交協(xié)議的活動機制：第63頁，共85頁。初始協(xié)調(diào)者寫end of trans到日志初始參與者寫begin transaction等待準(zhǔn)備提交寫ready到日志有要求撤消的？寫abort到日志提交撤消就緒消息類型?撤消提交準(zhǔn)備撤消提交全局撤消全局提交寫abort到日志no寫commit到日志no寫abort到日志abort寫commit到日志commit第64頁，共85頁。兩階段提交協(xié)議的執(zhí)行過程：1）表決階段：對當(dāng)前事務(wù)形成一個決定。 協(xié)調(diào)者： 寫“

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

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

34、狀態(tài)。 協(xié)調(diào)者和參與者可能進入互相等待狀態(tài)。第67頁，共85頁。1. 試比較集中式、分布式事務(wù)的特點。2. 總結(jié)分布式數(shù)據(jù)庫2-PC的特點，并指出它所存在的問題。本節(jié)重點第68頁，共85頁。4.分布式數(shù)據(jù)庫并發(fā)控制機制一、分布式并發(fā)控制概述1 分布式并發(fā)控制的目的：為并發(fā)執(zhí)行的全局事務(wù)，產(chǎn)生一個可串行化調(diào)度。2 局部調(diào)度：每個站點上的調(diào)度稱為局部調(diào)度3 全局調(diào)度：數(shù)據(jù)庫系統(tǒng)全局事務(wù)的調(diào)度。4全局調(diào)度的可串行性局部調(diào)度的可串行性！局部調(diào)度的可串行性：全局調(diào)度的可串行性？問題：一個數(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 調(diào)度S1 = R1, W1, C1, R2, W2, C2 站點2 調(diào)度S2 = R2, W2, C2 , R1, W1, C1 設(shè)：站點1，站點2上都有y的副本，且都執(zhí)行事務(wù)T1, T2。全局調(diào)度不可串行！5. 全局調(diào)度的沖突可串行性應(yīng)滿足的條件:單副本控制協(xié)議1) 每一個局部調(diào)度是沖突可串行化的。2) 任意兩個沖突操作在它們同時出現(xiàn)的各個局部調(diào)度中，必須有相同的執(zhí)行順序。第70頁，共85頁。二、并發(fā)控制法并發(fā)控制算法悲觀法樂觀法封鎖法時標(biāo)排序法混合法加鎖法時標(biāo)排序法集中式加

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

37、 Phase Locking-2PL) 持有X鎖的事務(wù)，必須到結(jié)束事務(wù)才能開鎖。2、死鎖管理1）全局死鎖：分布式數(shù)據(jù)庫中，涉及多個站點的死鎖稱為全局死鎖。第73頁，共85頁。站點A站點B事務(wù)T1持有對X的鎖事務(wù)T2持有對Y的鎖事務(wù)T2請求對X的鎖事務(wù)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 分布式死鎖檢測法 每個站點都有死鎖檢測器，負(fù)責(zé)檢測本地可能的死鎖。 每個站點按照一定規(guī)則，向相關(guān)站點發(fā)送潛在的死鎖回路圖。4）死鎖的解決原則：撤消并恢復(fù)代價最小的事務(wù)。 撤消并恢復(fù)年輕的事務(wù)。 撤消并恢復(fù)占用資源較少的事務(wù)。 撤消并恢復(fù)具有最短運行時間的事務(wù)。第76頁，共85頁。四 并發(fā)控制的時標(biāo)技術(shù)1. 時標(biāo):唯一識別一個事務(wù)，并用于對事務(wù)進行排序的標(biāo)識符。2. 時標(biāo)的構(gòu)成：“本地計數(shù)器值， 站點標(biāo)識符3. 時標(biāo)

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