前言

在第一篇文章中，笔者又做了一些补充。因为补充内容属于该课程第一章节的内容。此后笔者文章的更新主要会以完整章节为主，而不是上一次课更新一次。这篇文章将主要是记录分布式数据库系统的设计课程总结，也就是该门课程的第二章。该门课程主要分为三个部分，第一部分主要介绍一些基础概念(也就是第一篇文章)，第二部分主要是讲分布式数据库系统的设计(也就是该篇文章，实际课程中只占据一个章节),第三部分主要讲数据库管理系统中的一些技术实现要点。第三部分是该门课程的重点，占到百分之八十左右。

一、分布式数据库系统创建方法

分布式数据库系统有两种创建方法，即自底向上的组合法和重构法。

• 自底向上的组合法
  即利用现有的计算机网络和现存于各节点上的独立数据库系统，通过建立一个分布式协调管理系统，将他们集成为一个统一的DDBS，即基于之前的非分布式数据库系统站点进行构建。该方法工作量比较小，实现周期短，仅需要建立一个分布式协调管理系统即可。但是同样会面临几个问题如：解决数据一致性、可靠性；异构数据模型的转换问题；还要分析现存系统的功能。
• 重构法
  根据应用需求，按照某种设计思想和方法，采用统一的 观点，从总体设计开始，重新建立一个分布式数据库系统。该方法可以从最开始解决数据的一致性和可靠性问题，但是投资大、开发周期长。

二、分布式数据库系统设计目标

分布式数据库系统设计的目标除包括集中式数据库设计中的目标外，还要包括如下加点：

• 数据库的本地性(近地性)
  即尽量减少对网络的应用，尽可能减少站点之间的通信次数和通信量。所以分布式数据库系统设计的一个主要原则是使数据和应用实现最大程度的本地性。
• 控制数据的适当冗余
  分布式系统在可用性和可靠性方面由于非分布式系统，主要原因之一是因为分布式数据库系统中存在数据的适当冗余。
• 工作负荷分布
  其中工作负荷分布要相对均匀，不能让其中摸个站点称为瓶颈，威胁到整个系统的运行。
• 存储的能力和费用
  这个就不做过多解释。

三、分布式数据系统设计内容

分布式数据库系统的设计主要包含两个方面:应用(功能)设计和数据库设计。基于应用需求的考虑(1、应用的原发站点；2、应用在站点被激活的频率；3、应用对数据对象的访问次数、类型和统计分布)，其中数据库的设计主要包含两个方面。

• 逻辑结构设计

• 物理结构设计
  数据的分片设计和数据片段位置的分配设计。下文将重点讲解这两点。

四、自顶向下设计DDB

4.1 数据库的分片设计

4.1.1 分片设计的目的

片段是指数据在各站点上分配和存储的逻辑单位。分片设计的基本目的是产生一个对全局数据核实的划分方案。使用这种方案得到的片段，不但能够减少应用中的操作量，而且能够对于应用具有最大可能的本地性(即个片段位于其使用最多的站点上)。

4.1.2 分片原则

• 完整性原则
  全局关系的所有数据项必须包含在某个片段中。
• 重构性原则
  所有片段必须能够还原全局关系。
• 不相交原则

4.1.3 分片方式

在第一篇文章中就有简单讲到几种分片方式，这里再进一步说明，并补充诱导分片方式。

• 水平分片
  将一个关系按某个条件划分成若干元组的子集。
  对全局关系执行选择操作的结果。
• 垂直分片
  将一个关系按列以属性组划分成若干片段。
  对全局关系执行。
  为保证可重构性，键属性应包含在每一个片段中。
• 混合分片
  水平分片和垂直分片的混合操作。
  可以理解为在一种分片方式的基础上再次进行其他分片方式。
• 诱导分片
  将一个关系按另一个与其有关联性质的关系的属性做水平分片。即数据库中表的关系，涉及外键和內键概念。如有两张表，一张表示公司职员信息表(包含部分信息，不包含位置信息)，另一张是公司部门表(包含位置信息)。不同的部门可能在不同的城市，所以公司职员信息表也会按照公司部门信息表来进行分片。 这种分片结果具体是通过‘半连接’操作的结果计算得到 。诱导分片是对全局关系执行半连接操作的结果。

自然连接的个数为：R和S中公共属性做组合(c)的结果。如下图，R中有 2 个 c1 和 1 个 c2，S中有 1 个 c1 和一个 c2 ，所以2 x 1 + 1 x 1 = 3。

另外，还要知道下图中，∝:表示半连接 ∞:表示自然连接。πr表示取R表的映射，即取R表中包含的属性A、B、C。如果是πs则表示取S表的映射，即取S表中包含的属性C、D。

下面两个等式均是说明自然连接和半连接之间的关系。等式的左边都是半连接，等式的右边是对自然连接做了一些转化，转化成半连接。

4.2 数据库片段的位置分配设计

4.2.1 数据片段位置分配的方法

数据库片段的位置分配方法概括来说主要有两种非冗余分配法和冗余分配法。

• 非冗余分配法
  即一个片段只分到一个场点。非冗余分配的涉及比较容易，最简单的方法是‘最佳适应’法(best-fit），即对每一种分配都进行估算，然后选择收益最好的站点。该法不考虑把一个片段和另一个相关片段放在同一站点相互影响的情况，即不考虑诱导分片的情况。
• 冗余分配法
  冗余分配的设计主要有下面两种方法：
  (1)“选择所有收益场点”法:首先确定一种非冗余的分配方案，然后从全部场点中选择一组站点，如果将片段的一个副本分配到这组站点所得到的收益高于花费的代价，就把该副本分配给这一组站点。
  (2)“添加副本”法:首先确定一种非冗余的分配方 案，然后添加副本，直到收益小于代价。

4.2.2 分配的费用和收益的估算

在说估算之前，请先了解下列各个变量所代表的含义。下面的各种计算基本都是基于这些变量来建立的。 变量含义说明

(1)水平分片估算

• a.最佳适应法
  将片段 fi 分配到对fi访问次数最多的站点上(可理解为分别找到每个片段 i ，所在的站点 j 上所有应用累加起来读写片段 i 的数量。计算得到的 Bij 最大即为最大收益结果)。在站点 j 上对 fi 的本地访问次数为:

  
  

• b.选择所有收益场点法
  将应用的本地检索收益与从其他站点发出的更新代价比较。将片段 i 分配到站点 j 得到的本地检索收益如下。注意这里和最佳收益法不一样，下式只针对读操作做，没有涉及写操作。

  
  
  

  将片段 i 分配到场点 j 从其他站点发出的更新代价:

  
  
  所以总的收益以Brij 和Buij间的差衡量:
  
  如果Bij >0，则将片段i分配到j站点。最佳适应法中只选择一个站点，而选择所有站点收益场点法中，只要收益大于损失，就可以在该站点添加副本。

• c.添加副本法
  添加副本可以额外 高系统的可用性和可靠性，意大利人S.Ceri 出用β函数估算添加副本带来的额外收益。选择所有站点收益场点法，只考虑了更新操作和近地性。“添加副本”法 中将可靠性和可用性因素都考虑进去，下面这个函数可以衡量可靠性。该公式中，当di = 1时，该式值为0。随着di从1到无穷大的逐步增加，该式的值会逐渐增大，但是增大到一定程度时，该式的值增加程度会越来越不明显。这点敲好和可靠性与副本数量的规律呈一致。
  

  
  di 为片段i的副本个数( i的冗余度) ，Fi 为片段i在每个站点全复制时的收益。结合选择所有收益场点法中的公式，可用下列公式估算在站点j上添加副本的收益:
  
  当di 增加，而Bij的增大不明显时，就停止增加di 。
  (2)垂直分片估算
  注意下图中的A3为虚线，A4为实线。
  
  将全局关系垂直分片R1和R2，并将R1和R2分配到Site1和 Site2上。根据片段的应用情况分别计算收益:

• 应用组 A1
  对于应用组A1，发自本地站点Site1，而且只检索和更 新R1，且更新不涉及R1的键。此时可获得收益:

  
  

• 应用组 A2
  对于应用组A2，发自本地站点Site2 ，而且只检索和
  更新R2，且更新不涉及R2的键。此时可获得收益:

  
  

• 应用组 A3
  对于应用组A3，它发自站点Site3，访问R1或R2。原先进 行本地访问，现在需要做远程访问，因此损失:

  
  

• 应用组 A4
  对于应用组A4，它发自Site3 ，同时访问R1和R2，原先进 行本地访问，现在需要做两次远程访问，因此损失:

  
  

• 应用组 A5
  对于应用组A5，它发自除Site1 、 Site2 、 Site3之外的其 它站点，原先同时访问R1和R2(远程访问)，现在需要多做 一次远程访问，因此损失：

  
  
  

• 总的收益

  
  

五、DADAID-D方法

DADAID-D 是作为集中式数据库设计 DADAID-1 方法论的扩充而构造的，后者分成四个阶段: 需求分析、概念设计、逻辑设计和物理设计。DADAID-D 要求对其增加两个阶段：分布分析阶段和分布设计阶段。DADAID-D 方法的分布式数据库设计步骤如上图。

上图中的概念设计，是指在需求分析的基础上，用统一的方法或建模语言设计出来基本概念，进一步得到全局数据模式和全局操作模式，该步骤无需考虑计算机中相关实现细节。概念设计常用的工具是 E-R 图。另外还要知道，从需求分析到概念设计这个过程需要人的主观能动性。上图中的逻辑设计具体是指将概念设计得到的结果用计算机的形式实现。

分布要求分析的目的是收集以后用于推动分布设计所需要的信息。这一阶段的输入是对用户分布的要求和全局数据概念模式与操作模式。输入是三种类型的表：

• 频率表：在各站点上每应用的激活频率。
• 划分表：潜在可能的水平分片规则。
• 极化表：基于定量分析方法说明如何影响应用处理的本地性，指明由一给定站点发出的一给定应用访问一给定片段的概率。

DADAID-D 方法中分布设计分为四个阶段：分片设计、非冗余分配、冗余分配、局部模式重构。其中非冗余分配和冗余分配也可以统称为分配设计。关于分片设计和分配设计就不在重述，前文中已经写到。这里只简单说下局部模式重构。局部模式重构是指重新构造分配到各站点的片段的局部模式。比如：假设 f1 被分为 f11和 f12 ，分别放在 1 和 2 站点上。 其中 2 站点上还有 f2 ，f2 没有做分片处理，f2 和 f12 做关系重构的话，则 f11 和 f2 也要做关系匹配(f11 和 f2不在同一站点上，所以实现起相对比较麻烦)。

六、分布式数据库设计实际案例简单分析

下面将结合一个简化的飞机订票系统案例，按照DADAID-D 方法分析其大概实现过程以及相关细节实现方案原因。

6.1 案例介绍

假设订票系统维护在一个数据库，该数据库分布在三个站点(即三个机场1、2、3)。数据库存储机场规程、班机起降和旅客订票等数据。按照该案例额，可以很容易找到三个实体对象即机场、班机和旅客。他们分别带有的基本属性如下:

• 旅客:名字、电话
• 班机:机号、日期、可用座位、登机口、座位图、延期
• 机场:符号、区域(如:‘N’、’E’、’S’表示所在大概方位)、城市、 安全规则

6.2 全局概念模式E-R图(概念设计)

按照三个实体对象和三个应用(订票、登记、起飞)可以得出如下全局概念模式 E-R 图。

6.3 全局操作模式(概念设计输出)

全局操作模式是指应用的全局操作的模式。这里针对三个应用即订票、登记、起飞具体操作模式将做进一步介绍。下图中的 k 表示属性，表示他们被用作访问数据的关键词；“o, w”中，o表示输出，w表示写入。

6.3.1 订票

用于旅客预订机票操作。

6.3.2 登记

用于旅客登机登记任务。依旅客姓名、班机号、日期确定旅客和班机，找出票 的种类、座位图，更新座位图，创建“登记”实例( 座位号、行李号)。

6.3.3 起飞

显示即将从一个机场起飞的 30 个班机信息。

6.4 创建逻辑访问表

基于上述全局操作模式分析，对每个实体，估算应用的定量数据，建立逻辑访问表。表中的列对应于操作，行对应于书体属性。

6.5 全局关系数据模式(概念设计输出)

针对上述分析这里可以得出七个对象(三个实物和三个操作)，其中登记操作又进一步细化得到从和到两个操作。

1. 机场(符号，区域，城市，安全规则)
2. 班机(机号，日期，可用座位，座位图，登机口
   延期)
3. 旅客(名字，电话)
4. 从(机号，日期，符号，起飞时间)
5. 到(机号，日期，符号，到达时间)
6. 订票(名字，机号，日期，种类)
7. 登记(名字，机号，日期，座位号，行李)

6.6 分布要求分析

6.6.1 频率表

频率表给出各个应用在三个站点上使用的频 37 率(激活的次数)。

6.6.2 划分表

划分表给出各个实体的各种可能分片的方式。

• 1、基本划分
  基本划分是结合实际业务场景，直观上就可以做出的一些分片方式判断。如下表，实体机场可以依据区域做分片处理，实体旅客可以依据电话号码的前三位做区分(美国的电话号码前三位表示区域信息)。

  
  基本划分表

• 2、导出划分
  在获得基本划分之后，可以基于机场划分为区域(也就是基本划分表的前两行)的这个基本划分可能产生的导出划分表。
  

  导出划分表
  上述导出划分表中的班机起飞区域指旅客各次订票所对应的班机起飞区域。显然一名旅客有可能选择过一个/两个/三个起飞区域。所以会有如下注释表中的七种可能，也就是说实体旅客存在七种分片方式(P1~P7)。也可以看出，上述的导出过程为：“机场” >>>>“班机” >>>>“旅客”。
  注释表

6.6.3 极化表

极化表给出从一个站点发出的一个应用访问分布式数据库某片段的概率。

极化表

6.7 分布设计

6.7.1 分片设计

这里的分片设计主要是为各个实体选择合适的分片原则。

垂直划分对本案例无用。这是因为三个站点的业务都是完全一样的，所以所需要的数据也都是一致的。如果三个站点的应用不一样，所需要的数据也不一样，各个应用可能会使用到实体对象的不同属性，此种情况下应该考虑使用垂直分片方式。

基于上述的分布要求分析，可以得到各个实体(机场、班机、旅客)的水平分片方式:

• “机场”基于所在区域做水平分片(片段:机场1，机场2，机场3)
• “班机”基于起飞机场所在区域做诱导分片(片段:班机1，班机2，班机3)
• “旅客”基于旅客订票涉及的所有班机起飞 区域做诱导分(片段:旅客1，旅客2，旅客 3，......，旅客7)

6.7.2 非冗余分配

• 站点1:机场1，班机1，旅客1
• 站点2:机场2，班机2，旅客2
  旅客4，旅客6，旅客7
• 站点3:机场3，班机3，旅客3
  旅客5

参照上述 6.6.1 的频率表和 6.6.3 的极化表，分配 “旅客4”，“旅客5”，“旅客6”，“旅客7”。至于为何要如此分配做一个简单的计算便可清晰看出。可以结合 4.2.2 节中的最佳适应法做收益计算，下面的计算就拿机场片段 P1 分别在三个站点上的收益比较来计算分析。
P1分布在站点 1 的收益为:

B1 = 10000 * 80  + 8000 * 0 + 100 * 100 = 810000

P1分布在站点 2 的收益为：

B2 = 20000 * 20  + 12000 * 0 + 120 * 0 = 400000 

P1分布在站点 3 的收益为

B3 = 10000 * 10  + 8000 * 0 + 100 * 0 = 100000 

结合上述计算，显而易见，机场片段 P1 分布在站点 1 上收益最大、最为合理。同理，无论是班机片段，还是旅客片段都是按照上述同样的方式计算得出。

另外，从 6.6.1 的频率表可以看出，站点 2 的客流量明显比站点 1 和 3 大，所以多数旅客片段(旅客4，旅客6，旅客)分配在站点 2 上，这一点也是合情合理的。

6.7.3 冗余分配(对旅客实施)

许多情形中，与冗余有关的代价超出了同一实体所有片段的效益，机场和班机就是此种情况，所以机场、班机不做冗余分配，都只存储在一个站点上；旅客 4、5、6 分别有两个副本，分配到起飞机场所在的站点上; 旅客 7 有三个副本，分配到所有站点。

• 站点1:机场1，班机1，旅客1
  旅客4，旅客5，旅客7
• 站点2:机场2，班机2，旅客2
  旅客4，旅客6，旅客7
• 站点3:机场3，班机3，旅客3
  旅客5，旅客6，旅客7

6.7.4 局部模式重构

重构分配到各站点的片段的局部模式，重点解决 “联 系”的分配。

七、自底向上设计DDB

通常把现有数据库继承起来构成分布式数据库时，可采用自底向上的方法。该方法重点是把现有的各种不同的数据库模式集成为全局模式。模式集成过程中主要是应用继承的思想，抽离出公共部分。然后针对不同数据库分别创建子类。

注意，自底向上的设计方法不宜于水平关系的设计。同一个全局关系的各个水平分片必须具有相同的关系模式，这一要求在自顶向下的设计方法中很容易实现。但是，自底向上的设计方法是先独立地设计各个数据库，然后再把他们集成起来，这种情况下很难发现这个特点。因为水平分片是分布式数据库设计中一个重要且很有用的特点，所以在继承过程中应该设法下盖本地关系的定义，这样就可以把这些本地关系看成是一公共全局关系的水平分片。

把现有数据库继承为一个分布式数据库时，原有的数据库很可能用不同的 DBMS ，这将构成易购系统，增加数据集成的复杂性。在集成时可以在每对不同的DBMS之间进行一对一的翻译，但通常情况下并不是如此做。而是选择一公共数据模型，然后再把设计这个 DBMS 的所有不同模式都翻译成这种唯一的表示方法。

综上所述，自底向上的设计方法中需重点解决三个问题:

• 选择公用数据模型描述数据库的全局模式
• 将各站点的数据模式翻译成公用数据模型
• 模式集成

小结

本文介绍了数据库系统设计中的基本概念、方法、目标和设计内容。设计方法有自顶向下和自底向上，其中重点讲了自顶向下的DADAID-D方法。并结合简化版的飞机订票系统案例说明分布式数据库自顶向下的DADAID-D设计方法。另外，在第四节(自顶向下设计DDB)中，重点分析了数据库片段分配的费用和收益的估算，该部分内容在数据库设计中比较重要，应结合飞机订票系统案例重点理解。