分布式数据库系统的设计.ppt

1、徐俊刚 （),分布式数据库系统及其应用,2009年2月2009年6月,分布式数据库系统设计概述 自顶向下设计分布式数据库 DATAID-D方法 实例研究：飞机订票系统 自底向上设计分布式数据库,分布式数据库系统设计,第2章,分布式数据库设计概述,1,创建方法,组合法,剖析网络功能 剖析原有数据库系统 解决数据的一致性、完整性和可靠性 难度较大 通常是异构或者同构异质DDBS,分布式数据库设计概述,1,重构法,根据实现环境和用户需求 按照DDBS的设计思想和方法 从总体设计做起，包括LDBS,重新建立一个DDBS 可有效解决数据一致性、完整性和可靠性问题。 通常是同构异质或同构同质DDBS,DD

2、BS设计,DDB设计,应用设计,全局模式设计,局部数据库设计,相关应用需求,各个应用的原发站点,各个应用在每个站点的激活频率,各个应用对要求访问数据对象的访问次数、类型和统计分布,分片和分布,DDBS 设计目标,本地性或近地性,存储能力和费用,尽量减少通信次数和通信量，90/10准则,分片和分布方案（本地和远程访问次数）择优,控制数据适当冗余,冗余增加了可靠性、可用性，提高了效率,维护数据一致性开销增加,工作负荷分布,各站点可以分担整个工作任务,本地性降低,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,举例,基本水平分片 以关系自身的属性性质为基础，执行“选择”操作，将关系分割成若干个不相交的片段。 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,属性亲和矩阵,行列调整寻找分割点,属性和矩阵,穷举属性亲和矩阵的列排列 行与列要同时调整 发现好的 “分割点” 极大化每个分割内的亲合力（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发出, 只使用Rs, 得益 BAs = Fks Nki ( k As) 应用组Ar: 自站点t发

21、出, 只使用Rt, 得益 BAt = Fkt Nki ( k At) 应用组A1: 由站点r发出, 原先使用Rt或Rs(本地), 现在要一次远程，损失 BA1 = Fkr Nki ( k A1) 应用组A2: 由站点r发出, 原先使用R(本地), 现在要两次远程，损失 BA2 = Fkr Nki ( k A2) 应用组A3: 由不同于站点r,s,t的站点发出, 要访问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）,分布要求分析阶段 频率表：各站点上每一应用激活次数（假设所有应用在所有站点上都能执行） 划分表：可用于模式中各实体的潜在水平

23、分片规则 极化表：指明由一个站点发出的一给定应用访问一给定片段的频率（定量分析方法）,分布设计阶段 分片设计 非冗余分配 冗余分配 局部模式的重新构造,分布设计,全局数据模式,逻辑访问表,分布要求,站点逻辑模式,站点逻辑访问表,三个站点 站点1：丹佛机场（CO） 站点1：纽约机场（NY） 站点1：亚特兰大机场（GA） 数据库存储内容 机场规程 班机调度 班机可用情况 旅客订票情况 三个应用 订票应用 登记应用 起飞应用,实体左下角和右下角的数字表示：示例总数和应用选择的平均示例数 访问数据库中的起飞与到达机场、起飞与到达时间和班机日期，以k表示这些关键词 确定班机后，建立旅客的一个新的示例及联

24、系“订票”的一个示例，把用户的信息（名字、电话写入数据库 O表示输出，w表示写入,根据数据库中的旅客名字，班机号，班机日期，查明有关旅客和班机的示例，显示“种类”信息。 根据“种类”信息和座位图，将一个座位号分配给旅客，并写入座位图和座位号属性，以及旅客的检查行李号,产生即将离开机场的30架班机的信息显示在TV监视器上。 根据数据库中的机场符号，当前日期，起飞时间，到达时间，查明班机号、 起飞时间、 出入口、 延期、目的地机场符号、目的地城市，显示出来。,实体访问表：班机,实体访问表：机场,实体访问表：旅客,联系访问表：从,联系访问表：到,联系访问表：订票,联系访问表：登记,站点1：丹佛（CO

25、） 站点2：纽约（NY） 站点3：亚特兰大（GA） 应用a：订票 应用b：登记 应用c：起飞,将机场的区域属性选作为机场实体的划分准则 将旅客电话号码前三位（区域码）作为旅客实体的划分属性 谓词选择性表示按照该准则划分各类元组所占的百分数,两种方法划分班机实体，应用不同的联系“从”或“到”和机场划分区域于同一基本划分，结果不同。 根据第一订票地点和班机起飞区域做导出划分 机场班机乘客,分四步： 对每一实体选择分片原则 确定非冗余分配 在非冗余分配上引入冗余 在每一站点上重新构造局部模式,机场实体： 基于区域的水平分段 机场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. 确定非冗余分配,冗余超出了同一实体所有片断的效益 机场实体：不进行冗余分配 班机实体：不进行冗余分配 有限冗余 旅客实体： 预定离开两个区域的乘客：，旅客4，旅客5，旅客6，放到两个站点上 预定离开三个区域的乘客：旅客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）,系统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上发出, 读5个 R1记录, 5个 R2记录 A2: 在Site3上发出, 读5个R3记录 , 5个R2记录 A3: 在Site2上发出, 读10个R2记录. 问: 1. 如果以本地应用为主要设计目标, 那个分配较优? 2. 假定A3改为要修改10个R2记录, 并仍以本地应用为其设计目标, 则那个分配方案较优?,站点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