分布式数据库复习要点

分布式数据库复习要点第一章1、 分布式数据库的定义（P4）物理上分散而逻辑上集中的系统，它使用计算机网络将地理位置分散而管理和控制又需要不同程度集中的多个逻辑单位（通常是集中式数据库系统）连接起来，共同组成一个统一的数据库系统。分布式数据库系统可以看成是计算机网络和数据库系统的有机结合。 2、 分布式数据库的两种分类方法（P7）l 按局部DBMS的数据模型分同构型DDBS：各个站点上数据库使用同一数据模型同构同质型-数据模型相同，且是同一种DBMS（同一厂家）同构异质型-数据模型相同，不是同一种DBMS异构型DDBS ：各站点上数据库的数据模型类型不同l 按DDBS的全局控制类型分全局控制集中型DDBS：全局控制机制和全局数据词典位于中心站点全局控制分散型DDBS：全局控制机制和全局数据词典分散在网络的各个站点上。全局控制可变型DDBS：也称主从型DDBS。分成两组站点，一组包含全局控制机制和全局控制词典，另外一组不包含。3、分布式数据库的组成成分（两部分）（P9）l 数据：分布式数据库的主体，包括局部数据和全局数据。l 数据目录：数据结构的定义、全局数据的分片、分布、授权、事务恢复等描述，包括局部和全局数据目录。4、 分布式数据库的数据分片的定义和类型（3种）（P10）数据分片：又称数据分割、数据分段，局部数据库是由全局数据库分割而成。三种类型：l 水平分片：按特定条件把全局关系的所有元组划分成若干个互不相交的子集，对全局关系施加选择运算。l 垂直分片：把全局关系的属性集分成若干个子集，对全局关系施加投影运算。l 混合分片：以上两种方法的混合。5、 分布式数据库的分布策略（4条）（P11）数据分布：根据某种策略把数据分片所得的逻辑片断分散地存储在各个站点上.l 集中式：所有数据都安排在同一站点上l 分割式：所有数据只有一份，被分割成若干个逻辑片段，每个片段被放置在特定的站点l 复制式：所有数据有多个副本，每个站点都有一个完整的数据副本l 混合式：分割式和复制式的混合6、 分布式数据库的模式结构（P13）分四层：l 全局外层：全局外模式-全局应用的用户视图。l 全局概念层：全局概念模式-描述全局数据的逻辑结构和数据特性； 分片模式-描述全局数据的逻辑划分； 分配模式-根据数据分布策略，定义各片段的物理存放站点。l 局部概念层：局部概念模式-各个站点上全部物理映像的集合。l 局部内层：局部内模式-全局/本站点数据在本站点的存储描述。7、 分布式数据库的功能模块（P.16-17）l 查询处理模块：任务是减少查询处理的代价l 完整性处理模块：负责维护数据库的完整性和一致性l 调度处理模块：发布局部处理命令，管理数据传输l 可靠性处理模块：负责监视系统的各个部分是否有故障出现。8、 分布透明性的层次（三层P.25-26）分布透明性也叫分布独立性，包括三个层次：l 分片透明性：用户编写应用程序只对全局关系进行操作，不必考虑数据的逻辑分片。l 位置透明性：也叫分配透明性。用户编写应用程序需要了解数据分片情况，但不必了解副本和各片段的站点位置情况。l 局部数据模型透明性：不必了解站点上数据库的数据模型及其数据对象的表示性质。第二章 DDB设计1、DDB设计的两个方法 P39-40l 自顶向下：（对应于DDB创建方法中的重构法）从头开始设计分布式数据库。根据系统的实现环境和用户需求，按照分布式数据库系统的设计思想和方法，采用统一的观点，从总体设计做起，包括各站点上的数据库系统，重新建立一个DDBS。可以有效解决数据一致性、完整性和可靠性问题。通常是同构异质或者同构同质的。l 自底向上：（对应于DDB创建方法中的组合法）通过聚集现存数据库来设计分布式数据库。利用现有的计算机网络和独立存在于各个站点上的现存数据库系统，通过建立一个分布式协调管理系统，将它们集成为一个统一的DDBS。通常是异构或者同构异质。2、 DATAID-D方法 P52这是自顶向下设计分布式数据库的一个典型方法，增加的两个阶段：l 分布要求分析阶段输入：用户分布要求、全局数据概念模型、全局数据操作模式；输出：频率表（各个站点每一应用激活次数）、划分表（各实体的潜在水平分片规则）、极化表（由一个站点发出的一给定应用访问一给定片段的频率）。l 分布设计阶段 分片设计：对实体进行水平分片和垂直分片。 非冗余分配：利用最佳适应法，把各片段映射到使用最多的站点上。 冗余分配：起初使用非冗余分配，在每次迭代时，计算因增加一副本使其变成本地访问的得益与为维护该副本一致性所需要附加远程修改的损失之差值，如果是个整数，就把该副本存储到该得益站点。 局部模式的重新构造：重新构造片段分配站点上的局部模式。3、数据片断分配法 P50，同时参见PPT相关部分4、DATAID方法的应用 P55，同时参见PPT相关部分第三章 分布式查询处理和优化1、 关系代数知识，并能进行实例运算，类似习题3.6的运算要了解 （重点PPT上例题）2、 查询树, 查询变换, 限定关系等定义l 查询树：将一个查询的关系代数表达式进行语法分析得到一颗语法树：叶子节点是查询涉及的关系，各个节点是关系代数操作符，根节点是查询结果。语法树又称查询树。l 查询变换：从全局查询到片段查询的变换？l 限定关系: R:QR 称为R的限定关系，其中QR 表示查询。逻辑片段就是一个限定关系。s city=london(Supplier) 的限定关系: Supplier: s city=london3、 基于关系代数等价变换的查询优化实例（重点看P80-82）基本原理：把查询问题转换为关系表达式；关系表达式到查询树（语法树）的变换；全局查询到片段查询的变换（把全局查询树中的全局关系名，用重构该全局关系的各片段名替换，变换成相应片段上的查询树）；利用关系代数等价变换规则的优化算法，尽可能先执行选择和投影操作。4、 基于半连接的算法的查询优化的操作过程和代价估算（83-84） （重点看PPT例题）5、 基于直接连接算法的查询优化处理的四种方法，重点1、2、4算法。 (重点看书P85)l 站点依赖：如果两个关系不同站点的分片在属性A上没有交集（说明它们之间连接结果为空，只进行本站点片段连接再合并就够了），则可以只在同一站点上做片段连接操作，然后合并连接结果。l 分片和复制：如果不符合站点依赖的条件，则选择一组站点，把查询引用的某个关系的所有片段分布到这些站点上，其余被引用关系则复制到每个选定站点中去，这样在每个站点进行本地连接，再合并结果，必然会覆盖到所有该连接的元组（因为每一个站点都有另一个关系的完全副本）。l Hash划分：如果两个关系不符合站点依赖的条件，利用Hash函数对分片关系上的连接属性作站点依赖计算，再据此分片，比如按连接属性取值为奇偶数来把元组发送到不同站点，这样分片后两个关系必然就满足站点依赖条件，再进行本地连接。这实际是构造站点依赖的一种方法。第四章 分布式数据库中的事务管理和恢复1、分布式事务的定义和特性 P97定义：事务是访问数据库的最小逻辑工作单位，它是一个操作序列。分布式事务是一个分布式操作的序列，被操作的数据分布在不同站点上。ACID特性：l 原子性（Atomicity）： 事务的操作要么全部执行, 要么全部不执行 ,保证数据库一致性状态。l 一致性（Consistency）： 事务的正确性。并发执行的多个事务,其操作的结果应与以某种顺序串行执行这几个事务所得的结果相同。l 持久性（Durability）：事务提交后, 其操作的结果将永久化, 与提交后发生的故障无关。l 隔离性（ Isolation）：事务在提交前，决不允许把它对共享数据所作改变的结果提供给其他事务使用。 2、分布式事务的结构 P99（一个应用由若干个分布式事务组成，每个分布式事务由不同站点的若干子事务组成）分布式事务的一般结构：Begin Transaction原语：开始一个事务T1T2: 子事务或操作序列:TnCommit原语：事务成功完成的结束Rollback或Abort原语：事务失败的结束3、 分布式事务执行的控制模型（三种）P105分布式事务控制模型是指协调分布式事务中各成员DBMS执行其子事务的通用方法，有三种:l 主从模型：分布式事务管理器作为主控制器，局部事务管理器（LTM）作为从属控制器，LTM之间无通信。l 三角模型：控制权是分布式事务管理器和LTM之间分享的。LTM之间可以传递数据，避免了主从之间不必要的传输。l 层次控制模型：LTM还可再创建Agent，控制其它LTM执行，比前两种复杂。4、事务恢复的概念 P108当发生故障时，保证事务原子性的措施称为事务故障恢复，简称事务恢复，主要依靠日志来实现。5、事务的状态和状态转移 P109事务在执行过程中的状态变化：事务开始后立即进入活动状态，可以进行读写操作；事务结束时进入部分提交状态；事务到达提交点时进入提交状态；如果检查出故障或者事务在活动状态期间被撤销，则进入故障状态；终止状态表明事务已经离开系统。6、本地事务恢复的过程（P.112）本地事务恢复的过程类似于集中式数据库系统中事务的恢复：1） 从“重启动文件” 读出最近Checkpoint的地址, 定出Checkpoint在Log文件中的位置。 （找最近的检查点）2） 创建Redo表（初态为空）；创建 Undo表(即Checkpoint Record中的活动事务表)。3） 从Checkpoint Record起沿log向前检索，遇到begin transaction的log记录，其对应的事务记入Undo表；遇到commit的log记录，其对应事务从UNDO表移入Redo表，直至log完。 （在Undo表和Redo表中加响应的事务）4） 反向检索Log, 将Undo表中事务, 按log记录的操作，做Undo，直到遇到对应的Begin Transaction。 （执行Undo）5） 从Checkpoint Record起正向检索Redo表中事务的Log记录, 并执行之, 直到对应的Commit记录。 （执行Redo）7、两阶段提交协议定义和原则（P115-116）将本地原子性提交行为的效果扩展到分布式事务, 保证了分布式事务提交的原子性。基本思想是：坚持在分布式事务结果生效之前，所有参与执行分布式事务的站点都同意提交。（2PC把提交过程分为两个阶段：表决阶段目的是形成共同的决定；执行阶段目的是实现这个决定。）全局提交规则：l 只要至少有一个参与者撤销事务，协调者就必须做出全局撤销的决定；l 只有所有参与者都同意提交事务，协调者才能做出全局提交的决定。8、两阶段提交协议的通信结构（P117，还是把ppt上图看一下） 集中式：通信只发生在协调者和参与者之间，参与者之间不交换信息 分层式：协调者是在树根的DTM代理者，协调者与参与者之间的通信不使用直接广播，而是使用报文在树中上下传播。每个DTM代理是通信树的一个内部节点，它从下层节点处收集报文或向它们广播报文。 线性：参与者之间可以互相通信。系统中的站点间要排序，消息串行传递。 分布式：允许所有参与者在第一阶段相互通信，从而可以独立做出事务终止决定。9、主文本更新法分布式数据库中数据更新方法之一。指定一个副本为主文本, 更新时只对主文本进行；然后由主文本站点将主文本更新内容及时发送到各辅文本站点，各辅文本的更新可以并行进行。问题-更新传播必须在短时间内完成, 否则将获得“过时”数据；主文本不可用, 将引起其它辅文本也不可用。改进方法-移动主文本法。第五章 分布式数据库中的并发控制1、并发控制的定义 P131并发控制就是负责正确协调并发事务的执行，保证并发存取操作不至于破坏数据库的完整性和一致性，确保并发执行的多个事务能够正确地运行并获得正确的结果。2、串行调度、可串行化调度和一致性调度的定义 P133 串行调度：若一个调度S，其每个事务的执行均有TiTj，即事务Ti的所有操作都先于事务Tj的操作， 每个事务相继执行，这样的调度S为称串行调度。 可串行化调度：如果一个调度等价于某个串行调度，则该调度称为可串行化调度。 一致性调度：执行一个调度可以使得数据库从一个一致性状态转变为另一个一致性状态，则称调度为一致性调度。 事务的可串行性：若干个事务并发执行的结果与按希望那个的顺序执行的结果相同时，称诸事务是可串行的。3、并发控制算法的分类 P140并发控制机制分为两种类型：悲观算法和乐观算法。悲观算法使事务的并发执行在执行生命周期的开始就同步化，而乐观算法将同步化延迟到事务执行周期的结束。4、基于封锁的并发控制算法 P141基本思想：事务访问数据项之前要对该数据项加锁，如果已经被其他事务加锁，就要等待，直到那个事务释放该锁为止。5、封锁粒度、锁的类型 P141锁的粒度：锁定数据项的范围。锁粒度小，并发度高，锁开销大。包括以下几个层次： 数据库记录中的一个字段值 一条数据库记录 一个磁盘块（页面） 一个完整的文件 整个数据库锁的类型： 共享锁：Share锁，S锁或者读锁 排它锁：eXclusive锁，X锁，拒绝锁或写锁 更新锁：Update锁，U锁6、两阶段封锁协议 P147一个事务所有的封锁操作（读写）都在第一个解锁操作之前，则该事务遵守两阶段封锁协议。这样一个事务可以被分成两个阶段：l 上升阶段(成长阶段)：只能获取新锁，而不能释放已有的锁l 收缩阶段(衰退阶段）：只能释放已有的锁，而不能获得新锁保守2PL：要求事务在开始执行之前就持有所有它要访问的数据项上的锁。严格2PL：事务提交或撤销之前，绝对不释放任何一个写锁；在事务结束时，同时释放所有的锁。严酷2PL：事务在提交或撤销之前，不能释放任何一个锁。7、多粒度锁、意向锁的定义和锁的相容性 P153多粒度锁：封锁的粒度不是单一的一种粒度，而是有多种粒度意向锁：如果对一个节点加意向锁，则说明该节点的下层节点正在被封锁；对任一节点封锁时，必须先对它的上层节点加意向锁。包括意向共享锁（IS）、意向排他锁（IX）以及共享意向排他锁（SIX）三种类型。锁的相容性：8、基于时标的并发控制方法基本概念、基本思想、时标分配方法 P163基本概念：不通过互斥来支持串行性，而是通过在事务启动时赋给时标（时间戳）来实现；时标是用来唯一识别每个事务并允许排序的标识；如果 ts(T1) ts(T2) ts(Tn), 则调度器产生的序是: T1,T2, . Tn。基本思想：每个事务赋一个唯一的时标，事务的执行等效于按时标次序串行执行。如果发生冲突，是通过撤销并重新启动一个事务来解决的。事务重新启动时，则赋予新的时标。优点是没有死锁，不必设置锁。时标分配方法： 全局时标：使用全局的单调递增的计数器 局部时标：。每个站点基于其本地计数器自治地指定一个时标，同时附加上其自身的站点标识符。9、多版本法的基本概念 P166 并发控制的多版本技术。多版本并发控制协议：维护了一个数据项的多个版本值。思想是：通过读取数据项的较老版本来维护可串行性，使得系统可以接受在其他技术中被拒绝的一些读操作。10、多版本2PL的基本思想 P167当一个事务T持有数据项X的写锁时，其他事务T依旧可以读X。通过X的两个版本实现这样的功能：一个版本是最近已提交版本；另外一个X是事务T获得该项上写锁时创建的新版本。其它事务可以继续读X的已提交版本，而事务T可以根据需要更新X的值。在T提交之前需要获得X的验证锁，一旦获得验证锁，老版本改为最新版本。第六章 分布式数据库中的可靠性1、可靠性和可用性的概念及其两者的关系 P173可靠性：数据库在一给定时间间隔内不产生任何失败的概率。强调数据库的正确性。可用性：给定的时间t，数据库可以正常运行的概率。强调的是当需要访问数据库时，它是可用的。两者关系： 通常认为构建可用性系统比可靠性系统容易 两者是统一的，可靠性高的系统可用性自然好 两者又是矛盾的，增加错误风险的情况下，可提高可用性；采用太谨慎的策略会降低可用性。2、MTTD、MTBF、MTTR三者的定义，及其图示 P178l 平均检测时间(MTTD)：一个故障在它发生一段时间后才被检测出，这一段时间叫潜伏期，同种系统的平均故障潜伏时间称为平均故障检测时间。l 平均修复时间(MTTR)：修复一个失败的系统所需要的期望时间。l 平均故障间隔时间(MTBF)：可以自我修复的系统中相继失败之间的期望时间。3、分布式可靠性协议的执行过程 P179 Begin-Transacrion：登录 Read：LTM先在事务处理的缓冲区中读，若不在，则向缓冲区管理器发Fetch命令，读出数据后，LTM将它交给调度程序 Write：若在Buffer中得到，则在那更新，否则对Buffer Manager发Fetch命令，读出数据并修改，同时数据的前像和修改后的后像写入日志。 Abort：根据日志做Undo Commit：将事务结束记录写入日志4、分布式可靠性协议的组成（三个协议） P180分布式数据库系统的可靠性协议包括提交协议、终结协议、恢复协议。 提交和恢复协议详细说明提交命令和恢复命令是如何执行的 终结协议解决一个站点失效时，未失效站点如何处理该失效事件的问题5、非阻断协议的充要条件和三阶段提交协议的定义 P187提交协议是非阻断的充要条件是, 在其状态转换图中不存在: 没有状态同时与提交状态和撤销状态“相邻” 没有不可提交状态与提交状态“相邻”在2PC的等待状态和提交状态之间增加一个状态，作为一个缓冲，用于在准备提交但是还没有提交的时候。因为从初始状态到提交状态之间有三次状态转换，所以称为三阶段提交协议。6、三阶段提交协议的超时处理 P189 协调者 在等待状态超时：协调者单方面Abort 在预备提交状态超时：将所有参与者移入预备提交状态 在提交/撤销状态超时：忽略 参与者超时 在初始状态超时：与2PC中的情况相同 在就绪状态超时：终结协议 在预备提交状态超时：终结协议7、网络分割中基于表决的协议 P192分为多数表决法和法定人数表决法？多数表决法的基本思想是：如果大多数站点提议执行某事务，那么该事务就被执行。概括为表决基于法定人数。实现提交协议必须满足的规则：每个站点i有选票数Vi, 系统总投票数为V。l 事务在提交前，它必须获得提交法定票数Vcl 事务在撤销前，它必须获得撤销法定票数Val Va+VcV, 当0 Va, Vc V。前两条指出事务终结时必须获得的投票数；最后一条保证事务不能同时既被撤销又被提交。8、采用版本号检测不一致性 P200允许对数据项操作的站点的副本是主副本, 其它是孤立或隔离的副本。正常工作期间, 全部副本都是主副本, 并且互相一致, 每份副本维持一个原版号和一个当前版本号。初始时原版本号置为0，当前版本号置为1；每当对副本执行一次更新，只是当前版本号加1。网络分割时, 每个孤立副本的原版本号被置为当前版本号值。这样直到分割修复为止, 此原版号不会改变。这时比较所有副本的当前版本号和原版本号就能暴露出不一致性。（如果分割修复时，发现分割区域原版本号和未分割区域当前版本号不同且分割区域原版本号和分割区域当前版本号也不同，则不一致。各个分割区域中当前版本号不同，也可能不一致。）第七章 分布式数据库的安全性和目录管理1、不安全因素的三个方面 P207-数据存储在各个站点上存在的不安全因素-访问各个站点上数据存在的不安全因素-数据在各站点之间传输时存在的不安全因素2、安全层次（五个层次） P209 物理层：保护数据不受侵入者的物理破坏 用户层：防止保密字被盗 OS层：从访问系统的口令到并发进程之间隔离，都要提供保护 网络层：保证是与可信赖的站点通信,保证链路没有被窃听和篡改 数据库系统：为不同需求的合法用户授予不同的权限3、 数据库安全的术语 P2111） 主体(Subject) ：引起信息流动或改变系统状态的主动实体, 如用户、 程序、 进程。2） 客体(Object) ：蕴含或接收信息的被动实体，信息的载体, 如DB, 表, 记录, 视图, 属性等。3） 可信计算基（trusted computing base）：实现安全保护机制的集合体（包含硬件、固件和软件）。4） 域：主体有能力存取的客体集合5） 安全级(Security Level) ：主体和客体的访问特权, 一般主体安全级表示主体对客体敏感信息的操作能力, 客体安全级表示客体信息的敏感度6） 敏感度标记：表示客体和主体的安全级的一条信息。可信计算基使用它来确定是否使用强制访问控制。7） 最小特权原理：主体在执行授权任务时，应被授予完成该任务所需的最小存取权。8） 访问监控器：监控主体和客体之间授权访问关系的部件。9） 信道：系统内的传输信息的通路。10) 隐蔽信道(Covert Channel)：以危害系统安全的隐蔽方式传输信息的通信信道11) 自主访问控制(Discretionary Access Control) ：基于主体身份或主体所属组的身份或二者结合来限制对客体访问的方法. 具有访问权的主体能自行决定其访问权直接或间接转授给别人。12) 强制访问控制(Mandatory Access Control) ：基于主体与客体各自所具有的敏感度标记的控制关系来决定主体对客体的访问. 标记是由系统安全员指派, 用户不能随意修改, 更不能转让 。13) 数据库的安全策略:根据用户需求、安装环境、建立规则和法律等方面的限制来制定的，用来描述访问规则和访问特征的关系。14) 形式化安全保护策略模型：安全保护策略的完整精确描述。15) 安全保护策略模型：安全保护策略的非形式化描述4、面向用户的口令法 P215面向用户的口令系统是每个用户或每个组用户有一个口令，该口令允许用户只能访问他所需要的数据对象。5、多级安全模型的系统状态定义 P217多级安全BLP模型系统状态v是集合V中的元素， V=(B M F H) ：B为当前存取集, B (S O A) ,S为主体集， O为客体集 ，A为访问方式集合；M是存取控制矩阵，每个元素表示主体对客体的访问权限集合；F为安全级函数；H为当前客体层次结构。6、自主访问控制和强制访问控制 见术语部分7、数据库安全评估标准的分类和分级 P2271991年美国国家计算机安全中心根据TCSEC制订紫皮书可信计算机系统评估标准的可信DBMS说明，DBMS的安全分4类,7级, 25条评估标准： D：最低保护 C：自主保护类, 基于主体身份来限制对客体访问。 C1级：自主安全 保护 C2级：可控存取保护 B：强制保护类, 基于主体与客体各自所具有的敏感度标记的控制关系来决定主体对客体的访问 B1级：标记安全保护 B2级：结构化保护 B3级：安全域保护 A：验证保护类 A1级：可验证保护8、身份认证的三个级别 P229系统登录认证： OS检查数据库连接 ：DBMS验证数据库对象使用：DBMS核实其对数据对象的存取权限第八章 分布式数据库与C/S模式结构1、C/S模式定义和当前流行的两种模式 P242C/S模式系统：某些站点是客户机站点，而另一些站点是服务器站点；所有的数据驻留在服务器站点；所有的应用都在客户机站点运行；一般不提供完全的位置透明性。当前流行的两种模式：1）传统的两层结构C/S-服务器（或服务器群）存储数据，客户机群存取数据，服务器扮演支配角色。2）正在涌现的三层C/S-数据层、功能层和表示层：数据层是驻留在主机上的DBMS；功能层是应用服务器，负责应用逻辑处理；表示层由客户机实现，是应用的用户接口。2