《分布式并发》PPT课件.ppt

第5章分布式并发控制 计算机科学与技术学院 5 1问题提出与抽象 一读写异常问题二分布式数据库管理系统的抽象1数据库与DM DataManagers 数据库可以看作是一个逻辑数据项集合 记作X Y Z 每一个逻辑数据项可以存储在系统的任何DM中 也可以冗余地存储在多个DM中 TM TransactionManagers 2用户与事务用户的数据库请求是通过执行事务与DDB发生联系的 事务可以来自于自含查询语言的联机查询如 QUEL 也可是报告书写语言的报告生成程序如 PRG 还可以是应用程序设计语言嵌入的数据操纵语言编写的应用程序 如 PROC 一个事务模拟为一个READ和WRITE操作的序列 而不关心其内部计算 一个事务的逻辑写集是该事务要写的所有逻辑数据项的集合 如果一个事务的存储读集或存储写集与另一个事务的存储写集相交 则称这两个事务是冲突的 Conflict 5 2用于并发控制的DDBS抽象结构 每一个在DDBMS中执行的事务都由一个单独的TM管理 即事务发出其所有的操作给一个特定的TM 所有为执行该事务所需要的分布式计算由该TM管理 在响应事务的命令时 TM向DM发出命令 说明具体的存储数据项将被读或写 由DM对相应数据子集进行操作 一 集中式事务处理模式 一个集中式DBMS可以看作是在一个站点上的只有一个TM机构的管理软件 当一个事务T发出BEGIN操作时 TM给T初始化一个私有工作区 当T发出READ X 时 TM检查私有工作区是否包含X的一个副本 如果包含X的一个副本值并返回到T 否则TM发命令到相应的DM 检索X的一个副本值并返回到T 这个操作记为 DM READ X 当T发出WRITE X VALUE 时 如果私有工作区含有X则更新其值 否则建一个具有此新值的X的副本 并放入工作区 当一个事务T发出END操作时 TM为每一个更新的逻辑数据项X发出DM WRITE X 使相应的DM对X所在的数据子集的X的值得到更新 当所有的DM WRITE处理后 T的执行完成 撤销私有工作区 在这种模式下 可以把READ和WRITE看作是用户对数据库请求的事务级操作 而把DM READ和DM WRITE看作是对数据库的内部操作 两段提交 TWO phaseCommit 提交工作分两步完成 从T的私有工作区中复制X Y Z 的值 并把这些值暂时放在安全的地方 如果在这一步中DBMS失效 则放弃事务的提交 DBMS把X Y Z 的值复制到存储数据库 如果在这一步中DBMS失效 应启动恢复过程 从安全存储器中读出X Y Z 的值 并重新提交 直到成功为止 二 分布事务处理模型 1 DDBMS中的私有工作区一个事务T的私有工作区通常并不在与T的TM相同的场所 而是分布在包含T所访问数据的所有场所中 2 DDBMS中的两阶段提交问题在DDBMS中 由于可能一个场所失效而系统的其它部分继续工作 使得原子提交问题变得更加复杂与困难 在分布式DBMS中 引入TM与DM之间的预提交操作 pre commit 这个操作使DM从私有工作区复制数据项到安全存储器 每个接收与提交的DM能够确定在提交活动中还有哪些DM参加 如果T的TM在发生所有的DM WRITE之前失效 则尚未收到DM WRITE的那些DM能够识别这些情况 并查询是否有DM收到DM WRITE 如果有DM接收到DM WRITE 则剩余的这些DM就像它们也接收到命令一样的进行执行 三 分布式事务处理模式 当一个事务T发出BEGIN操作时 T的TM给T初始化一个私有工作区 当T发出READ X 时 TM检查私有工作区是否存在X的一个副本 如果包含X的一个副本 T就使用这个副本的值 否则TM选择X的某个存储副本Xi DM从数据库中检索这个副本的值 把这个值存入私有工作区 当T发出WRITE X VALUE 时 如果工作区含有X的一个副本值 则将私有工作区相应的更新 否则建一个具有新值VALUE的X的副本 当一个事务T发出END操作时 两段提交开始 对于T更新的每一个逻辑数据项X X的每一个存储副本Xi TM给Xi所在的DM发出Pre Commit 在所有预提交处理以后 TM对所有由T更新的逻辑数据项的所有副本发DM WRITE 直到所有数据项的所有副本处理结束后T的执行结束 5 3分布式并发控制理论 一 无干扰执行与可串行性考虑事务的一个集合T1 Tn 令E0是这些事务的一个执行 E0最保险的实现策略是串行执行 即每一个事务是在下一个事务开始之前完成 如果这些事务的另一个执行E1中有事务的并行执行 但E1和E0在输出和对数据库的影响上都有相同的结果 则称E1是可串行的 Serilizable 数据库并发控制的目标就是只允许可串行的执行出现 计程 用一组计程 Log 做事务的执行模型 其中每一个DM有一个计程 每个计程指出在一个DM中DM READ和DM WRITE的执行次序 定义5 1由一组计程所代表的执行是可串行的 如果满足下列条件 1 对每一个计程 对于其操作出现在此计程中的每一次事务Ti和Tj 要么所有的Ti的操作在Tj的操作之前进行 要么所有的Tj的操作在Ti的操作之前完成 2 对每一对事务Ti和Tj 如果在某一计程中 Ti的操作在Tj之前 则在任一Ti和Tj同时出现的其他计程中 Ti的操作也必须在Tj的操作之前 例5 1假设有事务T1 T2 T3 涉及的数据项X Y和Z的副本用Xi Yj和Zk i j k 1 2 表示 设Ri 和Wi i 1 2 3 分别表示事务Ti的读 写操作 则下列执行是串行的 因为它满足定义5 1的条件 1 和 2 即对所有DM的计程都满足T1先于T2 T2先于T3 DM1 R1 X2 R2 Y1 W3 X1 DM2 W1 Y2 W2 Z1 DM3 W2 Z2 R3 Z3 下列执行可能不是串行的 因为他满足条件5 1 但不满足5 2DM1 R1 X1 W1 Y1 R2 Y1 W3 X1 DM2 W2 X2 W1 Y1 DM3 W2 Z3 R3 Z3 下列执行不是串行的 因为它不满足条件5 1或条件5 2DM1 R1 X2 R2 Y1 W3 X1 W1 Y1 DM2 W2 Z1 W1 Y2 DM3 W2 Z3 Y3 Z3 二 操作的冲突与执行的等价 1操作冲突的类型 1 读写冲突对数据项X Ti发出DM READ X Tj发出DM WRITE X Ti Tj次序不同则Ti执行结果不同 2 写写冲突对数据项X 如果事务Ti发出DM WRITE X Tj也发出DM WRITE X 执行的次序不同 执行的结果不一样 2执行的等价定义5 2令E1和E2是两个执行等价 分别用计程 L11 L12 L1n L21 L22 L2n 来刻画 其中Lij表示Ei在DMj的执行 如果下列条件成立 则E1 E2是等价的 对每个j 1 j n L1j和L2j包含相同集合的DM READ和DM WRITE 而且每一对冲突的操作在其两个计程中的相对次序相同 这样就能保证 每个DM READ操作在两个执行中所读的数据项是相同的 每个数据项的最后DM WRITE操作是相同的 定理5 1设T T1 T2 Tn 是该事务的集合 E是这些事务的一个执行 用计程集合 L1 Ln 来表示 如果存在一种T的总次序 称作串行性次序 使得对所有的Ti和Tj的对应冲突操作Oi和Oj 保证在所有计程中Oi和Oj遵循这个串行性次序 则E是可串行的 三 并发控制处理模式 1 关系 令E是由一组计程所表示的执行 在E中可能有三种二元关系值得关注 分别记作RW WR WW 对每一对事务Ti Tj 他们的定义为 TiRWTj当且仅当在E的某个计程中 Ti读某个数据 随后Tj写此数据 TiWRTj 当且仅当在E的某个计程中 Ti写某个数据 随后Tj读此数据 TiWWTj当且仅当在E的某个计程中 Ti写某个数据 随后Tj写此数据 RWR用来标记RW WR的连续实施 用的术语意味着 对于给定的 如果存在着一个总事务次序 使得与所有的关系一致 则E是可串行的 要使后面这个条件成立 当且仅当是无回路的 即不存在一个序列i1i2 i2i3 使得中间出现交叉 2 读写和写写同步的结合模式 定理5 2 令 RWR和 WW与执行E相关联 如果下列条件满足 则E是可串行的 所有的 RWR和 WW关系是无回路的 存在一个总事务次序 使得这个次序即与所有 RWR关系相一致 也与所有 WW关系一致 5 4两相封锁并发控制算法 一锁的粒度 Granularity 1 表锁 2 页锁 3 行锁 4 项锁二锁类型 1 读锁S Shared 2 写锁X eXclusive 3 更新锁U Update 三锁的相容性 四 两相封锁 2PL 算法思想 2PL算法对并发的控制 通过两个相对独立的阶段进行 第一阶段 称为生长阶段 在这个阶段 一个事务得到越来越多的锁 而不释放任何锁 第二阶段 称为紧缩阶段 如果一个事务释放一个锁 则进入紧缩阶段 在紧缩阶段 这个事务逐步释放锁 并禁止它得到另外的锁 当事务终止或撤销时 所剩余的锁自动释放 五 2PL算法的基本实现 无副本 且把数据项X的调度程序布置在同X所在的DM中 通过DM的操作隐含地实现锁的请求和释放 1 读锁可以隐含地DM READ操作来请求 2 写锁可隐含地由Pre Commit请求 3 写锁隐含地由DM WRITE操作释放 因为DM WRITE表示紧缩阶段的开始 4 释放读锁需要特殊的释放锁操作 因为DM READ并不导致紧缩阶段的开始 六 主副本2PL算法 主副本2PL算法是对基本的2PL算法的改进 要求 1 对所有逻辑数据项的所有副本 指定其中一个为该数据项的主副本 2 在访问逻辑数据项的任何副本之前 都必须得到主副本的有关锁 实现过程为 读锁情况 事务首先访问存放主副本X1的DM已确定是否存在冲突锁 无冲突时然后访问存储X2的DM以完成数据的传输 写锁情况 事务首先请求X的主副本X1的DM 以确定是否存在冲突锁 在不存在冲突锁时给X的主副本加写锁 然后向所有的副本发出预提交操作Pre Commit 为了减少读操作的代价 可以使用快照技术 七 表决2PL算法 当事务T要写时 它的DM给每一个拥有X副本的DM发Pre Commit操作 这些DM总是发回 置锁 或 锁阻塞 信号 当DM中大多响应 置锁 后 TM给所有的DM发出DM WRITE操作 进入第二阶段 否则等待 直到接收到足够的 置锁 操作 才进行提交的第二阶段 八 集中式2PL算法 2PL的调度程序可以集中放在一个单一的中心场所 而不在数据库中分布 在访问任何场所的数据之前 必须从集中式2PL调度程序中得到对应的锁 实现简单 但通信费用高 5 5时间戳并发控制方法 一 基于时标的并发控制方法1基本概念 1 时标 用来唯一地识别每个事务并允许排序的标识符 时标除具有唯一性外还有单调性 同一事务管理程序所产生的两个时标将是单调递增的 2 分配时标的方法A使用一个全局 整个系统 的单调递增的计数器 缺点难以维护 B每个站点基于本地计数器自治地指定一个时标 时标由两部分组成 如果每个站点能够访问其自身的系统时钟 那么可使用系统时钟值来代替计数器值 3 时标排序规则设两个冲突操作Qij与Qkl分别属于事务Ti与Tk Qij在Qkl之前执行当且仅当ts Ti ts Tk 在这种情况下 Ti称为年老的事务 Tk被称为年轻的事务 基本时标法参见图5 1 在图5 1中 有三个事务在并发执行 事务T1的时间戳为ts T1 事务T2的时间戳为ts T2 事务T3的时间戳为ts T3 且ts T1 ts T2 ts T3 在时刻t8 事务T2的写操作违反了第一条规则 从而T2被撤销 并在时刻t14重新启动 在时刻T14 按照忽略废弃写规则 事务T1的写操作被安全地忽略 因为这次写操作本应在时刻t12被事务T2的写操作覆盖 2全局性时标的形成和调整 假设有两个站点 在每个站点设置一个计数器 每当发生一个事务 计数器值加一 这就解决了同一站点内事务的次序问题 对不同站点 在发送报文时把本站点计数器值包含在报文中 用以近似的同步各站点的计数器值 若站点1收到一个报文的计数器值为Y 它比本地现行计数器X的值大 则把本地计数器值X改为Y 1 否则本地计数器值在原值基础上加1 二 基本时标法 1规则 1 每个事务在本站点开始时赋予一个全局性唯一时标 2 在事务结束之前 不对数据库进行物理修改 3 事务的每个读操作或写操作都具有该事务的时标 4 对于数据库中的每个数据X 记录对其进行读操作和写操作的最大时标 分别记为RTM X 和WTM X 5 如果事务被重新启动 则被赋予新的时标 2执行过程 1 设Ts是对数据X进行读操作的时标 如果Ts WTM X 则拒绝该操作 并使发出该操作的事务用新时标重新启动 否则执行操作 且把RTM X 置为 max RTM X Ts 2 设Ts是对数据X进行写操作的时标 如果Ts RTM X 或Ts WTM X 则拒绝该操作 并使发出该操作的事务用新时标重新启动 否则执行写操作 且把WTM X 置为 max WTM X Ts 这种方法避免死锁是以重新启动作为代价的 三 保守时标法 1保守时标法的规则 1 每个事务只在一个站点执行 他不激活远程的程序 仅仅能向远程站点发出读或写请求 2 每个站点必须按时标时间的顺序发送读 写数据的请求 在传输中也不会改变这个次序 以保证各个站点能够按时标顺序接收来自不同站点的全部读写请求 3 每个站点都为其他各个站点发来的读写操作开辟一个缓冲区 把接收到的读写操作分别保存在相应的缓冲区中 2保守时标的执行步骤假定某个站点K上 其各个缓冲区队列都已不空 即每个站点都已向它至少发送了一个读和一个写操作 就停止接收 处理在缓冲区队列中的操作 例如 站点i上的缓冲区队列情况如下 站点1站点2站点3 站点nR11R21R31 Rn1R12R22R32 Rn2R13R23R24W11W21W31 Wn1W22W32 Wn2W23 由规则2知不可能有来自任何站点的年长请求到达本站点 此时执行步骤如下 1 设RT min Rij WT min Wij 2 按下法处理在缓冲区队列里的Rij和Wij 扫描R队列 若各队列中存在 R ij WT的Rij则按顺序执行他们 执行完成后就从队列中把它们去掉 扫描W队列 若各队列中存在 Wij RT的Wij就按顺序执行它们 执行完成后从队列中把它们去掉 3 修改 RT min Rij WT min Wij 此时的Rij和Wij已是剩余的Rij和Wij了 4 重复上述 2 和 3 直到没有满足条件的操作 或者 若某个或某些R队列为空时 RT 0 若某个或某些W队列为空时 WT 0 继续接收各个站点发送来的读写请求操作 若其各个缓冲区队列又都不为空 仍按上面的步骤继续 3存在的问题和解决办法 1 如果一个站点从不向某个别站点发送操作的话 则执行中假定就不符合 操作就无法执行 解决办法是周期性的发送 空操作 2 该方法要求网络上所有站点都连通 这在大型系统中难以做到 可对无实际读写请求的每个站点发送一个时标为很大的空操作 3 该方法过分保守 一律按时标的顺序执行R和W 其中包括了不会发生冲突的读操作 也被缓冲起来同等对待 四 多版本时标法 事务管理器分配给每个事务一个时标 这个时标也用来跟踪每一个版本的时标 具体处理如下 1 一个Ri X 表示事务i对数据X的一个版本上的读操作 这是通过查找X的一个版本来完成的 如果Ts Xr 是比Ts Ti 小的最大时标 那么Xr就是被查找的版本 然后就把Ri Xr 传送给数据处理器 2 一个Wi X 表示为Wi Xw 操作 这样Ts Xw Ts Ti 并且被送给数据处理器 当且仅当写操作事务时标Ts Ti 比其他已经读取X的一个版本 比如Xr 的事务的时标值大 Ts Xw Ts Xr 换言之 如果调度器已经处理了一个Rj Xr 操作 若Ts Ti Ts Xr Ts Tj 那么Wi X 被拒绝 为了节省空间 数据库的多个版本可以不时地被清除 五 死锁问题 死锁的形成 1 死锁预防在2PL调度程序中 如果一个锁请求被拒绝 则调度程度对请求锁的事务Ti和现在拥有锁的事务加以 死锁测试 如果不发生死锁 则Ti允许等待 否则 其中一个事务被撤销 也可以给事务指派优先级 让Ti等待Tj 当且仅当Ti的优先级低于Tj 基于时间戳的死锁预防方法大体有两类 等待 死亡 若Ti等待Tj如果Ti的优先级低于Tj则允许等待 否则撤销Tj并迫使它重新启动 受伤 等待 Ti的优先级等于Tj Ti等待 否则撤销Tj 2 死锁检测 1 集中式死锁检测指派一个场所为分布式系统的死锁检测器 每一个调度程序将其局部等待图发送到死锁检测器 然后构造局部图 并组合局部图成系统范围的等待图 2 层次死锁检测把数据库场所组成一个层次 或一个树 层次中每一个节点有一个死锁检测器 局部于一个单一节点之死锁在那个场所被检测 包含相同区域的两个或两个以上的场所中的死锁将由区域死锁检测器检测 六 分布式并发控制算法的性能分析 1 性能评价问题一个并发控制算法性能的衡量是一个综合指标 涉及四个主要因素 场所间的通信开销 局部处理开销 事务重新启动的次数和费用 事务阻塞的数