（计算机应用技术专业论文）基于冗余的3pc协调者替代算法的研究.pdf

上海师范大学硕士学位论文 摘要 摘要 随着数据库技术和网络技术的发展，分布式数据库系统越来越受到人们的关 注。由于分布式数据库的分布性和逻辑整体性的特点，如何保证分布式事务提交 的原子性，是分布式数据库系统比较关心的问题。三阶段提交协议是在两阶段提 交协议的基础上提出的，在保证分布式事务提交原子性的基础上，局部的改善了 两阶段提交协议易阻塞的缺点，提高了系统性能和系统资源的利用率。但是三阶 段提交协议也有自身的固有的缺点：网络通信量比较大。因此，如何减少三阶段 提交协议的通信量对分布式数据库系统有着重要的意义。 本文首先介绍了常用的事务提交协议，其中详细介绍了几种三阶段提交协议： 基于代理的三阶段提交协议( p 3 p c ) 、基于心跳技术的三阶段提交协议( h b b 3 p c ) 、 基于冗余的三阶段提交协议( r 3 p c ) ，并分析了这三种提交协议的优缺点。 接着，本文在r 3 p c 的基础上，针对协调者发生阻塞后，以提高选择新的效率 高的协调者为目的，对三阶段提交协议进行了改进，提出了两种新协调者选择算 法：计数器选择算法和1 l 选择算法。同时分析了这两种算法的优缺点。 最后，本文分析了分布式数据库系统中的故障，并给出了常用的恢复策略。 阐述在故障发生后，新协调者如何接替原来协调者的工作。 关键字：分布式数据库，三阶段提交协议，协调者选择算法 上海师范大学硕士学位论文 a b s t r a c t a b s t r a c t w i t ht h ed e v e l o p m e n to fd a t a b a s et e c h n o l o g ya n dn e t w o r kt e c h n o l o g y ，p e o p l ea r e p a y i n gm o r ea t t e n t i o no nd i s t r i b u t e dd a t a b a s es y s t e m b e c a u s eo ft h ec h a r a c t e r i s t i co f d i s t r i b u t i o na n dl o g i co ft h ed i s t r i b u t e dd a t a b a s e ，h o wt oe n s u r et h ea t o m i c i t yo f d i s t r i b u t e dt r a n s a c t i o nc o m m i t ，i sm o r ec o n c e m e db yd i s t r i b u t e dd a t a b a s es y s t e m t h r e e p h a s ec o m m i tp r o t o c o li sa d v a n c e db a s e do nt h et w o - p h a s ec o m m i tp r o t o c 0 1 o n t h eb a s i so fe n s u r i n gt h ea t o m i c i t yo ft h ed i s t r i b u t e dt r a n s a c t i o nc o m m i t ，t h r e e p h a s e c o m m i tp r o t o c o lh a si np a r t i a l l yi m p r o v e dt h es h o r t c o m i n g so ft h et w o - p h a s ec o m m i t p r o t o c o lw h i c hi se a s yt ob l o c k i n g ，a n de n h a n c e ds y s t e mp e r f o r m a n c ea n ds y s t e m r e s o u r c eu t i l i z a t i o nr a t e b u tt h et h r e e - p h a s ec o m m i tp r o t o c o lh a si t so w ni n h e r e n t d i s a d v a n t a g e s ：al a r g e r n e t w o r kc o m m u n i c a t i o n t h e r e f o r e ，h o wt or e d u c et h e t h r e e - p h a s ec o m m i tp r o t o c o l sn e t w o r kc o m m u n i c a t i o nh a sa ni m p o r t a n ts i g n i f i c a n c et o t h ed i s t r i b u t e dd a t a b a s es y s t e m f i r s t ，t h i sp a p e ri n t r o d u c e st h ec o m m d nt r a n s a c t i o nc o m m i tp r o t o c o l ，a n dg i v e s d e t a i l e dd e s c r i p t i o n so fs e v e r a lt h r e e - - p h a s ec o m m i tp r o t o c o l s ：p r o x yb a s e dt h r e e p h a s e c o m m i tp r o t o c o l ( p 3 p c ) ，h e a r tb e a tb a s e dt h r e e p h a s ec o m m i tp r o t o c o l ( h b b 3 p c ) ， a n dr e d u n d a n c yb a s e dt h r e e - p h a s ec o m m i tp r o t o c o l ( r 3 p c ) t h i sp a p e rh a sa n a l y z e d t h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e s et h r e ec o m m i tp r o t o c 0 1 t h e n ，o nt h eb a s i so fr 3 p c ，i na l l u s i o nt ot h ec o o r d i n a t o r sb l o c k i n g ，f o rt h e p u r p o s eo fi m p r o v i n gt h es e l e c t i o no ft h en e we f f i c i e n c yc o o r d i n a t o r ；t h i sp a p e r a m e l i o r a t e st h et h r e e p h a s ec o m m i tp r o t o c o la n dp u t sf o r w a r dt w on e wc o o r d i n a t o r s e l e c t i o na l g o r i t h m s ：t h ec o u n t e rs e l e c t i o na l g o r i t h ma n dt h e 厂忍s e l e c t i o na l g o r i t h m a tt h es a m et i m e ，t h i sp a p e ra n a l y z e st h ea d v a n t a g e sa n dd i s a d v a n t a g e so ft h e s et w o a l g o r i t h m s f i n a l l y , t h i sp a p e ra n a l y z e st h ef a i l u r eo ft h ed i s t r i b u t e dd a t a b a s es y s t e ma n dg i v e s ac o m m o nr e c o v e r ys t r a t e g y a n di td e s c r i b e sh o wt h en e wc o o r d i n a t o rt os u p e r s e d et h e o l dc o o r d i n a t o r w o r ka f t e rt h ef a i l u r eo c c u r r i n g k e y w o r d s ：d i s t r i b u t e dd a t a b a s e ，t h r e e p h a s ec o m m i tp r o t o c o l ，c o o r d i n a t o rs e l e c t i o n a l g o r i t h m 学位论文独创性声明 本论文是我个人在导师指导下进行的研究工作及取得的研究成果。论文 中除了特别加以标注和致谢的地方外，不包含其他人或机构已经发表或撰写 过的研究成果。其他同志对本研究的启发和所做的贡献均已在论文中做了明 确的声明并表示了谢意。 论文作者签名：金多燕 日期：刊饥 i 学位论文知识产权权属声明 本人完全了解上海师范大学有关保留、使用学位论文的规定，即：学校 有权保留送交论文的复印件，允许论文被查阅和借阅；学校可以公布论文的 全部或部分内容，可以采用影印、缩印或其它手段保存论文。保密的论文在 解密后遵守此规定。 论文作者签名：名五嚣受 日期：知f o 工f 3 9 留叫 卑一u 侑m 上海师范大学硕十学位论文 绪论 第1 章绪论 分布式数据库兴起于2 0 世纪7 0 年代，繁荣于8 0 年代，而在9 0 年代分布式 数据库更以其特有的优势：分布性和开放性，重新获得了广大用户青睐，其应用 领域已从分布式计算、i n t e m e t 应用、数据仓库扩展到高校的数据复制。随着社会 的发展，许多应用程序和用户对分布式数据库系统的依赖同益加大，他们要求其 处理的事件是多样化的，包括大容量的数据。这样的应用可以是银行系统、航空 公司订票系统或者许多其他的联机信息系统。因此分布式数据库管理系统( 分布 式数据库) 除了提供高性能，还应有较高的可用性、可靠性和可维护性【l 】。 1 1 问题的提出及研究 1 1 1 问题提出 分布式数据库( d i s t r i b u t e dd a t a b a s e ，d d b ) 是指分布在计算机网络上的一组逻 辑相关的多个数据库的组合，网络中的每个站点逻辑上由单个计算机组合，因此， 对于分布式数据库需考虑两种事务：局部事务和全局事务。局部事务是指访问和 更新一个站点的事务，局部事务的操作与集中式数据库中的事务操作一样；全局 事务是访问和更新多个局部站点的事务，为了保证全局事务的原子性，则需要所 有站点的局部事务的执行保持一致，即所有站点要么全部执行事务，要么全部撤 销事务。 实际中应用最为广泛的原子提交协议有：两阶段提交协议和三阶段提交协议。 两阶段提交协议把本地事务的处理扩展到分布式事务中，解决了分布式事务提交 原子性的问题，同时两阶段提交协议的实现比较简单且可靠。但是两阶段提交协 议仍然存在一些固有的缺陷，即当系统中某个站点因本身问题或者通信线路的不 畅而长时间没有响应时，会导致整个事务部不能正常提交，这样会使整个系统陷 入阻塞状态。两阶段提交协议这个缺陷严重影响了分布式数据库系统的性能，及 其系统资源的利用率 6 j 。 针对两阶段提交协议易阻塞的缺点，提出了三阶段提交协议。三阶段提交协 议包括三个阶段：投票表决阶段、预提交阶段、决策三个阶段。即在预提交阶段， 只有协调者收到所有参与者的预提交确认消息后，才发送全局事务提交命令，否 则将撤销事务。因此三阶段提交协议是非阻塞的，但是由于三阶段提交协议多了 一个预提交的阶段，其网络通信量比较大，而且由于每次总要等待所有参与者的 确认消息，事务提交的效率受到系统中最慢提交站点的影响1 4 j 。 绪论上海师范大学硕七学位论文 1 1 2 研究意义 随着数据库技术和网络技术的迅速发展和日益普及，分布式数据库的应用越 来越广泛，对其他领域的应用越来越重要，如航空售票系统、银行系统、地理信 息系统、指挥控制系统等都是采用分布式数据库系统。在现在的网络环境下，为 了保证数据的独立性、安全性、完整性，对分布式数据库的研究更为重要，其中 对分布式事务的提交协议的研究一直以来都是重要内容。 一个性能良好分布式事务管理需考虑这几个方面：执行效率、并行性、可靠 性。分布式事务提交协议为了满足这几个方面，必须尽量做n - 减少站点发生阻 塞的概率、控制站点问报文交换的数量、站点故障恢复及重启的次数，减少事务 夭折的次数【_ 7 1 。但在现实中，这三个目标很难全部兼顾到，原因在于这三个目标之 问既相互联系又相互矛盾。因此，提高这三个目标的某一个或是某两个，对于分 布式数据库的整体效率以及分布式数据库的可靠性和可用性，有着很大的现实意 义。 1 2 国内外研究现状 分布式事务的处理是分布式数据库技术研究的热点问题，为了保证分布式事 务执行的原子性，各个站点上的局部事务就必须在执行的最终结果上保持一致， 即所有局部事务要么在所有站点上全部提交，要么都终止。目前主要的事务提交 协议有：两阶段提交协议( t w o p h a s ec o m m i t m e n tp r o t o c o l ，2 p c ) 和三阶段提交 协议( t h r e e p h a s ec o m m i t m e n tp r o t o c o l ，3 p c ) 。因为两阶段协议本身的一些缺陷， 即当局部站点出项故障或者是通信不畅时，事务不能正确提交( c o m m i t ) 、撤销 ( a b o r t ) 或者回滚( r o l lb a c k ) ，事务易于进入阻塞状态，这对分布式数据库的性 能有很大影响，以及减低了系统资源的利用率。本文主要研究三阶段提交协议。 1 2 1 三阶段协议现状 传统的三阶段提交协议( 3 p c ) 协议虽然解决了两阶段提交协议( 2 p c ) 的易 阻断的缺点，但是在三阶段提交协议中，参与者不仅需要保持与协调者之间的通 信、执行本地事务，而且还要在协调者发生阻塞时，推举出新的协调者，所以网 络通信量较大。因此如何减少网络通信量是改进三阶段提交协议的重要内容。现 有的三阶段提交协议有： 基于代理的3 p c 分布式事务提交协议( p 3 p c ) 基于心跳技术的三阶段提交协议( h b b 3 p c ) 基于冗余的3 p c 分布式事务提交协议( r 3 p c ) 2 上海师范大学硕十学位论文绪论 1 3 本文的研究内容 本文对目前常用的事务提交协议以及三阶段提交协议( p 3 p c ，h b b 3 p c ， r 3 p c ) 进行研究和分析：两阶段提交协议实现比较简单，但容易阻塞；传统三阶 段协议无阻塞，但是网络通信量比较大；新的三阶段提交协议虽然对协调者做了 某些调整，但没有说明在协调者发生阻塞后如何快速选择效率高的新协。 本文的创新点： 1 在r 3 p c 的基础上，对从协调者队列做了某些改进，使之更好的为提高事 务的执行效率和可靠性服务； 2 提出了两种新协调者选择算法，使之在协调者阻塞后能快速选出效率高 的协调者； 最后分析了改进后的协议及算法的优缺点。本文的主要研究内容具体描述如 下： 1 根据分布式数据库和事务处理的特点，分析了事务提交协议的工作原理 ( 一阶段提交协议、两阶段提交协议和三阶段提交协议) ，并分析了它们 各自的优缺点，对现有的三阶段提交协议方法进行分析( 包括：p 3 p c ， h b b 3 p c ，r 3 p c ) 。并在r 3 p c 的基础上，对其候选协调者队列进行改进， 使之不再是传统意义上的冗余后备协调者队列； 2 在协调者阻塞后，需要系统尽快在后备协调者队列中选出新的协调者。 本文根据这列特殊的后备协调队列的特点，以及数据包自身的特点，提 出了两种新的协调者选择算法：计数器选择算法和t t l 选择算法； 3 对改进后的协议以及新协调者选择算法进行研究，分析了这两种算法的 优缺点分析了分布式数据库故障的类型及恢复技术，并介绍了在协调者 阻塞后，新协调者如何接替工作。 4 分析了分布式数据库中常见的故障类型及恢复技术，并介绍了在协调者 阻塞后，新协调者如何接替原来协调者的工作。 1 4 文章的结构 本文的文章结构如下： 第一章绪论，阐述了传统三阶段提交协议的存在的问题，并指出其改进 的研究意义。分析了目前国内三阶段提交协议的研究现状，针对传统三阶 段提交协议所存在的缺陷提出了本文的研究内容。 第二章分布式数据库的基本概述。本章简要介绍了分布式数据库、分布 式数据库管理系统和分布式事务的相关知识，以及对现有的事务提交协议 作了简要的介绍。 绪论 上海师范大学硕士学位论文 4 第三章是对改进后的三阶段提交协议进行详述。包括传统三阶段提交协议 的改进；协调者阻塞后如何快速选择效率高的新协调者算法的改进，提出 两种协调者选择算法：计数器选择算法和t t l 选择算法；并分析了这两 种算法的优缺点。 第四章着重介绍了故障恢复的类型和有关的故障恢复技术，并介绍了在协 调者阻塞后，新协调者如何接替工作。 第五章是对全文工作的总结，指出并分析了在三阶段提交协议的改进工作 中尚不完善的部分，并对以后的后续工作进行了展望。 上海师范大学硕士学位论文现有事务提交协议 第2 章现有事务提交协议 近年来，随着i n t e r n e t 的普及和企业规模的不断扩大，分布式数据库应用的范 围越来越广，如何保证分布式事务在各个站点上正确的调度执行，显得越来越重 要。 2 1 分布式数据库的有关概念 分布式数据库( d i s t r i b u t e dd a t a b a s e ，d d b ) 是一组逻辑相关的分布在计算机网 络上的多个数据库的组合，网络中的每个站点逻辑上由单个计算机组合，位于站 点( s i t e ) 上的数据库被称为局部数据库。这个定义强调了分布性和逻辑整体性这 两点。 分布式数据库管理系统( d i s t r i b u t e dd a t a b a s em a n a g e m e n ts y s t e m ，d d b m s ) 是 管理分布式数据库并使之对用户分布透明的软件系统；d d b 和它的d d b m s 一起 被称为分布式数据库系统( d d bs y s t e m ，d d b s ) ，有时被称为分布式数据库( 如 图2 1 ，分布式数据库的结构) 。一个典型的分布式数据库系统( d d b s ) 包括处理 单元( 节点) ，通信链路( 边) ，内存单位，数据库和程序。这些资源通过通信网 络连接，并显示信息流如何通过通信网络在各个节点间通信。一些节点上的程序 可以运行使用其他节点的数据库。 2 2 分布式数据库的分类 图2 1d d b s 示意图 分布式数据库按不同的分类方法，可分为多种类型。根据节点是否采用相同 的数据库系统，可将分布式数据库分为：同构分布式数据库( h o m o g e n e o u s 5 现有事务提交协议上海师范大学硕士学位论文 d i s t r i b u t e dd a t a b a s e ) 和异构分布式数据库( h e t e r o g e n e o u sd i s t r i b u t e dd a t a b a s e ) 。 在同构分布式数据库中，所有的站点都使用共同的数据库管理系统软件，它 们之间不仅相互了解，而且合作处理用户的需求。在这样的系统中，本地的站点 放弃了作为其自治权一部分的更改模式或者数据库管理系统软件的权利。为了使 得事务处理能在多个站点间进行，数据库管理系统软件还必须和其他站点合作来 交换事务的信息。相反，在异构分布式数据库中，不同的站点有不同的模式和使 用不同的数据库管理软件。站点之间可能彼此并不了解，在事务处理过程中，仅 仅为合作提供有限的功能。模式的差别经常是查询处理中的主要问题，软件的差 别称为访问多站点事务处理的障碍 2 1 。 在本文中，主要关注同构分布式数据库。 2 3 分布式数据库系统的特点 随着网络技术的发展，以及用户需求不断增加，集中式数据库系统已不能满 足人们需要求。因此，根据人们的需求将不同站点上的集中数据库系统通过网络 连接成的一个完整的、全局的大型数据库系统一分布式数据库系统。但不是简单 的通过网络连接，与集中式数据库系统相比较分布式数据库系统具有自己的性质 和特征【z j 。 1 提高了系统的可靠性。分布式数据库系统是由位于不同站点上的集中式 数据库通过网络连接而成的，因此，除了要访问的站点发生故障时，否 则其他某个局部站点发生故障时，并不影响正常工作。这样提高了整个 系统的可靠性。 2 适当增加数据冗余度。在集中式数据库系统中，尽量减少冗余度是系统 的目标之一。但是在分布式数据库中，增加数据冗余度可方便检索，提 高了系统的查询速度、可用性和可靠性。 3 数据独立性。在分布式数据库中，数据独立性除了包括数据的逻辑独立 性和数据的物理独立性，还包括数据分布独立性( 也成为分布透明性) ， 即指使用户不必关心数据的逻辑分片，不必关心数据物理位置分布的细 节，也不必关心重复副本( 冗余数据) 一致性问题，同时也不必关心局 部站点上数据库支持哪种数据模型【2 l 。 4 集中与自治相结合的控制结。由于分布式数据库系统的组成特点，所以 对数据控制也存在两种控制机制：局部站点可以独立管理本站点的数据 库，具有自治功能；而对于如何协调各个局部站点工作，又需要分布式 数据库系统具有集中控制的能力。至于那种控制程度高，要看具体的环 境。 6 上海师范大学硕十学位论文现有事务提交协议 2 4 分布式事务 2 4 1 集中式事务 所谓集中式事务是相对分布式事务而言的，指用户定义的对一个数据库的一 组操作序列，可能包括许多计算任务，这些操作要么全不做，要么全不做，是一 个不可分割的工作单位，事务是数据库的逻辑工作单位。事务具有四个特性，也 称为a c i d 特性： 1 原子性( a t o m i c i t y ) ，也成为全或无特性，是指事务要么成功提交，即事 务中操作序列全部；要么失败，即事务中式操作序列至少有一个没有成 功执行。 2 一致性( c o n s i s t e n c y ) ，是指事务的执行并不违反访问的共享对象的完整 性约束。即事务执行的结果必须使数据库从一个一致性的状态转到另一 个一致性的状态。因此，只有当数据库只包含成功提交事务的结果时， 才能说数据库处于一致性状态中。 3 易隔离性( i s o l a t i o n ) ，是指事务执行的中间过程对于其他并发事务是不 可见的，并发执行的事务之间不能相互干扰。事务的隔离性已被串行化 理论的证实。 4 持续性( d u r a b i l i t y ) ，也称为永久性( p e r m a n e n c e ) ，是指事务提交的更 新是永久性的。一个事务一旦提交后，接下来的其他操作或者故障都不 应该对其执行的结果有任何影响。 一个简单的事务执行过程如下： b e g i nt r a n s a c t i o n s q l 语句 i f s q l 语句都成功执行 c o m m i tt r a n s a c t i o n e l s e r o l l b a c kt r a n s a c t i o n 2 4 2 分布式事务 由分布式数据库( d d b ) 的定义：一组分布在算机网络上的逻辑相关的计的 多个数据库的组合，网络中的每个站点逻辑上由单个计算机组合，可知分布式事 务应包含两种事务，即局部事务( l o c a lt r a n s a c t i o n ) 和全局事务( g l o b a l t r a n s a c t i o n ) 。局部事务是指访问和更新一个站点的事务，且局部事务的操作和集 中式事务的操作一样，具有a c i d 特性；全局事务是访问和更新多个局部站点的 事务，对于全局事务的操作，要保证其a c i d 特性的任务可能复杂的多，因为可 7 现有事务提交协议上海师范大学硕十学位论文 能有多个站点同时对数据库进行更新操作。只有全局事务中的各个局部站点都完 成操作时，全局事务才能正确提交，所以其中一个站点的故障或者通信线路的故 障，都有可能破坏其a c i d 特性。 因此，在分布式数据库中，事务的执行被分为若干操作序列，每个序列称之 为个子事务，子事务以每个局部站点为基础。只有当所有局部站点上的子事务都 正确的调度、执行，并正常结束、提交后，分布式事务才算执行成功。通常会有 一个站点作为所有事务的协调者，负责将任务分配到各个站点上，同时对于用户 来说，任务的分配是透明的。其他参与事务执行的站点统一称为参与者站点，事 务的协调者和参与者按照一定的协议来进行协调执行，从而保证了数据和数据库 的一致性。从上面可以看出，分布式事务还具有不同于集中式事务的特剧4 j ： 1 协调性，分布式事务在执行时被分成若干个子事务，为了保证事务执行 的原子性及数据库的一致性，各个子事务之间需协调执行。因此在分布 式事务执行时，必须指定至少一个局部站点作为协调站点来协调各个子 事务的调度，并决定事务的提交或夭折，并保证分布式事务的a c i d 特 性。 2 通信性，在分布式事务中，除了保证局部站点的事务正确执行提交外， 还需要与其他的局部站点进行通信。协调站点需协调其他站点的执行， 而参与站点需等待协调站点的命令，以正确执行事务。因此，与集中式 数据库相比较，分布式事务无论是其组成，还是执行方式都要复杂的多。 3 通信消息的控制，在分布式数据库系统中，除了要控制数据外，还要加 强对通信消息的控制，由于分布式数据库系统的特点，分布式事务不仅 有数据操作，而且各个局部站点间( 主要是协调站点和参与站点间的通 信) 还需要通过网络来相互通信，这样网络上就产生大量通信消息。因 此如何减少通信消息的个数也是分布式数据库管理的一个重要目标。 2 5 现有的分布式事务提交协议 在集中式数据库中，事务的执行必须保证其原子性，即事务所要执行的操作 要么全部提交，要不全部撤销或回滚。而在分布式数据库系统中，有两种事务， 一个是涉及多个站点数据操作的全局事务和只涉及一个站点操作的局部事务。所 以在分布式数据库系统中，把一个全局事务可看成是由不同站点上的若干局部事 务组成。因此，分布式事务的原子性是：组成全局事务的局部事务要么一致地全 部提交，要么一致的全部撤销或者回滚。现有的事务提交协议如下： 2 5 1 二阶段事务提交协议 为了确保分布式数据库中事务执行的原子性，事务中的参与者必须协调好它 8 上海师范大学硕十学位论文现有事务提交协议 们的操作，以便要么全部撤销事务要么全部提交事务。这个可以通过原子提交协 议( a t o m i cc o m m i tp r o t o c o l ，a c p ) 来完成。其中最常用的原子提交协议是两阶 段提交协议。 两阶段协议( 2 p h a s e c o m m i t m e n tp r o t o c o l ，简称2 p c ) ，两阶段提交包括两个 阶段：投票阶段( 准备阶段) 和决策阶段( 如：图3 ，简单的两阶段提交处理过程) 。 并且把一个分布式事务的事务管理分为两类：一是协调者，其他的是参与者。协 调者负责对事务操作作最后决定：提交( c o m m i t ) 或者撤销( a b o r t ) 。所有参与者 负责在各自局部站点上管理相应子事务操作的执行。在投票阶段，决定是否所有 参与者都提交了事务；在决策阶段，协调者决定事务要么全部提交要么全部撤销， 并且所有的参与者响应这个决定。为了提供容错性，协调者和参与者的站点把这 一过程写入日志中。两阶段提交协议的内容是【7 j ： 投票阶段：在投票阶段，协调者通过发送“准备”消息，请求所有的参与者 同意事务的操作，以确保数据的永久性。当参与者收到“准备消息时，如果参 与者准备提交事务，那么它投票“是 。如果参与者的状态时准备提交，就可以保 证该事务可以进行本地提交并将此操作在日志记录中写入，这样在站点失败后， 可根据日志来恢复事务的执行。同时如果参与者已经投票“是，将不再有单方 面的撤销或提交这个事务的权利，并且参与者将被认为是阻塞，直到收到协调者 发过来的最终决策命令。 如果某个参与者还没有做好提交事务的准备，也就是说，参与者不能保证正 确提交事务，则必须中止该事务的执行，并不发表任何表决。 决策阶段：如果协调者已经收到所有参与者肯定的投票( 如，“是”的投票) ， 则提交事务并将提交日志记录写入日志文件中。日志文件可以保证在协调者失败 的情况下，协调者重新启动时，仍然可以成功地执行事务。如果任何一个参与者 投了否定的票( 如，“不”的投票) ，协调者将决定撤销事务并在日志文件中写入 该操作。在协调者已经将提交( 或撤销) 日志记录写入后，协调者发一个“提交 ( 或者“撤销 ) 消息给所有投票是的参与者。 当某个参与者接收到最终决策时，将把这个提交( 或撤销) 决策记录写入日 志文件中以表明事务已经提交( 或撤销) ，并释放该事物所需要的所有资源并返回 一个应答消息( 命名为“a c k 消息) 给协调者。协调者接收到所有参与者发送的 应答消息后，丢弃任何保存在主存上的关于该事务的信息，并“忘掉”该事务。 从上面的描述可以得出，在一般处理过程中，n 个站点在执行提交或者撤销一 个事物时的花费是一样的。2 p c 的日志复杂性总共是2 n 1 ，及消息复杂性为3 ( n 1 ) 。 2 p c 的时间复杂度是3r o u n d s ，第一个r o u n d 用于发送“准备”请求，第二个r o u n d 用于发送投票，最后一个r o u n d 用于发送决策消息。这里的复杂度并不包括消息、 n 1 个应答消息的时间复杂度以及它们之间的通信时间，因为这些消息是用来在事 9 现有事务提交协议上海师范大学硕十学何论文 务已经提交或是撤消后，记录目的的。 c o o r d i n a t o r ， p a r t i c i p a n t v o t i n g p h a s e y 竺 f o r c ew r i t e 。 7 p r e p a r c dr e c o r d 、一 f o r c e w r i t e d e c i s i o nr e c o r d 芝竺_ f o r c e w r i t e d e c i s i o n d e c i s i o nr e c o r d p h a s e w r i t cl i o n f o r c e d a c k 一e n dr e c o r d ， 图2 - 2 两阶段提交过程 可以看出，在两阶段协议中，当系统发生故障时，各场地采用的是完全同步 的方法来保证数据库的一致性，称为紧密一致性( t i g h tc o n s i s t e n c y ) 。这中方法虽 然可以保证在任何时刻整个分布式数据库系统的一致性和原子性，但是从实际应 用的角度来说，它的缺陷也是非常明显的。有两阶段提交提议本身特点决定了其 有两个缺点： 1 ) 阻塞性( b l o c k i n g ) ，两阶段协议在协调者失败时就会进入阻塞状态，同 时参与者也会处于不确定的状态；并且参与者会一直占用资源直到收到 协调者恢复后发送的下一个消息。 2 ) 状态不一致性( s t a t ei n e o n s i s t e n e y ) ，在协调者发生阻塞时，参与者可能 出于提交状态，也可能出于撤销状态，称这个为状态的不一致。如果不 存在参与者失败，那么协调者在发送提交消息后进入提交状态。 2 5 2 一阶段事务提交协议 最近，一阶段提交协议又重新被人们考虑，典型的一阶段提交协议有i m p l i c i t y e s v o t e ( i y v ) 和c o o r d i n a t o rl o g ( c l ) 。与两阶段提交协议相比，一阶段提交协议， 通过减少阶段提交协议中的投票阶段，即两次通信，和一次日志写入来减少花费。 尽管一阶段提交协议的效率相比两阶段提交协议要好些，但是阶段提交协议忽 略了分布式系统中的事务执行。这个有两个方面的原因： 1 ) 一阶段提交协议能解决的实际问题还没有确定，而且有时认为一阶段提 交协议可能不能保证事务执行的原子性。 2 ) 一阶段提交协议协议的设计者在事务处理时做了大量的假设。例如，i w 和c l 都假设事务中的参加者外化了是日志记录，并严格按照两段锁 ( t w o p h a s el o c k i n g ) 的并发控制。这些假设在大多数现实的事务处理 1 0 上海师范大学硕十学位论文现有事务提交协议 系统中是不现实的【9 1 。 事实上，在如何保持事务执行的原子性的问题上，一阶段提交协议有着自己 独特的方法，我们称之为：独裁的原子提交。每个参与者都有一个初始值，提交 或者撤销，并且各个参与者之间达成初始值决定。因此，一阶段提交协议需满足 下列条件： 同意的协议：每个参与者的最终决定都是一样的； 同意的有效性：参与者的决定是初始值； 完整性：参与者在收到一个决定后，就不能更改它的决定了； 终止：如果所有的失败都恢复了，并且没有新的失败发生，所有的参与者 将最终达成一致决定。 一阶段提交协议不同于经典的原子提交问题，参与者不需要投票。参与者只 是有一个事物执行结果的一个初始值，而这个初始值决定于它们执行事务的操作。 然后，参与者执行提交协议以达成个一个共同的结果。例如，一个参与者已经成 功执行，且收到所有确认消息，并始终相信协调者的初始值是提交，但是参与者 的初始值却是撤销；反过来说，如果协议的协调者收到所有的参与者发送的确认 消息，且参与者的初始值是提交，但是协调者的初始值却是撤销。参与者也有可 能最终达成一个与初始值不同的决定。 通过减少对投票的需求，一阶段提交协议确实比两阶段提交协议的性能要好。 但是，一阶段提交协议是建立在参与者管理事务这个假设上的。假设在原子提交 协议( a c p ) 启动前每个操作是都得到确认，相反，恢复协议假设增加确认消息 的数量。 2 5 3 三阶段事务提交协议 三阶段协议( 3 p c ) 是在二阶段协议( 2 p c ) 的基础上提出的，针对两阶段提交协议 的缺点，三阶段提交协议有一个“预提交 阶段。三阶段协议有三个阶段：包括： 投票阶段、预提交阶段、提交阶段。3 p c 的基本思想为：三阶段提交协议中，在 投票表决阶段和决策之间增加一个“预提交 阶段。协调者发出预提交消息，在 等待所有参与者发的确认消息后，协调者再发送提交或是撤销的消息。3 p c 协议 的工作过程【1 4 1 ： 第一阶段：协调者发送“提交 消息给所有参与者，每个参与者根据自身 站点的情况进行回复，如果确定提交，就发送“o k ；否则发送“n o to k 。 只有所有的参与者投票“o k ”时，才进入第二阶段。果有部分参与者没 有投票“o k ，则一段时间后参与者将终止并释放其占用的资源。 第二阶段：协调者发送“准备提交消息给所有参与者，参与者收到消息 后，若已经准备好提交，则回复“a c k ”，若长时间没有收到某个参与者 现有事务提交协议 上海师范大学硕十学位论文 的回复，则认为该站点失败或超时。 第三阶段：协调者收到所有参与者的“a c k 消息后，发送提交消息。 图2 - 33 p c 中协调者和参与者的状态剧 当然三阶段提交协议也有本身的缺点： 1 只有当多个站点失败三阶段协议才是有问题的，例如，协调者正处于“预 提交状态且发送提交消息后就阻塞了，而参与者在接收消息之后或之 前也阻塞。所以，参与者进入撤销状态，但是根据协议，协调者进入提 交状态后，不管其是否阻塞或是接收到“a c k ”消息，因此，协调者在 没有接收到所有“a c k ”消息时就进入提交状态，参与者没有发送“a c k 消息就进入撤销状态。在这种情况下，协调者和参与者将因为各自的阻 塞而显示不同的状态。 2 网络通信量比较大，从理论上看，3 p c 是非阻断的，但是由于多了一个 预提交阶段，网络通信量要比两阶段提交协议大的多，由于每次都需等 待所有参与者的确认消息，因此事务提交的效率受到系统中最后提交的 站点的牵制。 在三阶段提交协议的这两个缺点中，第一个发生的可能性比较少，我们通常 考虑的是第二个缺点，即三阶段提交协议的网络通信量比较大，而对三阶段提交 协议的改进，也多从这个方面来考虑。 2 5 4 现有提交协议的性能比较 三阶段提交协议虽然改变了两阶段提交协议的易阻塞的缺点，但是其网络通 信量比较大，这两种协议的性能比较如表2 1 。 1 2 上海师范大学硕士学位论文 现有事务提交协议 表2 12 p c 和3 p c 性能比划1 0 】 协议提交时 夭折时 是否1 是否原子 类型阻断性性 消息 日志 消息日志 3 p c6 n3 n + 43 n + 1 3 n + 3 2是是 2 p c4 n 2 n + 14 n2 n + l否是 1 3 基于冗余的3 p c 协调者选择算法的改进上海师范大学硕士学位论文 第3 章基于冗余的3 p c 协调者选择算法的改进 两阶段提交协议技术虽然简单、使用较为可靠，但是由于本身的一些固有缺 点，如站点出现故障或者通信故障时，系统易于陷入阻塞状态，严重影响系统性 能和系统资源的利用率。同样三阶段提交协议虽然局部地解决了两阶段协议中易 阻塞问题得缺点，但是由于多了一个预提交阶段，网络通信量要比两阶段提交协 议大的多，由于每次都需等待所有参与者的确认消息，因此事务提交的效率受到 系统中最后提交的站点的牵制。下面对传统的3 p c 和现有的对3 p c 方法来分析。 3 1 三阶段提交协议的分析 3 1 1 传统三阶段提交协议的分析 由于在3 p c 中，参与者自身的工作有：1 ) 关注和保持与协调者之间通信；2 ) 执行本地事务；3 ) 在协调者发生阻塞时，推举出新的协调者。因此在3 p c 中，参 与者的工作比较多，且推选新协调者的效率低。 对参与者来说，其最主要的工作室执行本地事务。因此，为减少3 p c 协议的 通信量及提高其效率，可以从这二个方面着手： 1 ) 提高协调者和参与者的透明性，即对参与者来说只是知道存在协调者， 而不用关注协调者是阻塞还是正常通信，更不用关注如何与其通信。 2 ) 提高推选协调者算法的效率，即传统的3 p c 中，协调者是从参与者中产 生，由于参与者的数量可能比较大，协调者阻塞时，推举新的协调者的 效率比较低，因此减少候选协调者的数量和改进推选算法可以提高推选 效率。 文章主要从这两个方面来改进传统的3 p c 协议。 3 1 2 现有的三阶段提交协议的分析 传统的三阶段提交协议( 3 p c ) 协议虽然解决了两阶段提交协议( 2 p c ) 的易 阻断的缺点，但是传统的三阶段提交协议仍有自身的缺点。现有的三阶段提交协 议有： 1 ) 基于代理的3 p c 分布式事务提交协议( p 3 p c ) l l 列 p 3 p c 协议在传统的3 p c 提交协议的基础上，为了减低开销，增加了一个协 调者代理节点，并且使参与者相信代理协调者和协调者是样的，同时系统不推 选新的协调者，其结构图，如图3 1 。 1 4 上海师范大学硕十学位论文 基丁冗余的3 p c 协调者选择算法的改进 图3 lp 3 p c 协议结构图 p 3 p c 的工作原理：在正常情况下，参与者不直接与主协调者通信，而是将消 息发送给代理协调者。对于参与者来说，代理协调者就是主协调者，且在小于参 与者设定的超时时间前，代理协调者将产生的日志发送给主协调者。主协调者不 参加事务的指挥，主要负责将收到的日志重新建一个与代理协调者相同的数据库。 对于参与者来说，代理协调者和主协调者之间的通信时透明的，参与者只知道有 一个代理协调者存在，其他的与传统的3 p c 一样。 2 ) 基于心跳技术的三阶段提交协议( h b b 3 p c ) 【”】 所谓“心跳( h e a r tb e a t ) 技术，是指主协调者每间隔一定的时间发送消息给 协调者，这个消息称为心跳。h b b 3 p c 以传统3 p c 协议为基础，同时增加了冗余 的协调者，但是对于参与者来说，冗余的协调者是透明的。其结构图，如图3 2 。 图3 - 2h b b - 3 p c 协议结构图 h b b 3 p c 协议的工作原理：在事务开始时，系统中只有一个协调者，负责协 调参与者的工作，其功能与传统3 p c 协议中的协调者一样。同时，在系统中存在 一个后背后备队列- 从协调者队列，与协调者的功能相同，只是不发送任何命令 给参与者，且在任意时刻，从协调者和协调者的状态时一致的。而对于参与者来 说，它们不知道从协调者的存在，并且参与者相信，主协调者永远不会阻塞。从 基于冗余的3 p c 协调者选择算法的改进上海师范大学硕十学位论文 协调者通过“心跳 来感知主协调者是否阻塞。两个心跳之间的间隔称之为“心 跳间隔 ，其应远远小于传统3 p c 协议中的超时。如果从协调者在一定时间间隔后 没有收到主协调者的心跳，则认为主协调者阻塞了，同时立即提升自己为主协调 者，并接管原主协调者的工作，给参与者发送命令。对参与者说，主协调者与从 协调者之间的接替是透明的，且所有无论是主协调者还是从协调者被看成是一个 整体，参与者只需要相信协调者永远不会被阻塞。 3 ) 基于冗余的3 p c 分布式事务提交协议( r 3 p c ) i l 州 r 3 p c 协议是在传