分布式数据库第二章

1、分布式数据库,1,第二章 分布式数据库系统的设计,-王冠,分布式数据库,2,2.1分布式数据库系统设计概述,DDBS的创建方法： 组合法 Bottom-up 集成法。利用现有的计算机网络和现存于各节点上的独立数据库系统，通过建立一个分布式协调管理系统，将他们集成为一个统一的DDBS。 需解决的问题 分析现存系统的功能 解决数据一致性、可靠性 异构数据模型的转换 优点 工作量小，仅需建立一个分布式协调管理系统 实现周期短，花费小 保护用户投资,分布式数据库,3,重构法 根据应用需求，按照某种设计思想和方法，采用统一的观点，从总体设计开始，重新建立一个分布式数据库系统。 需解决的问题 采用统一的设

2、计思想考虑设计问题 便于解决数据一致性、可靠性 投资大、周期长,分布式数据库,4,DDBS设计的内容 应用（功能）设计 数据库设计 逻辑结构设计 物理结构设计 数据的分片设计、分配设计 考虑应用需求 应用的原发站点 应用在站点被激活的频率 应用对数据对象的访问次数、类型和统计分布,分布式数据库,5,DDBS设计目标 数据库的本地性（近地性） 应用所需的数据应当尽可能在本地场点找到 数据的可用性和可靠性 工作负荷分布 存储的能力和费用,分布式数据库,6,DDB的设计方法 自顶向下 需求分析 概念设计 逻辑设计 分布设计 物理设计 自底向上 根据各场点的概念模式设计全局概念模式,分布式数据库,7,

3、2.2 自顶向下设计DDB,数据库的分片设计 逻辑片段 数据在各站点上分配和存储的逻辑单位 一般根据访问频率分段，使具有相同访问频率的数据划分到一个片段中 使应用最大可能的本地性,分布式数据库,8,分片原则 完整性原则 全局关系的所有数据项必须包含在某个片段中 重构性原则 所有片段必须能够还原全局关系 不相交原则,分布式数据库,9,水平分片 将一个关系按某个条件划分成若干元组的子集 对全局关系执行选择操作的结果,例 S( S#, Sname, Age, Sex ) define fragment S1 as select * from S where Sex = M define fragme

4、nt S2 as select * from S where Sex = F,分布式数据库,10,合适分片的谓词性质：令P=P1, P2, ,Pn是简单谓词集合。若P是合适的，则，P应该满足： “完整的”：使用P分片的结果，导致应用对同一分段内各元组的访问是等概的。 “最小的”：P中各个简单谓词Pi (i=1,2,n)，都是与应用密切相关的。即，没有多余的Pi 。,例：全局关系EMP(Eno,Name,Deptno,Job,Sal) 应用：查询属于部门1，且是程序员的雇员 P = DEPT=1是不完整的 P = DEPT=1，Job=“P”是合适的 P = DEPT=1，Job=“P”，Sal

5、1500不是最小的。,分布式数据库,11,垂直分片 将一个关系按列以属性组划分成若干片段 对全局关系执行投影操作的结果 为保证可重构性，键属性应包含在每一个片段中,例：全局关系Emp(Eno,Name,Deptno,Job,Sal) Emp1(Eno, Name, Sal) Emp2(Eno, Deptno, Job),分布式数据库,12,混合分片 水平分片和垂直分片的混合操作,分布式数据库,13,诱导分片 将一个关系按另一个与其有关联性质的关系的属性做水平分片 对全局关系执行半联接操作的结果,R与S的半联接 RS=R(RS) 或 RS= R( R(S) ),分布式数据库,14,例：全局关系E

6、mp(Eno,Name,Deptno,Job,Sal) Dept(Deptno,Dname,city) 对Dept按city做水平分片： Dept1=city=beijing Dept Dept2=city=shanghai Dept 根据Dept对Emp做诱导分片： Emp1=Emp Dept1 Emp2=Emp Dept2,分布式数据库,15,数据库的分配设计 将逻辑片段分配到各场点上 分配方法： 非冗余分配：一个片段只分到一个场点 “最佳适应”法（best-fit）：分别计算分配方案的收益，选择收益最好的一个。 不考虑相关片段的影响,分布式数据库,16,分配方法： 冗余分配： “选择所有

7、收益场点”法：首先确定一种非冗余的分配方案，然后从全部场点中选择一组站点，如果将片段的一个副本分配到这组站点所得到的收益高于花费的代价，就把该副本分配给这一组站点。 “添加副本”法：首先确定一种非冗余的分配方案，然后添加副本，直到收益小于代价。,分布式数据库,17,分配的费用和收益的估算 i-片段序号 j-站点序号 k-应用序号 Fkj-应用k在站点j上激活的频率 Rki-应用k对片段i 进行检索访问的次数 Uki-应用k对片段i 进行更新访问的次数 Nki = Rki + Uki -应用k对片段i进行访问的总次数,分布式数据库,18,不同分片方式下的收益计算 水平分片 1.“最佳适应”法（b

8、est-fit） 将片段fi分配到对fi访问次数最多的站点上。在站点j上对fi的本地访问次数为： Bij = k( Fkj * Nki) 分别计算每个站点的Bij ，找出其值最大的站点，将fi分配到此站点。,分布式数据库,19,2. “选择所有收益场点” 将应用的本地检索收益与从其他站点发出的更新代价比较： 将片段i分配到站点j得到的本地检索收益: Brij = k( Fkj * Rki) 将片段i分配到场点j从其他站点发出的更新代价: Buij = k jj( Fkj * Uki ) 总的收益以Brij 和Buij间的差衡量： Bij = Brij- c*Buij (c=1) 如果Bij 0

9、，则将片段i分配到j站点。 将片段i分配到使B 0所有站点,分布式数据库,20,3. “添加副本”法 添加副本可以额外提高系统的可用性和可靠性，意大利人S.Ceri提出用函数估算添加副本带来的额外收益: (di) =（1 21 - di ）* Fi 其中：di -片段i的副本个数（ i的冗余度） Fi -片段i在每个站点全复制时的收益 用下列公式估算在站点j上添加副本的收益： Bij = Brij- c*Buij + (di) 当di 增加，而Bij的增大不明显时，就停止增加di 。,分布式数据库,21,不同分片方式下的收益计算II 垂直分片 将全局关系垂直分片R1和R2，并将R1和R2分配到

10、Site1和Site2上。根据片段的应用情况分别计算收益：,Site1,Site2,Site3,Sitex,网络,R1,R2,A1,A2,A3,A4,A5,分布式数据库,22,case1: 对于应用组A1，发自本地站点Site1，而且只检索和更新R1，且更新不涉及R1的键。此时可获得收益： BA1 = k( Fk * Nk1 ) k A1,case2: 对于应用组A2，发自本地站点Site2 ，而且只检索和更新R2，且更新不涉及R2的键。此时可获得收益： BA2 = k( Fk * Nk2 ) k A2,case3: 对于应用组A3，它发自站点Site3，访问R1或R2。原先进行本地访问，现在

11、需要做远程访问，因此损失： BA3 = k( Fk * Nki ) i = R1 或 R2; k A3,分布式数据库,23,case4:对于应用组A4，它发自Site3 ，同时访问R1和R2，原先进行本地访问，现在需要做两次远程访问，因此损失： BA4 = 2*k( Fk * Nki ) i 对应片段R; k A4,case5:对于应用组A5，它发自除Site1 、 Site2 、 Site3之外的其它站点，原先同时访问R1和R2（远程访问），现在需要多做一次远程访问，因此损失： BA5 = j k( Fkj * Nki ) k A5 ; j Site1, Site2, Site3; i =

12、1 或 2,总的收益：B = BA1 + BA2 BA3 BA4 BA5,分布式数据库,24,2.3分布式数据库的分布透明,分布式数据库的数据独立性 用户或用户程序使用分布式数据库时，不必关心数据的分布情况，包括：全局数据的逻辑分片、片段的物理位置分配、各站点数据库的数据模型。 或者说，全局数据的逻辑分片、片段的物理位置分配、各站点数据库的数据模型对用户和用户程序透明。 也称分布透明性（Distribution Transparency)。,分布式数据库,25,分布透明性的等级 分片透明性 用户编写程序时只针对全局模式，不必考虑数据的逻辑分片、片段的物理位置分配、各站点数据库的数据模型。,Se

13、lect Sname From Supplier Where Sno = s001,分布式数据库,26,位置透明性 用户编写程序时要了解全局数据的分片情况，但不必了解各逻辑片段的复制副本情况，也不必关心各片段及其副本的站点位置分配情况。,Select SName From Supplier1 Where SNO = s001,分布式数据库,27,局部数据模型透明性 用户编写程序时要了解全局数据的分片情况、各逻辑片段的复制副本情况，以及各片段和它们的副本的站点位置分配情况，但不必了解各站点上数据库的数据模型。,Select SName From Supplier1 AT Site1 Where

14、Sno = s001,分布式数据库,28,2.4 DADAID-D方法,意大利米兰工业大学提出的自顶向下的设计方法，由集中式数据库设计基础上扩展而来,分布式数据库,29,局部物理模式,全局逻辑设计,需 求 分 析,概 念 设 计,分 布 设 计,局部逻辑设计,分布要求分析,局部物理设计,用户分布要求,局部逻辑模式,分布式数据库,30,分布要求分析 收集有关分布的信息，如水平划分的划分谓词，各应用在各站点的激活频率，产生： 应用的频率表：在各站点上每应用的激活频率 划分表：潜在的水平分片规则 极化表：基于定量分析方法说明如何影响应用处理的本地性，指明由一给定站点发出的一给定应用访问一给定片段的概

15、率,分布式数据库,31,分布设计 根据全局数据库模式定义、逻辑访问表和分布要求，将数据分配到各站点上，产生站点的逻辑模式和访问表。分阶段： 分片设计： 产生逻辑片段 保证各应用以相同的频率访问各片段 分配设计： 非冗余分配 冗余分配 局部模式重构： 重新构造分配到各站点的片段的局部模式。全局模型中联系的分配,分布式数据库,32,非冗余分配 将各片段映射到使用最多的站点 针对每片段，对每站点分别计算： Bj = k( Fkj * Nki) 找出Max(Bj ),则该片段分配到该站点,冗余分配 使用“贪婪”启发式 在需要增加冗余的前提下，增加一个副本，计算变成本地访问的收益和维护一致性带来的损失的

16、差值,分布式数据库,33,分布式数据库设计例子,飞机订票系统 订票系统分布在三个站点（机场1，2，3）。数据库存储机场规程、班机起降和旅客订票等数据。,实体及其属性：,旅客：名字，电话 班机：机号，日期，可用座位，登机口，座位图，延期 机场：符号，区域（如：N、E、S)，城市，安全规则,分布式数据库,34,概念设计-全局概念模式（E-R图）,分布式数据库,35,全局操作模式（应用）,a. 订票: 用于旅客预订机票。,分布式数据库,36,b. 登记: 用于旅客登机登记任务。,依旅客姓名、班机号、日期确定旅客和班机，找出票的种类、座位图，更新座位图，创建“登记”实例（座位号、行李号）,分布式数据库

17、,37,c. 起飞: 显示即将从一个机场起飞的30个班机信息,分布式数据库,38,全局关系数据模式,1. 机场（符号，区域，城市，安全规则）,2. 班机（机号，日期，可用座位，座位图，登机口，延期）,3. 旅客（名字，电话）,4. 从（机号，日期，符号，起飞时间）,5. 到（机号，日期，符号，到达时间）,6. 订票（名字，机号，日期，种类）,7. 登记（名字，机号，日期，座位号，行李）,分布式数据库,39,创建逻辑访问表 给出各个应用在每个实体上的操作类型和数量,例 “班机”实体逻辑访问表,分布式数据库,40,分布要求的分析,1. 频率表：给出各个应用在三个站点上使用的频率（激活的次数）,分布

18、式数据库,41,2. 划分表：,1）基本划分,给出各个实体的各种可能分片的方式。,分布式数据库,42,2）导出划分,注：最后一行“班机起飞区域”指：旅客各次订票所对应的班机起飞区域。因此，这里的“导出”过程是“机场”“班机”“旅客”。显然，一名旅客有可能选择过一个/两个/三个起飞区域。,分布式数据库,43,注释表：,分布式数据库,44,3. 极化表：给出从一个站点发出的一个应用访问某片段的概率。,分布式数据库,45,飞机订票系统的分布设计,分片设计：为各个实体选择合适的分片原则。,1）垂直划分对本例无用。,2）各个实体水平分片原则： “机场” 基于所在区域做水平分片（片段：机场1，机场2，机场3）, “班机” 基于起飞机场所在区域做诱导分片（片段：班机1，班机2，班机3）, “旅客” 基于旅客订票涉及的所有班机起飞区域做诱导分片（片段：旅客1，旅客2，旅客3