分布式數據庫系統(tǒng)的設計.ppt

1、徐俊剛 （),分布式數據庫系統(tǒng)及其應用,2009年2月2009年6月,分布式數據庫系統(tǒng)設計概述 自頂向下設計分布式數據庫 DATAID-D方法 實例研究：飛機訂票系統(tǒng) 自底向上設計分布式數據庫,分布式數據庫系統(tǒng)設計,第2章,分布式數據庫設計概述,1,創(chuàng)建方法,組合法,剖析網絡功能 剖析原有數據庫系統(tǒng) 解決數據的一致性、完整性和可靠性 難度較大 通常是異構或者同構異質DDBS,分布式數據庫設計概述,1,重構法,根據實現環(huán)境和用戶需求 按照DDBS的設計思想和方法 從總體設計做起，包括LDBS,重新建立一個DDBS 可有效解決數據一致性、完整性和可靠性問題。 通常是同構異質或同構同質DDBS,DD

2、BS設計,DDB設計,應用設計,全局模式設計,局部數據庫設計,相關應用需求,各個應用的原發(fā)站點,各個應用在每個站點的激活頻率,各個應用對要求訪問數據對象的訪問次數、類型和統(tǒng)計分布,分片和分布,DDBS 設計目標,本地性或近地性,存儲能力和費用,盡量減少通信次數和通信量，90/10準則,分片和分布方案（本地和遠程訪問次數）擇優(yōu),控制數據適當冗余,冗余增加了可靠性、可用性，提高了效率,維護數據一致性開銷增加,工作負荷分布,各站點可以分擔整個工作任務,本地性降低,DDBS 設計方法,自頂向下方法（重構法）,混合方法,自底向上方法（組合法）,假若有全局關系R 被分片為子關系(片段)集合 R = R1,

3、 R2, , Rn, 則 R滿足 完整性 ?x R, RiR 必有 xRi ，i=1,2,n 可重構性 存在函數 g 使得R = g(R1, R2, , Rn) 即，R= Ri (水平分片）,R= Ri （垂直分片） 不相交性 Ri Rj =空集,ij,i,j=1,2,n(水平分片) Ri Rj =主鍵屬性,i,j=1,2,n(垂直分片),分片原則,職工關系 E (e#, name, loc, sal,) 查詢: Qa: select * Qb: select * from E from E where loc=Sa where loc=Sb and and .,舉例,e# NM Loc Sa

4、l E,5,7,8,Sa,1000,Sally,Sb,2500,Tom,Sa,500,Joe,e# NM Loc Sal,e# NM Loc Sal,5,8,Sa,1000,Tom,Sa,500,Joe,7,Sb,2500,Sally,.,.,.,.,F,站點Sa,站點 Sb,舉例,基本水平分片 以關系自身的屬性性質為基礎，執(zhí)行“選擇”操作，將關系分割成若干個不相交的片段。 R = R1, R2 R1 = loc=Sa(E) R2 = loc=Sb(E),基本水平分片,若 R = R1, R2, , Rn, 則 完整性 對于每一個元組 tR, RiR 使得 tRi 不相交性 對tRi, Rj

5、使得 tRj, i j 可重構性 操作是 (可以忽略, 因為完整性就蘊含著) R = R1, R2, , Rn P = p1, p2, , pn是一簡單謂詞集合，為保證分片的正確性，P必須是： 完整的：同一分片中的任意兩個元組被應用同樣概率訪問。 最小的：集合P中的所有謂詞與應用密切相關。 具有完整性和最小性不是必要條件, 但是對于簡化分配問題有好處,基本水平分片,例子 EMP ( E#, NAME, DEPT, JOB, SAL, TEL, ) DEPT=1,2 JOB=P, -P 假定，應用經常查詢的內容是屬于部門1且是程序員的職員。 則可能有的水平分段限定 P= DEPT=1 （不是完整

6、的） P=DEPT=1, JOB=P （是完整的、最小的） P=DEPT=1, JOB=P, SAL500 （完整的，不是最小的）,基本水平分片,如何保證分片原則,“手工”檢查! e.g., R1 = loc=Sa E ; R2 = loc=Sb E 生成具有滿足分段原則的限定謂詞,基本水平分片,設有關系 E (e#,name,Loc,sal,A,), 查詢使用的簡單謂詞（Ai Value）是: A5, Loc = Sa, Loc = Sb 下一步: - 生成 “小項” 謂詞 - 消除無用謂詞 給定簡單謂詞集 Pr= p1, p2,. pn , 則“小項”謂詞（minterm predicat

7、e）形式: p1* p2* pn* 這里 pk* 是 pk 或是 pk,謂詞生成舉例,(1) A5 Loc=SA Loc=SB (2) A5 Loc=SA (Loc=SB) (3) A5 (Loc=SA) Loc=SB (4) A5 (Loc=SA) (Loc=SB) (5) A5) Loc=SA Loc=SB (6) A5) Loc=SA (Loc=SB) (7) A5) (Loc=SA) Loc=SB (8) A5) (Loc=SA) (Loc=SB),小項謂詞選擇,(9) (A5 Loc=SA Loc=SB (10) (A5 Loc=SA (Loc=SB) (11) (A5 (Loc=S

8、A) Loc=SB (12) (A5 (Loc=SA) (Loc=SB) (13) (A5) Loc=SA Loc=SB (14) (A5) Loc=SA (Loc=SB) (15) (A5) (Loc=SA) Loc=SB (16) (A5) (Loc=SA) (Loc=SB),小項謂詞選擇,R2:5 A 10 Loc=SA R3:5 A 10 Loc=SB R6:A 5 Loc=SA R7:A 5 Loc=SB R10:A 10 Loc=SA R11:A 10 Loc=SB,分片結果,注:無用段的消除依賴于應用的語義,e.g.: 如果 LOC 可以是 SA, SB, 則最終分段集合應該加上

9、 R4:5 A 10 Loc SA Loc SB R8:A 5 Loc SA Loc SB R12:A 10 Loc SA Loc SB,小項選擇率（minterm selectivity） 對某一給定小項謂詞用戶查詢可能選擇到的元組數 訪問頻率（Access frequency）用戶應用訪問數據的頻率 小項訪問頻率可以通過用戶查詢頻率獲得,分片數量信息,例子 E(#, NM, LOC, SAL,) 有查詢應用 Qa: select *Qb: select * from Efrom E where LOC=Sa where LOC=Sb and and .,如何選擇小項謂詞舉例,(1) Pr

10、= R1 = E (2) Pr = LOC=Sa, LOC=Sb R2= loc=Sa E, loc=Sb E (3) Pr = LOC=Sa, LOC=Sb, Sal1000 R3= loc=Sa sal1000 E, loc=Sa sal1000 E, loc=Sb sal1000E, loc=Sb sal1000 E ,三種選擇,Loc=Sa sal 1000,Loc=Sa sal 1000,Loc=Sb sal 1000,Loc=Sb sal 1000,R1,R3,R2,Qa: Select loc = Sa .,Qb: Select loc = Sb .,圖示,Loc=Sa sal

11、1000,Loc=Sa sal 1000,Loc=Sb sal 1000,Loc=Sb sal 1000,R1,Qa: Select loc = Sa .,Qb: Select loc = Sb .,此處元組有較 高的選擇概率,此處元組選 擇概率較低,分段內元組選擇概率不等 因此 R1 不好.,理由,Loc=Sa sal 1000,Loc=Sa sal 1000,Loc=Sb sal 1000,Loc=Sb sal 1000,R2,Qa: Select loc = Sa .,Qb: Select loc = Sb .,元組選擇 概率相等,因此 R2好.,R3不好 .,理由,導出分片 從另一個關

12、系的屬性性質或水平分片推導出來 例子 SC(S#, C#, GRADE) S ( S#, SNAME, AGE, SEX) 要求： 將SC劃分為男生各門課成績和女生的各門成績,導出水平分片,按S的屬性導出 Define fragment SC1 as Select SC.S#,C#,GRADE From SC, S Where SC.S#=S.S# and SEX=M Define fragment SC2 as Select SC.S#,C#,GRADE From SC, S Where SC.S#=S.S# and SEX=F 按S的水平分片（SF/SM）導出 Define fragmen

13、t SC1 as Select * From SC Where S# in (Select SF.S from SF) Define fragment SC2 as Select * From SC Where S# in (Select SM.S from SM),導出水平分片例子,通過“投影”操作把一個全局關系的屬性分成若干組，基本目標是將使用頻繁的屬性聚集在一起 全局關系R=Ri,i=1,2,n 如果屬性AR,必有ARi,i=1,2,n,而且RiRj=Ap,ij，Ap為R的碼或元組標識符，則稱Ri,i=1,2,n是關系R的一個垂直分片。 如果屬性AR,必有ARi,i=1,2,n,而且Ri

14、Rj=（Ap, A-p),ij，A-p為R的一個或多個非碼屬性時，稱Ri,i=1,2,n是關系R的一個垂直群集。,垂直分片和垂直群集,EMP(E#, NAME, SAL, TEL, MAGNUM, DEPT) 假定 Key: E# 主要應用: Sa 站點查詢NAME, SAL, TEL; Sb 站點查詢NAME, MAGNUM, DEPT 垂直分片:EMP1(E#, NAME, SAL, TEL) EMP2(E#, MAGNUM, DEPT) 垂直群集:EMP1(E#, NAME, SAL, TEL) EMP2(E#, NAME, MAGNUM, DEPT),垂直分片/垂直群集例子,E1,E,

15、E2,垂直分片例子,例子: E1(#,NM,LOC) E2(#,SAL) E(#,NM,LOC,SAL) E1(#,NM) E2(#,LOC) E3(#,SAL),?,垂直分片設計,非鍵屬性 A1, A2,An 應用 Q1, Q2,.,Qm freq(Qi) = Qi 的訪問頻率,屬性的親和關系,R1K,A1,A2,A3 R2K,A4,A5,屬性親和矩陣,行列調整尋找分割點,屬性和矩陣,窮舉屬性親和矩陣的列排列 行與列要同時調整 發(fā)現好的 “分割點” 極大化每個分割內的親合力（affinity）, 極小化跨分割的訪問,垂直分片算法,水平 基本： R 根據 local屬性 導出 根據外鍵關系 垂

16、直 R,分片小結,混合分段,R,R1,R2,R11,R12,R21,R22,水平,垂直,分片小結,混合分段的重構,R11,R12,R21,R22,水平,垂直,U,在滿足用戶需求的前提下, 把設計好的數據片段分配到相應的站點上存儲 例子: E(#,NM,LOC,SAL) R1 = loc=Sa E ; R2 = loc=Sb E Qa: select where loc=Sa. Qb: select where loc=Sb,Site a,Site b,R1,R2 存 放在哪?,?,分配方法,非冗余分配設計方法,最佳適應法,其他方法,冗余分配的設計方法,所有得益站點法,附加復制法,應用需求,確定

17、非復制問題的解 確定一組站點分配副本,確定非復制問題的解 從最有益處增加副本 到附加復制無好處為止,什么是段的最好配置/什么是最好的冗余副本數: 極小化查詢響應時間 極大化吞吐量 極小化 “代價” . 約束? 有效的存儲空間 有效的帶寬, 站點處理能力, 保持 90% 的響應時間低于 X（如0.5秒） .,單個片段 F 站點 S1, Sm 變量 X1, , Xm 0 如果 F 不在 Sj上存儲 1 如果 F 在 Sj上存儲 Total cost = Read Cost + Write Cost + Storage Cost 確定 Xj 的值, 1 j m, 使總代價極小,Xj =,讀代價,Re

18、ad cost = ti MIN Cij i:讀申請源站點 ti: 站點Si上的讀申請激活次數 Cij: 從 Si讀Sj站點分段F的代價,i=1,m,j,寫代價,Write cost = Xj ui Cij i: 寫申請源站點 j: 被更新站點 Xj: 0 if F not stored at Sj 1 if F stored at Sj ui: 站點 Si 上更新激活次數 Cij: 從站點 Si 更新 Sj 分段 F 的代價,i=1,j=1,m,m,Updates,ui,存儲代價,Store Cost = Xi di Xi: 0 if F not stored at Si 1 if F st

19、ored at Si di: 站點 Si 存儲分段 F 的代價,i=1,m,目標函數,min ti MIN Cij + Xj ui Cij + Xi di,j,i=1,j=1,i=1,m,m,m,即使最簡單的公式也是 NP-完全問題 通常, 使用方法 盡可能將片段分配在被局部訪問位置,“最佳適應” 方法（非冗余分配） Bij = k Fkj Nki “所有得益站點” 方法（冗余分配） Bij = k Fkj Rki - c k jjFkj Uki i 片段下標 j 站點下標 k 應用下標 Fkj 應用k 在站點j上激活的頻率 Rki 應用k被激活一次,對片段i讀的次數 Uki 應用k被激活一次

20、,對片段i寫的次數 Nki 應用k被激活一次,對片段i讀寫的總次數,最佳適應法 將片斷Ri分配到訪問Ri次數最多的那個站點上 Bij= kFkj*Nki 所有得益站點法 將片斷Ri的副本分配到所有得益站點j上 Bij= kFkj*Rki -c*k jj Fkj*Uki 如Bij 0，則站點j是得益站點，放置Ri的一個副本 附加復制法 Di表示片斷Ri的冗余度（副本個數）,Fi表示Ri在所有站點都復制的得益,假設關系R垂直分片R1和R2, R1分配到s站點, R2分配到t站點. 應用組As: 自站點s發(fā)出, 只使用Rs, 得益 BAs = Fks Nki ( k As) 應用組Ar: 自站點t發(fā)

21、出, 只使用Rt, 得益 BAt = Fkt Nki ( k At) 應用組A1: 由站點r發(fā)出, 原先使用Rt或Rs(本地), 現在要一次遠程，損失 BA1 = Fkr Nki ( k A1) 應用組A2: 由站點r發(fā)出, 原先使用R(本地), 現在要兩次遠程，損失 BA2 = Fkr Nki ( k A2) 應用組A3: 由不同于站點r,s,t的站點發(fā)出, 要訪問Rt和Rs, 損失 BA3 = Fkj Nki ( k A3,j r,s,t) 分配得益 Bist = BAs + BAt - BA1 - BA2 - BA3,分布式數據庫設計階段 需求分析 概念設計 分布要求設計 全局邏輯設計

22、分布設計 局部邏輯設計 局部物理設計,收集分布信息 水平分片謂詞 每一應用在各站點激活頻率 概念設計之后進行,收集分布信息 分布要求和全局邏輯模式作為輸入 形式為全局數據庫模式和邏輯訪問表 輸出為分片模式和分配模式 全局邏輯設計之后進行,說明： 1.設計數據字典； 2.全局數據模式； 3.全局操作模式； 4.簡化全局模式； 5.邏輯訪問表； 6.各站點邏輯模式； 7.各站點訪問表； 8.局部邏輯模式 （關系或Codasyl）； 9.局部物理模式 （關系或Codasyl）,分布要求分析階段 頻率表：各站點上每一應用激活次數（假設所有應用在所有站點上都能執(zhí)行） 劃分表：可用于模式中各實體的潛在水平

23、分片規(guī)則 極化表：指明由一個站點發(fā)出的一給定應用訪問一給定片段的頻率（定量分析方法）,分布設計階段 分片設計 非冗余分配 冗余分配 局部模式的重新構造,分布設計,全局數據模式,邏輯訪問表,分布要求,站點邏輯模式,站點邏輯訪問表,三個站點 站點1：丹佛機場（CO） 站點1：紐約機場（NY） 站點1：亞特蘭大機場（GA） 數據庫存儲內容 機場規(guī)程 班機調度 班機可用情況 旅客訂票情況 三個應用 訂票應用 登記應用 起飛應用,實體左下角和右下角的數字表示：示例總數和應用選擇的平均示例數 訪問數據庫中的起飛與到達機場、起飛與到達時間和班機日期，以k表示這些關鍵詞 確定班機后，建立旅客的一個新的示例及聯

24、系“訂票”的一個示例，把用戶的信息（名字、電話寫入數據庫 O表示輸出，w表示寫入,根據數據庫中的旅客名字，班機號，班機日期，查明有關旅客和班機的示例，顯示“種類”信息。 根據“種類”信息和座位圖，將一個座位號分配給旅客，并寫入座位圖和座位號屬性，以及旅客的檢查行李號,產生即將離開機場的30架班機的信息顯示在TV監(jiān)視器上。 根據數據庫中的機場符號，當前日期，起飛時間，到達時間，查明班機號、 起飛時間、 出入口、 延期、目的地機場符號、目的地城市，顯示出來。,實體訪問表：班機,實體訪問表：機場,實體訪問表：旅客,聯系訪問表：從,聯系訪問表：到,聯系訪問表：訂票,聯系訪問表：登記,站點1：丹佛（CO

25、） 站點2：紐約（NY） 站點3：亞特蘭大（GA） 應用a：訂票 應用b：登記 應用c：起飛,將機場的區(qū)域屬性選作為機場實體的劃分準則 將旅客電話號碼前三位（區(qū)域碼）作為旅客實體的劃分屬性 謂詞選擇性表示按照該準則劃分各類元組所占的百分數,兩種方法劃分班機實體，應用不同的聯系“從”或“到”和機場劃分區(qū)域于同一基本劃分，結果不同。 根據第一訂票地點和班機起飛區(qū)域做導出劃分 機場班機乘客,分四步： 對每一實體選擇分片原則 確定非冗余分配 在非冗余分配上引入冗余 在每一站點上重新構造局部模式,機場實體： 基于區(qū)域的水平分段 機場1， 機場2， 機場3 班機實體：基于起飛機場的導出水平分段 班機1，班

26、機2， 班機3 旅客實體： 基于旅客預定的所有班機起飛的導出水平分段 旅客1，旅客2，旅客3，旅客4，旅客5，旅客6，旅客7，,1. 分片設計,根據分片原則 站點1：機場1， 班機1， 旅客1 站點2：機場2， 班機2， 旅客2 站點3：機場3， 班機3， 旅客3 根據極化表和頻率表 站點2：旅客4，旅客5，旅客6，旅客7 站點3：旅客5,2. 確定非冗余分配,冗余超出了同一實體所有片斷的效益 機場實體：不進行冗余分配 班機實體：不進行冗余分配 有限冗余 旅客實體： 預定離開兩個區(qū)域的乘客：，旅客4，旅客5，旅客6，放到兩個站點上 預定離開三個區(qū)域的乘客：旅客7，放到三個站點上,3. 冗余分配

27、,BC,站點1的局部模式,4. 局部邏輯模式,自然分配,班機2,從,到,訂票,登記,到,機場2,旅客2u 旅客4u 旅客6u 旅客7,AC,站點2的局部模式,4. 局部邏輯模式,自然分配,班機3,從,到,訂票,登記,到,機場3,旅客3u 旅客5u 旅客6u 旅客7,AB,站點3的局部模式,4. 局部邏輯模式,自然分配,將現有的各種不同的數據庫模式集成為全局模式. 三個問題 選擇公用數據庫模型來描述數據庫的全局模式 把每個站點上的本地模式翻譯成公用數據模型 把各站點上的本地數據模式集成為一公用的全局模式,自底向上方法主要問題是構造一個全局模式（超視圖）. 把各站點上的數據庫模式看成是全局模式的一

28、個視圖 這個問題就可看作是視圖綜合問題 概括分層結構支持視圖綜合 經典方法就是生成三個實體：一個具有共同屬性（超類型），兩個具有不相交屬性（子類型） 視圖綜合次序 一次把一個視圖和全局模式進行綜合，逐步構造起全局視圖 通常，最好首先綜合最大的或最重要的視圖，然后跟著綜合小的或者不重要的視圖,班 機,機號,日期,可用座位,出入口,座位圖,延期,班 機,機號,日期,可用座位,機型,座位圖,識別相似性 模式命名相似性 模式結構相似性 不同Site上有相似應用, 使用各自DB的數據副本, 則這兩Site之間有某些相似點. 識別沖突 命名沖突：同物異名（EMP,EMPLOYEE），異物同名 域差異 定標

29、差異：計量單位不同(天、小時、分鐘、秒） 結構差異：同一對象有的用實體描述, 有的用屬性描述. 處理操作期間不一致的數據策略（5種，p64-65）,系統(tǒng)B概念模式,班機,訂票,旅客,標識符,起飛,起飛時間,座位圖,可用座位,種類,名字,電話,到達,到達時間,班機,班機B,班機A,飛機符(機號),日期 (1,3),可用座位,座位圖,出入口,登記,訂票,從,到,機場,到達時間,到達機場,起飛時間,起飛機場,起飛時間,到達時間,座位號,檢查行李,旅 客,種類,名字,電話,綜合后建立的全局模式,數據集成,XML Ontology View,Exercise 1 已知有如下兩種段分配: A R1在Sit

30、e1, R2在Site2, R3在Site3. B R1和R2在Site1, R2和R3在Site3. 另已知有如下應用(所有應用的頻率相同) A1: 在Site1上發(fā)出, 讀5個 R1記錄, 5個 R2記錄 A2: 在Site3上發(fā)出, 讀5個R3記錄 , 5個R2記錄 A3: 在Site2上發(fā)出, 讀10個R2記錄. 問: 1. 如果以本地應用為主要設計目標, 那個分配較優(yōu)? 2. 假定A3改為要修改10個R2記錄, 并仍以本地應用為其設計目標, 則那個分配方案較優(yōu)?,站點1,站點2,站點3,站點3,站點2,站點1,A1 R1,A3 R2,A2 R3,A1 R1, R2,A3,A2 R2, R3,方案A,方案B,讀取,更新,10,10,10,5,5,圖2-12 COMPANY關系數據庫模式, 主碼用下劃線標出,EMPLOY,DEPARTMENT,DEPT_LOCATION,PROJECT,WORKS_ON,DEPENDENT,Exercise 2,三個站點A,B,C 部門1（總部），部門2，部門3 在站點B上頻繁訪問EMPLOYEE,PROJECT中有關工作在部門2的雇員和該部門管轄的項目信息 在站點C上頻繁訪問EMPLOYEE,PRO