第三章分布式数据库的设计

第三章分布式数据库的设计分布式数据库系统原理与应用内容简介在系统设计中，最基本问题就是分布式数据库的分布问题，即如何对分布式数据库进行逻辑划分和实际物理分配。数据的逻辑划分称数据分片。本章主要针对数据分布进行介绍，以关系数据库为例来说明。两种设计策略（Top-down和Bottom-up）分片的定义水平分片水平分片的设计垂直分片的设计分片的表示方法分配设计分布式数据库系统原理与应用DDBS设计内容DDBS设计DDB设计应用设计全局模式设计局部数据库设计相关应用需求各个应用的原发站点各个应用在每个站点的激活频率各个应用对要求访问数据对象的访问次数、类型和统计分布分片和分布分布式数据库系统原理与应用DDBS设计目标DDBS设计目标本地性或近地性存储能力和费用尽量减少通信次数和通信量，90/10准则分片和分布方案（本地和远程访问次数）择优控制数据适当冗余冗余增加了可靠性、可用性，提高了效率维护数据一致性开销增加工作负荷分布各站点可以分担整个工作任务本地性降低90%的数据在本地站点得到分布式数据库系统原理与应用Top_Down和Bottom-UP应用场合Top_Down:适于新设计一个数据库系统。（designedfromscratch）Bottom-UP:已存在许多数据库系统，并将它们集成为一个数据库。典型的数据集成的研究。本课程侧重top-down设计中存在的关键技术。两种设计策略分布式数据库系统原理与应用两种设计策略Top-down设计过程基于五步递归实现:1.需求分析（Requirementanalysis）2.概念设计、视图集成、E-R表示、转换到关系模式3.分布设计、数据分片和分配4.物理设计5.性能调优（Tuning）分布式数据库系统原理与应用两种设计策略-Top-down需求分析系统需求说明书调优概念设计外部模式定义全局概念模式视图设计分布设计局部概念模式物理设计局部物理模式分布式数据库系统原理与应用源于多数据库应用Database1Database2Databasen…Translator1Translator2Translatorn…InS1InS2InSn…IntegratorGCS两种设计策略-Bottom-up分布式数据库系统原理与应用分片的定义例：某集团公司由地理位置在不同城市的总公司和下属两个分公司组成，彼此之间靠网络相连接，业务管理由分布式数据库系统完成。其网络结构图如下所示总公司分公司1分公司2网络假设：人事系统中，有职工关系，定义为：EMP{ENO，EName，Salary，DNO}。场地定义：总公司为场地0，职工关系为EMP0分公司1为场地1，职工关系为EMP1分公司2为场地2，职工关系为EMP2EMP=EMP0+EMP1+EMP2为全局数据分布式数据库系统原理与应用分片的定义数据分布要求方案1：公司总部保留全部数据。方案2：各单位只保留自己的数据。方案3：公司总部保留全部数据，各分公司只保留自己单位的数据。系统采用以上不同方案，对应需求不同的数据分配方案。如:上面三种方案中，除方案1外，均须进行分片定义。方案3中，分公司的数据信息除本场地存储外，总部场地也存储一份相同信息，存在在不同场地上互称副本。总部（EMP）分公司1（无）分公司2（无）总部（EMP0）分公司1（EMP1）分公司2（EMP2）总部（EMP）分公司1（EMP1）分公司2（EMP2）场地0场地1场地2方案1方案2方案3分布式数据库系统原理与应用分片的定义定义片段（Fragment）：是分布式数据库中数据的存储单位。分片（Fragmentation)：对全局数据的划分。片段:划分的结果称为片段。分配（Allocation）：对片段的存储场地的指定，称为分配。当片段存储在一个以上场地时，称为数据复制（Replication）。如果每个片段只存储在一个场地，称为数据分割（Partition）存储。分布式数据库系统原理与应用分片的定义分片的作用减少网络传输量。如：采用数据复制，可就近访问所需信息。需频繁访问的信息分片存储在本地场地上。增大事务处理的局部性。局部场地上所须数据分片分配在各自的场地上，减少数据访问的时间，增强局部事务效率。提高数据的可用性和查询效率。就近访问数据分片或副本，可提高访问效率。同时当某一场地出故障，若存在副本，非故障场地上的数据副本均是可用的。保证了数据的可用性、数据的完整性和系统的可靠性。使负载均衡。减少数据访问瓶颈，提高整个系统效率。分布式数据库系统原理与应用分片的定义分片设计过程分片过程是将全局数据进行逻辑划分和实际物理分配的过程。全局数据由分片模式定义分成各个片段数据，各个片段数据由分配模式定义存储在各场地上。分片过程如下图所示。GDBFDBPDB分片模式分配模式GDB：全局数据库（GlobalDB）FDB：片段数据库（FragmentationDB）PDB：物理数据库（PhysicalDB）分布式数据库系统原理与应用分片的定义分片模式：定义从全局模式到片段模式的映射关系。分配模式：定义从片段模式到物理模式的映射关系。1：N时为复制；1：1时为分割。RR1R2R3R3R2R1R2R3场地1场地2场地3全局关系片段副本分布式数据库系统原理与应用分片的定义分片设计过程说明GDB=∑FDBi表示全局数据库是划分的多个片段数据库的集合。F(GDB)=FDB〈≡〉F-1(FDB)=GDBF()：表示分片模式映射函数，F-1()表示分片模式的反映射函数。即全局数据库经分片模式映射函数得到全局数据的各个片段，相反，所有片段经分片模式反映射函数得到全局数据。P(FDB)=PDB〈≡〉P-1(PDB)=FDBP()：表示分配模式映射函数，P-1()表示分配模式的反映射函数。即片段数据库经分配模式映射函数得到物理数据库，相反，物理数据库经分配模式反映射函数得到片段数据库。分布式数据库系统原理与应用分片的定义分片的原则在构成分布式数据库系统时，设计者必须考虑数据如何分布在各个场地上，即全局数据如何进行逻辑划分和物理分配问题。哪些数据需分布存放、哪些数据不需要分布存放、哪些数据需要复制等，对系统进行全盘考虑，使系统性能最优。但无论如何进行分片，必须遵循下面原则：完备性：所有全局数据必须映射到某个片段上。可重构性：所有片段必须可以重新构成全局数据。不相交性：划分的各片段所包含的数据不允许相同。分布式数据库系统原理与应用分片的定义分片的原则完备性如果全局关系R划分的片段为R1,R2,…,Rn，则对于R中任意数据项d（dR），一定存在dRi（1in）。可重构性如果全局关系R划分的片段为R1,R2,…,Rn，则存在关系运算，使得R=R1R2…Rn。不相交性如果全局关系R水平划分的片段为R1,R2,…,Rn，则任意两个不同的片段的交集为空，即RiRj=（ij,1in,1jn）。分布式数据库系统原理与应用分片的定义分片的种类分布式系统按系统实际需求对全局数据进行分片和物理分配。分片的种类有三种。水平分片：按元组进行划分，由分片条件决定。垂直分片：按关系属性划分，除关键字外，同一关系的某一属性不允许出现在一个关系的多个分片中。混合分片：既包括水平分片也包括垂直分片。属性或元组关系根据需要进行相应的分片分布式数据库系统原理与应用分片的定义分布透明性透明性：指对用户和高层系统隐蔽具体实现细节。分布透明性指分片透明性、分配透明性和局部映射透明性。分片透明性：指用户不必考虑数据属于哪个片段。分配透明性：指用户不必考虑各个片段的存储场地。局部映射透明性：用户不必考虑数据的局部存储形式。分布式数据库系统原理与应用水平分片的设计水平分片的定义水平分片是将关系的元组集划分成若干不相交的子集。每个水平片段由关系中的某个属性上的条件来定义，该属性称为分片属性，该条件称为分片条件。定义设有一个关系R，{R1，R2，…，Rn}为R的子关系的集合，如果{R1，R2，…，Rn}满足以下条件，则称其为关系R的水平分片，Ri称为R的一个水平片段。（1）R1，R2，…，Rn与R具有相同的关系模式（2）R1∪R2∪…∪Rn=R（3）Ri∩Rj=Φ（i≠j，1≤i≤n）分布式数据库系统原理与应用水平分片的设计按下面分片条件进行分段：E1：满足（Dno=201）的所有分组；E2：满足（Dno=202）的所有分组；E3：满足（Dno〈〉201ANDDno〈〉202）的所有分组。例如：设有雇员关系EMP{ENO,ENAME,SALARY,DNO}ENOENAMESALARYDNO001张三1500201002李四1400202003王五800203分布式数据库系统原理与应用水平分片的设计将关系EMP分成了三个子关系，部门编号Dno等于201的元组（E1）、部门编号Dno等于202的元组（E2）和其他元组（E3）。分片属性：部门编号Dno分片条件：E1：Dno=201E2：Dno=202E3：Dno〈〉201ANDDno〈〉202003王五1200203002李四1400202001张三1500201ENOENAMESALARYDNO001张三1500201002李四1400202003王五800203E1：E2：E3：分布式数据库系统原理与应用水平分片的设计根据水平分片定义，满足：E1,E2,E3和EMP关系模式相同；E1∪E2∪E3=EMPE1∩E2=Φ，E1∩E3=Φ，E2∩E3=Φ因此，E1、E2和E3是EMP的水平分片。分布式数据库系统原理与应用水平分片的设计水平分片的表示水平分片实际上是关系的选择操作，因此，用选择操作σ表示，选择条件为分片谓词q，则R的片段可表示为：σq(R)。例：E1=σDno=201（EMP）SQL：SELECT*FROMEMPWHEREDNO=201E2=σDno=202（EMP）SQL：SELECT*FROMEMPWHEREDNO=202E3=σDno〈〉201ANDDno〈〉202（EMP）SQL：SELECT*FROMEMPWHEREDno〈〉201ANDDno〈〉202分布式数据库系统原理与应用水平分片的设计正确性判断分片必须遵循完备性、可重构性和不相交性三个原则。通过验证满足这三个特性判断分片的正确性。例如：上例的验证过程：完备性证明:((Dno=201)∪(Dno=202)∪(Dno201∩Dno202)=T)证明：(Dno=201)∪(Dno=202)∪(Dno201∩Dno202)=((Dno=201)∪(Dno=202))∪(¬((Dno=201∪Dno=202))=T满足完备性。分布式数据库系统原理与应用水平分片的设计正确性判断可重构性证明(E1∪E2∪E3=EMP)证明：E1∪E2∪E3=σDno=201(EMP)∪σDno=202(EMP)∪σDno201ANDDno202(EMP)=σDno=201∪Dno=202∪Dno201ANDDno202(EMP)=σT(EMP)=EMP满足可重构性。分布式数据库系统原理与应用水平分片的设计正确性判断不相交性证明(E1∩E2=Φ，E1∩E3=Φ，E2∩E3=Φ)证明：E1∩E2=σDno=201∩Dno=202（EMP）=σF（EMP）=Φ同理：E1∩E3=Φ，E2∩E3=Φ满足不相交性。根据上面三原则证明可知：该水平分片的设计是正确的。分布式数据库系统原理与应用水平分片的设计水平分片的影响因素水平分片是基于谓词条件划分关系。分片需求信息：来源于应用信息和数据库信息，应用信息：包括定性信息和定量的信息。数据库信息：主要指全局模式中模式间的关联关系（用于导出水平分片）定性信息（Qualitative）:查询中的谓词。分为：简单谓词(simplepredicate):小项谓词(Mintermpredicate)：简单谓词的连接。定量信息（Quantitativeinformati