一、前言

分布式数据库（ Distributed Database ），简称DDB，即物理上分散而逻辑上集中的数据库系统。

它是数据库技术与计算机网络相结合的产物，也因此，其高度依赖高速网络。

分布式数据库系统（ Distributed Database System)，简称DDBS。分布式数据库管理系统简称为DDBMS。分布式数据库系统DDBS = DDB + DDBMS

比较经典的一句话是，分布式数据库应该看起来完全像一个非分布式数据库。

信息孤岛

信息孤岛是指相互之间在功能上不关联互助、信息不共享互换以及信息与业务流程和应用相互脱节的计算机应用系统。

如果这些独立的系统之前进行交互，会出现复杂的交互网络。

分布式数据库系统的特点

• 物理分布性：数据不是存放在一个站点上
• 逻辑整体性：是与分散式数据库系统的区别
• 站点自治性：是与多处理机的系统的区别
• 数据分布透明性：用户不必知道所操作的数据放在何处
• 集中与自治相结合：各数据库彼此独立自治，又整体集中
• 存在适当的数据冗余度：适当的数据冗余，在分布式情况下很多时候是方便的
• 事务管理的分布性：分布式事务管理是一个挑战

二、分布式数据库分类

按局部数据模型分类

• 同构型DDBS
• 同构同质型
• 同构异质型：（同一数据模型，不同的DBMS）
• 异构型DDBS

按全局控制类型分类

• 全局控制集中型DDBS
  分布式控制和数据字典集中在一个站点
• 全局控制分散型DDBS
  分布式控制和数据字典分散在各个站点
• 全局控制可变型DDBS（主从型，主站点＋辅站点）

三、数据分片

当数据量过于庞大，单机难以支撑时，会面临扩展瓶颈，那么就需要将数据进行拆分，分散在多个数据库实例上。

数据分片是指将数据全局划分为相关的逻辑片段，有水平切分、垂直切分、混合切分三种类型。

• 水平切分:可以简单地理解为按照数据行进行切分，即一部分行放在某数据库，另外一部分放在另外的数据库实例。比如可以按照时间、地区拆分，亦或是根据hash进行拆分。
• 垂直切分：垂直拆分可以简单理解为按照表进行分类，将表分布在不同的节点上,基本目标是将使用频繁的属性聚集在一起

• 混合切分：水平切分与垂直切合的结合。
  

数据分片的基本原则

• 完备性条件
• 可重构性条件
• 不相交性条件

分片时遵循的两个原则

• 完整的：同一片段的任意两个元组能够被任一应用以同等概率访问
• 最小的：分配的和实际应用的是密切相关的

分片

垂直分片后将数据组合起来需要执行连接运算，比水平分片后的数据组合要困难一些。

分布式数据库的模式结构

• 全局外模式
• 全局概念模式
• 分片模式
• 分配模式
• 局部概念模式
• 局部内模式

四、分布式查询处理及优化

分布式数据库需要考虑查询问题，其需要做的就是把一个分布式数据库上的高层次查询映射为本地数据库上的操作，最后通过网络通信，将操作结果汇聚起来。

相对于集中式数据库，分布式数据库还要考虑额外的几个问题：

• 选择最优站点查询
• 数据传送方式
• 站点之间交换数据的问题

相对于集中式的查询目标，分布式需要多考虑一项 “通信开销代价”

对水平分片的优化

• 尽量把选择条件下移到分片的限定关系处，再把分片的限定关系与选择条件进行比较，去掉它们之间存在矛盾的相应片断。
• 如果最后剩下一个水平片断，则在重构全局关系的操作中，就可去掉“并”操作.

对垂直分片的优化

• 把垂直分片所用到的属性集，与查询条件中的投影操作所涉及的属性相比较，去掉无关的垂直片断。
• 如果最后只剩下一个垂直片断与查询有关时，去掉重构全局关系的**“连接”**操作（至少可以减少“连接”操作的次数）

基于半连接算法的查询优化

网络中两个站点间进行连接操作时，需要将一个站点的关系通过网络传输到另一站点与在该站点上的关系进行连接操作。在这个过程中，如果传输整个关系，那么网络传输中的数据量会很大，网络本身复杂多变，如果一次性传输较大的数据量定会产生不少问题，而在实际的连接操作中，并非所有的数据都参与连接操作。

因此为减少传输数据量，可以禁止那些不参与或者无用的数据在网络中传输，而半连接操作就是针对这一问题提出来的，它要实现的目标是减少进行连接操作关系的数据量，从而减少在网络上的传输的数据量，但同时在某种程度上会增加通信的次数以及本地处理的时间。

简单来说，就是在连接之前，先消除无用数据，减少网路通信中传输的数据量。

基于直接连接算法的查询优化

• 利用站点依赖信息
• 分片与复制算法
• 站点依赖和数据复制结合
• Hash划分算法

五、分配设计

• 冗余
• 部分冗余
• 不冗余

设计原则

在实际应用中，部分冗余应用是比较多的

设计所需要的信息

• 数据库信息
• 应用信息
• 结点信息
• 网络信息

习题

• C0传输延迟
• C1单位数据传输代价

模式集成

异构多数据源在模式层面的集成

六、分布式并发控制

1.分布式数据库的基本封锁算法

简单分布式封锁法

• 封锁全部副本（各站点负责各自数据的封锁管理）
• 过程消息（请求封锁、封锁确认、请求更新、更新确认、解除封锁）需要发送n次
• 各站点间进行相当大的数据传输。

主站点封锁法(集中封锁法)

• 选定一个站点为“主站点”，负责系统全部封锁管理。
• 容易造成“瓶颈”，制约可靠性和可用性

2.两阶段封锁协议(2PL)

• 所有的封锁操作必须在第一次解锁操作之前
• 任何事务在操作数据之前必须获得锁
• 第一阶段是封锁阶段，也称扩张阶段，第二阶段是解锁阶段，也称收缩阶段
• 第一阶段和第二阶段间隔点称为封锁点

若分布式数据库中，事务遵循2PL，则分布式数据库事务处理是可串行化的。

2PL分类

• 基本的2PL（在完成数据项的访问后立即释放锁，可能产生死锁，可能读到“脏数据”）
• 保守的2PL（事务在执行操作前获得所有操作数据上的锁，不会产生死锁，但难以实现）
• 严格的2PL（事务在提交或撤销前不能释放任何排他锁，可避免脏数据，不能避免死锁）
• 严酷的2PL（事务在提交或撤销前不能释放任何锁，也不能避免死锁）

实现方法

集中式2PL实现

分布式2PL实现

3. 多粒度封锁

• 允许多粒度树中的每个结点被独立地加锁。
• 对一个结点加锁意味着这个结点的所有后裔结点也被加以同样类型的锁。
• 数据项可能以两种方式封锁：显式封锁和隐式封锁，显示封锁和隐式封锁不能冲突。
• 检查会比较是否加锁会比较麻烦，故为了管理的方便引入意向锁。

4.意向锁

• 如果对一个节点加意向锁，则说明该节点的下层节点正在被封锁
• 对任一节点封锁时，必须先对它的上层节点加意向锁
• 意向锁指出该节点的某个后代需要锁的类型

意向锁的类型

意向锁并不是真正锁数据，它是表明一种意思，即该结点的下层结点正在实际加锁

• 意向共享锁(IS)
  对一个数据对象加IS锁，表示某些后代将会请求S锁。
  、例：若对元组加S锁，则对数据库和关系要加IS锁。
• 意向排它锁(IX)
  对一个数据对象加IX锁，表示可能对其下层结点加X锁。例：若对元组加X锁，则对数据库和关系要加IX锁。
• 共享意向排它锁(SIX=S+IX)
  对一个数据对象加SIX锁，表示当前结点处于S封锁中，但是下层某些结点将请求X锁。即事务要读下层结点中的对象，还可能要更新一些对象，因此要对当前结点加IX锁。

锁的相容矩阵

需要注意的是两个事务对某个结点T的SIX和IX是不相容的，因为对于SIX=S+IX，那么根据多粒度锁树的概念，T结点的子结点是加S锁和X锁的，那么这就会出现读写锁冲突。

5.可串行化调度

串行调度：

• 一个事务的第一个动作是在另一个事务的最后一个动作完成后开始。即调度中事务的各个操作不会交叉，每个事务相继执行。
• 串行调度总是可以正确执行，但是串行调度效率很低。

如果一个调度等价于串行调度，那么称该调度为可串行化调度。

判断可串行化调度

p < S q：（指在S调度序列中，p排在q的前面）

例如：

有：
所以通过优先图算法可以看出来S3 是有回路的，不是可串行化的。

并发控制的时标技术

基于时标的并发控制方法

• 给每个事务赋予一个唯一的时标，事务的执行等效于按时标次序串行执行。如果发生冲突，则通过撤消并重启一个事务来解决的。事务重新启动时，则赋予新的时标。
• 时标(Time Stamp)用来唯一识别每个事务并允许排序的标识
• 时标具有唯一性和单调性，可以采用计数器或系统时钟来产生时标，在分布式系统中有全局时标和本地时标之分。
  

七、分布式事务控制

• 事务是访问或更新各种数据项的最小逻辑工作单位
• 一个分布式事务由主事务（负责事务的开始、提交或异常终止）和多个子事务（局部事务，完成对数据的操作）组成。
• 分布式事务与一般事务的不同表现在，全局事务的主事务和子事务都完成才能提交，任何一个子事务失败，都要Rollback

分布式事务抽象模型

可分为本地事务管理器和分布式事务管理器。

集中式事务模型

总结

对分布式数据库的最终目标，是“让一个分布式数据库看起来不像是一个分布式数据库”。