第二章分布式数据库系统设计-Read课件.ppt

1、第二章 分布式数据库系统设计2008.9第二章 分布式数据库系统设计 分布式数据库系统设计概述分布式数据库系统设计概述 自顶而下设计分布式数据库系统自顶而下设计分布式数据库系统 自顶而下设计分布式数据库系统设计实例自顶而下设计分布式数据库系统设计实例 自底向上分布式数据库系统设计自底向上分布式数据库系统设计 分布式数据库系统的优点和存在的技术问题分布式数据库系统的优点和存在的技术问题分布式数据库系统设计概述分布式数据库系统设计概述 分布式数据库系统的构建方法分布式数据库系统的构建方法 分布式数据库设计的内容分布式数据库设计的内容 分布式数据库设计目标分布式数据库设计目标 分布式数据库设计方法分

2、布式数据库设计方法分布式数据库系统的构建方法分布式数据库系统的构建方法 组合法：自底向上组合法：自底向上 重构法：自顶向下重构法：自顶向下组合法组合法网络DBMS1DBMS2DBMSn分布式协调管理系统用户1用户2用户m重构法重构法网络分布式数据库管理系统用户1用户2用户m分布式数据库设计的内容分布式数据库设计的内容 集中式数据库设计内容集中式数据库设计内容 数据库设计数据库设计 概念模式设计（描述数据库应用所使用的全部数据）概念模式设计（描述数据库应用所使用的全部数据）内模式设计（概念模式到存储模式的映射）内模式设计（概念模式到存储模式的映射）围绕数据库而展开的应用设计围绕数据库而展开的应用

3、设计 分布式数据库的设计内容分布式数据库的设计内容 分布式数据库设计分布式数据库设计 全局模式设计全局模式设计 每个站点的局部数据库的设计每个站点的局部数据库的设计数据分片设计数据分片设计位置分配设计位置分配设计 围绕分布式数据库而进行的应用设计，需要考虑：围绕分布式数据库而进行的应用设计，需要考虑：各应用的原发站点各应用的原发站点 各应用在每个站点被激活的次数各应用在每个站点被激活的次数 各应用对所要求访问的每个数据对象的访问次数、类型和统计分布各应用对所要求访问的每个数据对象的访问次数、类型和统计分布分布式数据库设计的目标分布式数据库设计的目标 分布式数据库的本地性或近地性：分布式数据库的

4、本地性或近地性：尽量减少对网尽量减少对网络的使用，减少网络通信次数和通信量，络的使用，减少网络通信次数和通信量，90%的的数据在本地访问数据在本地访问 控制数据的适当冗余：控制数据的适当冗余：为提高本地性、并发度和为提高本地性、并发度和可靠性要增加副本；为维护数据一致性，要减少可靠性要增加副本；为维护数据一致性，要减少副本副本 工作负荷分布：工作负荷分布：将工作负荷分布到各个站点，充将工作负荷分布到各个站点，充分利用每个站点的计算机能力和资源，提高并行分利用每个站点的计算机能力和资源，提高并行运行程度运行程度 存储能力和费用：存储能力和费用：虽然存储费用与虽然存储费用与CPU、I/O、以及传输

5、的费用相比不重要，但必须考虑各站点以及传输的费用相比不重要，但必须考虑各站点的存储能力的存储能力分布式数据库设计的方法分布式数据库设计的方法 自顶向下设计方法：从头开始构建数据库自顶向下设计方法：从头开始构建数据库 自底向上设计方法：聚集现存数据库来设计分布自底向上设计方法：聚集现存数据库来设计分布式数据库式数据库自顶而下设计分布式数据库系统自顶而下设计分布式数据库系统 自顶向下设计分布式数据库的步骤和内容自顶向下设计分布式数据库的步骤和内容 数据的分片设计数据的分片设计 数据库片段的位置分配设计数据库片段的位置分配设计自顶向下设计分布式数据库的步骤和内容自顶向下设计分布式数据库的步骤和内容

6、需求分析：收集用户数据库应用的规格说明，产需求分析：收集用户数据库应用的规格说明，产生一种无歧义的定义和在设计数据库中要考虑的生一种无歧义的定义和在设计数据库中要考虑的元素分类，这些信息被收集在设计的数据字典中元素分类，这些信息被收集在设计的数据字典中 概念设计：产生全局、综合数据库模式的一种概概念设计：产生全局、综合数据库模式的一种概念规格说明和在此模式上执行应用的概念规格说念规格说明和在此模式上执行应用的概念规格说明明 逻辑设计：将综合概念模式转换成一给定逻辑设计：将综合概念模式转换成一给定DBMS类型的数据库模式类型的数据库模式 分布设计：以全局的、与站点无关的模式作为输分布设计：以全局

7、的、与站点无关的模式作为输入，以产生分布式数据库各站点的子模式作为输入，以产生分布式数据库各站点的子模式作为输出，包括分片设计和片段的分配设计出，包括分片设计和片段的分配设计 物理设计：要遵照选定物理设计：要遵照选定DBMS的能力和特点进行的能力和特点进行数据的分片设计数据的分片设计 分片设计的基本目的分片设计的基本目的 产生一个对全局数据合适的划分方案，使得在数据产生一个对全局数据合适的划分方案，使得在数据分配和存储时减少应用中的操作量，增加应用的本分配和存储时减少应用中的操作量，增加应用的本地性地性 数据分片的基本类型和方法数据分片的基本类型和方法 水平分片水平分片 垂直分片垂直分片 混合

8、分片混合分片 水平分片水平分片 初级水平分片：以关系自身的属性性质为基础，执行选择操初级水平分片：以关系自身的属性性质为基础，执行选择操作，将关系划分成若干不相交的片段作，将关系划分成若干不相交的片段 对全局关系进行合适的水平分片，需要确定一组不相交的、完整的限对全局关系进行合适的水平分片，需要确定一组不相交的、完整的限定语，即：令定语，即：令P=P1,P2,Pn是一简单谓词的集合，为了正确而有效是一简单谓词的集合，为了正确而有效地分片，则地分片，则P必须是必须是“完整的完整的”和和“最小的最小的”，满足：，满足：只有当属于同一分片中的任意两个元组被任一应用以同等概率进行访问时，只有当属于同一

9、分片中的任意两个元组被任一应用以同等概率进行访问时，称谓语集合称谓语集合P是完整的。是完整的。如果集合如果集合P的全部谓词与应用密切相关，称的全部谓词与应用密切相关，称P是最小的。是最小的。例：全局关系例：全局关系EMP(E#,NAME,DEPT,JOB,SAL,TEL,)DEPT=1,2 JOB=P,-P，若应用经常查询的内容是属于部门，若应用经常查询的内容是属于部门1且是程序员的雇员。且是程序员的雇员。P=DEPT=1是不完整的是不完整的P=DEPT=1,JOB=P是正确的，也是合适的，因为这样可以分为：是正确的，也是合适的，因为这样可以分为：DEPT=1,JOB=P、DEPT=2,JOB

10、=P、DEPT=1,JOB=-P、DEPT=2,JOB=-P四个片段，满足完整、最小、不相交四个片段，满足完整、最小、不相交P=DEPT=1,JOB=P，SAL500是完整的，但不是最小的是完整的，但不是最小的 导出水平分片：不是以自身的属性性质为基础，而是从导出水平分片：不是以自身的属性性质为基础，而是从另一个关系的属性性质或水平分片推导出来的，采用导另一个关系的属性性质或水平分片推导出来的，采用导出式水平分段可以使片段之间的连接变得更容易出式水平分段可以使片段之间的连接变得更容易 连接图：又称结合图，当一个应用需要对两个全局关系连接图：又称结合图，当一个应用需要对两个全局关系进行连接操作时

11、，理论上应该对两个关系的全部元组进进行连接操作时，理论上应该对两个关系的全部元组进行比较。如果行比较。如果R水平分片为水平分片为Ri，i=1,2,n；S水平分片水平分片为为Sj，j=1,2,m，需要将，需要将Ri与与S进行比较，有以下可进行比较，有以下可能：能：jiSR不相交，无相同属性值元组存在不相交，无相同属性值元组存在jiSR相交，有相同属性值元组存在相交，有相同属性值元组存在当连接增多时，这种连接不容易判断，用连接图：圆圈当连接增多时，这种连接不容易判断，用连接图：圆圈表示关系的片段，小圆圈之间的无向边表示非空片段之表示关系的片段，小圆圈之间的无向边表示非空片段之间的连接间的连接全连接

12、：连接图中包括两个关系全连接：连接图中包括两个关系R和和S之间的片之间的片段之间的所有连接段之间的所有连接全连接图简单连接图分区连接图分区连接图：连接图中不包含某些连接，且一个分区连接图：连接图中不包含某些连接，且一个连接图由两个或多个子图组成，而这些子图之间连接图由两个或多个子图组成，而这些子图之间无连接边无连接边简单连接图：连接图中不包含某些连接，且每个简单连接图：连接图中不包含某些连接，且每个子图只有一条边子图只有一条边 垂直分片：确定一个全局关系垂直分片：确定一个全局关系R的垂直分片需要的垂直分片需要根据应用以根据应用以“同样方式同样方式”访问的属性来进行分组访问的属性来进行分组,垂直

13、分片不同于垂直集群，垂直分片的组必须只垂直分片不同于垂直集群，垂直分片的组必须只在某个键属性上重叠，其他属性不可重叠；垂直在某个键属性上重叠，其他属性不可重叠；垂直集群的组在其他属性上也可以重叠。垂直集群有集群的组在其他属性上也可以重叠。垂直集群有时候更好的实现本地性时候更好的实现本地性 垂直分片的基本目标：使频繁使用的属性聚集在一垂直分片的基本目标：使频繁使用的属性聚集在一起，当各个应用只使用一个属性子集时，存在一个起，当各个应用只使用一个属性子集时，存在一个理想的垂直分片理想的垂直分片 垂直分片的方法垂直分片的方法 分裂法：将全局关系逐渐分成片段，分分裂法：将全局关系逐渐分成片段，分 成组

14、法：将属性逐步聚集成片段，合成组法：将属性逐步聚集成片段，合数据片段的位置分配设计数据片段的位置分配设计 数据片段位置分配方法数据片段位置分配方法 分配方式分配方式 非冗余分配：每个片段在一个站点上，用最佳适应法非冗余分配：每个片段在一个站点上，用最佳适应法 冗余分配：每个片段映射到一个或多个站点，需要确定片冗余分配：每个片段映射到一个或多个站点，需要确定片段复制的程度，复制的利益随着检索与更新间的比值而增段复制的程度，复制的利益随着检索与更新间的比值而增加加所有得益站点法：先确定非复制问题的解，然后在全部站点中确所有得益站点法：先确定非复制问题的解，然后在全部站点中确定一组站点，给这组站点中

15、的每个站点分配片段的一个副本，这定一组站点，给这组站点中的每个站点分配片段的一个副本，这样做的好处要比付出的代价大样做的好处要比付出的代价大附加复制法：首先确定非复制问题的解，然后从最有益处起逐步附加复制法：首先确定非复制问题的解，然后从最有益处起逐步附加复制的副本，此过程直到附加复制的副本，此过程直到“附加复制附加复制”已无明显的好处为止已无明显的好处为止 数据片段分配的费用和得益估算数据片段分配的费用和得益估算 i表示片段下标表示片段下标 J表示站点下标表示站点下标 K表示应用下标表示应用下标 Fkj表示应用表示应用k在站点在站点j上被激活的频率上被激活的频率 Rki表示应用表示应用k被激

16、活一次，对片段被激活一次，对片段i进行检索访问的进行检索访问的次数次数 Uki表示应用表示应用k被激活一次，对片段被激活一次，对片段i进行更新访问的进行更新访问的次数次数 Nki=Rki+Uki表示应用表示应用k被激活一次，对片段被激活一次，对片段i进行访问进行访问的总次数的总次数 水平分片水平分片 非冗余分配使用非冗余分配使用“最佳适应法最佳适应法”。将片段。将片段i分配到访问分配到访问Ri次次数最多的那个站点，在站点数最多的那个站点，在站点j上上Ri的本地访问次数为：的本地访问次数为：kkikjijNFB 冗余分配使用冗余分配使用“所有站点得益法所有站点得益法”。将片段。将片段i的副本分配

17、到的副本分配到所有得益站点所有得益站点j上，所谓得益站点是指在这些站点上，应用上，所谓得益站点是指在这些站点上，应用的检索访问费用总比从任何一个其他站点发出的应用对的检索访问费用总比从任何一个其他站点发出的应用对Ri的更新访问的费用要低，估算差额：的更新访问的费用要低，估算差额：估算max（Bij）=ijB kkjjkikjkikjijUFcRFBC是更新访问与检索访问的代价比，如果Bij0则，在站点j上存放Ri的一个副本，Ri就被分配在j上 冗余分配使用冗余分配使用“附加复制法附加复制法”。另。另Di表示片段表示片段Ri的冗余度，的冗余度，（副本个数），（副本个数），Fi表示表示Ri在每个站点全都复制的得益，在每个站点全都复制的得益，Di与与Fi之间存在如下关系：之间存在如下关系：iDiFDi)21()()1()(ikkjjkikjkikjijDUFcRFB 其中：（1）=0，（2）=Fi/2，（3）=3Fi/4，修改得益公式，得到求站点j上引入Ri新副本的得益公式 垂直分片垂直分片 假设把站点假设把站点r上的关系上的关系R垂直分片成两个片段垂直分片成两个片段Rs和和Rt，并将，并将Rs和和Rt分别分配在站点分别分配在站点s和和t上，然后将应用分组并估算它们的得益情况：上，然后将应用分组并估算它们的得益情况：