《分布式数据库飞机订票系统幻灯片》由会员分享，可在线阅读，更多相关《分布式数据库飞机订票系统幻灯片（32页珍藏版）》请在金锄头文库上搜索。
1、1,飞机订票系统的分配设计,2,飞机订票系统：,1 分布式数据库系统的概述 2 数据库片段的位置分配设计 3、飞机订票系统实例分析,3,1、分布式数据库系统定义,分布式数据库系统中的数据是物理分布在用计算机网络连接起来的各个站点上；每一个站点是一个集中式数据库系统，都有自治处理的能力，完成本站点的局部应用；而每个站点上的数据并不是互不相关的，它们构成一个逻辑整体，统一在分布数据库管理下，共同参与并完成全局应用，并且分布式数据库系统中的这种“分布”对用户来说是透明的，也就是说，本地与远程结合的“接缝”是被隐蔽的，用户几乎感觉不到远程与本地结合的接缝的存在，即“一个分布式系统应该看起来完全像一个非
2、分布系统”。,4,2、分布式系统的设计,分布设计：位于逻辑设计与物理设计之间，以一个全局的与站点无关的模式作为输入，以产生分布式数据库各站点的子模式为结果输出，包括数据的分片设计和片段的位置分配设计 分片：把一全局对象（实体或关系）细分成若干逻辑片段的过程 分配：把各片段映射到一个或多个站点的过程，片段是最合适的数据分配单位,5,3、分布式数据库系统设计的内容,相类似于集中式数据库设计：数据库+应用 数据库设计：全局模式设计+局部模式设计 关键点：全局模式如何划分并映射到站点 新设计问题：数据的分片、片段的位置分配,6,数据的分配设计,分配的概念,在满足用户需求的前提下, 把设计好的数据片段分
3、配到相应的站点上存储 例子: 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 存 放在哪?,7,分配方法,分配方法,非冗余分配设计方法,最佳适应法,冗余分配的设计方法,所有得益站点法,附加复制法,应用需求,确定非复制问题的解 确定一组站点分配副本,确定非复制问题的解 从最有益处增加副本 到附加复制无好处为止,其他方法,8,优化问题,什么是段的最好配置/什么是最好的冗余副本数: 1、极小化查询响应时间 2、极大化吞吐
4、量 3、极小化 “代价” 约束条件： 1、有效的存储空间 2、有效的带宽, 站点处理能力, 3、保持 90% 的响应时间低于 X（如0.5秒,9,分配的简化模型,单个片段 F 站点 S1, Sn 变量X1, , Xn 0 如果 F 不在 Sj上存储 1 如果 F 在 Sj上存储 Total cost = Read Cost + Write Cost +Storage Cost 确定 Xj 的值, 1 j n, 使总代价极小,10,读代价,Read cost = ti MIN Cij i: 读申请源站点 ti: 站点Si上的读申请激活次数 Cij: 从 Si读Sj站点分段F的代价,i=1,分配的
5、简化模型,11,写代价,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 的代价,分配的简化模型,12,存储代价,Store Cost = Xi di Xi: 0 if F not stored at Si 1 if F stored at Si di: 站点 Si 存储分段 F 的代价,分配的简化模型,目标函数,min ti MIN Cij + Xj ui Cij + Xi di,j
6、,i=1,j=1,i=1,m,m,m,即使最简单的公式也是 NP-完全问题 通常, 使用方法 尽可能将片段分配在被局部访问位置,分配的简化模型,“最佳适应” 方法（非冗余分配） Bij = k Fkj Nk “所有得益站点” 方法（冗余分配） Bij = k Fkj Rki - c k jjFkj Uki i 片段下标 j 站点下标 k 应用下标 Fkj 应用k 在站点j上被激活的频率 Rki 应用k被激活一次,对片段i进行读的次数 Uki 应用k被激活一次,对片段i写的次数 Nki= Rki+ Uki 应用k被激活一次,对片段i读写的总次数,分配方法,最佳适应法 将片断Ri分配到访问Ri次数
7、最多的那个站点上 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发出, 只使用Rt, 得益 BAt = Fkt Nki ( k At) 应用组A1: 由站点r发
8、出, 原先使用Rt或Rs(本地), 现在要一次远程，损失 BA1 = Fkr Nki ( k A1) 应用组A2: 由站点r发出, 原先使用R(本地), 现在要两次远程，损失 BA2 = Fkr Nki ( k A2) 应用组A3: 由不同于站点r,s,t的站点发出, 要访问Rt和Rs, 损失 BA1 = Fkj Nki ( k A3,j r,s,t) 分配得益 Bist = BAs + BAt - BA1 - BA2 - BA3,垂直分片情况,垂直分片情况,假定把站点r上的关系R垂直分成两个片段Rs和Rt，并将Rs和Rt分别分配在站点S和t,然后将应用分组并估算它们的利益情况,18,飞机订票
9、系统,现有三个站点： 站点1：丹佛机场（CO） 站点2：纽约机场（NY） 站点3：亚特兰大机场（GA） 可供查询各自班机的可用情况。他们有不同的概念模型。现需要将这三个个系统合为一个分布式数据库系统，以便从三个站点的任一办公室能查询班机的可用情况。 结果： 综合后建立起来的全局模式中，有一个概括分层被用来表示三个站点。值得注意的是，对三个局部模式，应以不同的方法翻译一个需要有关班机从一给定机场起飞的信息的查询。,19,飞机订票系统的主要设计步骤,需求分析 需求分析简单地说就是分析用户的要求 概念设计 将需求分析得到的用户需求抽象为信息结构 即概念结构设计，如画-图 逻辑设计 将E-R图转换为相
10、应的数据模型相符合的 逻辑结构，如关系模型 物理设计 确定数据库的物理结构； 对物理结构进行评价 分布要求分析 收集关于分布的信息，如水平分片的划分谓词 每一应用在各站点激活的频率等 分布设计 产生全局数据的分片模式和片段的位置分配模 式，分配模式描述了分配在各站点上的数据情况,实例研究:飞机订票系统,飞机订票系统中的分布设计分四步： 对每一实体选择分片原则 确定非冗余分配 在非冗余分配上引入冗余 在每一站点上重新构造局部模式,21,机场实体： 基于区域的水平分段 机场1， 机场2， 机场3 班机实体：基于起飞机场的导出水平分段 班机1，班机2， 班机3 旅客实体： 基于旅客预定的所有班机起飞
11、的导出水平分段 旅客1，旅客2，旅客3，旅客4，旅客5，旅客6，旅客7，,1. 分片设计,22,目标：是把各片段映射到使用该片段最多的站点上 问题：如何识别最频繁访问该片段的站点？ 方法：根据频率表与极化表，采用“最佳适应法”，令 Fij应用i使用站点j的频率； Pijk应用i使用站点j时片段k的极化值 于是从站点j访问片段k的次数给出如下： 因此，片段k被分配到站点j，使得,非冗余分配,根据分片原则 站点1：机场1， 班机1， 旅客1 站点2：机场2， 班机2， 旅客2 站点3：机场3， 班机3， 旅客3 根据极化表和频率表 站点2：旅客4，旅客6，旅客7 站点3：旅客5,2. 确定非冗余分
12、配,24,冗余分配,冗余分配的执行是使用“贪婪”启发式，可以采用上面已经阐述过的“所有得益站点法” 或采用 “附加复制法”就是初起使用非冗余分配，在每次迭代时，计算因增加一副本使其变成本地的检索访问的得益与为维护该副本一致性所需要的附加远程修改访问的损失之差值这个数字是个较大的正数时，把该片段的副本存储到得益站点，否则就不增加,冗余超出了同一实体所有片断的效益 机场实体：不进行冗余分配 班机实体：不进行冗余分配 有限冗余 旅客实体： 预定离开两个区域的乘客：旅客4，旅客5，旅客6，放到两个站点上 预定离开三个区域的乘客：旅客7，放到三个站点上,3. 冗余分配,26,局部模式重新构造,局部模式的
13、重新构造是重新构造片段分配站点上的局部模式，这一阶段也负责ER全局模型中的联系分配大多数联系是作为对应实体标识符间的结合实现的，建议把联系放置在具有最大基数性的实体或片段的站点上，使得必须传送的实体标识符尽可能少,BC,站点1的局部模式,4. 局部逻辑模式,自然分配,班机2,从,到,订票,登记,到,机场2,旅客2u 旅客4u 旅客6u 旅客7,AC,站点2的局部模式,局部逻辑模式,自然分配,班机3,从,到,订票,登记,到,机场3,旅客3u 旅客5u 旅客6u 旅客7,AB,站点3的局部模式,局部逻辑模式,自然分配,30,31,这种解决办法的最大特征是，通过只查看分配在该班机起飞站点上的数据，就可以回答关于班机的所有请求；为准备班机起飞，也不需要远程信息。 这种解决办法的缺点在于，旅客信息重复，并且在进行订票时必须仔细地管理旅客信息。,分配的优缺点：,32,Thank you ! 谢谢观看！,
