Database Review

Overview

History

分布式数据库系统的研究始于20世纪70年代

第一个分布式数据库系统 SDD-1由CCA公司于 1979年在DEC机上实现

较早的DDBMS：POREL、System R*、 Distributed INGRES、C-POREL

Category

按局部数据模型分类

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

按全局控制类型分类

• 全局控制集中型DDBS

  分布式控制和数据字典集中在一个站点

• 全局控制分散型DDBS

  分布式控制和数据字典分散在各个站点

• 全局控制可变型DDBS（主从型，主站点＋辅站点）

数据分片（data fragmentation）

• 水平分片
• 垂直分片
• 混合分片
• 导出分片

分片规则

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

数据分布（data distribution）

根据某种策略把数据分片所得的逻辑片断分散地 存储在各个站点上

• 集中式（安排在同一站点上）
• 分割式（分布在不同站点上，无冗余）
• 复制式（每个站点都有一个完整的副本）
• 混合式（分割式和复制式的混合，有冗余）

模式结构

• 全局外模式：全局应用的用户视图
• 全局概念模式：全体数据的逻辑结构和特征的描述。
• 分片模式：描述每个片段及全局关系与片段间的映象，片段间不允许重复
• 分配模式（决定是否冗余）： 描述片段到不同结点间的映象（片段的存放位置）
• 局部概念模式 ：全局概念模式的子集在一个站点上的物理映像的逻辑结构及特征描述
• 局部内模式 ：描述局部概念模式涉及的数据在局部DBMS中的物理存储

特点

• 数据分片与数据分布独立
• 数据冗余显式控制
• 局部DBMS独立

DDBMS 功能结构

除集中式数据库的基本功能，还必须提供：

• 数据跟踪：利用日志记录数据分布、分片和复制的能力
• 分布式查询处理
• 分布式事务处理
• 复制数据的管理
• 数据完整性与安全性管理
• 分布式目录管理
• 站点间的通信

数据独立性

集中式

• 逻辑独立性
• 物理独立性

分布式

• 逻辑独立性
• 物理独立性
• 分布独立性（分布透明性）
  • 分片透明性（完全分布透明性，Level 1）
  • 分配（位置）透明性（中级分布透明性，Level 2）
  • 局部映象（数据模型）透明性（低级分布透明性，Level 3）
  • 无分布透明性：异构数据

其他透明性

• 并发透明性
• 故障透明性
• 复制透明性
• 语言透明性
• 网络透明性

Architecture

The architecture of a system defines its structure. This means that the components of the system are identified, the function of each component is specified, and the interrelationships and interactions among these components are defined.

The specification of the architecture of a system requires identification of the various modules, with their interfaces and interrelationships, in terms of the data and control flow through the system.

Design

组合法（自底向上）

1. 剖析网络功能
2. 剖析原有数据库系统
3. 解决数据 的一致性、 完整性和可靠性
4. 难度较大，通常是异构或者同构异质 DDBS

重构法（自顶向下）

1. 根据实现环境 和用户需求
2. 按照DDBS的设计思想和方法
3. 从总体设计做起(包括LDBS） 重新建立一个 DDBS
4. 可有效解决数 、据一致性、完 整性和可靠性问题。 通常是同构异质或同构同质 DDBS

混合法

目标

• 分布式数据库的本地性或近地性：数据存放在最频繁访问的地方（90/10准则）
• 控制数据的适当冗余：冗余增加了可用性、可靠性，提高了效率，也增加维护一致性的开销
• 工作负荷分布：各站点上存取应用尽量平衡，提高并行度和效率， 但可能降低本地性
• 存储能力和费用：根据站点的存储容量分布数据，也可由专门的站点存储数据

自顶向下

数据分片设计

分片目的 ：产生一个对全局数据合适的分片方案

• 将分片片段作为存储和分配单位时，能够减少应用的数据操作量；
• 对数据的存取具有最大可能的本地性，即使得应用能够尽量存取本站点的数据。

分片类型和方法

• 水平分片（基本的水平分片和导出的水平分片）
• 垂直分片
• 混合分片

水平分片性质

• 如果某个谓词pi将某个片段f，进一步分解为fi和fj，而且至少有一个应用对fi和fj的访问是不同的，那么此谓词pi就是相关的（relevant）；
• 如果所有谓词都是与应用相关的，那么这个谓词集合就是最小的；
• 完整性和最小性不是必要条件，但是对于简化分配问题 有好处。

算法生成分片

水平分片实际应用

• 确定谓词集合是否完备可能开销很大， 一般（建议）不考虑所有应用，而是考虑重要应用；
• 不区分具有相似特征的数据片；
• 得到兼顾效率的合适的水平分片

导出的水平分片

• 从另一个关系的属性性质或水平分片推导出来的
• 一般涉及多个关系
• 可使关系之间的连接变得更容易

垂直分片

通过“投影”操作把一个全局关系分成若干片段，基本目标是将使用频繁的属性聚集在一起

垂直分片设计

• 统计属性的亲和关系
• 构造属性亲和矩阵
• 寻找属性分割点

亲和关系

垂直分片与模式分解

• 类似，目的不一样；
• 模式分解是为了概念的单一化，是概念设计的内容；
• 垂直分片是为了数据的分布，是概念设计之后的内容；
• 模式分解需要考虑数据依赖；
• 垂直分片考虑的是数据的聚集性。

位置分配设计

在满足用户需求的前提下，把设计好的数据片段分配到相应的站点上，尽可能提高系统效益

费用和得益估算

水平分片估算

垂直分片估算

小结

• 设计最佳的分配方案是一个复杂的优化问题；
• 如果要求高可用性，且大多是检索应用，全复制是比较好的选择；
• 如果大多是在确定站点上的部分应用，应用数据应该复制到这些站点上；
• 如果执行许多更新，则要限制复制的副本；
• 从经验数据看副本数为2或3时收益较为理想。

DATAID-D方法

分布要求分析

分布设计

自底向上

自底向上方法要解决的问题

• 将现有的各种不同的数据库模式集成为全局模式
• 需要解决不同数据库之间的不一致

解决方法

在全局分布式层采用统一的数据模型表示

处理步骤

1. 选择公用数据库模型来描述数据库的全局模式
2. 把每个站点上的本地模式翻译成公用数据模型
3. 把各站点上的本地数据模式集成为一公用的全局模式

构造全局模式（超视图）的方法

• 把各站点上的数据库模式看成是全局模式的一个视图
• 采用概括分层结构进行视图综合
  • 共同属性构成超类型，“差”属性各建一个子类型
  • 一个具有共同属性（超类型），两个具有不相交属 性（子类型）

视图综合次序

• 一次把一个视图和全局模式进行综合，逐步构造起全局视图
• 首先综合最大的或最重要的视图，然后综合小的或者不重要的视图

视图综合需要解决的问题

• 识别相似性

  在已有的不同模式间识别属性、域或实体结构的相似部分，判别是否能够合并实体或概括为上层实体。

• 识别冲突

  在识别相似的基础上，分析相似数据的不同表示或域定义。通过引入差异或采用折中的方法解决冲突。

  • 命名冲突：同物异名，异物同名
  • 域差异：不同站点上的相同实体有不同的域
  • 定标差异：不同模式的相同属性有不同度量标准
  • 结构差异：现实世界中的同一对象有不同表示 （属性或实体）

• 处理操作间的不一致数据

  • 不一致的现象
    • 同一对象在不同站点有相同标识符；
    • 同一对象在不 同站点有不同的值；
    • 同一对象有新值和旧值；
    • 其它不符合逻辑的错误
  • 解决策略
    • 直接显示任一不一致值，且不通知用户
    • 直接显示不一致，通知用户，让用户处理
    • 将不一致值处理为一个新的结果，如求平均值
    • 显示最新值
    • 显示最可靠系统的值

Query Optimization

查询优化准则

集中式

• 查询转换为代数表达式
• 从所有等价表达式中选择最优的代数表达式

分布式

• 集中式问题
• 站点之间交换数据的问题
• 选择最优执行站点的问题
• 数据传送方式的问题

数据的分布和冗余增加了并行处理查询的可能性， 从而可以缩减查询处理的响应时间。

• 总代价最小

  

• 响应时间最短

  • 查询响应时间：与通信时间、站点上的处理时间有关
  • 可利用站点间的并行处理缩短查询时间

关系代数

连接

等值连接

自然连接

半连接

校正：

虽然半连接通常是基于等值条件的，但它的定义并不限制于等值连接。

外连接

限定关系

分布式查询分类

• 局部查询
• 远程查询
• 全局查询

局部查询

1. 选择运算尽可能先做
2. 把投影运算和选择运算同时进行
3. 把投影同其前或后的双目运算结合起来
4. 把某些选择运算和在它前面执行的笛卡尔积结合起来成为一个连接运算
5. 在执行连接前对关系适当地预处理（在连接属性上建立索引和对关系排序）
6. 找出公共子表达式

远程查询

• 只涉及单个站点上的数据，优化策略与局部查询相同
• 在有多个站点的情况下，就近处理

全局查询

• 具体化（materialization）
  • 对查询进行分解，确定查询使用的物理副本，落实查询对象
  • 对于多个副本，需研究如何选择副本，使通信代价最小，并提高处理的并行性。
• 确定操作执行的顺序
  • 确定二元操作中连接和并操作的顺序
    • 先执行所有连接，再执行并操作
    • 先执行部分并操作，再执行连接操作
  • 选择和投影尽可能早进行
• 确定操作的执行方法
  • 确定若干个操作的合并执行，确定可用的访问路径
  • 连接方法在查询优化中起着重要作用
• 确定执行站点
  • 考虑通讯费用和执行效率（负载均衡）
  • 执行站点不一定是发出查询的站点

分布式查询优化

基本原理

1. 把查询转变为关系代数表达式
2. 分析得到查询树（语法树）
3. 把全局查询映射为片段的查询，得到基于片段的查询树
4. 利用关系代数等价变换规则优化查询树

处理步骤

1. 将关系表达式表示为语法树的形式；
2. 利用等价变换规则尽量将选择和投影运算移向树的叶端，连接和合并操作尽可能上提；
3. 使多个选择和多个投影一起进行；
4. 将树的内部结点分组，形成不同的程序步。

优化算法

分布式环境中的特殊处理

• 如果是水平分片，把分片的限定（分片条件）与选择条件进行比较，判别它们之间是否存在矛盾，去掉存在矛盾的片段。
• 如果只剩一个水平片段，则可去掉重构全局关系的“并”操作。
• 如果是垂直分片，把片段中的属性集与投影操作涉及的属性集进行比较，去掉无关的片段。
• 如果只剩一个垂直片段，则去掉重构全局关系的“连接”操作。

水平分片查询优化

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

基于半连接的查询优化

s上基于半连接技术执行连接

代价估算

基于直接连接的查询优化

四种基于直接连接的优化算法（考虑关系分片）

1. 利用站点依赖信息的算法
2. 分片与复制算法
3. 站点依赖和数据复制结合算法
4. Hash划分算法

站点依赖算法

分片与复制算法

站点依赖与数据复制结合方法

Hash连接算法

比较

假定站点S1，S2分别有关系R1，R2的片段，每个片段的大小是R的一半 （R/2）

• 站点依赖算法
  • 无数据传递
  • 可利用索引做本地连接
  • 每个站点连接数据总量是R
• 分片和复制算法
  • 数据传输总量是R
  • 数据传送后，可能要重新创建索引
  • 每个站点的连接数据量是(3/2)R，一个全关系和一个片断
• Hash划分算法
  • 数据传送量是R
  • 索引可能无法使用（比片段复制算法效率更低）
  • 每个站点的连接数据量同站点依赖

常用策略

• 两个关系在同一个站点

  • R∞S，称外层关系为R，内层关系为S
  • 嵌套循环法
    • 顺序扫描外层关系R，对于R的每一元组扫描内层关系S
    • 查找在连接属性上一致的元组，组合起来构成结果的一部分。
    • 需要扫描一次关系R和Card（R）次关系S。
  • 排序扫描法
    • 先把两个关系按照连接属性进行排序
    • 然后按照连接属性值的顺序扫描这两个关系，使匹配的元组成为结果的一部分
    • 对两个关系都扫描一次，但增加了排序代价。

• 两个关系在不同一个站点，R（外层）和S（内层）

  • 整体传输
    • 如果传输S，则需保存S（被多次扫描）。
    • 如果传输R，则S可直接使用一次到来的R元组，不保存R。
  • 按需传输
    • 只传输需要连接的元组，一次一个元组，无需临时存储器。
    • 每次提取都要交换一次信息，传输代价高，只在高速局域网中才是合理的。
  • 三种选择执行站点的方法
    • R站点
    • S站点
    • 其他站点

• 利用并行性的直接连接操作策略

  • 通过重新分布元组实现操作内的并行，一般是不可行的，因为并行程度小，通信代价高。
  • 多个操作间的并行是可行的
    • 流水线并行
      • 一个操作A的输出元组作为第二个操作B的输入。
      • 在第一个操作尚未产生全部的输出元组集合之前，第二个操作就可以在它的输入上进行工作。
      • 可以在不同的站点上运行A和B，在A产生部分结果元组的同时，B来使用它们。
    • 独立的并行
      • 查询表达式中相互之间没有依赖关系的操作可以并行执行。

Transactions

事务概念

• 事务是访问或更新各种数据项的最小逻辑工作单位
• 它是一个操作序列
• 它可以使数据库从一个一致状态到另外一个一致状态
• 事务必须保证数据库的一致性
• 事务执行期间数据库可能不一致
• 当事务提交时数据库必须是一致的

分布式事务

• 分布式事务是集中式事务的扩充
• 分布式事务（全局事务）是数据库的一个分布式操作序列，被操作的数据分布在不同的站点上，这些操作要么全做要么全不做，是一个不可分割的工作单位。
• 一个分布式事务由主事务（负责事务的开始、提交或异常终止）和多个子事务（局部事务，完成对数据的操作）组成。
• 全局事务，涉及多个站点
• 局部事务，仅涉及一个站点
• 站点和通信链路故障都可能导致错误发生

分布式事务的特性（ACID）

• 原子性(Atomicity)

  一个事务要么全执行，要么全不执行，是不可分割的执行单位。

• 一致性(Consistency)

  指数据应满足的约束条件。分布式事务的执行能使得分布式数据库从一个一致状态转变为另一个一致状态。

• 隔离性(Isolation)

  事务更新过的数据在事务结束前对其他事务不可见。

• 持久性(Durability)

  已完成事务对数据的更新应持久，发生故障后应不会丢失更新。

分布式事务的独特性

• 全局事务的主事务和子事务全部成功提交，才能改变数据库状态，有一个失败，其他子事务操作都要撤销。
• 还要考虑数据传送、通信原语和控制报文等。

结构

分布式事务的状态

• 活动（Active）：从事务开始执行的初始状态始，事务执行中保持该状态。
• 部分提交（Partially Committed）：事务的最后一个语句执行后进入该状态。
• 失败（Failed）：一旦发现事务不能正常执行时进入该状态。
• 夭折（Aborted）：当事务被回滚后，数据库恢复到事务开始执行前的状态。
• 提交（Committed）：当事务成功执行后的状态。

实现模型

进程模型

• DBMS建立在操作系统之上；
• DBMS在创建进程、进程通信、读写磁盘、分配内存时请求操作系统服务；
• 分布式事务中的子事务序列是以进程方式完成的。

进程

• 进程是程序运行的最小单位，也是资源分配的最小单位。
• 包含进程说明与进程执行两个方面。
• 具有并发性，不同于过程。

事务代理（Agent）

• DDBMS中，各个站点上数据的操作是通过执行多个进程完成，这些进程称为分布式事务在执行站点上的“事务代理”。

• 事务代理是一个本地进程，代表应用执行对数据的操作。

• 代理可以执行应用程序员写的程序，也可以执行系统的原语函数。不同代理间通过报文实现通讯。

• 根代理（Root Agent）：应用启动站点上的代理。根代理所在的站点称作原发站点。

  一般，根代理负责发系统原语，只有根代理可以请求创建新代理。

进程协作（代理协作）

为了协调执行分布式应用的全局操作，分驻于不同站点的诸事务代理必须进行协调，有如下规定：

• 每一应用都有一个负责启动整个事务的根代理（总代理）。
• 只有总代理才能发出全局有效的事务开始、提交和撤销原语。
• 只有总代理才能请求建立新的事务代理。
• 各站点上的子事务都执行成功，总代理才能决定提交该事务；否则总代理将决定撤销该事务。

分布式事务管理问题（特殊性）

• 多个副本间的一致性

  在数据更新时，DDBMS负责保持多副本间数据的一致性。

• 站点故障

  当站点发生故障时, DDBMS能够检测到站点故障。当故障站点恢复后,DDBMS协同该故障站点上的DBMS, 使它的局部数据库保持与其他站点同步。

• 通信网络故障

  DDBMS应有能力处理通信网络故障：一般的通信故障和网络分割。

• 分布式提交

  采用提交协议保证分布式事务的正确提交。

事务管理的任务

• 当多个事务并发执行和事务执行发生错误（故障）时，使数据库仍保持一致状态。

​ 事务是一个一致计算与可靠计算的单位。

分布式事务管理的目标

• 维护分布式事务的原子性、一致性、持久性和隔离性。
• 获得最小的主存和CPU开销。
• 降低控制报文的传输个数和加快分布式事务的响应速度。
• 获得最大限度的系统可靠性和可用性。

抽象管理模型

• DTM（Distributed Transaction Manager）功能
  • 保证分布式事务的ACID特性；
  • 提供对分布式事务的控制和正确执行，包括：
    • 分布式事务的开始、结束；
    • 子事务的分解；
    • 协调子事务的执行；
  • 支持分布式事务执行的位置透明性，即将子事务分配到适当的站点上去执行。

控制模型

协调分布式事务中各成员DBMS执行其子事务的通用方法

• 主从控制模型
  • 主、从控制器，LTM之间无通信
• 三角控制模型
  • LTM之间可以传递数据，避免了主从之间不必要的传输
• 层次控制模型
  • LTM还可再创建Agent，控制其它LTM执行，比前两种复杂

故障

• 站点故障

  • 事务内部的故障
    • 非预期的、不正常的程序结束所造成的故障，如：
      • 计算溢出
      • 完整性破坏
      • 操作员干预
      • 输入输出错误
      • 并发事务的死锁等
  • 系统故障
    • 造成系统停止运行的任何事件，要求系统重启动，如：
      • CPU出错
      • 缓冲区满
      • 系统崩溃
      • 停电等
  • 介质故障
    • 磁盘损坏、磁头碰撞等，使数据库遭到破坏。

• 通讯故障

  • 报文故障
    • 报文错
    • 报文失序
    • 报文丢失
    • 报文延迟
  • 网络分割故障（网络断连）

故障处理难度

• 仅发生站点故障
• 站点故障与报文故障同时存在
• 站点故障、报文故障和网络分割故障同时存在

事务恢复

• 当发生故障时，保证事务原子性的措施称为事务故障恢复，简称事务恢复。
• 主要依靠日志来实现。

事务的提交点

• 当事务T在所有站点的数据库存取操作都已成功执行，并且所有操作对数据库的影响都已记录在日志中时，该事务T就到达提交点。

• 提交点后事务就成为已提交的事务，事务在日志中写入提交记录[commit,T]。

• 在系统发生故障时，扫描日志，检查提交记录，可以实现事务的恢复。

• 事务提交前强制写日志

  在事务到达提交点以前，还未写入磁盘的日志的任何部分，必须被写入磁盘。

• 提交点是一个时间点，是可以提交事务的所有变化或者取消事务的时间点。

• 提交点对于数据库来说是个一致点。

• 提交点也是事务的重启点，可以安全地撤销事务。

• 提交点也是事务锁定资源的一个释放点。

日志

• 保存所有影响数据库项的值的事务操作的信息
• 用于故障恢复
• 记录的内容
  • [start_transaction, T]
  • [write_item, T, x, 旧值, 新值]
  • [read_item, T, x]
  • [commit, T]
  • [abort, T]
  • Log:记录长度以及其他用于恢复过程的辅助信息
• 日志本身存在一个优先保护的问题

检查点（Checkpoint）

• 设置一个周期性（时间/容量）操作点，表示此前已执行完的事务是正确的
• 写检查点的操作
  • Log Buffer内容写入Log
  • 写检查点Log信息：当前活动事务表，每个事务最近一次Log记录在Log文件中的位置
  • DB Buffer内容写入DB
  • 将本次检查点Log项在Log文件中的地址记入“重启文件”
• 遵循“先写日志”原则

事务恢复的原则

1. 孤立和逐步退出事务的原则
   • 对事务内部的故障，不影响其它事务，将事务回退（UNDO）即可。
2. 成功结束事务原则
   • 已提交的事务应该满足事务的持久性，发生故障后应该重做(REDO) 它所做过的所有修改数据库的操作。
3. 夭折事务的原则
   • 非局部的不可排除的故障，撤销全部事务，恢复到初态。
   • 两种做法：
     • 利用数据备份恢复
     • 利用日志Undo

本地事务恢复

• 从“重启动文件”读出最近Checkpoint的地址，并定出Checkpoint在Log文件中的位置。
• 创建Redo表（空），Undo表（即Checkpoint相应内容中的活动事务表）。
• 前向检索Log，如果遇到Begin Transaction，则将对应事务记入到Undo表；如果遇到commit记录，则将对应的事务从Undo表移到Redo表。
• 反向检索Log，对Undo表中的事务，按照Log记录，做Undo操作，直到对应的Begin Transaction记录。
• 正向检索Log，对Redo表中的事务，按照Log记录，做Redo操作，直到对应的Commit记录。

分布式事务的恢复

由分布式事务管理器和局部事务管理器协同完成

分布式事务的撤消和提交

• 分布式事务的撤消：
  • 由总代理生成一个AGENT执行ABORT命令，各个DTM向LTM发局部ABORT命令，撤消各个子事务。
• 分布式事务的提交：
  • 由总代理生成一个AGENT执行COMMIT命令，各个DTM向LTM发局部COMMIT命令，提交各个子事务。
  • 分布式事务的提交比较复杂，需要通过协议来保障，比如两阶段提交协议。

两阶段提交协议

基本思想

• 将本地原子性提交行为的效果扩展到分布式事务，只有所有参与执行分布式事务的站点都同意提交，才能提交。

提交过程

• 第一阶段：表决阶段
• 第二阶段：执行阶段

两类代理

• 协调者：掌握提交和撤销事务的决定权，一般是总代理。
• 参与者：负责在本地数据库中执行写操作，并且向协调者提出提交和撤销子事务的意向。

2PC协议的重要特点

• 允许参与者单方面撤销事务；
• 一旦参与者确定了提交或撤销协议，它就不能再更改它的提议；
• 当参与者处于就绪状态时，根据协调者发出的消息种类，它可以转换为提交状态或者撤销状态；
• 协调者根据全局提交规则做出全局终止决定；
• 协调者和参与者可能进入互相等待对方消息的状态，需要使用定时器，保证退出消息等待状态。

两阶段提交协议的通信结构

• 集中式
• 分层式
• 线性
• 分布式

站点故障

• 参与者将就绪信息(“Ready”)写入日志前故障
  • 协调者等待超时，采取撤销决定，撤销其他子事务
  • 故障站点重启后简单撤销该事务。
• 参与者将“Ready”信息写入日志后故障
  • 其他站点正常结束该事务(Commit 或Abort)
  • 故障站点重启后，由协调者提供相关信息，正确结束(Commit 或 Abort)。
• 协调者在发送“Prepare（准备）”信息后，写入“commit（提交）”/“abort（撤销）”记录前，发生故障
  • 所有工作正常的参与者挂起
  • 协调者从头开始恢复，重新发“Prepare”信息
• 协调者在写入“commit”/“abort”记录后，写入“Complete(end_of_trans)”之前，发生故障
  • 需协调者重启时重新发决定信息，挂起的子事务继续提交，已提交子事务只发“ACK”信息。
• 协调者在写入“Complete”信息后发生故障
  • 重启时不做任何动作

报文故障

• 第一阶段：

  • 协调者的“Prepare”信息丢失

    没有收到“Prepare”信息的参与者等待，协调者也因等待超时，整个事务被撤销。

  • 参与者的回答信息（“Ready/Abort”）丢失

    协调者等待超时，整个事务被撤销。

• 第二阶段：

  • 协调者的“Commit/Abort”信息丢失

    参与者处于等待状态，可引入超时，请求再次发送。

  • 参与者的“ACK”信息丢失

    协调者等待，可引入超时，再次发送相关命令。

网络分割故障

• 协调者子网：
  • 在同一子网的参与者，可以正常结束。
  • 协调者收不到其它参与者的信息，按参与者故障处理。
• 参与者子网：
  • 参与者收不到协调者的信息，按协调者故障处理。

性能

• 简单，完全同步
• 具备紧密一致性
  • 任何时刻的数据一致性和全局事务的原子性
• 全局事务可用性低
• 系统效率比较低

数据更新

• 主文本更新法
  • 指定一个文本为主文本，其他的为辅文本
  • 数据的更新面向主文本
  • 主文本站点负责辅文本的更新
  • 主文本更新法的问题
    • 更新传播必须在短时间内完成，否则可能产生“过时”数据
    • 主文本站点不可用时，其他辅文本站点也不可用
• 移动主文本法
  • 若初次更新在辅文本上，把更新引向该数据的主站点；如果主站点此时尚未连通，则另选一个辅站点中的辅文本为该数据新的主文本进行更新；待原主文本站点连通后，系统自动把它改为辅文本，并按记录要求执行更新。
  • 如果初次更新在主文本上，但主文本站点与网络未接通，则此次更新操作失败，事务被撤销。
  • 移动文本法的问题
    • 网络分割成很多部分时，更新处理会不一致

Concurrency

并发控制就是负责正确协调并发事务的执行，保证并发的存取操作不至于破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确地运行并获得正确的结果。

调度

• 指事务处理执行的一个操作序列
• 事务的操作分为两类：Ri(x)、Wi(x)
• 一组事务的调度必须包含这些事务的所有操作，且操作顺序与原事务相同
• 调度的操作之间可能存在冲突
  • 读-写冲突
  • 写-写冲突

串行调度

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

一致性调度

• 如果调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称该调度为一致性调度。
• 串行调度总可以使数据库保持一致，属于一致性调度。
• 一致性调度不一定是可串行化调度
• 同一事务集上的可串行化调度，结果未必相同

调度等价（冲突等价）

• 不同调度S1和S2是等价的，其充分条件是：对任意一对冲突操作< Oi, Oj >，在调度S1中Oi优先Oj而在调度S2中Oi也优先Oj。

冲突操作

• 两个对同一数据项进行的操作中，有一个写操作，两者即为冲突操作。

可串行化调度

• 如果一个调度等价于串行调度，则该调度称为可串行化调度。
• 可串行化调度可以通过一系列非冲突操作的交换，调整为串行调度。

并发调度

• 一组并发执行的事务的调度序列。
• 必须保证每一事务内部的操作的顺序。
• 冲突操作必须先后依次执行。

分布式事务可串行化调度测试

• 可串行理论可以直接扩展到无重复副本的分布式数据库中。
  • 事务在每个站点上的执行调度称作局部调度。
  • 如果在无重复副本的分布式数据库中，每个局部调度都是可串行化的，则它们的并（全局调度）也是可串行化的。
• 在有副本的情况下，可能局部调度是可串行化的，但全局调度不是可串行化的。

数据副本情况

• 采用单副本可串行化调度，维持数据副本的相互一致性，此时要求：
  • 每一个局部调度必须是可串行化的。
  • 局部调度中的冲突操作必须具有相同的相对顺序（保证冲突事务的串行顺序是相同的）。
• 采用ROWA协议，读一个/写全部。
• 实际上难以实现同时写全部的操作。
• 有副本的情况下需要附加额外的副本控制协议。

并发控制

• 一般不测试调度是否可串行化，而是使用规则或协议保证产生一个可串行化的调度。
• 通过调度的可串行化来保证调度的正确性。

方法

• 基于封锁的方法

​ 锁定数据项以防止其他事务并发访问。

• 基于时间戳的方法

​ 给事务分配时间戳，根据时间戳顺序来执行事务。

• 悲观算法

​ 提前考虑和解决冲突。

• 乐观算法

​ 认为冲突一般不会发生，发生后再处理。

基于封锁

基本思想

• 事务访问数据项前要封锁该数据项；如果该数据项被其他事务锁定，则需要等待锁的释放。

锁的粒度

• 指锁定数据项的范围

粒度选择

• 数据库记录中的一个字段值
• 一条数据库记录
• 一个磁盘块（页面）
• 一个完整的文件
• 整个数据库

锁的类型

• 共享锁：Share锁，S锁或者读锁
• 排它锁：eXclusive锁，X锁，拒绝锁或写锁。
• 更新锁：Update锁，U锁（将被更新）

锁的选择

• 数据项既可以读也可以写，则要用X锁
• 如果数据项只可以读，则用S锁
• 锁的粒度大小取决于参与事务的类型

锁的操作

• read_lock(x)：读封锁
• write_lock(x)：写封锁
• unlock(x)：解锁

数据项的状态

• read_locked：读封锁
• write_locked：写封锁
• unlocked：未封锁

锁的操作和数据项的状态依靠系统锁表来记录

准则

方法

• 简单分布式封锁法

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

• 主站点封锁法（集中封锁法）

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

• 主副本封锁法

  • 每个数据项指定一个主副本，先对数据项的主副本进行封锁，然后再进行操作。
  • 主副本封锁，意味着所有的副本都被封锁。
  • 对只读操作要求过高。

• 快照方法

  • 快照是主副本的拷贝，是只读数据，可以提供复杂查询而不影响更新。
  • 可用来补充主副本封锁法。

读写锁并不能保证事务调度的可串行性

两阶段封锁协议

• 要求：
  • 任何事务在对数据操作前必须先获得锁；
  • 一个事务所有的封锁操作都在第一个解锁操作之前。
• 事务的执行分为两个阶段：
  • 第一阶段 获得锁阶段（也称为扩张阶段）。在这阶段，事务可以申请获得任何数据项上任何类型的锁，也可以进行锁的升级转换，但是不能释放任何锁；
  • 第二阶段 释放锁阶段（也称为收缩阶段）。在这阶段，事务可以释放任何数据项上的任何类型的锁，也可以进行锁的降级转换，但是不能再申请任何锁。
• 在分布式数据库中，若所有事务都遵循2PL，则分布式事务的调度执行是可串行化的。
• 2PL限制了一个调度中可以发生的并发事务的数量。

分类

• 基本的2PL

  • 在完成数据项的访问后立即释放锁（可提高并发度）
  • 2PL可能产生死锁。
  • 释放锁前事务管理器必须知道事务已经获得了所有锁，必须知道事务不再对已经获得锁的数据进行操作；
  • 如果在释放部分锁后事务撤消，其它事务就可能会读到“脏数据”，导致使其它事务也被撤消（级联撤销）。

• 保守的2PL（静态的2PL）

  • 事务在操作执行前获得所有操作数据上的锁。
  • 一次封锁所有数据项，否则等待。
  • 需要事务在数据操作前，预先声明读集（要读的所有数据项的集合）和写集（要写的所有数据项的集合）。
  • 不会产生死锁，但难以实现。

• 严格的2PL

  • 事务在提交或撤消前不能释放任何排它锁，即在提交或撤消前，一次释放所有的锁。
  • 可避免“脏”数据，不能避免死锁。

• 严酷的2PL

  • 事务在提交或撤消前不能释放任何锁，即在提交或撤消前，一次释放所有的锁。
  • 也不能避免死锁。

实现

• 集中式两阶段封锁协议的实现方法

  • 只有一个站点拥有封锁管理程序，负责锁管理；其他站点上的事务管理程序在请求封锁时，与该站点通信。
  • 属于主站点封锁法，容易造成瓶颈。

• 主副本两阶段封锁协议的实现方法

  • 每个数据确定一个主副本站点。
  • 在一组站点上实现封锁管理。
  • 每个封锁管理器管理一组指定单元上的锁。

• 分布式两阶段封锁协议的实现方法

  • 锁管理是分布式的，每个站点都有分布式封锁管理程序，负责本站点数据的加锁和解锁。
  • 一般采用“写全锁”的策略，即写操作时请求封锁所有数据，而读操作时，仅封锁其中的一个副本，称为“读一个/写全部”(ROWA协议)。
  • 也可以采用“封锁多数”的策略，即读操作和写操作都封锁一半以上的数据副本。

多粒度与意向锁

多粒度封锁

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

意向锁

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

意向锁的类型

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

多粒度封锁协议

1. 必须遵守锁的相容性规则；
2. 必须首先封锁树的根节点，可以用任何一种方式的锁；
3. 只有节点 N 的父节点以 IS 或 IX 方式封锁后，节点 N 才可以以 S 或 IS 方式封锁；
4. 只有当节点 N 的父节点以 IX 或 SIX 方式封锁后，节点 N 才可以以 X、IX 或 SIX 方式封锁；
5. 为遵循2PL协议，事务T在释放任何节点前，必须获得所有的锁；
6. 在事务T为节点 N 解锁前，必须先对其子节点解锁。即解锁的顺序从下层节点开始。

意向锁的小结

• 具有意向锁的多粒度加锁方法中，任意事务T要对一个数据对象加锁，必须先对它的上层节点加意向锁。
• 申请封锁时应该按自上而下的次序进行。
• 释放锁时则应该按自下而上的次序进行。
• 具有意向锁的多粒度加锁方法提高了系统的并发度，减少了加锁和释放锁的开销。

封锁粒度对并发控制的影响

• 大多数DBMS缺省设置为记录锁或页面锁。
• 粒度小，并发度高，锁开销大。
  • 数据项比较多，锁也多，解锁和封锁操作多，锁表存储空间大。
• 粒度大，并发度低，锁开销小。
• 如果是磁盘块，封锁磁盘块中的一条记录B的事务T必须封锁整个磁盘块；而另外一个事务S如果要封锁记录C，而C也在磁盘块中，由于磁盘块正在封锁中，S只能等待；如果是封锁粒度是一条记录的话，就不用等待了。

死锁处理

• 活锁
  • 在事务执行中，某个事务得不到锁而处于长期等待状态，这种现象称为活锁。
• 死锁
  • 有两个或多个事务的集合，其中每个事务Ti都在等待该集合中另外一个事务Tj释放它所需要的数据项上持有的锁，结果任何一个事务都无法继续执行，这种现象称为死锁。

死锁发生的条件

• 互斥条件：事务请求对资源的独占控制。
• 等待条件：事务已持有分配给它的资源，又去申请并等待别的资源。
• 非抢占条件：直到资源被持有它的事务释放前，不可能将资源强制从持有它的事务夺去。
• 循环等待条件：存在事务互相等待的情况。

死锁分类

• 局部死锁：仅在一个站点上发生的死锁。
• 全局死锁：涉及多个站点的死锁。

在分布式数据库中数据冗余增加引起死锁的机会

解决死锁

• 通过撤销一个或多个引起死锁的事务，打破全局等待图中的死锁回路。

• 一般考虑的因素：

  • 撤销年轻的事务；
  • 撤销占有较少资源的事务；
  • 撤销具有最短运行时间的事务；
  • 撤销具有最长运行时间的事务；
  • 撤销包含在多个回路中的事务。

• 受害者选择算法

死锁预防

• 进行预防性测试，使引起死锁的必要条件不成立

• 一般预防的方法

  • 对事务进行排序（标识符顺序或时间顺序），然后施加某种预防协议。

• 预防协议

  • 等待-死亡协议（非占先权法）
  • 伤害-等待协议（占先权法）

时标

• 基本思想

  • 给每个事务赋予一个唯一的时标，事务的执行等效于按时标次序串行执行。如果发生冲突，则通过撤消并重启一个事务来解决的。事务重新启动时，则赋予新的时标。

• 时标 (Time Stamp)

  • 用来唯一识别每个事务并允许排序的标识。
  • 时标具有唯一性和单调性。
  • 可以采用计数器或系统时钟来产生时标。
  • 在分布式系统中有全局时标和本地时标之分。

• 时标的排序规则

  • 若两个冲突操作Qij与Qkl，分别属于事务Ti与Tk，Qij在Qkl之前执行当且仅当tS(Ti) < tS(Tk)。

• 时标法的特点

  • 优点是没有死锁，不必设置锁。
  • 封锁和死锁检测引起的通信开销也避免了。
  • 但要求时标在全系统中是唯一的。

基本时标法

• 基本规则:

  1. 每个事务在本站点开始时赋予一个全局唯一时标；
  2. 事务的每个读操作或写操作都具有该事务的时标；
  3. 数据库中的每个数据项X都有读操作的最大时标RTM(X)和写操作的最大时标WTM(X)；
  4. 若事务T读X，其时标TS<WTM(X)，则拒绝读操作，并用新的时标重新启动；否则执行读操作，并将RTM(X)置为：max(RTM(X), TS)；
  5. 若事务T写X，TS < RTM(X) 或 TS < WTM(X)，拒绝写操作，并用新的时标重新启动，否则执行写并置WTM(X)为TS。

• 基本时标法的特点

  • 确保所有有冲突的操作，在所有站点上，都是按事务的时标顺序执行；
  • 不会产生死锁，可保证调度的可串行化；
  • 重启次数可能很多，可能导致事务最终以串行方式执行。

保守时标法

• 基本思想

  • 通过缓冲年轻的操作，直至年长的操作执行完成，因此操作不会被拒绝，事务也绝不被重启动。

• 基本规则

  1. 每个事务只在一个站点执行，不激活远程进程，仅能向远程站点发送读/写请求；
  2. 每个站点必须按时标的顺序发送读/写数据的请求，各个站点按时标顺序接收来自不同站点的全部读/写请求。
  3. 每个站点都为其他各个站点发来的读/写操作开辟一个缓冲区，把接收到的读/写操作分别保存在相应的缓冲区中。

• 假定某个站点k上，各个缓冲区队列都已不为空，即每个站点都已向它至少发送了一个读和一个写操作，就停止接收，处理在缓冲区中的操作。

• 假定站点i至少有一个缓冲的读和缓冲的写来自网中其他站点，根据规则2，站点i知道没有年老的请求来自其他站点（因为按序接收，所以不可能有比此更年老的请求到来，年老的比年轻的先到）。

• 保守时标法的执行过程

  • 在各个站点的缓冲队列中存放了需要在该站点上执行的读/写操作。操作将严格按照时标的顺序执行：
    1. 对于本站点上需要执行的读操作R，如果有某个写操作W被缓冲，且TS(R)>TS(W)，则R被送入等待队列直到写操作执行后R才能执行；
    2. 对于本站点上需要执行的写操作W，如果有某个读操作R被缓冲，且TS(W)>TS(R)，或有某个写操作W2被缓冲，且TS(W)>TS(W2)，则W进入等待队列直到缓冲区中的读/写操作被执行后W才能执行。

• 存在问题和解决方法

  • 如果一个站点从来不向某个站点发送操作的话，那么执行过程中的假定就不符合，操作就无法进行。解决办法是，周期性的发送带有时标的空操作。
  • 此方法要求网络上所有站点都连通，这在大系统中很难办到。为避免不必要的通信，可对无读写操作请求的站点，发送一个时标很大的空操作。
  • 此方法过分保守，一律按照时序来进行，其中包括了不冲突的操作。

多版本

• 基本思想

  • Multiversion concurrency control (MVCC)
    • 维护一个数据项的多个版本。
    • 写数据项时，写入一个新版本，老版本依然保存。
    • 读数据时，系统选择一个合适的版本，以维护当前执行调度的可串行性。
    • 系统可以接受在其他技术中被拒绝的一些读操作。

• 缺点

  • 需要更多的存储来维持数据库数据项的多个版本。

• 分类

  • 基于时标排序的多版本技术。
  • 基于两阶段封锁的多版本技术。

乐观法

• 基本思想
  • 假定事务冲突很少，事务先对数据进行读写操作，所有操作执行完后进行验证：事务是否违反可串行性，如果没有则提交；否则事务撤消，重新开始。
• 基于以下事实
  • 冲突的事务是少数（查询为主的系统少于5%）。
  • 大多数事务可以不受干扰地执行完毕。
• 乐观并发控制协议的三个阶段：
  • 读段/计算：
    • 在数据对象的局部副本上执行事务，这时其他事务不能存取此副本。事务从DB读数据，执行计算，并且确定写集数据项的新值。写操作总是对局部副本，仅当验证通过后，在事务结束处，才将其写入DB。
  • 验证段：
    • 检验并发事务的可串行性，该阶段验证修改应用是否引起完整性（一致性）的丢失，验证阶段通过，才能进入写段，否则事务重启动。
  • 写段/提交：
    • 验证阶段通过，则把事务的更新应用于数据库，对数据进行更新；否则，忽略所有更新，并重新开始该事务。

• 版本号机制——乐观锁的实现
  • 数据项加上一个版本号(x, v)，当数据被修改时，v值会加1。
  • 更新事务T在读取数据的同时也会读取v值，在提交更新时，若刚才读取到的v值等于x当前的v值才更新，否则重试更新操作。