您好、欢迎来到现金彩票网!
当前位置:彩运网 > 封锁粒度 >

8第八章 分布式并发控制-09

发布时间:2019-04-26 04:29 来源:未知 编辑:admin

  第八章 分布式并发控制 基本概念 并发控制问题 并发控制定义 基本锁的并发控制方法 锁的类型 封锁规则 锁的兼容性 锁的粒度 第八章 分布式并发控制 两段封锁协议( 两段封锁协议(2PL) ) 基本的两段封锁协议 严格的两段封锁协议( 严格的两段封锁协议(2PL) ) 并发控制理论基础 事务执行过程的形式化描述 集中库的可串行化问题 分布式事务的可串行化问题 分布库并发控制方法 §8.1 基本概念 并发控制问题 并发控制是分布式事务管理的基本任务之一, 并发控制是分布式事务管理的基本任务之一, 是分布式事务管理的基本任务之一 目的是保证分布式数据库系统中的多个事务的高 目的 是保证分布式数据库系统中的多个事务的高 效并发执行。 多个事务并发执行, 效并发执行 。 多个事务并发执行 , 就有可能产生 操作冲突, 操作冲突 , 如 : 出现重复读错误或读取了脏数据 造成数据库数据的不一致。 等,造成数据库数据的不一致。 并发控制确保事务满足一致性和有效性。 并发控制确保事务满足一致性和有效性。 确保事务满足一致性和有效性 §8.1 基本概念 (1)丢失修改错误 ) 初始x=100,若并行执行, 执行结果为 : T1:x=70;T2:x 若并行执行,执行结果为: : 初始 若并行执行 ; : =70,最终结果 的执行结果破坏了T1执 ,最终结果x=70;结果导致 的执行结果破坏了 执 ;结果导致T2的执行结果破坏了 行的结果,该种现象也称丢失修改错误。 行的结果,该种现象也称丢失修改错误。 §8.1 基本概念 (2)重复读错误 ) 例8.1.2有两个并发执行的事务T1和T2,其中x是数据库 中的一个属性,T1和T2操作序列如下所示: 一事务( 如:一事务(如:T1)重复读一数据项(x)时,得到不 )重复读一数据项( ) 同的结果,该种现象称重复读错误。 同的结果,该种现象称重复读错误。也称一个事务的执行 受到了其它事务的干扰。 受到了其它事务的干扰。 §8.1 基本概念 (3)读脏数据错误 ) 例8.1.3 有两个并发执行的事务T1和T2,其中x是数据 库中的一个属性, T1和T2操作序列如下所示: 可看到如下现象:事务 读取了 废弃的数据x, 读取了T1废弃的数据 可看到如下现象:事务T2读取了 废弃的数据 , 该种现象称读脏数据。应尽量避免读脏数据。因为, 该种现象称读脏数据。应尽量避免读脏数据。因为, 当事务T1废弃时 废弃时, 也必须废弃 即所谓的级联废 也必须废弃, 当事务 废弃时,T2也必须废弃,即所谓的级联废 通常读脏数据会导致级联废弃。 弃。通常读脏数据会导致级联废弃。 §8.1 基本概念 并发控制定义 并发控制就是利用正确的方式调度并发操作,避免 并发控制就是利用正确的方式调度并发操作, 就是利用正确的方式调度并发操作 造成数据的不一致性, 造成数据的不一致性,防止一个事务的执行受到其 可串行性。 它事务的干扰,保证事务并发执行的可串行性 它事务的干扰,保证事务并发执行的可串行性。 §8.2 基本锁的并发控制方法 锁的基本思想是要求事务在对一数据项进行操作 之前必须首先申请对该数据项进行加锁, 之前必须首先申请对该数据项进行加锁,申请成 功后才可对其操作。 功后才可对其操作。如果该数据项已被其它事务 加锁,则出现操作冲突,该事务必须等待, 加锁,则出现操作冲突,该事务必须等待,直到 该数据项被解锁为止。 该数据项被解锁为止。 §8.2 基本锁的并发控制方法 锁的类型 锁一般分两种类型, 排它锁( 锁一般分两种类型 , 排它锁 ( exclusive) 和 共享 ) 锁(shared)。 ) 排它锁常称为X锁或写锁; 排它锁常称为 锁或写锁; 锁或写锁 排它锁指当事务T对数据 施加排它锁之后 只允许事务T 排它锁指当事务 对数据A施加排它锁之后,只允许事务 对数据 施加排它锁之后, 自己读写A,其它事务都不可读写A 自己读写 ,其它事务都不可读写 。 共享锁称为S锁或读锁。 共享锁称为 锁或读锁。 锁或读锁 共享锁指当事务T对数据 施加共享锁之后 事务T和其它 共享锁指当事务 对数据A施加共享锁之后,事务 和其它 对数据 施加共享锁之后, 事务只能读取A。 事务只能读取 。 即共享锁允许多个事务同时访问同一数 据项A。 据项 。 §8.2 基本锁的并发控制方法 封锁规则 事务在执行过程中需对其访问的数据项进行加锁, 事务在执行过程中需对其访问的数据项进行加锁 , 访问结束要及时释放其对数据项加的锁, 访问结束要及时释放其对数据项加的锁 , 以便供其 它事务访问, 保证多个事务高度正确并行执行。 具 它事务访问 , 保证多个事务高度正确并行执行 。 体封锁规则为: 体封锁规则为: (1) 事务 在对 数据项 进行 读 /写操作 之前 , 必须对 事务T在对数据项A进行 写 操作之前 在对数据项 进行读 之前, 数据项A施加 读 /写锁 , 访问后立即 释放已申请的 锁 ; 数据项 施加读 写锁, 访问后 立即释放 已申请的锁 施加 写锁 立即 释放 已申请的 如果事务T申请不到希望的锁 事务T需等待, 申请不到希望的 (2)如果事务 申请不到希望的锁,事务 需等待,直 到申请到所需要的锁,之后方可继续执行 到申请到所需要的锁, §8.2 基本锁的并发控制方法 锁的兼容性 锁一般分读锁和写锁。读锁是进行读操作时加的锁, 锁一般分读锁和写锁。读锁是进行读操作时加的锁,允许多 读锁 个事务同时完成读操作,即具有共享性; 个事务同时完成读操作,即具有共享性;写锁是进行写操作 时加的锁,只允许申请该锁的事务进行写操作,所以, 时加的锁,只允许申请该锁的事务进行写操作,所以,写锁 不具有共享性,而具有排它性。写锁和读锁的相容性见下表: 不具有共享性,而具有排它性。写锁和读锁的相容性见下表: §8.2 基本锁的并发控制方法 锁的粒度 封锁数据对象的单位称锁的粒度, 封锁数据对象的单位称锁的粒度,即指被封锁的数据对象 称锁的粒度 的大小。锁的粒度也称锁的大小。 的大小。 锁的粒度也称锁的大小。系统根据自己的实际情 况确定锁的粒度,锁的粒度可以是关系的字段属性、 况确定锁的粒度,锁的粒度可以是关系的字段属性、关系 的元组、关系(也称文件)或整个数据库等。 的元组、关系(也称文件)或整个数据库等。 锁粒度的大小对系统的并发度和开销有一定影响, 锁粒度的大小对系统的并发度和开销有一定影响,锁粒度 越大,系统的开销越小,但降低了系统的并发度。 越大,系统的开销越小,但降低了系统的并发度。针对并 发控制,系统的并发度与锁粒度成反比。如下表所示: 发控制,系统的并发度与锁粒度成反比。如下表所示: 粒度 小 大 开销 大 小 并发度 高 低 两段封锁协议( §8.3 两段封锁协议(2PL) ) 两段封锁协议( 两段封锁协议(2PL)是数据库系统中解决并发控制 ) 的重要算法之一。遵循两段锁协议规则的系统可保 的重要算法之一。遵循两段锁协议规则的系统可保 证事务的可串行性调度。 证事务的可串行性调度。 两段封锁协议的实现思想是将事务中的加锁操作和 两段封锁协议的实现思想是将事务中的加锁操作和 解锁操作分两阶段完成, 解锁操作分两阶段完成,并要求并发执行的多个事 务要在对数据操作之前进行加锁, 务要在对数据操作之前进行加锁,且每个事务中的 所有加锁操作要在解锁操作以前完成。 所有加锁操作要在解锁操作以前完成。 两段封锁协议( §8.3 两段封锁协议(2PL) ) 通常两段封锁协议分为基本的两段封锁协议和严格 通常两段封锁协议分为基本的两段封锁协议和 基本的两段封锁协议 的两段封锁协议。 的两段封锁协议。 在两段封锁协议实现中,系统的加锁方式分两种: 在两段封锁协议实现中,系统的加锁方式分两种: ?显示锁方式,由系统加封锁命令实现; 显示锁方式,由系统加封锁命令实现; 显示锁方式 ?隐式锁方式,由系统自动加锁实现。 隐式锁方式,由系统自动加锁实现。 隐式锁方式 两段封锁协议( §8.3 两段封锁协议(2PL) ) 基本的两段封锁协议 基本的两段封锁协议的内容分两阶段,加锁阶段和 基本的两段封锁协议的内容分两阶段 , 加锁阶段 和 解锁阶 具体规则描述如下: 段。具体规则描述如下: 阶段1: 阶段 :加锁阶段 ?事务在读写一个数据项之前,必须对其加锁; 事务在读写一个数据项之前,必须对其加锁; 事务在读写一个数据项之前 ?如果该数据项被其它使用者已加上不相容的锁,则 如果该数据项被其它使用者已加上不相容的锁, 如果该数据项被其它使用者已加上不相容的锁 必须等待。 必须等待。 阶段2: 阶段 :解锁阶段 ?事务在释放锁之后,不允许再申请其它锁; 事务在释放锁之后,不允许再申请其它锁; 事务在释放锁之后 两段封锁协议( §8.3 两段封锁协议(2PL) ) 在事务执行过程中,两段封锁协议( 在事务执行过程中,两段封锁协议(2PL)的加锁、解锁示 )的加锁、 意图( 意图(图8.1)如下: )如下: 基本的两段封锁协议(2PL) 基本的两段封锁协议 两段封锁协议( §8.3 两段封锁协议(2PL) ) (1) 避免丢失修改错误 ) 下图描述了事务T 并行执行时产生了丢失修改错误。 下图描述了事务 1和T2并行执行时产生了丢失修改错误。 若采用两段封锁协议进行并行控制: 若采用两段封锁协议进行并行控制: 当事务T 申请写锁时,均申请不到,必须等待, 当事务 1、T2申请写锁时,均申请不到,必须等待,直到 另一事务释放对数据项x的锁为止 的锁为止。 废弃, 另一事务释放对数据项 的锁为止 。 如 : T2 废弃 , 释放读 得到写锁,完成写操作。事务T2重启动后 重启动后, 锁;则T1得到写锁,完成写操作。事务 重启动后,读取 x(事务 执行的结果 , 直至完成操作 。 因此 , 不会出现 事务T1执行的结果 事务 执行的结果), 直至完成操作。 因此, 丢失修改错误。 丢失修改错误。 两段封锁协议( §8.3 两段封锁协议(2PL) ) (2) 避免重复读错误 ) 下图描述了事务T1和T2并行执行时产生了重复读错误。若采用 下图描述了事务 并行执行时产生了重复读错误。 两段封锁协议进行并行控制: 两段封锁协议进行并行控制: 从上图可见,当事务 申请写锁时,不能申请成功, 从上图可见,当事务T2申请写锁时,不能申请成功,必等 当事务T 再次读数据项x时 读取的x值与第一次读到 待,当事务 1再次读数据项 时,读取的 值与第一次读到 的值相同,不会出现重复读错误。 的值相同,不会出现重复读错误。 两段封锁协议( §8.3 两段封锁协议(2PL) ) 2PL不能避免级联废弃 为什么? 不能避免级联废弃,为什么 为什么? 两段封锁协议( §8.3 两段封锁协议(2PL) ) 严格的两段封锁协议( 严格的两段封锁协议(2PL) ) 严格的两段封锁协议与基本的两段封锁协议内容基本 上是一致的,只是解锁时刻不同。 上是一致的,只是解锁时刻不同。严格的两段封锁协 议(2PL)是在事务结束时才启动解锁,保证了事务 )是在事务结束时才启动解锁, 所更新数据的耐久性。 所更新数据的耐久性。 采 用 两 段 封 锁 协 议 ( 2PL ) 的 事 务 执 行 过 程 为 : begin_transaction→ 加 锁 → 操 作 → 提 交 / 废 弃 → commit/abort) 解锁。 (commit/abort)→解锁。 两段封锁协议( §8.3 两段封锁协议(2PL) ) 提交/废弃(commit/abort)时解锁过程具体如下: 提交/废弃(commit/abort)时解锁过程具体如下: 具体如下 commit的处理 (1) 对commit的处理 ?释放读锁; 释放读锁; 释放读锁 ?写日志; 写日志; 写日志 ?释放写锁。 释放写锁。 释放写锁 abort的处理 (2) 对abort的处理 ?释放读锁; 释放读锁; 释放读锁 ?(反做)undo; )undo; (反做)undo ?释放写锁; 释放写锁; 释放写锁 两段封锁协议( §8.3 两段封锁协议(2PL) ) 严格的两段封锁协议(2PL) 严格的两段封锁协议 §8.4 并发控制理论基础 事务执行过程的形式化描述 并发控制的主要目的是保证分布事务及分布式数据 并发控制的主要目的是保证分布事务及分布式数据 目的 库的一致性。并发控制既要实现分布事务的可串行 库的一致性。 又要保持事务具有良好的并发度。 性,又要保持事务具有良好的并发度。无论集中式 数据库, 数据库,还是分布式数据库的并发控制均是以串行 化理论为基础,并以它为模型来检验方法的正确性。 化理论为基础,并以它为模型来检验方法的正确性。 按串行化理论, 按串行化理论,一个在数据库上运行的事务的所有 操作,按其性质分为读和写两类。通常,一个事务 操作,按其性质分为读 两类。通常, Ti对数据项 的读操作和写操作记为 i(x)和Wi(x)。 对数据项x的读操作和写操作记为 的读操作和写操作记为R 和 。 一个事务T 所读取数据项的集合,称为T 的读集, 一个事务 i所读取数据项的集合,称为 i的读集, 所写的数据项的集合,称为的写集,分别记为R(Ti) 所写的数据项的集合,称为的写集,分别记为 。 和W(Ti)。 §8.4 并发控制理论基础 设有事务T 完成的操作如下: 例8.4.1设有事务 1,完成的操作如下:T1:x=x+1;y=y+1;其 设有事务 ; ; 为数据库中的两个数据项。 中x、y为数据库中的两个数据项。 、 为数据库中的两个数据项 的操作可表示为: 则:T1的操作可表示为:R1(x) W1(x) R1(y) W1(y); ; R(T1)={x,y}; ( , ; W(T1)={x,y}; ( , ; 在一个数据库上,各个事务所执行的操作组成的序列, 在一个数据库上,各个事务所执行的操作组成的序列,称为 事务的历 事务的 历 程 , 记为 H , 有时也称调度 ( Schedule, 也称 历史 history)。用于记录各事务的操作顺序。 ) 用于记录各事务的操作顺序。 对于一个历程上的任何两个事务, 如果T 对于一个历程上的任何两个事务 , Ti 和 Tj , 如果 i 的最后一 个操作在T 的第一个操作之前完成,或反之, 个操作在 j的第一个操作之前完成,或反之,则称该历程为串 行执行的历程,简称为串行历程 否则称为并行历程 串行历程, 并行历程。 行执行的历程,简称为串行历程,否则称为并行历程。系统通 常希望事务历程中的各个事务是并发的, 常希望事务历程中的各个事务是并发的,但同时又等价于一个 串行的事务历程,即事务历程是可串行化的。 串行的事务历程,即事务历程是可串行化的。 §8.4 并发控制理论基础 设有事务T 完成的操作为: 例8.4.2设有事务 1和T2,T1和T2完成的操作为: 设有事务 T1:R1(x) R1(y) W1(x) W1(y); ; T2: R 2(x) W2(y); ; 设有:历程 分别为: 设有:历程H1和H2,H1和H2分别为: H1:R1(x) R1(y) W1(x) W1(y) R 2(x) W2(y) H2:R1(x) R 2(x)R1(y) W1(x) W1(y) W2(y) 历程H1和H2也可用下图等价表示: 也可用下图等价表示: 历程 在历程H 事务T 的所有操作都是在事务T 的操作之前完成的, 在历程 1中,事务 1的所有操作都是在事务 2的操作之前完成的,因此该 历程是串行历程。而在历程H 不满足串行历程的定义,因此是并行历程。 历程是串行历程。而在历程 2不满足串行历程的定义,因此是并行历程。 §8.4 并发控制理论基础 集中库的可串行化问题 无论在集中式数据库系统中,还是在分布式数据库系统中, 无论在集中式数据库系统中,还是在分布式数据库系统中,事 务的并发调度都要解决并行执行事务对数据库的冲突操作, 务的并发调度都要解决并行执行事务对数据库的冲突操作,使 冲突操作串行执行,非冲突操作并行执行。 冲突操作串行执行,非冲突操作并行执行。 只是在分布式数 据库系统中,事务是分解为各个场地上的子事务的执行实现的。 据库系统中,事务是分解为各个场地上的子事务的执行实现的。 因此,分布式事务之间的冲突操作, 因此,分布式事务之间的冲突操作,转化为了同一场地上的子 事务的冲突操作, 事务的冲突操作,分布事务的可串行性调度转化为了子事务的 可串行性调度。下面先介绍可串行化涉及的概念, 可串行性调度。下面先介绍可串行化涉及的概念,然后介绍集 中库的可串行化问题。 中库的可串行化问题。 (1)可串行化定义 ) 在集中式数据库系统中的一个历程H, 定义 在集中式数据库系统中的一个历程 , 如果等价于一个 串行历程,则称历程H是可串行化的 由可串行化历程H所决 串行历程,则称历程 是可串行化的。由可串行化历程 所决 定的事务执行顺序,记为SR(H)。 定的事务执行顺序,记为 。 §8.4 并发控制理论基础 (2)事务的执行顺序 事务的执行顺序 事务的并发调度就是要解决并行执行事务对数据库的 冲突操作。 冲突操作。 如果分别属于两个事务的两个操作O 定义 如果分别属于两个事务的两个操作 i和Oj,操作 同一个数据项, 至少其中一个操作为写操作, 其中一个操作为写操作 同一个数据项 , 且 至少 其中一个操作为 写操作 , 则 Oi 这两个操作是冲突 冲突的 和 Oj 这两个操作是 冲突 的 。 如 : R1(x) W2(x)和 W 1(x) 和 W2(x)均为冲突操作。若在一个串行历程中,“”表示 均为冲突操作。 均为冲突操作 若在一个串行历程中, 表示 的两个冲突操作O 先于关系, 对分别属于T 先于关系 , 对分别属于 i 和 Tj 的两个冲突操作 i 和 Oj , 若存在O 若存在 iOj,则TiTj。 §8.4 并发控制理论基础 (3) 历程等价的判别方法 ) 如果一个历程H等价于一个串行历程 , 则称历程H是可 如果一个历程 等价于一个串行历程, 则称历程 是可 等价于一个串行历程 串行化的。判断两个历程等价的定理和引理如下: 串行化的。判断两个历程等价的定理和引理如下: 定理8.1 对于任意两个历程 1和H2等价的充要条件为: 对于任意两个历程H 等价的充要条件 充要条件为 定理 ① 在 H1 和 H2 中 , 每个读操作读出的数据是由相同的写 操作完成的; 操作完成的; 每个数据项上最后的写操作是相同的。 ② 在 H1 和 H2 中 , 每个数据项上最后的写操作是相同的 。 对于两个历程H 如果每一对冲突操作O 引理 对于两个历程 1和H2,如果每一对冲突操作 i和Oj, 中有O 中也有O 是等价的。 在H1中有 iOj,在H2中也有 iOj,则H1和H2是等价的。 §8.4 并发控制理论基础 设有三个历程H 分别为: 例8.4.3 设有三个历程 1、H2和 H3,分别为: H1:R1(x) R1(y) W1(x) W1(y) R 2(x) W2(x); ; H2:R1(x) R 1(y) W 1(x) R 2(x) W1(y) W2(x); ; H3:R1(x) R 1(y) R 2(x) W 1(x) W1(y) W2(x)。 。 要求:判断历程 是否为可串行化的历程。 要求:判断历程H2和 H3是否为可串行化的历程。 从上面的历程H 中可看出,事务T 从上面的历程 1中可看出,事务 1的所有操作都是 在事务T 的操作之前完成的,因此可判断,历程H 在事务 2的操作之前完成的,因此可判断,历程 1 是串行历程。 是串行历程。 §8.4 并发控制理论基础 下面根据两历程等价引理分别判断H 是否与历程H 等价, 下面根据两历程等价引理分别判断 2和H3是否与历程 1等价, 若等价,则该历程是可串行化的历程。判别如下: 若等价,则该历程是可串行化的历程。判别如下: 首先找出历程H 的冲突操作; ① 首先找出历程 1、H2和 H3的冲突操作; 找出历程H 中与历程H ② 分别 找出历程 2 和 H3 中与历程 1 的等价冲突操作 , 用 ”表示。 “ 表示。 H1:R1(x) R1(y) W1(x) W1(y) R2(x) W2(x); ; 则结果有如下所示: 则结果有如下所示: H2的冲突操作 R1(x) W2(x) W 1(x) R 2(x) W 1(x) W2(x) H2:R1(x) R 1(y) W 1(x) R 2(x) W1(y) W2(x); ; H3:R1(x) R 1(y) R 2(x) W 1(x) W1(y) W2(x)。 。 H1的冲突操作 R1(x) W2(x) W1(x) R2(x) W1(x) W2(x) H3的冲突操作 R1(x) W2(x) R 2(x) W 1(x) W1(x) W2(x) 可知,历程H 与历程H 等价,因此历程H 是可串行化的历程; 可知,历程 2与历程 1等价,因此历程 2是可串行化的历程; 历程H 与历程H 不等价,因此历程H 不是可串行化的历程。 历程 3与历程 1不等价,因此历程 3不是可串行化的历程。 §8.4 并发控制理论基础 3、分布式事务的可串行化问题 分布式事务的可串行化问题 在分布式事务执行过程中,每个场地S 定义 在分布式事务执行过程中,每个场地 i上的 子事务执行序列, 称为局部历程, 子事务执行序列 , 称为局部历程 , 用 H( Si ) 表 ( 示。 在分布式数据库系统中,将分布事务的可串行性 在分布式数据库系统中, 调度转化为了以场地为基础的子事务的可串行性 调度。用下面定理 引理判断分布式事务是否是 定理或 调度 。 用下面 定理 或引理 判断分布式事务是否是 可串行化的。 可串行化的。 §8.4 并发控制理论基础 于n 式事务T 场地上S 定理 对 于 个 分布 式事务 1 、 T2 、 … Tn 在 m 个 场地上 1 、 S2、… Sm上的并发执行,记为 。如果 是可串行化的,则必须 上的并发执行,记为E。如果E是可串行化的 是可串行化的, 满足以下条件: 满足以下条件: 是可串行化的; (1) 每个场地 i上局部历程 (Si)是可串行化的; ) 每个场地S 上局部历程H( ( 2)存在 的一个总序, 使得在总序中, 如果有 iTj, 则在各 的一个总序, )存在E的一个总序 使得在总序中,如果有T 局部历程中必须有T 局部历程中必须有 iTj。 个分布式事务, 是这组事务在 是这组事务在m个 引理 设T1、T2、… Tn是n个分布式事务,E是这组事务在 个 个分布式事务 场地上的并发执行, ( 场地上的并发执行,H(S1)、H(S2)、… H(Sm)是在这些 ( ( 场地上事务的局部历程,如果E是可串行化的 是可串行化的, 场地上事务的局部历程,如果 是可串行化的,则必须存在一个 总序,使得对T 的任两个冲突操作O 如果在H( 总序 , 使得对 i和 Tj的任两个冲突操作 i和Oj, 如果在 ( S1) 、 H(S2)、… H(Sm)中有 iOj,当且仅当在总序中有 iTj。 中有O 当且仅当在总序中有T ( ( §8.5 分布库并发控制方法 并发控制既要实现分布事务的可串行性, 并发控制既要实现分布事务的可串行性,同时又要保持事务具 既要实现分布事务的可串行性 有良好的并发度,保证分布事务及分布式数据库的一致性。 有良好的并发度,保证分布事务及分布式数据库的一致性。在 分布式数据库系统中,常常采用严格的两段封锁协议( 分布式数据库系统中,常常采用严格的两段封锁协议(2PL) ) 实现并发控制,另外,还有多版本的时间印方法及乐观方法。 实现并发控制,另外,还有多版本的时间印方法及乐观方法。 下面介绍两段封锁协议(2PL)的几种封锁方法。 下面介绍两段封锁协议( )的几种封锁方法。 1、 集中式实现方法 、 集中式实现方法是在分布库中设立一个2PL调度器,所有封锁 调度器, 集中式实现方法是在分布库中设立一个 调度器 请求均由该调度器完成。该种实现方法实现简单, 请求均由该调度器完成。该种实现方法实现简单,但存在易受 调度器所在场地故障影响和需要大量通讯费用的不足。 调度器所在场地故障影响和需要大量通讯费用的不足。 §8.5 分布库并发控制方法 集中式实现方法 只有一个2PL调度器,锁由集中式封锁管理器提供 只有一个 调度器, 调度器 数据处理在参与者场地 Participating sites Coordinating TM Central Site LM (1) Lock Request (2) Lock Granted (3) Operation (4) End of Operation (5) Release Locks §8.5 分布库并发控制方法 分布式实现方法 分布式实现方法是在每个场地上都有一个2PL调度器,每个调 分布式实现方法是在每个场地上都有一个 调度器, 每个场地上都有一个 调度器 度器处理本场地上的封锁请求。 度器处理本场地上的封锁请求。该种实现方法避免了集中式实 复杂性。 现方法存在的不足,但同时也增加了实现全局调度的复杂性 现方法存在的不足,但同时也增加了实现全局调度的复杂性。 Communication structure : Coordination TM Participating LMs Participating DPs (1) Lock Request (2) Operation (3) End of Operation (5) Release Locks §8.5 分布库并发控制方法 对复制数据的封锁方法 在分布式数据库中,为提高系统的有效性、 在分布式数据库中,为提高系统的有效性、可靠性及存取 效率,常在多个场地上存放多个数据库的副本, 效率,常在多个场地上存放多个数据库的副本,当系统的 某一或多个场地发生故障时, 某一或多个场地发生故障时,可通过其它场地上的数据副 本完成数据处理。 本完成数据处理。但同时也增加了系统选择副本及处理多 副本更新等相应处理功能,即增加了系统的复杂性。 副本更新等相应处理功能,即增加了系统的复杂性。通常 多副本的并发控制方法分为基于特定副本的封锁方法和基 分为基于特定副本 多副本的并发控制方法分为基于特定副本的封锁方法和基 投票的封锁方法 基于特定副本的封锁方法又分为主副 的封锁方法。 于投票的封锁方法。基于特定副本的封锁方法又分为主副 本法、主场地法和后备场地的主场地法; 本法、主场地法和后备场地的主场地法;基于投票的封锁 方法分为读 写全法 多数副本法。 写全法和 方法分为读—写全法和多数副本法。 §8.5 分布库并发控制方法 (1) 基于特定副本的封锁方法 ①主副本法 主副本法规定每一数据项在某个场地上的副本为 主副本法 规定每一数据项在某个场地上的副本为 主副本, 主副本 , 通常主副本选择在用户申请封锁某数据 项较多的场地, 该场地也称为主场地。 项较多的场地 , 该场地也称为主场地 。 所有封锁 申 请 由 主 副 本 所 在 场 地 的 锁 管 理 器 LM ( lock manager) 完成 。 采用主副本法 , 降低了通信费 ) 完成。 采用主副本法, 但也降低了并发程度。 用,但也降低了并发程度。 §8.5 分布库并发控制方法 ②主场地法 主场地法规定保存副本的某个场地为主场地, 主场地法规定保存副本的某个场地为主场地,所有封 规定保存副本的某个场地为主场地 锁申请由主场地的锁管理器 锁管理器LM(lock manager) 完 锁申请由主场地的 锁管理器 ( ) 即系统中的所有封锁申请都要传到主场地, 成。即系统中的所有封锁申请都要传到主场地,由主 场地决定是否同意封锁请求。由于在主场地法中, 场地决定是否同意封锁请求。由于在主场地法中,所 有锁申请由一个场地处理,易形成瓶颈, 有锁申请由一个场地处理,易形成瓶颈,当主场地出 故障时,整个系统将瘫痪。 故障时,整个系统将瘫痪。 ③后备场地的主场地法 为防止主场地故障,设立另一个场地为后备主场地, 为防止主场地故障,设立另一个场地为后备主场地, 当主场地发生故障后,由后备主场地顶替主场地。 当主场地发生故障后,由后备主场地顶替主场地。 §8.5 分布库并发控制方法 (2) 基于投票的封锁方法 ①读—写全法 写全法 写全法指当事务对某一数据项加锁时 读—写全法指当事务对某一数据项加锁时,若为读锁,只需封 写全法指当事务对某一数据项加锁时,若为读锁, 锁其中一个副本, 锁其中一个副本,即只需向选中的副本所在场地发送锁申请报 若为写锁,必须封锁所有副本, 文;若为写锁,必须封锁所有副本,即需要向所有存有该数据 项的副本所在场地发送锁申请报文。因此, 项的副本所在场地发送锁申请报文。因此,在写锁情况下通信 费用较大,为避免该不足,提出了多数法。 费用较大,为避免该不足,提出了多数法。 ②多数副本法 多数副本法是指在对数据项进行加锁时, 多数副本法是指在对数据项进行加锁时,必须封锁数据项一半 是指在对数据项进行加锁时 以上的副本。无论读锁还是写锁申请,都要向n个副本中的至 以上的副本 。 无论读锁还是写锁申请 , 都要向 个副本中的至 个副本所在场地发加锁请求。 少(n+1)/2个副本所在场地发加锁请求。申请成功后,若为读锁, 个副本所在场地发加锁请求 申请成功后,若为读锁, 读取一个副本的值;若为写锁,需向n个副本发送新值 个副本发送新值。 读取一个副本的值;若为写锁,需向 个副本发送新值。 §8.5 分布库并发控制方法 并发控制算法分类 §8.6 基于时间印的并发算法 锁方法通过锁的互斥维护可串行性. 锁方法通过锁的互斥维护可串行性 Timestamp method maintains serializability by assigning a unique timestamp to every transaction and executing transactions accordingly. What is a timestamp? an identifier for transaction used to permit ordering monotonicity – timestamps generated by the same TM are monotonically increased in values. §8.6 基于时间印的并发算法 How to assign a timestamp value use a monotinically increasing counter, but this is difficult in distributed environment use a two-tuple form local-counter-value, site-identifier use local-system-clock, site-identifier Note site ID is put in the least significant position to avoid the situation that timestamps from a site will always be larger/smaller than timestamps from another site. §8.6 基于时间印的并发算法 ts(Ti) – the timestamp value of transaction Ti. How to schedule by the TO Rule: Check each new operation against conflicting operations that have been scheduled. If the new operation belongs to a younger transaction than ALL conflicting ones, then accept it; otherwise reject it and the entire transaction has to restart with a new timestamp. §8.6 基于时间印的并发算法 This means the system maintains the execution order according to the timestamps order. TM is responsible for assigning a timestamp to each transaction and attach it to each database operation. Two timestamps maintained by DBMS for each data item x for scheduling: [rts(x)]: the largest of transactions that have read x. timestamps of of [wts(x)]: the largest of timestamps transactions that have written x. §8.6 基于时间印的并发算法 Principle of basic timestamp algorithm §8.6 基于时间印的并发算法 Principle of basic timestamp algorithm How to maintain timestamps among sites When ts(T) rts(x), the read is rejected. Site 2 adjusts its timestamp by making it larger than rts(x) and restart. Why? Avoid ts(site 1) ts(site 2) which may make operations from site 2 never get executed. §8.6 基于时间印的并发算法 Conservative TO Algorithm Basic TO algorithm: dead lock free but too many restarts. Conservative TO algorithm delays each operation until there is an assurance that no operation with smaller timestamps can arrive at that scheduler. Basic technique at site i, each scheduler i has one queue Qij for each TM at site j in the system an operation from TMj is placed in Qij in increasing timestamp order. Scheduler i executes operation from ALL queues in this order also. §8.6 基于时间印的并发算法 Conservative TO Algorithm This reduces the number of restarts. But restart may occur when a queue is empty. §8.6 基于时间印的并发算法 Conservative TO Algorithm Suppose Q23 is empty and scheduler 2 chooses an operation op from Q21 and Q22. But later a conflicting operation with smaller timestamp than ts(op) from site 3 arrives, then this operation must be rejected and restarted! To improve, use extremely conservative algorithm complemented by in each queue there is at least one operation, or if a TM does not have a transaction to process, it has to send a message periodically to inform that in the future it will send timestamp larger than that of the message. §8.6 基于时间印的并发算法 Conservative TO Algorithm Extremely conservative algorithm actually executes transaction serially at each site. Too conservative! An operation may have to wait for the coming of a younger operation of an empty queue – a delay problem! Improvement: define transaction classes and set a queue for each class instead of each TM. Transaction classes are defined by their read set and write set. If a transaction’s read set and write set are subset of a class, then the transaction belongs to that class. It is difficult to define transaction classes! §8.6 基于时间印的并发算法 Multiversion TO Algorithm Each write creates a new version of the data item to be updated. Versions are transparent to users. Transactions are processed on a state of database that it would have seen if they were executed serially in timestamp order. §8.6 基于时间印的并发算法 Multiversion TO Algorithm §8.6 基于时间印的并发算法 OPTIMISTIC CONCURRENCY CONTROL ALGORITHMS 悲观算法假设冲突经常发生,而乐观算法等到写阶段开始时, 悲观算法假设冲突经常发生 , 而乐观算法等到写阶段开始时 , 才进行冲突验证. 才进行冲突验证 悲观算法 乐观算法 §8.6 基于时间印的并发算法 OPTIMISTIC CONCURRENCY CONTROL ALGORITHMS Concepts of optimistic algorithms Timestamps are only associated transactions, but not with data items. with Timestamps are assigned at the beginning of validation phase, but not the initialization of transactions. §8.6 基于时间印的并发算法 OPTIMISTIC CONCURRENCY CONTROL ALGORITHMS §8.6 基于时间印的并发算法 OPTIMISTIC CONCURRENCY CONTROL ALGORITHMS §8.6 基于时间印的并发算法 OPTIMISTIC CONCURRENCY CONTROL ALGORITHMS 全局校验 There is no known optimistic method for doing it! One pessimistic method for doing it – A transaction is globally validated if all the transactions that precede it in the serialization order (at that site) terminate i.e. commit/abort. 乐观算法的优点: 高并发性. 乐观算法的优点 高并发性 乐观算法的缺点: 用于排列事务的高存储代价. 乐观算法的缺点 用于排列事务的高存储代价 No implementation at the time of writing the textbook. §8.7 Oracle多版本的并发控制举例 Oracle 提供: 提供: 一致读查询:在某一时刻查询产生一致结果; 一致读查询:在某一时刻查询产生一致结果; 非阻塞查询:数据写入器从来不阻塞查询。 非阻塞查询:数据写入器从来不阻塞查询。 例如: 例如:select sum(account_balance) from accounts 正确结 果是¥ 果是¥1250 但在读取完第一行,正在读取第2和第 行时, 和第3行时 但在读取完第一行, 正在读取第 和第 行时, 自动取款机发生 交易, 从帐号123中移到 中移到456中,结果如何? 交易,把¥400从帐号 从帐号 中移到 中 结果如何? 行 账户(account_number) 账户余额 (account_balance) 1 2 3 4 123 234 345 456 ¥500.00 ¥250.00 ¥400.00 ¥100.00 §8.7 多版本的并发控制方法 其他数据库中,汇总时锁定整张表或读取某些行时锁定它们。 其他数据库中,汇总时锁定整张表或读取某些行时锁定它们。 Oracle 采用多版本方式,存在多版本,查询不锁定任何数据; 采用多版本方式,存在多版本,查询不锁定任何数据; 修改数据时,两个不同的地方产生记录: 日志( 修改数据时,两个不同的地方产生记录:redo日志(重做和前 日志 插入、删除行信息; 记录, 滚、插入、删除行信息;undo记录,写到回滚段,用于事务失 记录 写到回滚段, 败时撤销操作。 败时撤销操作。 在数据库中,相同的信息有多个版本, 在数据库中,相同的信息有多个版本,所有版本在数据库中 利用这些不同时间点的数据“ 不同时间点可用 , Oracle 利用这些不同时间点的数据 “ 快 提供一致读查询和非阻塞查询。 照”,提供一致读查询和非阻塞查询。 §8.7 多版本的并发控制方法 行 1 2 3 4 时间 T1 T2 T3 T4 T5 T6 读第4行 发现第 行已经被改变 读第 行,发现第4行已经被改变 回滚到时间为T1时的块 时的块。 了,回滚到时间为 时的块。查 询将从此块读出值为¥ 询将从此块读出值为¥100 提供¥ 提供¥1250作为结果 作为结果 读第2行 合计)=¥ 读第 行,sum(合计 ¥750 合计 读第3行 合计)=¥ 读第 行,sum(合计 ¥1250 合计 更新第4行 在第 行上设置独占锁防止其他更新 更新第 行,在第4行上设置独占锁防止其他更新 但不是读取)。 )。第 行在在是 行在在是¥ (但不是读取)。第4行在在是¥500 查询 读第1行,sum(合计 ¥500 合计)=¥ 读第 行 合计 更新第1行 在第 行上设置独占锁防止其他变化 行上设置独占锁防止其他变化。 更新第 行,在第1行上设置独占锁防止其他变化。 行存在是¥ 第1行存在是¥100 行存在是 账户 123 234 345 456 账户余额 ¥500.00 ¥250.00 ¥400.00 ¥100.00 账户过户事务 非阻塞读取 的实现方式 提交事务 T7 T8

http://funnyland.net/fengsuolidu/57.html
锟斤拷锟斤拷锟斤拷QQ微锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷锟斤拷微锟斤拷
关于我们|联系我们|版权声明|网站地图|
Copyright © 2002-2019 现金彩票 版权所有