（计算机系统结构专业论文）分布式数据库死锁检测算法研究.pdf

中文摘要 摘要 分布式数据库的死锁检铡是并发控制领域的一个重要问题。 在分布式系统研究领域中，死锁条件通常是根据资源请求方式来确定的。根 据分布式数据库中事务发出不同的资源请求方式，现有的分布式数据库死锁检测 算法通常针对某种资源请求模型而提出。分布式数据库不同于一般分布式系统， 其死锁条件不仅与资源请求方式相关，而且与资源授予方式相关。同时，现有的 分布式数据库死锁检测算法通常假设系统采用排它锁模式或共享排它锁模式，而 忽略了分布式数据库系统中普遍应用的多锁模式，使得算法无法有效应用于分布 式数据库系统。本文将详细介绍分布式事务、并发控制和资源请求模型，总结出 分布式数据库系统的通用死锁条件。 分布式数据库死锁检测算法主要分为集中式、层次式和分布式。集中式和层 次式算法通常正确性较高，但消息通讯量太大。与之相反，分布式算法通常消息 通讯量较小，但正确性较低。由于分布式算法更为灵活、有效，论文将深入研究 分布式算法，并提出种新的分布式死锁检测算法基于d d a 和改进探针的死 锁检测算法。该算法是全局状态检测方法( d d a 算法) 和基于探针的算法的结合； 算法提出了一种新的探针传递规则，当事务结点收到第一个探针( 包括启动探针) 时，结点将接受( 继续传播) 并记录探针：当事务结点在接受某个探针后再收到 其它探针时，结点将拒绝( 停止传播) 该探针，并记录下探针对( 被拒绝的探针， 接受的探针) 。算法对传统探针进行了扩展，引入了扩展探针、探针对、探针簇等 概念，建立了新的死锁判断机制，如果存在一个探针路径 ( x i ，y o ( 1 i n ) ，且 y n 是x 1 的基，那么w f g 中存在环。算法通过对探针对序列的合并计算，减少 d d a 之间全局信息的传送。由此该算法可以有效地避免假死锁和幻象死锁，避免 死锁无法被检测到的情形，降低消息量。 论文对该算法进行了正确性分析、性能分析，并通过模拟实验检验了算法。 关键词：分布式数据库，死锁检测，等待图，扩展探针，探针对，探针簇，死锁 检测代理，多锁模式 英文摘要 a b s t r a c t d e a d l o c kd e t e c t i o ni nd i s t r i b u t e d 蛐b a s ei s a ni m p o r t a n tp r o b l e mi nt h ea r e ao c o n c u r r e n c y c o n t r 0 1 i nt h er e s e a r c ha r e ao fd i s t r i b u t e d s y s t e m s ，d e a d l o c k c o n d i t i o n s a r e c o m m o n l y d e t e r m i n e db yr e s o u r c er e q u e s tm o d e a c c o r d i n gt od i f f e r e mr e s o u r c er e q u e s tt h a ti s s u e db y t r a n s a c t i o n s ，e x i s t i n gd e a d l o c kd e t e c t i o na l g o r i t h m s o fd i s t r i b u t e dd a t a b a s ea r ec o m m o n l y p r e s e n t e df o rc e r t a i nr e s o u r c er e q u e s tm o d e l d i s t r i b u t e dd a t a b a s ei sd i f f e r e n tf r o mg e n e r a l d i s t r i b u t e ds y s t e m ，i t sd e a d l o c kc o n d i t i o ni sn o to n l yr e l a t e dw i t hr e s o u r c er e q u e s tm o d e ，b u t a l s or e l a t e dw i mr e s o u r c eg r a n tm o d e m o r e o v e r , b e c a u s ee x i s t i n gd e a d l o c kd e t e c t i o n a l g o r i t h m so f d i s t r i b u t e dd a t a b a s ec o m m o n l y a d o p tx l o c km o d eo rs p al o c km o d e a n dl o s e s i g h to fm u l t i p l el o c km o d ew h i c h i s a p p l i e dw i d e l yi nd i s t r i b u t e dd a t a b a s es y s t e m s ，t h e s e a l g o r i t h m s c a nn o tb ea p p l i e d a v a i l a b l yi n d i s t r i b u t e dd a t a b a s e s y s t e m s i nt h i sp a p e r , d i s t i r b u t e dt r a n s a c t i o n , c o n c u r r e n c yc o n t r o la n dr e s o u r c er e q u e s tm o d e la r ei n t r o d u c e di n d e t a i l t h eu n i v e r s a ld e a d l o c kc o n d i t i o ni nd i s t i r b u t e dd a t a b a s es y s t e mi ss u m m a r i z e d d e a d l o c kd e t e c t i o na l g o r i t h m so fd i s t r i b m e dd a t a b a s ec a r lb ec l a s s i f i e di n t oc e n t r a l i z e d ， l a y e r e d a n dd i s t r i b u t e d c e n t r a l i z e da n d l a y e r e da l g o r i t h m sc o m m o n l y h a v eh i g e rc o i r e c n l e s s b u tt h e i rn u m b e ro fm e s s a g e sa r et o og r e a t ，b yc o n t r a r i e s ，f o rd i s t r i b u t e da l g o r i t h m s ，t h e i r n u m b e ro f m e s s a g e sa r ec o m m o n l yp e t t y , b u tt h e i rc o r r e c t n e s si sp o o r b e c a u s ed i s t i r b u t e d a l g o r i t h m s a r em o r ea g i l ea n de f f i c i e n t ，t h i s p a p e rw i l l l u c u b r a t ed i s i t f i b u t e dd e a d l o c k d e t e c t i o na l g o r i t h m sa n db r i n gf o r w a r dan e wd i s t r i b u t e da l g o r i t h m - - a nd e a d l o c kd e t e c t i o n a l g o r i t h mb a s e dd d a a n d m o d i 每e dp r o b e t h i sa l g o r i t h me o m b i n a t et h ei d e a lo ft h eg l o b a l s t a t ed e t e c t i o nm e t h o d ( d d aa l g o r i t h m ) a n d a l g o r i t h m sb a s e do np r o b e i tp r e s e n t san e w r u l eo f p r o b ew a n s m i s s i o n , t h a ti sw h e nt r a r m a c d o nn o d er e c e i v e st h ef i r s tp r o b e ( c o n t a i n s i n i t i a lp r o b e ) ，t h en o d ew i l la c c e p t ( c o n t i n u et h ep r o b et r a n s m i s s i o n ) a n dr e c o r dt h e p r o b e ， w h e nt r a n s a c t i o nn o d er e c e i v c so t h e rp r o b ea g a i n ，t h en o d er e f u s et h ep r o b e ( s t o pt h ep r o b e t r a n s m i s s i o n ) a n dr e c o r dt h ep r o b e c o u p l e ( r e f u s e dp r o b e ，a c c e p t e dp m b e ) i nt h i sa l g o r i t h m ， t h en o t a t i o n so fp r o b e c o u p l e ，e x t e n t e d p r o b ea n dp r o b e - c l u s t e r e t ca r e 百v e n , a n dan e w m e c h a n i s mo f d e a d l o c kd e t e c t i o ni sb u i l t ，i f t h e r ei sa p r o b e p a t h ( x i ，y j ) ( 1 i n ) ，a n dy n i s t h eb a s eo f x h t h e nt h e r ei sac y c l ei nw f g 豇l i sa l g o r i t h mc a l lr e d u c et h en u m b e ro f g l o b a l i n f o r m a t i o nt r a n s m i s s i o nb y u s i n gm e r g ec o m p u t a t i o no f t h ep r o b e c o u p l e s ot h i sa l g o r i t h m c a r la v o i df a l s ed e a d l o c ka n dp h a n t o md e a d l o c k ，c 锄a v o i du n d e t e c t e dd e a d l o c k r e d u c et h e n u m b e r o f m e s s a g e s f i n a l l y , t h ec o r r e c h l e s sa n dp e r f o r m a n c eo f t h i s a l g o r i t h ma r ea n a l y s e d ，a n dt e s t e db y i i i 重庆大学硕士学位论文 s i m u l a t i o ne x p e r i m e n t a t i o n k e yw o r d s ：d i s t r i b u t e dd a t a b a s e ，d e a d l o c kd e t e c t i o n ，w a i t f o rg r a p h ，e x t e n t e d - p r o b e ， p r o b e - c o u p l e ，p r o b e - c i u s t e r , d e a d l o c kd e t e c t i o na g e n t ，m u l t i p l el o c km o d e i v 1 绪论 1绪论 1 1 研究意义与目的 伴随着网络技术的不断成熟，商业应用系统逐步发展为分布式体系结构，这 种体系结构的底层数据库最初采用的仍然是集中式数据库系统。为了提高数据本 地访问能力，降低网络通讯量，人们发现必须对应用的共享数据资源进行分布式 管理，由此诞生了分布式数据库系统。分布式数据库系统是数据库技术和网络技 术相结合的产物，而不仅仅是两者简单的组合。 由于分布式数据库系统强大的事务处理能力和数据管理能力，越来越多的企 业采用分布式数据库系统实现企业管理数据化。随着企业的不断发展，分布式数 据库系统变得相当庞大，需要支持大量的并发事务处理。目前各种大型分布式数 据库系统在并发控制策略上普遍采用了封锁技术。由于大量用户频繁地并行地访 问数据，对同一资源的冲突操作必然存在，这就可能导致分布式死锁的产生。 如果系统中存在死锁而不能被及时检测到并加以解决，那么处于死锁的那些 事务将永远处于阻塞状态，应用将无法正常结束，甚至，随着死锁存在时问的延 长，将导致更多事务的阻塞，最终使系统陷于瘫痪。因此及时检测出死锁是分布 式数据库系统必须加以解决的重要现实问题。同时，我们知道，死锁问题并不是 数据库系统所特有的，任何资源共享系统都可能存在死锁问题。分布式数据库系 统作为一种典型的资源共享系统，对其死锁检钡4 的研究，可以为其它系统的死锬 检测研究提供一定的参考价值。 由于分布式死锁检测方法比集中式和层次式检测方法具有更高的灵活性和有 _ 毅性。我们期望在前人研究的基础上，继续深入对分布式死锁检测方法的研究。 目前，分布式死锁检损i 研究中的主要问题有： 根据应用的不同需求，应用所发出的资源请求方式不尽相同。现有的资源请 求模型包括了：单一资源模型、a n d 模型、o r 模型、a n d o r 模型及k _ o u t 0 f n 模型。针对不同的资源请求模型，相应的死锁条件各有区别。尽管很多算法的作 者指出研究的算法是应用于分布式数据库系统的，但实际上是针对某种资源请求 模型而提出的。我们有必要深入分析分布式数据库系统特有的资源请求模型和死 锁条件，提出具有代表性和通用性的死锁检测算法。 由于分布式数据库系统是由物理上分布于不同站点的数据库集合而成的，不 同站点之间通讯是通过发送消息的方式来实现的，为了提高死锁检测算法的效率， 我们需要尽量降低网络中的消息传送量。 重庆大学硕士学位论文 为了提高算法整体性能，分布式死锁检测算法通常允许在多个站点上启动， 并行进行各自的死锁检测，如果处理不当，很可能造成同一个死锁被多次重复地 检测和解决，这就是所谓的“幻象死锁”。对幻象死锁的检测实际上是多余的，这 是我们需要避免的。 现有的分布式死锁检测算法通常由于死锁解决处理不当，造成后续检测中出 现“假死锁”，这样的死锁实际上是不存在的，假死锁的最大问题是将造成不必要 的事务夭折。这也是我们需要解决的。 1 2 研究现状 数据库系统中发生死锁的必要条件是：持有等待条件，事务已经持有分配 给它的资源，又去申请并等待另外的资源；非剥夺条件，除非事务释放其占有 的资源，否则不强制夺走它所拥有的资源；循环等待条件，两个以上的事务处 于相互等待的循环链中。 常见的死锁处理方式有：死锁预防、死锁避免、死锁检测与解决。 为了预防死锁，只需使死锁存在的必要条件之一不成立即可。比如为所有资源 排序，预测事务要求的资源集合，系统依照资源排序情况，为事务顺序地封锁资 源。由于分布式系统中的资源规模相当大，而且系统中的资源处于动态变化中， 所以为分布式系统中的所有资源排序显得极不现实。同时由于该方法要求事务在 开始其操作前必须先得到可能会用到的所有资源，同时其它事务又不会请求对这 些资源的使用，因此，这种方法会极大地降低系统的并发程度。 与死锁预防相比，死锁避免采用了不同的策略。当事务提出对资源的申请时， 死锁避免方法令其等待一定长度的时间，如果时间片用完，事务仍然没有得到该 资源，系统则使资源的申请方或占有方夭折。更复杂的算法可能还会包括判定事 务优先级的策略。死锁避免比预防实现简单，也更灵活。但由于时间片长度难以 把握，将可能造成不必要的事务夭折。 不同于死锁避免和死锁预防，死锁检测方法是一种相对乐观的方法。在采用 死锁检测方法的系统中，只有在系统怀疑可能死锁时，才开始检测以进一步确定 系统是否死锁。分布式数据库系统中，应用的访问冲突相对比较分散，发生死锁 的概率比较低，同时由于死锁避免和预防方法在分布式数据库中实施比较困难， 现有分布式数据库系统通常采用了死锁检测方法。 死锁检测方法中通常使用等待图w f g ( w a i t f o rg r a p h ) 作为表达事务间等 待关系的数学模型。在w f g 中，结点t i 表示事务，边( t i ，t j ) 表示事务t i 等待，该 边在t i 申请对q 现持有的资源s r 加锁时建立，在b 释放其在资源s t 上的锁后删除。 2 1 绪论 当w f g 中出现环时，表明系统中存在死锁。 分布式数据库系统中死锁检测方法按照计算结构可以分类为：集中式死锁检 测、层次式死锁检测和分布式死镇检测。 集中式死锁检测通常指定系统中的某个站点作为中央站点，当系统怀疑发生 死锁时，由该站点收集系统中所有站点的w f g ，并根据这些图构造全局w f g ， 在全局w f g 中查找环。 集中式死锁检测存在3 个严重的限制： 系统可靠性问题：当中央站点出现故障时，系统将无法继续正常工作； 系统瓶颈问题：所有站点都将w f g 向中央站点传递，中央站点的网络通 讯量过大： 有效性问题：w f g 的及时更新能力差，将降低算法检测结果的有效性。 层次式死锁检测通常根据应用和数据的分布情况，将系统中的所有站点组织 为一个层次式结构。在该层次结构中，叶结点代表实际的物理站点；分支结点称 为局部检测站点，由其下级的某个站点担任；根结点称为全局检；9 1 1 | 站点。当系统 怀疑发生死锁时，叶结点将自身w f g 发送到其层次结构中的上级结点，由上级结 点将其所有下级结点的w f g 组合为局部w f g ，并进行局部的死锁检测和解决， 稍后，再将不包含局部死锁的局部w f g 传递到上级结点，上级结点继续进行死锁 检测，直到根结点得到全局w f g ，并得出相应检测结果。 层次式死锁检测将死锁检测任务分布在多个站点执行，提高了系统效率，避 免了系统出现通讯瓶颈问题。但同时，层次式死锁检测也存在多个限制： 系统可靠性问题：当全局死锁检测站点发生故障时，系统将无法继续正常 工作； 算法灵活性问题：系统的层次结构是相对固定的，如果系统进行了扩充或 改动，那么原有的层次结构可能已经不适合了。 、 有效性问题：同集中式检测算法一样，w f g 的及时更新能力差，将降低 算法检测结果的有效性。 与集中式和层次式死锁检测相比较，分布式死锁检测的特点是每个站点( 或 者每个事务) 都可以执行死锁检测任务。集中式和层次式检测算法通常是依赖于 对静态w f g 的分析，而分布式检测算法通常采用动态分析w f g 的方式。 现有的分布式死锁检测算法可以分类为：超时方法( t i m e o u tm e t h o d ) 、路径 推进( p a t h p u s h i n g ) 、边追踪( e d g e c h a s i n g ) ( 也称基于探针的算法) 、扩散计算 ( d i f f u s i o n c o m p u t a t i o n ) 、全局状态检测( g 1 0 b 8 1s t a t ed e t e c t i o n ) 。 3 重庆大学硕士学位论文 1 3 研究内容 论文主要研究分布式数据库的死锁检测问题，包括了对分布式数据库死锁条 件以及死锁检测算法的研究。 分布式数据库死锁检测算法作为死锁检测算法一个重要研究分支得到了广泛 深入的研究。由于资源请求方式的不同，死锁条件各不相同，因此，现有的死锁 检测算法通常针对某种资源请求模型提出。当前的分布式数据库死锁检测算法通 常沿用了这一思想，根据分布式数据库中事务的不同资源请求方式而提出相应算 法。这使得很多算法具有很大局限性，缺乏通用性。死锁条件必然与资源请求方 式相关，但同时还须取决于资源授予方式。现有的分布式数据库死锁检测算法没 有充分分析分布式数据库的死锁条件，只是照搬分布式系统进程死锁条件来展开 研究，回避了问题的本质。论文希望通过较为详细、具体的分析以获得能表达分 布式数据库的通用死锁条件， 现有分布式死锁检测算法通常在某种资源请求模型中具有自己独特的优势。 超时方法简单，但造成不必要的事务天折。路径推进方法采用边构造w f g 边检测 的方式能较早发现死锁，但缺乏全局一致概念，无法避免假死锁。基于探针的算 法在所有算法中需要的消息量最少，但算法检测结果的准确性不够，容易出现假 死锁。扩散计算最适合于a n d o r 或k o u t - o f n 模型的死锁检测，但在其他资 源请求模型中，则比基于探针的算法具有更高的消息量，性能较低。全局状态检 测方法具有全面、充分的全局信息可以有效避免假死锁，但算法消息量太大。论 文希望在分布式数据库系统的通用死锁条件基础上，总结各种算法的优、缺点， 通过综合这些算法的优点，设计出新的适用于分布式数据库的死锁检测算法。 论文的具体工作包括以下几点： 总结了分布式数据库系统的通用死锁条件； 提出了一种基于d d a 和改进探针的死锁检测算法。 该算法的特点： 该算法是全局状态检测方法( d d a 算法) 和基于探针的算法的结合。 该算法提出了一种新的探针传递规则，当事务结点收到第一个探针( 包括 启动探针) 时，结点将接受( 继续传播) 并记录探针：当事务结点在接受某个探 针后再收到其它探针时，结点将拒绝( 停止传播) 该探针，并记录下探针对( 被 拒绝的探针，接受的探针) 。 该算法对传统探针进行了扩展，引入了扩展探针、探针对、探针簇等概念， 建立了新的死锁判断机制，如果存在一个探针路径 ( x i ，y j ( 1 i n ) ，且y n 是 x 1 的基，那么w f g 中存在环。 4 1 绪论 该算法通过对探针对序列的合并计算，以减少d d a 之间全局信息的传送。 由此该算法可以有效地避免假死锁和幻象死锁，避免死锁无法被检测到的情 形，降低消息量。 另外，算法依赖的w f g 的边( t i ，q ) 不仅表示t i 等待i ，同时表示t i 的锁类型与 t i 的锁类型不相容，使得算法可以适用于多种锁模式，同时在死锁解决策略方面 我们选择了产生关键探针对的事务作为牺牲者，使得算法的死锁解决代价较低， 特别是对于多环相交的情况。 本文各章按以下方式组织： 第一章介绍了论文研究意义与目的，概括了当前死锁检测研究现状，指出了 论文研究内容； 第二章介绍了分布式数据库系统的相关概念着重介绍了分布式数据库系统 的封锁技术： 第三章介绍了现有的分布式死锁检测算法，同时指出了各类算法存在的问题， 研究了分布式数据库系统的资源请求模型，并得出了分布式数据库系统的死锁条 件； 第四章着重介绍基于探针的死锁检钡4 算法，提出了新的算法设想； 第五章详细介绍了基于d d a 和改进探针的死锁检溅算法设计思路及算法描 述； 第六章给出了新算法的正确性分析和性能分析，并遥过模拟实验检验了新算 法； 第七章总结了论文研究情况， 1 、4 本章小结 本章指出了论文研究的目的和意义，介绍了论文的研究现状，最后阐述了论 文的研究内容和各章节的内容安排。 5 2 分布式数据库系统 2 分布式数据库系统 2 1 概述 2 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 ) 的研究始于2 0 世 纪7 0 年代。它是数据库技术和网络技术相结合的产物。荚国计算机公司c c a 于1 9 7 9 年在d g c - i o 和d e c - 2 0 上实现了世界上第一个分布式数据库系统s d d l ( s y s t e mo fd i s t r i b u t e dd a t a b a s e ) 。 进入8 0 年代，随着计算机的广泛应用和计算机网络技术的迸一步发展，分布 式数据库进入成长阶段。如德国的斯图加特大学研制的p o r e l 系统、美国i b m 公 司的s a nj q s e 研究室研铋的姆和曲s t e mr 等。 2 0 世纪9 0 年代，d d b s 已进入商品化应用阶段，分布式数据库已经成熟并得 到广泛应用。 2 。1 。2 分布式数据库系统定义 分布式数据库系统”是一组数据集，逻辑上它们属于同一个系统，而物理上 它们分散在用计算机网络连接的多个站点上，并统一由一个分布式数据库管理系 统管理。与传统的集中式数据库系统样，分布式数据库系统可分为分布式数据 库和分布式数据库管理系统。 1 分布式数据库( 肋b _ d i s t r i b u t e dd a t a b a s e ) 分布式数据库分两个层次：全局数据库和局部数据库。全局数据库( g d b g l o b a ld a t a b a s e ) 是计算机网络环境中各站点或节点上数据库的逻辑集合，它是 虚拟的、逻辑的；而分布式数据库系统中的各站点数据库为局部数据库( l d b l o c a ld a t a b a s e ) ，它是物理存在的。在分布透明的分布式数据库系统中，用户只 与全局数据库打交道，局部数据库对用户透明。 2 分布式数据库管理系统( d d b m s ) 分布式数据库管理系统是分布式数据库系统中的一组软件，负责管理分布环 境下逻辑集成数据的存取。分布式数据库管理系统对d d b 的管理分两个层次： 是全局数据库管理系统( g d b m s ) ，负责接收用户请求、根据全局字典对用户请求 进行优化形成分布计划、将分布计划交给局部数据库管理系统执行，并且组装执 行结果显示给用户；一是局部数据库管理系统( l d b m s ) ，功能与传统的集中式数 据库管理系统相似，负责访问局部数据库。在分布透明的分布式数据库系统中， 用户只与全局数据库管理系统打交道，局部数据库管理系统对用户透明。 重庆大学硕士学位论文 2 1 3 分布式数据库的特点 分布式数据库具有如下特点： 1 数据的物理分布性：数据库中的数据不是集中存储在一个地区一台计算机 上，而是分布在不同站点的计算机上。 2 数据的逻辑整体性：数据库虽然在物理上是分布的，但这些数据并不是互 不相关的，它们在逻辑上是互相联系的整体。 3 数据的分布独立往( 也称分布透明性) ：在用户看来，整个数据库仍然是 一个集中的数据库，用户不关心数据物理位置分布的细节，也不必关系数据副本 的一致性，分布的实现完全由系统来完成。 4 站点自治和协调：系统中的每个站点都具有独立性，能执行局部的应用请 求，每个站点又是整个系统的一部分，可通过网络处理全局的应用请求。 5 数据的冗余：与集中式数据库不同，分布式数据库中应存在适当冗余来提 高系统处理效率和可靠性。 2 1 。4 分布式数据库的优点 分布式数据库具有如下优点： 1 可靠性：由于分布式数据库可以通过在多个不同的站点冗余地存放数据来 恢复失效的数据，所以单一的部件失效不一定会使整个系统失效。 2 自治性：在分布式数据库中，各站点可以对自己管理的信息加以控制，可 以制定各自使用信息的策略，使它们较少地依赖某些远程数据处理中心。同时也 因为系统的自治性带来了系统存在异构问题。 3 模块性与系统升级能力：d d b 是将一些功能较小的数据库综合成一个功能 更强的数据库系统，用以满足个单一数据库无法满足的应用要求。显然，增加 一个新站点的代价要小于完全新建一个大的集中式数据库的代价。 4 效率及可用性：通过合理的分布数据，使得数据存储于其常用的站点上， 既缩短了响应时间，减少了通讯费用，又提高了数据的可用性。数据的冗余存储 还提高了存取数据的并发程度，大大提高系统的数据吞吐量和响应速度。 2 2 分布式事务 2 2 1 事务概念 事务是作为单个逻辑工作单元执行的一系列操作。一个逻辑工作单元必须有四 个属性，称为a c i d ( 原子性、一致性、隔离性和持久性) 属性，只有这样才能成 为一个事务： 8 2 分布式数据库系统 1 原子性：一个事务的操作要么全部执行，要么全部不执行。原子性要求事 务如果中断执行，那么它的所有执行结果将被取消。事务中断的原因包括事务中 止和系统故障。一个事务的中止可以由该事务自己( 或其用户) 来请求，也可以 由系统来强迫中止，典型例子为系统过载和死锁。 2 一致性：事务在完成时，必须使所有的数据都保持一致状态。在经历事务 的执行后，数据库将从一个一致性状态迁移到另一个一致性状态。 3 隔离性：由并发事务所作的修改必须与任何其它并发事务所作的修改隔离。 事务查看数据时数据所处的状态，要么是另一并发事务修改它之前的状态，要么 是另一事务修改它之后的状态，事务不会查看到由其它事务修改的数据的中间状 态。为了确保事务的隔离性，通常使用的是可串行性理论。 4 持久性：一旦一事务提交以后，系统必须保证其操作的结果永不丢失，且 与后续的故障无关。 2 2 2 分布式事务 分布式事务和集中式事务一样，具有原子性、一致性、隔离性和持久性的特点。 但由于分布式系统的特性，分布式事务在执行时将被分解为若干站点上的子事务， 为了在某个站点上执行操作，分布式事务必须在相应站点上创建一个事务代理， 由它来执行该站点上的子事务部分。另外，在子事务的调度执行中，必须有个 协调者进程协调各子事务的执行。一般来说，这样的协调进程由启动该分布式事 务的始发站点上的代理进程承担。这时该代理进程称为根代理( r o o ta g e n t ) 。根 代理者的功能包括：启动整个分布式事务；请求其它站点创建事务代理执行子事 务；发出“事务开始”、“提交”和“回滚“原语。 2 2 3 分布式事务管理参考模型 分布式事务管理参考模型如图2 1 所示 9 重庆大学硕士学位论文 i n t e r f a c e1 ：5 = 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 、c r e a t e i n t m r f a c m2 ：l o c a l _ h m g i n 、l o c a l c o m m l t 、l o c a l _ r o l i b a c k l o c a l c r c a t e 图2 1 分布式事务管理参考模型 f i g 2 1r e f e r e n c em o d e lo fd i s t r i b u t e dt r a n s a c t i o nm a n a g e m e n t 1 事务代理 如前所述，一个分布式事务是由多个站点协调工作完成的操作序列。为了在 各个站点完成这些操作，分布式事务必须在这些站点上有一系列事务代理。代理 之间通过消息( m e s s a g e ) 进行通信。 在参考模型的最高层一分布式事务层( d i s t r i b u t e dt r a n s a c t i o n ) ，它由 多个代理组成，其中一个称为根代理( r o o ta 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 l b a c k 原语。同时 它也负责请求创建( c r e a t e ) 新的代理。不失一般性，可以假定接口1 仅仅为根 代理使用。 2 分布式事务管理器一d t m ( d i s t r i b u t e dt r a n s a c t i o nm a n a g e r ) 在参考模型的第二层是分布式事务管理层( d t m ) 。它由各结点的本地d t m 代 理组成。作为一个整体，d t m 实现接口l ( i n t e r f a c e1 ) 的：b e g i n t r a n s a c t i o n 、 c o m m i t 、r o l l b a c k 、c r e a t e 。它负责请求创建( c r e a t e ) 本地代理和发出创建新 的代理原语。 3 本地事务管理器一l t m ( l o c a lt r a n s a c t i o nm a n a g e r ) 在参考模型的最底层是本地事务管理层。它负责实现：l o c a l b e g i n 、 l o c a l c o m m i t 、l o c a lr o l l b a c k ，完成本地事务管理功能( 失败恢复、并发控制) 。 接口2 有一个l o c a l c r e a t e 原语，本地代理的创建是l t m 的功能。l o c a l b e g i n 1 0 2 分布式数据库系统 原语开始一个子事务( s u b t r a n s a c t i o n ) ，它是同一个分布式应用的组成部分。 全局b e g i n 和c o m m i t r o l t b a c k 命令不仅对根代理有效，也对事务的所有代 理有效以保证分布式事务的原予佳。 l t m 的存在使我们能把精力集中在分布式事务管理的特殊问题上一即保证 所有的l t m 采取同样的决定，要么都c o m m i t 要么都r o l l b a c k 。同时使我们可不关 心在每个结点实现这个决定的问题。 图2 2 显示了一个分布式事务中，参考模型各个组成部件发出的原语和信息。 图2 2 参考模型各个组成部件发出的原语和信息 t f i g 2 2p r i m i t i v ew o r d sa n di n f o r m a t i o ni nr e f e r e n c em o d e l 2 2 4 两阶段提交协议 为了实现分布式事务管理的原子性，保证所有的l t m 采取同样的决定，分布式 数据库系统一般采用两阶段提交协议( 2 p c t w op h a s ec o m m i tp r o t o c 0 1 ) 。在两 阶段提交协议中，称根代理为协调者，所有其它必须起提交的代理为参与者。 协调者的责任是最终决定是提交还是夭折，参与者实施这最后的决定，完成对本 地数据库的更新。 2 p c 的基本思想是为全部参与者做出关于提交或夭折的致决定。如果其中有 一个参与者不能本地提交其子事务，则全部参与者必须本地天折。此协议由两阶 段组成：判断阶段和实现阶段。判断阶段的目的是获得一个共同的决定：实现阶 段的目的是实现判断阶段所确立的决定。协议的原理如下： 重庆大学硕士学位论文 判断阶段： 协调者在日志中写入“预提交”命令 发送“预提交”命令给所有参与者且开始计时 参与者等待“预提交”命令 i f 参与者可以提交t h e n b e g i n 在日志中写入子事务的记录 在日志中写入“准备提交” 向协调者发“准备提交”信息 e n d e l s eb e g i n 在日志中写入“夭折” 向协调者发“夭折”信息 e n d e n d 实现阶段： 协调者等待接收所有参与者的应答信息并检查超时 i f 超时或收到至少一个“夭折”t h e n b e g i n 在日志中写入“全部夭折” 向所有的子事务发“夭折”命令 e n d e l s eb e g i n 在日志中写入“全部提交” 向所有的参与者发“提交”命令 e n d e n d 参与者等待协调者的命令 根据命令在日志中写入“夭折”或“提交” 向协调者发“已执行”信息 执行“提交”或“夭折”命令 协调者等待接收所有参与者的“已执行”信息 在目志中写入“完成” 1 2 2 分布式数据库系统 2 3 并发控制 2 ，3 1 并发控制概念 事务的可串行性通常作为多个事务执行的正确性准则。更精确地说，多个事 务的某个执行过程是正确的，当且仅当其是可串行化的( 如果多个事务的某个执 行过程与同样的这些事务的某个串行执彳于过程产生的结果相同，则称其为可串行 化的) 。 可串行性判断方法如下： 1 ) 各单个事务如能将数据库从一个正确状态转变为另一个正确状态，就认为 其是正确的。 2 ) 任何一个串行顺序依次运行多个事务也认为是正确。这里串行顺序可为 “任何一个”，是基于各单个彼此间相互独立的假定。 3 ) 穿插执行过程是正确的，当且仅当其与某个串行执行过程等价，即是可串 行化的。 分布式并发控制的目的是保证分布式数据库系统中多个并发事务的高效正确 执行。为了讨论分布式事务并发控制的正确性，引入两种事务调度模型，一种是 以封锁技术为基础的形式模型，一种是以对戳技术为基础的时问模型。 在数据库系统中，事务是以发出读操作和写操作原语的方式来存取数据库的， 任一事务t i 的读操作记为r i ( x ) ，写操作记为w i ( x ) ，x 是一数据项。负责控制事 务请求的数据库操作的执行顺序的部件叫调度器，它是数据管理器( d m ) 的一部 分。调度器确定数据库操作的穿插执行，确保数据摩状态保持一致。数据库操作 的一次穿插执行称为一个调度，如： r i ( x ) r j ( x ) w 。( x ) r k ( x ) w j ( x ) 表示事务t i ，t j ，t k 对数据对象x 的读写操作，这几个事务可以串行执行，也可 并行执行。当它们并行读写数据对象x 时，就可能造成数据对象x 的不一致性， 因此必须对这些并发操作进行控制。事务的并发控制就是保护事务的并发操作正 确执行。如果并发操作的事务的某种调度执行结果与它们按某种顺序串行执行它 们的结果相同，则称这种调度为可串行化调度。可串行化调度是事务正确性的唯 一准则。在实现过程中，可以采用封锁技术及时戳技术来实现事务的可串行化调 度。 2 ，3 2 基于时戳技术的并发控制 用时戳技术实现事务的并发控制时，给每个事务赋予一个唯一的时戳，事务 的执行等价于按时戳的先后次序串行执行，即事务的冲突操作按时间的次序进行 调度。 重庆大学硕士学位论文 基于时戳技术的并发机制思想是，只有当某一数据项上由一较年长的事务写 入以后才允许另一较年轻的事务对该数据项进行读写，否则它拒绝这个操作并重 新启动该事务，即一个事务只能读写它以前的事务写入的数据而不能读写它以后 的事务写入的数据。当出现年长的事务读写年轻事务写入的数据时，该年长事务 遭拒绝且重新启动被赋予一个新的时戳，直到该时戳大于原来年轻事务，即它变 得比年轻事务更年轻时才可以读写原年轻事务写入的数据。 基于时戳技术的并发控制包含了保守的时戳方式和基本时戳方式。保守的时 戳方式由于有等待状态，因此有可能出现死锁。避免死锁的唯一方法是超时以后 发送一空操作。基本时戳方式中无死锁的问题，因此不需要死锁检测及解决，事 务重启的次数较多。 时戳技术不是我们的研究内容，这里不再详述，有兴趣的读者请参看相关文 献。 2 3 。3 基于封锁技术的并发控制 1 基本封锁技术 基于封锁技术的并发控制思想是，事务在对数据项操作之前必须先申请该数 据项的锁，只有申请到锁以后，即封锁成功以后，才可以对数据项进行操作。通 过锁的共享及排斥的特性，实现事务的可串行化调度。锁的类型一般有两种类型： 读锁( 也称为共享锁s l 0 c k ) 和写锁( 也称为排它锁x l o c k ) 。 我们说来自不同事务的对同一数据资源的封锁请求是相容的，当且仅当，它 们可以同时被授予。 以下是共享排它锁模式的相容矩阵： 表2 1 共享排它锁模式的相容矩阵 t a b l e2 1c o m p a t i b i l i t ym a t r i xo fs xl o c km o d e xs xnny snyy yyy y 表示相容，n 表示不相容，一表示不申请锁。 有许多锁模式( 排它锁、共享排它锁、语义锁) ，但它们实现并发控制的原 理是一样的，即对事务问出现的冲突操作，通过加锁的原则及锁的相容机制实现 冲突操作的可串行化调度，当锁类型相容时，事务并行执行，当锁类型不相容时， 事务串行执行。 使用锁模式的典型算法是两阶段锁协议( 2 p l 协议) ，它要求任何事务对数据 1 4 2 分布式数据库系统 项的操作先加锁，如果一个事务一旦释放了一个封锁，它将不再获得其他封锁。 因此两段锁协议分为两个阶段：第一阶段是获得锁阶段，第二阶段释放锁阶段。 由于分布式事务在执行时是以站点为基础划分为多个子事务进行执行，而子 事务的操作是全局事务操作序列的一部分，因此当全局事务遵循2 p l 协议时，各 子事务也遵循2 p l 协议。对子事务而言，2 p l 协议是一正确的调度方法，所以分布 式事务的调度主要考虑的是子事务的调度。 2 ，多副本的并发控制 在分步式数据库中，存放数据项的多个副本，可以提高系统的可用性、可靠 性及存取效率，但同时也带来新的问题，如副本的选择及数据的一致性问题，这 些问题增加了并发控制的复杂性。下面讨论几种重