（交通信息工程及控制专业论文）基于并行分层式链路分布式数据更新的协议及副本复制研究.pdf

西南交通大学博士研究生学位论文 第1 页 摘要 士 在分布式数据库领域j 分御式数据更新是极其重要的研究课题，因为数 据更新操作必须满足数据库的完整性、一致性、可靠性和稳定性要求。针对 分布式数据库的要求，分布式数据更新有强一致性和弱一致性之分，强一致 性的数据更新是通过分布式事务的协议进行，这个协议必须满足a c i d 特性； 弱一致性主要体现在数据副本复制上。 借鉴分布式数据库领域中众多专家、学者关于分伟式数据更新的相关研 究工作，取得了以下研究成果： 一提出并构造了满足强一致性及a c i d 特性的p 2 l 2 p c 协议 1 分布式数据库的传统连接结构具有各自优点的同时，它们有其无法 克服的问题，为了解决这些问题，应在链路补偿方面作一定研究，使链路生 成和形成多元化，为分布式数据更新提供更完善的连接结构，基于此目的建 立了并行分层式链路。并行分层式链路是在一个连接结构中，具有链路分层 的同时又有补偿的并行链路，最终目的是完善、优化地执行分布式数据更新。 2 目前已经提出许多分布式数据库提交协议，尽管这些协议都能保证 分布式事务a c i d 特性，但基本采用的是投票法的“一票一次性否决”规则。 本文采用投票法“一票多次性否决”规则，提出并构造了p 2 l 2 p c 协议，即 数据更新在并行分层式链路基础上，只有在一个参与者的一个子事务的所有 消息是提议撤消情况下，协调者才能确认该参与者是建议撤消。 3 按照分布式事务原则的要求，对p 2 l 2 p c 协议是否满足各个准确性准 则进行了证明。通过证明可知p 2 l 2 p c 协议在分布式数据更新时很好地保证 了分布式事务原子性，即维护了数据库的一致性。 4 通过记录日志次数、报文交换数量和事务失败率三个方面将2 l 2 p c 协议和其它协议进行了性能评价和比较。p 2 l 2 p c 协议通过适当提高日志操 作次数和报文发送次数来降低协议执行的失败率，表明p 2 l 2 p c 协议有其特 定的优点，尤其是p 2 l 2 p c 协议较高的成功率，使分布式数据更新事务的成 功得到保证。 5 对分布式数据更新时可能发生的故障进行了分类分析，并针对p 2 l 2 p c 协议设计了故障恢复协议和事务终结协议。故障的发生是破坏数据库完整性 和致性的主要原因，通过对分布式数据库系统故障的模糊性界定，使 第1 i 页西南交通大学博士研究生学位论文 p 2 l 2 p c 协议在故障恢复时，具有较高的可靠性；通过对故障发生在不同阶 段的终结请求分析，设计了p 2 l 2 p c 协议的终结协议，从终结分析和终结协 议的设计可以看出，p 2 l 2 p c 协议消除分布式事务被挂起现象，即尽可能不 让事务阻断发生。 二弱一致性的副本更新问题研究 1 基于并行分层式链路对传统的对等复制进行了改进，提出了优先级 约束的衍生对等复制策略，同时推断出衍生对等复制的可行性链路；结合对 等复制和优先级约束原则设计了优先级约束衍生对等复制算法，为副本复制 的并发控制奠定了一定基础。 2 对分布式数据库系统发展过程中出现的多分割副本问题进行了系统 的分析，同时对多分割副本传播复制提出了三种策略：单次传播复制策略、 二次传播吞吐复制策略和并行二次传播吞吐复制策略。三种策略的基本思想 是将多分割副本分解再吞吐传播，并还原复制，主要解决副本数据不重复传 播问题、未修改数据不进行传播问题及并行链路中多分割副本复制问题。 三针对p 2 l 2 p c 协议及副本复制问题进行并发控制研究 1 基于时效期对p 2 l 2 p c 协议的并发控制问题进行了分析，并建立了 p 2 l 2 p c 协议的时效锁并发控制方式。 2 针对对等复制过程中并发情况提出了中断策略和优先级准封锁策略， 同时对多分割副本复制过程中的并发控制问题进行了分类分析，并提出了多 分割副本复制的并发控制算法。 四结合快速发展的分布式应用技术，对本文的理论研究内容进行了技术实 现方面的可行性设计，从而提出了分布式数据库接力访问模型。 1 分布式数据库接力访问模型的核心思想是将多层体系结构的分布式 应用技术应用于分布式数据库访问上。 2 分布式数据库接力访问模型功能特点是将请求异地数据和异地数据 请求都以消息机制进行推送，解决在访问分布式数据库情况下网络开销过 大、数据库互连复杂、数据更新时保证一致性困难等问题。 关键词：2 p c 协议：p 2 l 2 p c 协议：副本复制； 分布式数据更新；分布式数据库系统 a bs t r a c t i nt h ef i e l do fd d b s f d i s t r i b u t e dd a t a b a s es y s t e m ) ，d i s t r i b u t e dd a t a u p d a t i n gi s a v e r yi m p o r t a n t r e s e a r c h f u l p r o b l e m ，b e c a u s e d a t a u p d a t i n g m u s tf u l f i l i n t e g r a l i t y ，c o h e r e n c e ，r e l i a b i l i t ya n ds t a b i l i t yo f t h ed a t a b a s e f r o mt h er e q u i r i n g o ft h ed d b s ，d i s t r i b u t e dd a t au p d a t i n gi sd i v i d e di n t os t r o n gc o h e r e n c ea n d w e a kc o h e r e n c e i ns t r o n gc o h e r e n c e ，d a t au p d a t i n gi sd o n eb yt h ep r o t o c o lo f d i s t r i b u t e dt r a n s a c t i o n ，t h i sp r o t o c o lm u s tf u l f i la c i d w e a kc o h e r e n c ea i ma t c o p yr e p l i c a t i o n u s ef o rr e f e r e n c et h em a n y r e s e a r c ho fo t h e re x p e r ta n ds c h o l a r ， t h ef o l l o w i n gr e s e a r c hr e s u l t sa r ea c h i e v e d 1 p 2 l 2 p cp r o t o c o lf u l f i l l i n gs t r o n gc o h e r e n e ea n da c i di sr e s e a r c h e d ( a ) t h et r a d i t i o n a ll i n ks t r u c t u r eo fd d b sh a si t s e l fs t r o n gc h a r a c t e r i s t i c ，b u t a l s oi th a si n c o n t e s t a b l es h o r t c o m i n g ，s os h o u l dt od or e s e a r c hi nr e d e e m i n gl i n k ， t o p r o v i dp e r f e c t l i n kf o rd i s t r i b u t e dd a t au p d a t i n g ，b a s eo nt h i s p u r p o s e t o b u i l d i n gp a r a l l e l - l a y e r e d l i n k ( b ) n o w , m a n yd d b sp r o t o c o l h a v eb e e nr e s e a r c h e d ，b u tt h e s e p r o t o c o l a d o p t e db a s i c a l l y “o n e v o t eo n e o f fv e t o ”o fv o t i n gm e a n s p 2 l 2 p cp r o t o c o l a d o p t “o n ev o t et i m ea f t e rt i m ev e t o ”r u l e d i s t r i b u t e dd a t au p d a t i n gi sd o n eb y p a r a l l e l - l a y e r e d l i n k ，o n l yw h e na l lm e s s a g eo f o n ep a r t i c i p a t o rs u b t r a n s a c t i o n r e p o r ta b o r t ，c o o r d i n a t o rc o n f i r mt h a tt h i sp a r t i c i p a t o rr e q u e s ta b o r t ( c ) b yp r o v i n g ，w h e nd i s t r i b u t e dd a t a i s u p d a t e d ，p 2 l 2 p cp r o t o c o l a s s u r e p r i m e l yt h e a t o m i co fd i s t r i b u t e d t r a n s a c t i o n ，a l s o a s s u r et h ec o h e r e n c eo f d a t a b a s ei nt i m e ( d ) f r o mr e c o r d i n gl o gc o u n t ，c o m m u t a t i v em e s s a g ea m o u n t ，t r a n s a c t i o n a b o r t e d r a t i o ，p 2 l 2 p cp r o t o c o l i s c o m p a r e d w i t ho t h e r p r o t o c 0 1 p 2 l 2 p c p r o t o c o lr e d u c ea b o r t e dr a t i ob ye n h a n c i n gm o d e r a t e l yl o gm a n i p u l a t i v ec o u n t a n dm e s s a g e s e n d i n gc o u n t ，t h i se x p l a i nt h a tp r e f e r a b l e s u c c e s s f u lr a t i oo f p 2 l 2 p c p r o t o c o lm a k e ag o o de n s u r i n gi nd i s t r i b u t e dd a t au p d a t i n g ( e ) p o s s i b l ew e n tw r o n gi sa n a l y z e dc l a s s i f y l yw h e nd i s t r i b u t e dd a t au p d a t i n g ， s of a i l u r er e s u m p t i v ep r o t o c o la n dt e r m i n a t i v ep r o t o c o la r cd e v i s e dt op 2 l 2 p c p r o t o c 0 1 t h eo c c u r r i n go ff a i l u r ei s m o s tc a u s ed e s t r o y i n gt h ei n t e g r a l i t ya n d c o h e r e n c eo fd d b s ，b yd i f f e r e n t i a t i n ga b s o l u t e l yt h ef a i l u r e ，t om a k ep 2 l 2 p c 第lv 页西南交通大学博士研究生学位论文 p r o t o c o l h a sb e t t e r r e l i a b i l i t y i n r e v e r t t i n gf a i l u r e b ya n a l y z i n g t e r m i n a t i v e r e q u e s ti nd i f f e r e n tf a i l u r ep h a s e ，t h et e r m i n a t i v ep r o t o c o li s d e v i s e d i ti sk n o w t h a tp 2 l 2 p c p r o t o c o le l i m i n a t e st h ei n t e r d i c t t e dt r a n s a c t i o n 2 c o p yr e p l i c a t i o ni nw e a k c o h e r e n c e ( a ) b a s e o i l p a r a l l e l l a y e r e d l i n k ，t o a m e l i o r a t et r a d i t i o n a l p e e r t o p e e r r e p l i c a t i o n ，r a i s ep r i r e s t r i c td e r i v a t i v e p e e r t o p e e rr e p l i c a t i o n ，a n d d e d u c e f e a s i b i l i t yr e p r o d u c t i v el i n k p e e rt op e e rr e p l i c a t i o na n dp r ir e s t r i c tr u l ec o m b i n e t of o r mp r ir e s t r i c td e r i v a t i v ep e e rt op e e rr e p l i c a t i o na l g o r i t h m ( b ) b ya n a l y z i n gd e t a i l e d l y m u l t i i n t e r s e c t e d c o p y , t h r e e m e t h o d so f r e p l i c a t i o n a r ed e v i s e d ：o n c e s p r e a dr e p l i c a t i o nm e t h o d ，t w i s p r e a dt h r u p u t r e p l i c a t i o n m e t h o da n d p a r a l l e lt w i s p r e a dt h r u p u tr e p l i c a t i o n m e t h o d t h e i r e s s e n t i a lt h i n k i n gi st h a tm u l t i i n t e r s e c t e dc o p yi sd i s a s s e m b l e d ，s p r e a d ，r e v e r t e d ， a n dr e p l i c a t i o n ，t h e ym a k et h a td a t ai s s p r e a du n r e p e a t e d l y ，d a t au n a m e n d e di s n o ts p r e a d ，a n dh o wt od a t as p r e a da n d r e p l i c a t ei np a r a l l e ll i n k 3 c o n c u r r e n c y c o n t r o lo fp 2 l 2 p ca n dm u l t i - i n t e r s e c t e dc o p y r e p l i c a t i o n ( a ) b a s eo nt i m el i m i t ，t oa n a l y z ec o n c u r r e n c yc o n t r o lo fp 2 l 2 p cp r o t o c o l ， a n du p b u i l dm e t h o do ft i m el i m i tl o c kc o n c u r r e n c yc o n t r o lo fp 2 l 2 p cp r o t o c 0 1 ( b ) i n t e r r u p t i v em e t h o da n dp r e l o c km e t h o d a r ep u tf o r w a r d ，a n db ya n a l y z i n g d e t a i l e d l yc o n c u r r e n c yc o n t r o lo fm u l t i i n t e r s e c t e dc o p yr e p l i c a t i o n ，t od e v i s e a l g o r i t h mo fc o n c u r r e n c yc o n t r o lo f m u l t i i n t e r s e c t e dc o p y 4 c o m b i n i n gr a p i d l yd e v e l o p i n gd i s t r i b u t e da p p l i e dt e c h n i q u e ，i nt e c h n i c a l r e a l i z i n g ，t od of e a s i b i l i t yd e s i g nf o rt h e o r e t i cp a r tr e s e a r c h e d ，a n dt h e b a t o nm o d e lo fd i s t r i b u t e dd a t a b a s ei sp u tf o r w a r d t h e p r i n c i p l ea n dt e c h n o l o g yo f b a t o nm o d e la r et h a td i s t r i b u t e da p p l i c a t i o ni s a p p l i e do i ld i s t r i b u t e dd a t a b a s e i t l sf u n c t i o ni s t h a tr e q u e s te c d e m i cd a t ao r e c d e m i cd a t a r e q u e s t i s p u s h e db ym e s s a g e i t c a ns o l v em u c hp r o b l e mi n g r e a t n e s sb u r d e no fn e t w o r k ，c o m p l e xc o n n e c t i n go fd a t a b a s e ，d a t ac o n s i s t i n g e t c k e y w o r d s ：2 p c p r o t o c o l ，p 2 l 2 p cp r o t o c o l ，c o p yr e p l i c a t i o n d i s t r i b u t e dd a t au pdating，ddbs 西南交通大学 学位论文版权使用授权书 本学位论文作者完全了解学校有关保留、使用学位论文的规定， 同意学校保留并向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅。本人授权西南交通大学可以将本学位 论文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或扫描等复制手段保存和汇编本学位论文。 本学位论文属于 l 、保密口，在年解密后适用本授权书； 2 、不保密囤，适用本授权书。 ( 请在以上方框、内打“”) 学位论文作者签名：荔i 多目甏 指导教师签名：镎坳 日期：”砰年f 肚日 日期：聊毕年，胡；日 西南交通大学 学位论文创新性声明 本人郑重声明：所呈交的学位论文，是本人在导师指导下独立进行研究工 作所取得的成果。除文中已经注明引用的内容外，本论文不包含任何其他个人 或集体已经发表或撰写过的研究成果。对本文的研究做出贡献的个人和集体， 均已在文中作了明确的说明。本人完全意识到本声明的法律结果由本人承担。 本学位论文的主要创新点如下： 1 基于对分布式数据库系统传统连接结构的分析，构造了并行分层式连 接结构( 第二章第二节) ：同时结合2 p c 协议，提出了并行分层式链路两阶段 提交协议( 第二章第三节) ；另外针对并行分层式链路两阶段提交踯议设计了 浚协议的终结协议( 第二章第五节) 。 2 基于并行分层式链路对传统的对等复制进行了改进，结合对等复制和 优先级约束原则提出了优先级约束衍生对等复制策略，同时设计了优先级约束 衍生对等复制算法( 第三章第二节) 。 3 对多分割副本进行了系统的分析，并针对多分割副本复制传播提出了 单次传播复制策略、二次传播吞吐复制策略和并行二次传播吞吐复制策略，同 时针对三种策略设计了多分割副本复制传播的算法( 第三章第三节) 。 4 对本文理论研究内容进行了技术实现方面的可行性设计，从而提出了 分布式数据库接力访问模型( 第五章第四节) 。 学位论文作者签名： 日期：叼￥年，月 日 西南交通大学博士研究生学位论文 第1 页 第1 章绪论 由于计算机网络技术的发展及数据库应用需求的拓展，使分布式数据 库系统( d i s t r i b u t e dd a t a b a s es y s t e m ，简称d d b s ) 应运而生，并且成为 计算机技术尤其是数据库领域最为活跃的研究方向之一：分布式数据库系统 是数据库技术与计算机网络相互渗透和有机结合的产物，它主要研究在计算 机网络中如何进行数据的分布和处理，通俗地说，d d b s 是地理上( 或物理 上) 分散而逻辑上集中的数据库系统”。”“1 3 2 。 d d b s 通过计算机网络将地理位置分散而管理和控制需要不同程度集中 的逻辑单元( 通常是集中式数据库系统) 连接起来，共同组成一个统一的数 据库系统，可以说集中式数据库系统的日益完善和计算机网络不断发展，再 加上社会领域对信息时代的数据共享和互连等需求为d d b s 的产生、发展及 应用提供了前提条件。 1 1 分布式数据库系统概述 1 1 1 分布式数据库系统的产生与发展 ( 1 ) 分布式数据库系统的诞生 分布式数据库系统的诞生并不是偶然的，它和计算机科学中其它技术一 样受到两个方面的推动：一方面是应用需求的变化，另一方面是计算机其它 技术的发展，尤其是数据库技术和网络技术的迅猛发展。 在应用需求方面，如在一些拥有地理分散的子公司的企业中，地理位置 的分散造成了业务数据的分散，总公司与各分公司处于不同的城市或城市中 的各个地区，在业务上它们除了处理各自的数据，也需要彼此之问进行数据 的交换和处理，如何处理分散的数据和集中的管理，曾是困绕数据库开发者 多年的难题，分布式数据库系统技术的出现为解决这个问题提供了可能，所 以那些在地域上分散而在管理上需要相对集中控制的大集团、大机关、大企 业如全球性或全国性的公司、跨地区连锁店管理、保险业、交通运输业如民 航定票系统及铁路定票系统等、军事上如情报系统及决策指挥系统等、旅游 业、银行汇兑等等，这些组织和行业的应用都涉及到地理上分散的业务管理， 这就需要一种系统既有各部门的局部控制和分散管理，同时也要有这个组织 第2 页西南交通大学博士研究生学位论文 和行业的全局控制和统一的协调管理，这种统一的协调管理要求相关部门的 信息既能共享，又能统一管理。 随着计算机网络技术的发展以及地理上分散的部门、公司、厂商对于数 据库应用的需求。数据库技术从单机扩展至网络，对数据的收集、存储、处 理和传播由集中式走向分布式、从封闭走向开放。针对这些需求，集中式数 据库系统已经无法提供合适及优良的支持，这就迫切需要相关部门的数据信 息通过网络连接起来，形成一个分布式数据库系统，或重新构造一个既能满 足单个部门独立处理又适合全局范围应用的分布式数据库系统。 另一方面是计算机功能增强、通讯网络飞猛发展及集中式数据库系统的 日趋完善，为数据的分散、分布提供了成熟的环境，这也为分布式数据库系 统的研究、研制及实现提供了必要的条件。 ( 2 ) 分布式数据库系统的发展 分布式数据库系统在应用需求和技术迅猛发展背景下，各个先进国家均 不约而同地抓住分布式数据库系统新的发展方向，投巨资进行研究和开发。 在系统的开发上，典型的如美国计算机公司( c c a ) 研制的s d d l 系统和 d d m 系统l l “l ，美国加利福尼亚大学的分布式i n g r e s 系统n3 ，美国i b m 公司 的r $ ( r = r ，r r ，r r r ，表示任意数目的r ) 系统和s y s t e mr 系统“2 “”“”“， 法国的s i r i u s 计划，德国s t u t t g r t 大学研制的p o r e l 系统 2 “”1 等等： 在国内，一些科研单位和高校先后建立和实现几个各具特色的分布式数据库 系统，如由中国科学院数学研究所设计，由该所和上海科学技术大学、华东 师范大学合作实现的c - p o r e l 系统，武汉大学研制的w d d b s 承lw o o d d b s 系统， 东北大学研制的d m u f o 系统，东南大学计算机系开发的s u n d d b 系统以及中 固人民大学与知识工程研究所研制的d o s s e l s 等等“。t 3 2 ，这些都对我国分 布式数据库系统的技术理论研究和应用起到积极的推动作用，尤其是2 0 0 1 年1 2 月信息产业部对华中理工大学和武汉华工达梦数据库有限公司联合研 究开发的d m 3 系统通过鉴定，标志着我国在分布式数据库系统的研究和开发 上又有了新的突破和发展 t 3 2 。 在理论研究上，每年数次大型国际学术会议和各种学术研讨会的交流以 及若干先驱分布式数据库系统的研制，都使分布式数据库系统的理论和技术 不断丰富，尤其是近年来网格技术的提出拓展了分布式数据库系统的研究 o “”1 “”“”“；目前四大数据库公司o r a c l e 、s y b a s e 、 n f o r m i x 、 s o l s e r v e r 以及其它分布式数据存储系统至少都吸收了分布式数据库系统理 论研究中提出的概念、方法、技术、算法和技巧“”“”“”“。1 3 “，如 西南交通大学博士研究生学位论文第3 页 半连接、两阶段提交协议即2 p c 协议2 13 1 ，1 捌、时戳、分布式目录m 0 1 等。 尽管分布式数据库系统理论上日趋成熟，但技术的复杂性尤其在复杂的 应用情况下，许多问题极其不容易解决，所以许多学者和技术人员等继续针 对分布式数据库系统进行理论的研究及技术上的探索。 1 1 2 分布式数据库系统特点 在d d b s 中，计算机网络将逻辑单元分散的数据库系统连接起来进行逻 辑上的集中管理，其中每个逻辑单元称为站点或结点( s i t e ) ，而这些站点 在地理上是分散的，即站点分布在不同的国家、不同的城市、不同的区域等； 而逻辑上集中管理即是各个站点上的数据库系统共同组成统一的数据库系 统，由d d b s 进行统一管理和控制。 d d b s 有如下的特点，这些特点形成了与多处理机系统和集中式数据库 系统的区别： ( 1 ) 物理分布性( 2 ) 逻辑整体性( 3 ) 站点自治性 ( 4 ) 适当增加数据冗余度( 5 ) 数据独立性( 6 ) 数据分片 ( 7 ) 副本( 8 ) 事务管理分布性( 9 ) 目录结构 ( i o ) 集中与自治相结合的控制机制( 1 1 ) 描述数据库 1 1 3 分布式数据库系统研究的必要性 随着传统的数据库、计算机网络和数字通信技术的飞速发展，以数据分 布存储和分布处理为主要特征的分布式数据库系统的研究和开发越来越受到 人们的关注。分布式数据库系统虽然有诸多优点，但由于其开发较为复杂， 在一定程度上制约了它的发展，同时也带来了许多新问题，如：数据一致性 问题、数据远程传递的实现、通信开销的降低等，这些都使得分布式数据库 系统的开发变得较为复杂。 进行分布式数据库系统研究的必要性主要体现在两个方面：_ 方面是社 会目前及未来的应用需求，另一方面是分布式数据库系统中存在的问题。 ( 1 ) 在社会需求方面 在组织或行业内部需要将地理上分散的部门数据进行统一管理和调度， 以便为信息化管理和决策提供共享。如政府行业即各级政府部门、财政部门、 税务部门、教育系统、国防系统、公检法系统、卫生系统等，属于典型的分 布式组织结构体系，因此，建立一个简单、可靠并符合政府行业特定需求的 第4 页西南交通大学博士研究生学位论文 信息系统，让信息能够在政府各级部门之间有效流动起来，从而提高政府各 部门的办公效率，提高信息决策能力，以便更有效地进行监控和管理，是政 府各部门信息化建设的关键：再如交通运输业的铁路定票系统的异地购票问 题：假设一个乘客从出发地到目的地需要中间转乘，如何使乘客在出发地一 次性购票就是分布式数据库系统面临的问题。 随着未来信息化发展程度的加深，多个组织和行业之间也需要分散数据 的共享和交互，如交通运输业中多个行业票务数据共享问题，假设一乘客出 行需要转乘的同时，还要变更出行方式，这就需要民航、铁路等信息数据共 享交互，这方面未来的需求随着信息化发展必然是分布式数据库系统未来发 展的前景。 ( 2 ) 分布式数据库系统中存在的问题 正是分布式数据库系统中数据的“分布式”才产生了一系列比集中式 数据库系统更复杂、难度更大的理论问题和技术难题。分布式数据库系统存 在的问题即分布式数据库系统中主要的理论研究和技术探讨体现在以下几个 方面1 2 t 1 1 3 1 ，1 3 ： 数据的分片、分布与冗余度异构数据库的互连 分布式数据查询处理数据副本复制 分布式事务的管理并发控制 分布式数据库系统的可靠性目录管理 本文主要针对分布式数据更新处理进行研究，当然分布式数据更新处 理必然涉及到其它问题i r o n , ”7 1 ”“”“5 “”“”1 t 2 1 ，这些问题都是相辅 相成的，本文进行的分布式数据更新处理研究主要涉及分布式事务的管理、 并发控制中的锁机制、副本复制、分布式数据库系统的可靠性及目录管理等。 1 2 分布式数据更新研究背景 分布式数据更新比传统集中式的事务更为复杂，因为数据的更新是分 布式的更新，即数据更新涉及多个站点的数据。 分布式数据更新主要是从两个方面进行：一个是一个站点对相关站点 数据进行d m l 操作，这种情况下的数据更新在分布式数据库系统中通过分布 式事务的制定、管理、执行、终结和故障恢复等进行；另一个是对被更新数 据的副本进行一致性复制。 无论哪种方式分布式数据更新，都必须保证数据库的一致性和可靠性。 西南交通大学博士研究生学位论文笋生夏 1 2 1 分布式事务管理 在分布式数据库系统的结构中，分布式事务管理处于核心地位，任何一 个数据应用的请求都是通过分布式事务的方式进行，分布式事务的执行使分 布式数据库从一种一致状态转化到另一种一致状态，达到特定的业务功能。 ( 1 ) 分布式事务定义 数据库系统的事务指用户在数据库上的一次原子操作过程，一个事务 是访问数据库的一个逻辑工作单位，它是一个操作序列。在分布式数据库系 统中的分布式事务继承了这一传统的事务概念，是传统事务的扩充，但是由 于在分布式数据库系统中数据是分布的，一个事务的执行可能涉及到多个站 点的数据，所以分布式事务的执行是分布的凹“。 分布式事务在执行时将被分解为与若干个站点相关联的操作序列，分 布式事务由这些操作序列组成，这些操作序列称为“子事务”，所以可以把 一个分布式事务看成是由若干个不同站点上的子事务组成“”“”“ 。 一个分布式事务的执行过程由如下几个基本过程组成： 生成用户事务；该事务分解成子事务； 分布执行各个子事务：收集消息结果：事务结束。 ( 2 ) 分布式事务结构 事务是一个逻辑工作单元，广_ b e g i nt r a n s a c t i o n 开始一个事务 也是访问数据库的最小单位。lt ， 、 在分布式数据库系统中，一个lt ：i 应用由若干个事务组成，每个lj 事务( 又称全局事务) 又由涉i 。 子事务或操作序列 及不同站点上的若干个子事务 li ( 又称本地事务或局部事务) i 。 组成“2 “3 “。一个分布式lt 。 事务一般以b e g i nt r a n s a c t i o n l广c o m m i t 事务成功完成结束 原语开始，最后用c o m m i t 原语t r 。l l b a c k 或a b 。r t 事务失败结束 篙为事务成警成的餐辘 图l _ 1 分布式事务基本结构r以o l l b a c k 或a b o r t 原语作为 8 1 1 “1 ”“。2 + “ 事务失败的结束标志。图卜1 是分布式事务的基本结构组成。 在分布式事务中有两个概念是必不可少的：一个是进程，在进程的说明中对 进程的行为模式进行定义，包括数据和对数据的一系列操作等，进程执行时按照 第6 页西南交通大学博士研究生学位论文 进程说明的模式启动进程，执行其中的一组操作来完成某一特定功能；另外一个 概念是事务代理( a g e n t ) ，在分布式数据库系统中，一个子事务在相应站点执行 的进程就成为该子事务在那个站点的事务代理，启动一个事务就激发某一站点执 行该事务的代理，有时这个事务代理的执行又可能引起另一个站点开始执行另一 个事务“”】。另外，各个进程需要通过事务代理进行进程上的协调，在协调方 面有如下规则： 每一个分布事务均有负责启动整个事务的总代理或称为根代理，负 责总代理的的站点为源站点。 只有总代理才能进行事务开始( b e g i nt r a n s a c t i o n ) 、提交( c o m m i t ) 或撤消( r o l i b a c k ) 的原语处理。 各个站点上的子事务都能成功执行，总代理才能决定提交该事务， 否则总代理将进行该事务的撤消处理。 ( 3 ) 分布式事务特性 在分布式数据库系统中，分布式事务仍然具有传统事务a c i d 特性“2 ： 原子性( a t o m i c i t y )一致性( c o n s is t e r i c y ) 隔离性( i s o l a t y )耐久性( d u r a b i l i t y ) 这几条性质对分布式事务操作的正确性起到了保证的作用，也维护了数 据库的一致性及完整性n “3 “”。 原子性要求事务的结果是要么全部提交( c o m m i t 成功结束) 要么全部 夭折( r o l i b a c k 不成功进行撤消结束) ，即c o m m i t 时事务的结果是完整的， 而r 0 1 1 b a c k 时则需要把数据库恢复到初始状态，不对数据库产生任何变动。 一致性要求并发运行的事务是可以串行化的，从而维护数据库一致性。 隔离性即指分布式数据库系统中的各个并行的分布式事务相互独立，互 不干扰。 耐久性指一个事务的运行结果不会丢失，即一旦一个分布式事务被成功 提交，则无论系统发生任何故障都不会丢失该事务的执行结果。 另外，分布式事务的a c i d 特性是在分布执行的环境下保持的。同时， 在分布式数据库系统中，针对分布式事务的算法设计、概念提出及技术实现 等都是在保证分布式事务a c i d 特性的前提下进行的。 ( 4 ) 分布式事务执行过程中故障的恢复 分布式事务本身发生故障或系统发生故障都会破坏数据库的完整性和 一致性。当发生分布式事务故障时，保证事务原子性的措施称为事务故障恢 复，简称为事务恢复 1 “。事务恢复主要靠日志来解决，恢复的原则有： 西南交通大学博士研究生学位论文 第7 页 独立和逐步退出事务原则：成功结束事务原则；夭折事务原则； 在分布式数据库系统的故障恢复机制中许多学者和技术人员等都作了大 量的研究和开发，但基本上都是在两阶段提交( 2p h a s e c o m m i t ) 协议的基 础上进行扩展或演变，产生许多概念、理论、算法、技术等来保证分布式事 务的a c i d 特性，同时对于数据库的可靠性和一致性都有相当可靠的保证。 1 2 2 两阶段提交协议 最基本的分布式事务执行的协议是两阶段提交( 2 p c ：2p h a s ec o m m i t ) 协议，2 p c 协议既简单又灵巧，它的目的是要得到并且最终实现分布式事务 结束的唯一而且是一致的决定，保证了分布式事务提交的原子性，并在不破 坏日志的情况下使故障快速恢复，同时使分布式数据库系统的可靠性提高， 达到分布式数据更新正常进行。 在2 p c 协议中把数据更新的分布式事务根代理站点即分布事务发起的 站点指定为协调者( c o o r d i n a t o r ) ，所有其它代理的站点称为参与者 ( p a r t i c i p a n t s ) ，只有协调者才对分布式事务具有提交或撤消的决定权， 参与者负责执行子事务对本地数据库进行d m l 操作，并向协调者发出本站点 撤消、提交子事务的意向消息及处理结果消息。 两阶段提交顾名思义就是进行分布式数据更新的事务分为两个过程： 第一阶段是表决阶段，即设法做出决定，目的是形成一个共同的决定： 第二阶段是执行阶段，目的是实现第一阶段做出的共同决定。 在弥补2 p c 协议方面，有大量的研究和设计工作已经进行或诈在进行， 这些工作虽然对2 p c 协议的可靠性、效率、可用眭及故障恢复等方面有很大 的改进，但所产生的理论、方法、概念、算法等都是在2 p c 协议的基本模式 上进行，是2 p c 协议的演变。 1 2 3 两阶段提交协议连接结构 2 p c 协议连接结构即为2 p c 协议的通信结构，即选择什么样的链路路径 进行2 p c 协议的执行 1 7 “”i t 6 。传统的连接结构有三种方式“1 1 3 2 ： 集中式2 p c 连接结构线性2 p c 连接结构分层式2 p c 连接结构 ( 1 ) 集中式2 p c 连接结构 集中式2 p c 连接结构的方式是分布式事务根代理站点与相关参与者站 点直接进行消息交流，参与者站点之间没有连接上的消息交流。图卜2 为集 第8 页西南交通大学博士研究生学位论文 中式2 p c 连接结构的简单示意图，图中边界为的图形代表协调者站点，其 它为参与者站点。 ( 2 ) 线性2 p c 连接结构 线性2 p c 连接结构中，参与者站点可以相互通信，但消息的进行是依 次后推和依次前推，在分布式事务执行时必须进行站点排序。在2 p c 执行的 第一阶段消息从根代理站点依次向后通信，直至到最后一个参与者站点；在 2 p c 执行的第二阶段，消息从最后参与者站点依次往前通信，直至到根代理 站点。图卜3 为线性2 p c 连接结构的简单示意图。 ( 3 ) 分层式2 p c 连接结构 分层式2 p c 连接结构是在集中式2 p c 连接结构基础上演变而来的，根 代理站点与部分相关参与者站点直接进行消息交流，而根代理站点与另外 部分参与者站点是通过某一中间站点进行间接消息交流，即根代理站点以外 的部分站点可以进行直接通信。图卜4 为分层式2 p c 连接结构的简单示意图。 第一阶段 i第二阶段 霹嚣 第二阶段 图卜2 集中式2 p c 连接结构图卜3 线性2 p c 连接结构 第一阶段 i 第二阶段 o = - h ! h 准备 ； 撇消提交建议i 全局撤消提交l撤消，提交处理 l 图卜4 分层式2 p c 连接结构 西南交通大学博士研究生学位论文第9 页 1 2 4 副本数据更新 在分布式数据库系统中，2 p c 协议尽管很好地保证数据更新时分布式 事务和数掘库的一致性，但在发生某些故障时，对于数据副本的更新会产生 较低的性能，即可用性程度下降；另外2 p c 协议也不可能很好的满足副本这 种数据集合的传递和更新，所以在进行数据副本更新时采用复制技术是有效 的技术方法之一 i 一1 1 “2 。1 比“垤2 1 1 2 扎“1 3 2 。 针对副本复制问题，数据分为源数据和副本，源数据指某一站点的主 数据，副本指源数据在不同站点的数据镜像。复制技术指在分布式数据库系 统中把被修改数据对应的副本中的相应数据异步地进行一致性更新。复制技 术主要有1 1 “5 8 6 8 8 ，1 ”1 “”1 13 “： 多站点数据副本更新；主文本更新法；移动主文本法： 快照( s n a p s h o t ) 方法；对等( p e e rt op e e r ) 复制。 1 3 分布式数据更新研究的必要性 在分布式