分布式数据库第二章

分布式数据库1第二章分布式数据库系统的设计--王冠分布式数据库22.1分布式数据库系统设计概述DDBS的创建方法：组合法Bottom-up–集成法。利用现有的计算机网络和现存于各节点上的独立数据库系统，通过建立一个分布式协调管理系统，将他们集成为一个统一的DDBS。–需解决的问题•分析现存系统的功能•解决数据一致性、可靠性•异构数据模型的转换–优点•工作量小，仅需建立一个分布式协调管理系统•实现周期短，花费小•保护用户投资分布式数据库3重构法–根据应用需求，按照某种设计思想和方法，采用统一的观点，从总体设计开始，重新建立一个分布式数据库系统。–需解决的问题•采用统一的设计思想考虑设计问题•便于解决数据一致性、可靠性•投资大、周期长分布式数据库4DDBS设计的内容应用（功能）设计数据库设计–逻辑结构设计–物理结构设计数据的分片设计、分配设计–考虑应用需求•应用的原发站点•应用在站点被激活的频率•应用对数据对象的访问次数、类型和统计分布分布式数据库5DDBS设计目标–数据库的本地性（近地性）•应用所需的数据应当尽可能在本地场点找到–数据的可用性和可靠性–工作负荷分布–存储的能力和费用分布式数据库6DDB的设计方法自顶向下–需求分析–概念设计–逻辑设计–分布设计–物理设计自底向上–根据各场点的概念模式设计全局概念模式分布式数据库72.2自顶向下设计DDB数据库的分片设计逻辑片段–数据在各站点上分配和存储的逻辑单位–一般根据访问频率分段，使具有相同访问频率的数据划分到一个片段中–使应用最大可能的本地性分布式数据库8分片原则–完整性原则•全局关系的所有数据项必须包含在某个片段中–重构性原则•所有片段必须能够还原全局关系–不相交原则分布式数据库9水平分片–将一个关系按某个条件划分成若干元组的子集–对全局关系执行选择操作的结果例S(S#,Sname,Age,Sex)definefragmentS1asselect*fromSwhereSex=‘M’definefragmentS2asselect*fromSwhereSex=‘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”，Sal1500}不是最小的。分布式数据库11垂直分片–将一个关系按列以属性组划分成若干片段–对全局关系执行投影操作的结果–为保证可重构性，键属性应包含在每一个片段中例：全局关系Emp(Eno,Name,Deptno,Job,Sal)Emp1(Eno,Name,Sal)Emp2(Eno,Deptno,Job)分布式数据库12混合分片–水平分片和垂直分片的混合操作分布式数据库13诱导分片–将一个关系按另一个与其有关联性质的关系的属性做水平分片–对全局关系执行半联接操作的结果R与S的半联接R∝S=πR(R∞S)或R∝S=R∞(πR(S))分布式数据库14例：全局关系Emp(Eno,Name,Deptno,Job,Sal)Dept(Deptno,Dname,city)对Dept按city做水平分片：Dept1=σcity=’beijing’DeptDept2=σcity=’shanghai’Dept根据Dept对Emp做诱导分片：Emp1=Emp∝Dept1Emp2=Emp∝Dept2分布式数据库15数据库的分配设计将逻辑片段分配到各场点上分配方法：–非冗余分配：一个片段只分到一个场点•“最佳适应”法（best-fit）：分别计算分配方案的收益，选择收益最好的一个。•不考虑相关片段的影响分布式数据库16分配方法：–冗余分配：•“选择所有收益场点”法：首先确定一种非冗余的分配方案，然后从全部场点中选择一组站点，如果将片段的一个副本分配到这组站点所得到的收益高于花费的代价，就把该副本分配给这一组站点。•“添加副本”法：首先确定一种非冗余的分配方案，然后添加副本，直到收益小于代价。分布式数据库17分配的费用和收益的估算i----片段序号j----站点序号k----应用序号Fkj----应用k在站点j上激活的频率Rki----应用k对片段i进行检索访问的次数Uki----应用k对片段i进行更新访问的次数Nki=Rki+Uki----应用k对片段i进行访问的总次数分布式数据库18不同分片方式下的收益计算水平分片1.“最佳适应”法（best-fit）将片段fi分配到对fi访问次数最多的站点上。在站点j上对fi的本地访问次数为：Bij=k(Fkj*Nki)分别计算每个站点的Bij，找出其值最大的站点，将fi分配到此站点。分布式数据库192.“选择所有收益场点”将应用的本地检索收益与从其他站点发出的更新代价比较：将片段i分配到站点j得到的本地检索收益:Brij=k(Fkj*Rki)将片段i分配到场点j从其他站点发出的更新代价:Buij=kj’j(Fkj’*Uki)总的收益以Brij和Buij间的差衡量：Bij=Brij-c*Buij(c=1)如果Bij0，则将片段i分配到j站点。将片段i分配到使B0所有站点分布式数据库203.“添加副本”法添加副本可以额外提高系统的可用性和可靠性，意大利人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分配到Site1和Site2上。根据片段的应用情况分别计算收益：Site1Site2Site3Sitex网络R1R2A1A2A3A4A5分布式数据库22case1:对于应用组A1，发自本地站点Site1，而且只检索和更新R1，且更新不涉及R1的键。此时可获得收益：BA1=k(Fk1*Nk1)kA1case2:对于应用组A2，发自本地站点Site2，而且只检索和更新R2，且更新不涉及R2的键。此时可获得收益：BA2=k(Fk2*Nk2)kA2case3:对于应用组A3，它发自站点Site3，访问R1或R2。原先进行本地访问，现在需要做远程访问，因此损失：BA3=k(Fk3*Nki)i=R1或R2;kA3分布式数据库23case4:对于应用组A4，它发自Site3，同时访问R1和R2，原先进行本地访问，现在需要做两次远程访问，因此损失：BA4=2*k(Fk3*Nki)i对应片段R;kA4case5:对于应用组A5，它发自除Site1、Site2、Site3之外的其它站点，原先同时访问R1和R2（远程访问），现在需要多做一次远程访问，因此损失：BA5=jk(Fkj*Nki)kA5;jSite1,Site2,Site3;i=1或2总的收益：B=BA1+BA2–BA3–BA4–BA5分布式数据库242.3分布式数据库的分布透明分布式数据库的数据独立性用户或用户程序使用分布式数据库时，不必关心数据的分布情况，包括：全局数据的逻辑分片、片段的物理位置分配、各站点数据库的数据模型。或者说，全局数据的逻辑分片、片段的物理位置分配、各站点数据库的数据模型对用户和用户程序透明。也称分布透明性（DistributionTransparency)。分布式数据库25分布透明性的等级分片透明性用户编写程序时只针对全局模式，不必考虑数据的逻辑分片、片段的物理位置分配、各站点数据库的数据模型。Supplier1Supplier2Supplier3站点1站点2站点3DDBMSSelectSnameFromSupplierWhereSno='s001'分布式数据库26位置透明性用户编写程序时要了解全局数据的分片情况，但不必了解各逻辑片段的复制副本情况，也不必关心各片段及其副本的站点位置分配情况。Supplier1Supplier2Supplier3站点1站点2站点3DDBMSSelectSNameFromSupplier1WhereSNO=‘s001’分布式数据库27局部数据模型透明性用户编写程序时要了解全局数据的分片情况、各逻辑片段的复制副本情况，以及各片段和它们的副本的站点位置分配情况，但不必了解各站点上数据库的数据模型。Supplier1Supplier2Supplier3站点1站点2站点3DDBMSSelectSNameFromSupplier1ATSite1WhereSno=‘s001’分布式数据库282.4DADAID-D方法意大利米兰工业大学提出的自顶向下的设计方法，由集中式数据库设计基础上扩展而来分布式数据库29局部物理模式全局逻辑设计需求分析概念设计分布设计局部逻辑设计分布要求分析局部物理设计数据字典用户分布要求全局数据模式全局操作模式简化全局模式逻辑访问表各站点访问表局部逻辑模式极化表频率表划分表站点逻辑模式分布式数据库30分布要求分析–收集有关分布的信息，如水平划分的划分谓词，各应用在各站点的激活频率，产生：应用的频率表：在各站点上每应用的激活频率划分表：潜在的水平分片规则极化表：基于定量分析方法说明如何影响应用处理的本地性，指明由一给定站点发出的一给定应用访问一给定片段的概率分布式数据库31分布设计–根据全局数据库模式定义、逻辑访问表和分布要求，将数据分配到各站点上，产生站点的逻辑模式和访问表。分阶段：分片设计：•产生逻辑片段•保证各应用以相同的频率访问各片段分配设计：•非冗余分配•冗余分配局部模式重构：•重新构造分配到各站点的片段的局部模式。全局模型中联系的分配分布式数据库32非冗余分配将各片段映射到使用最多的站点针对每片段，对每站点分别计算：Bj=k(Fkj*Nki)找出Max(Bj),则该片段分配到该站点冗余分配使用“贪婪”启发式在需要增加冗余的前提下，增加一个副本，计算变成本地访问的收益和维护一致性带来的损失的差值分布式数据库33分布式数据库设计例子飞机订票系统订票系统分布在三个站点（机场1，2，3）。数据库存储机场规程、班机起降和旅客订票等数据。实体及其属性：旅客：名字，电话班机：机号，日期，可用座位，登机口，座位图，延期机场：符号，区域（如：‘N’、’E’、’S’)，城市，安全规则分布式数据库34概念设计---全局概念模式（E-R图）班机机场旅客到从订票种类登记座位号行李到达时间起飞时间分布式数据库35全局操作模式（应用）a.订票:用于旅客预订机票。起飞时间[k]到到达时间[k]从班机200003旅客1000001机场402符号[k]可用座位[o,w]日期[k]种类[w]订票电话[w]名字[w]机号[0,w]分布式数据库36b.登记:用于旅客登机登记任务。座位图[o,w]订票旅客1000001名字[k]种类[o]班机200001日期[k]机号[k]登记座位号[w]行李[w]依旅客姓名、班机号、日期确定旅客和班机，找出票的种类、座位图，更新座位图，创建“登记”实例（座位号、行李号）分布式数据库37c.起飞:显示即将从一个机场起飞的30个班机信息到到达时间[ko]从起飞时间[ko]机场401符号[k]班机2000030日期[k]机场4030城市[o]符号[o]延期[o]机号[o]登机口[o]分布式数据库38全局关系数据模式1.机场（符号，区域，城市，安全规则）2.班机（机号，日期，可用座位，座位图，登机口，延期）3.旅客（名字，电话）4.从（机号，日期，符号，起飞时间）5.