（通信与信息系统专业论文）forces路由器中嵌套事务的应用研究.pdf

f o r c e s 路由器中的嵌套事务研究 摘要 在f o r c e s 路由器结构中包括一个控制件( c o n t r o le l e m e n t ， c e ) 和多个转发件( f o r w a r d i n ge l e m e n t ，f e ) ，并且一个c e 控制和 管理着上百个f e 。在f o r c e s 路由器中存在着事务( t r a n s a c t i o n ) ， 比如路由路径和资源的预留。传统的事务模型使用严格的二阶段提 交协议，即只要存在一个子事务执行失败，就必须回滚整个事务， 使系统回到执行之前的状态；当且仅当所有的子事务都执行成功 时，整个事务才可以提交。这种a 1 lo rn o t ( 全提交或全不提交) 的 事务部署方式影响了整个系统的性能，同时也一定程度的影响了事 务的部署成功率。因而前人在传统事务模型的基础上提出了嵌套的 事务模型，即当出现某个子事务执行失败时，该模型只回滚部署失 败的子事务，而保留部署成功的节点的状态，然后使用失败节点的 替代节点来继续完成整个事务。 在已有的嵌套事务模型的基础上本文做了如下的工作：首先在 嵌套事务的基础上提出了动态的嵌套事务模型，即动态的寻找替代 子事务：当存在某个子事务执行失败时，找到该子事务节点的左右 邻居节点，寻找这两个邻居节点之间的其它路径，如果存在，则部 署该路径上的子事务；若不存在，则继续寻找该邻居节点的邻居节 点，并循环上述操作直到找到另一条路径来执行事务；其次本文使 用数学公式证明了在f o r c e s 路由器中动态的嵌套事务模型较嵌套 事务模型的优势，同进证明了该模型较传统的事务模型在时间上的 的优越性并通过计算机仿真实验使结果显得更直观。除此以外，本 文还研究了f o r c e s 路由器中的两种部署方式，即单播的部署方式和 组播的部署方式，通过公式证明了这两种方式的优缺点并提出最优 的部署方式；最后基于f o r c e s 协议中已有的对事务机制的描述，本 文分别对传统事务模型和动态的嵌套事务的实现过程进行了设计。 关键词：嵌套事务，子事务，封闭的嵌事务，开放的嵌套事务， 失败域； n i i i ii iii i i iuiii ii iu l y 2 0 7 0 0 7 4 r e s e a r c ho nt h ea p p l i c a t l 0 no fn e s t e d t r a n s a c t i o ni nt h ef o r c e sr o u t e r s a bs t r a c t t h es t r u c t u r eo ff o r c e sr o u t e rc o n t a i n sac o n t r o le l e m e n t ( c e ) w h i c h c o n t r o l sa n dm a n a g e sh u n d r e d so ff o r w a r d i n ge l e m e n t ( f e ) t h e r e a r e t r a n s a c t i o n si nt h ef o r c e sr o u t e r s u c ha sr o u t i n ga n dr e s o u r c er e v e r s e t h e t r a d i t i o n a lt r a n s a c t i o nm o d e lu s e ss t r i c t l yt w os t a g e ss u b m i ta g r e e m e n t ，t h a t i s w h e na n ys u b t r a n s a c t i o nf a i l s ，t h ew h o l et r a n s a c t i o nh a st ob e e nr o l l e db a c kt ot h e s t a t eb e f o r et h ee x e c u t i o n a n dw h i l ea l lo ft h es u b t r a n s a c t i o n se x e c u t e d s u c c e s s f u l l y , t h et h et r a n s a c t i o nc a nb ea l l o w e dt oc o m m i t s u c ha l lc o m m i to ra l l n o tc o m m i tw h i c hi sc a l l e da l lo rn o ts t r a g e g ya f f e c t st h es y s t e mp e r f o r m a n c ea n d a l s ot h e s u c c e s s f u lr a t e s ob a s e do nt h et r a d i t i o n a lt r a n s a c t i o nm o d e l ，t h e p r e d e c e s s o r sp r o p o s e dt h en e s t e dt r a n s a c t i o nm o d e l i nt h i s m o d e l ，i to n l yr oi l s b a c kt h ef a i l e ds u b t r a n s a c t i o na n dr e s e r v e t h es t a t eo ft h es u c c e s s f ul s u b t r a n s a c t i o n s ，a f t e rt h a t ，i tw i l lc h o o s ea na l t e r n a t i v et oc o n t i n u et h et r a n s a c t i o n e x e c u t i o n a c c o r d i n gt ot h ee x i s t i n gt r a n s a c t i o nm o d e l ，t h i sp a p e rh a sd o n et h e f ol l o w i n gw o r k s ：f i r s t l y , i tp r o p o s e st h ed y n a mi cn e s t e dt r a n s a c t i o nm o d e lt h a ti s t os e a r c hf o raa l t e r n a t i v es u b t r a n s a c t i o nd y n a m i c a l l y ：w h e nan o d ef ef a i l s ，f i n d o u tt h et w on e i g h b o rn o d e so ft h i sf ea n dt r yt of i n do u ta n o t h e rr o a db e t w e e n t h e s et w on o d e s ，i fi th a so n e ，t h e ne x e c u ti t ，i fn o t ，t h e nr o l lb a c kt h ew h o l e i l l t r a n s a c t i o n s e c o n d l y ，t h ep a p e rh a v em a d es t r a c t d e r i v a t i o n b ym a t i m a t i c a i f o r m u l a r sa n dp r o o f e dt h es u p e r i o r i t yo ft h ed y n a m i cn e s t e dt r a n s c t i o n b e s i d e s t h i s ，i th a sa l s od o n es o m ec o m p u t e rs i m u l a t i o n si no r d e rt om a k et h er e s u l tm o r e i n t u i t i v e t h i r d l y , t h i sp a p e ra l s os t u d i e dt h et w od e p l o y m e n tm o d eo f t r a n s a c t i o n s w h i c hi sc a l l e dt h eu n i c a s ta n dm u l t i c a s ta n dd i s c u s s e st h e a d v a n t a g e sa n d d i s a n v a n t a g e so ft h e s et w om e t h o d s ，a l s o ，i tp r o p o s e sab e s tw a y a tl a s t ，b a s e do n t h em e c h a n i s md e s c r i p t i o no ft h et r a n s a c t i o ni nt h ef o r c e sa g r e e m e n t ，t h ep a p e r h a sm a d ead e s i g nf o rt h et r a n s a c t i o nf i a tt r a n s a c t i o nm o d e la n dd y n a m i cn e s t e d t r a n s a c t i o nm o d e l k e yw o r d s ：n e s t e dt r a n s a c t i o n ；s u b t r a n s a c i o n ；c l o s e dn e s t e dt r a n s a c t i o n ；o p e n n e s t e dt r a n s a c t i o n ；f a i l u r ed o m i n e i v 1绪论 1 1研究背景及意义 1 1 1 f o r c e s 路由器的研究 在新一代网络的研究中提出了f o r c e s ( f o r w a r d i n ga n dc o n t r o le l e m e n t s e p a r a t i o n ) 协议，即转发件与控制件分离的协议，该协议将路由器的控制 单元从路由器体系结构中分离出去，实现了地域上的分布式分布。而f o r c e s 路由协议主要用于路由器控制单元和转发单元之间的通信与交互心1 ，目前，已 经产生了f o r c e s 协议的需求文档r f c 3 6 5 4 阳1 及f o r c e s 协议的框架文档 r f c 3 7 4 6 ，但其具体的协议实现还处于研究阶段。 f o r c e s 路由器不同于传统的路由器，一个f o r c e s 路由器支持多个c e 及 成百上千个f e ，c e 与f e 之间并不只是单跳，反而更多的是多跳，一个控制 单元c e 可以控制和管理多个f e ，同时一个f e 又可以被多个c e 管理，从而实 现了c e 对f e 的分布式管理旧1 。一个c e 和其控制下的多个f e 组成了一个网络 件n e ( n e t w o r ke l e m e n t ) 。在n e 中的每个f e 甲元都存在多个功能模块，每个 功能模块定义并决定了f e 所具有的功能，因而在f o r c e s 路由器中每个任务 都可以由多个具有不同功能的f e 组合来实现。当有任务到达时，主要由c e 来控制和决定需要哪些f e 来完成该功能，同时c e 与f e 相分离的特性又决定 了f e 会承担大量的p c 计算。图1 - 1 表示了一个n e 的结构定义，该图中列出 了2 个c e 和2 个f e 的情况。 图i - ine 概念图 1 1 2 网络中的事务处理研究 在数据库中事务是用户定义的一系列操作序列，是数据库应用程序的基 本逻辑单元。在数据库中事务具有严格的a c i d ( a t o m i c i t y 原子性、 c o n s i s t e n c y 一致性、i s o l a t i o n 孤立性、d u r a b i l i t y 持续性) 特性：原子性 是指每个事务被认为是一个不可分割的单元，即若一个事务由多个任务组成， 则只有当每个任务都成功完成时才认为该事务成功，只要存在一个任务失败 则整个任务就失败；一致性是指不管事务成功或者是失败，当事务使系统处 于某个状态时必须保持一致性；孤立性是指每个事务都独立执行，他与系统 中的其它事务是相互独立的，其执行的结果只有在执行成功时才能被看到， 因而外界并不能看到其执行的中间状态；持续性是指一旦一个事务提交，其 产生的影响将会永久性的存在1 。 传统的事务采用原子事务模型，在该模型中一个事务就是一个操作序列， 没有内部结构且严格遵守a c i d 特性。在传统的实时数据库管理系统中，事务 的管理是基于单层的控制结构即具有单个起始点和终止点的事务结构，其事 务调度和并发控制满足可串行化的正确性标准。传统的事务模型采用二阶段 提交协议，即当存在某个参加者部署失败时，整个事务就失败，从而必须进 行回滚操作，只有当所有的参加者都部署成功时，事务才允许提交，由于当某 个参加者部署失败时，对于那些部署成功的参加者也需要进行回滚操作，这种 2 要么全部执行要么全不执行的事务处理模型大大降低了事务的处理效率 。因 而，相对于传统的事务模型，一些高级的事务处理模型应运而生，如嵌套事务 模型、多层事务模型、分布式混合实时事务模型、移动事务处理模型、s a g a s 、 分支汇合事务模型、柔性事务模型等 1 。而在这些高级的数据库模型中，由于 其事务相对较长并且复杂度也较高，因而需要对这些事务提出截止期的要求| 8 ( c h e na n dg r u e n w a l d ，1 9 9 6 ) 。现有的嵌套事务模型主要集中在研究非实时 数据库系统的并发控制上9 州川n 2 1 叭川( m o s s ，1 9 8 5 ：f e k e t ee t a 1 ，1 9 8 7 ，1 9 9 0 ：w e i h l ，1 9 8 8 ：l e e a n d f e k e t e ，1 9 9 l ：h a r d e r a n d r o t h e r m e l ，1 9 9 3 ：m a d r i a ，1 9 9 7 ) 。在现有的模型中，两阶段锁协议是用于嵌套 事务中并发控制的最一般的方法，在此基础上，还提出了一些冲突解决方法， 主要是在实时的传统事务模型中应用一些高性能的优先级分配技术( a b b o t t a n dg a r c i a m o l i n a ，1 9 9 2 ：u l u s o ya n db e l f o r d ，1 9 9 3 ) ，这个方法确保了高 优先级的事务不会被低优先级的事务阻碍。基于高优先级的方法，我们对于 嵌套事务模型提出了一个实时的并发控制协议，称为具有高优先级的两阶段 锁( 2 p l h p n ) 引。 在f o r c e s 路由器中也存在着多种事务刚1 1 圳，比如路由路径和资源预留两 类事务。其发生事务部署失败的原因主要有两个方而：( 1 ) 由于节点自身的问 题而发生部署失败，主要是指节点发生故障或操作错误等；( 2 ) 在f o r c e s 路 由器中，一个f e 可以受到多个c e 的控制，因而某个控制节点在对某个转发 节点进行部署时，会由于该转发节点已被其它控制节点所占用而发生冲突， 从而造成该节点事务执行的失败甚至会发生重复失败的情况；( 3 ) 由于在 f o r c e s 路由器中，c e 与f e 间消息的发送和接收具有一定的截止期的要求， 超过截止期事务即执行失败。因而，在f o r c e s 路由器中采用传统的事务模型 的效率较低，综合以上情况，本文研究的主要内容之一就是在f o r c e s 路由器 中采用嵌套的事务模型。i 司时，通过研究f o r c e s 下事务的两种部署方式来避 免因为截止期而发生事务部署失败的情况，同时也进一步提高事务的部署效 率。 1 2 研究现状 1 2 1 嵌套事务模型 显式地包含另一事务的事务称为嵌套事务，被包含者称为子事务，包含 者称为其父事务，子事务又可包含其自身的子事务，其中p ( f l ，t ：) 表示t 。是f ：的 父事务，c ( t ，f 2 ) 表示f 。是f ：的子事务m 2 引。 定义1 ：设有数据库事务集t ，一个事务t t 称为根事务，当且仅当 一了f t ，t t ( p ( t i , 乞) ) 定义2 ：设有数据库事务集t ，一个事务t t 称为叶子事务，当且仅当 - - , 3 t t ，( c ( ，l ，2 ) ) 定义3 ：对于一个数据库事务集t ，f 。，f ：t ，当且仅当 c ( ，l ，2 ) v p ( ，i ，t z ) v ( 3 t t ( p ( “) a p ( f ，f 2 ) ) 则t i ，t 2 位于同一事务家庭的，记为r ( t 。，t 2 ) 。 定义4 ：设有数据库事务集t ，f l ，t ：t ，当且仅当 c ( ，毛) a c ( t 2 ，t o ( 一1 3 t 丁o f 3a c ( ，f ) 人c ( f 2 ，f ) ac ( f ，t 3 ) ) ，则称t 3 为t l 和t 2 的最 近共同祖先，记为l c a ( t ，t 2 ，f 3 ) 。 在嵌套事务模型中，一个嵌套事务可以有任意多的子事务，子事务又可 以有任意多自己的了事务，这样就形成了一棵事务树，顶层事务为事务树的 根，没有子事务的事务为叶子事务，处在同一层的事务称为兄弟事务；从根 事务到给定子事务的路径上的所有子事务为给定子事务的祖先事务，而从它 到术端的所有子事务称为其子孙事务他0 。 4 前人已有的研究是在父事务与子事务关系的基础止将嵌套事务分成开放 与封闭两类模型，本人通过阅读文件并进行概括总结，把嵌套事务模型从以 下四个不同的角度来进行分类。 1 2 1 1 从子事务与父事务和子事务之间的关系出发 ( 1 ) 封闭的嵌套事务模型( c l o s en e s t e dt r a n s a c t i o nm o d e l ) m o s s 于1 9 8 5 年提出了封闭的嵌套事务模型心引。并且提出了予事务的概念。 在该模型中，一个事务可以分解成若干个子事务，我们把原始事务定义为父 亲事务，子事务定义为孩子事务；在该事务模型中，只有当父亲事务成功提 交后其子事务才能成功提交并把它产生的结果存入永久存储区，如果一个父 亲事务失败，则它所有的子事务都必须撤销，由于在该模型中，一个子事务 的提交严格地受到了父亲事务的限制，因而称为封闭的嵌套事务模型妇引。 相对于传统的事务模型，封闭的嵌套事务模型有以下两个优点：( 1 ) 它 允许内部的予事务之间并发执行；( 2 ) 提供了更好的失败控件处理，即发生 失败的子事务相对于其兄弟事务来说是独立的，即一个子事务的失败并不会 导致整个事务部署失败。 ( 2 ) 开放的嵌套事务模型 开放的嵌套事务模型与封闭的嵌套事务模型的区别体现在：当一个子事 务成功提交后，其提交状态对其它事务是可见的并且在其父亲事务提交之前 允许释放锁，即在一个父亲事务提交之前，子事务释放锁，从而可以由其它 子事务获得，提前了其它子事务的执行时问，提高了事务的执行效率他引。可 见开放的嵌套事务模型不再严格地受到父亲事务的限制。i 司时为了防止由于 父亲事务的失败而导敛所有子事务的撤销，文献还提出了开放和安全的嵌套 事务典型，在该模犁中，引入了恢复点子事务的概念。恢复点子事务是指这 样一类事务：当该事务成功提交后，其祖先事务必须提交，一旦其祖先事务 失败，则必须选择一个其它事务来继续完成其事务或者等系统恢复后再重新 执行，由于恢复点子事务所具有的该特性，因而其同时也具有开放性，当恢 复点子事务提交后，其执行的结果就具有永久性，因而在他成功提交后即可 释放所持有的锁1 。 在上述两个模型巾，除了父事务与子事务之间的关系之外，子事务之间 也存在着四种关系。基于文献所述，嵌套事务模型中的子事务之间存在着以 下四种依赖关系：( 1 ) 优先( p r e c e d e n c e ) 关系( 使用符号 - 表示) ：若 置 墨) ，则墨必须在l 执行完成之后才能执行；( 2 ) 选择 ( a l t e r n a t i v e ) 关系( 使用符号表示) ：若s 墨则s 和l 是二选一的关系， 即要么执行s ，要么执行譬。即使在2 p c 的第一阶段两个子事务都已经准备 就绪，但最终只有一个子事务能被提交( c o m m i t ) ，另一个必须被回滚；( 3 ) 偏好( p r e f e r e n c e ) 关系( 使用符号表示) ：若s _ ，则表示s 和t 之间 已存在二者选一关系，但可以设定某项条件使得在同等情况下s ，要比墨优先 执行，即只有s 执行失败才能执行一，本文称薯是s 的备用子事务。显然， 偏好关系是一种特殊的选择关系，且在实际应用中，为了表示予事务的执行 顺序，往往根据某种策略或算法将选择关系转化为偏好关系；( 4 ) 平等关系 ( 使用符号il 表示) ：不存在以上三种关系的子事务，则是平等关系，若s0 s ， 表示s 和s ，最终都必须被提交，但其执行的先后顺序是任意的幢引。 图卜2 给出了一个嵌套事务的基本组成图，事务t 是一个顶层事务，它启动 两个子事务t 1 和t 2 ，子事务t 1 启动它的子事务t 1 1 和t 1 2 ，子事务t 2 启动了它 的子事务t 2 1 和t 2 2 ，并且这两个子事务之间存在选择关系。左图中子事务t 2 的子事务t 2 1 、t 2 2 都无法提交，因此事务t 决定回滚整个事务，事务执行失败。 6 右图中子事务t 2 的子事务t 2 1 无法提交，协调者寻找t 2 1 的备用子事务t 2 2 ，当 t 2 2 执行成功时，协调者决定提交整个事务，事务执行成功。该图表明子事务 之间存在的特殊关系决定了整个事务是提交还是回滚。 t 1 l t - t i 1 2 飞 必 t 2 2 事务t 回滚事务t 提交 图卜2 嵌套事务 因而在嵌套事务模型中，一个子事务的失败不必一定要求其父事务【石l 滚， 父事务的执行并不具有严格的原子性，其父事务可以有如下选择：1 ) 重启该子 事务；2 ) 执行替代补偿”事务；3 ) 不予管理该子事务，父事务夭折1 2 引。 1 2 1 2从嵌套事务的部署方式出发 在嵌套事务中，父事务可以包含成百上千个子事务，因而每一个事务都 需要对多个参与者进行部署。从对多个参与者进行事务部署的方式出发，我 们可以把嵌套事务分成两类模型：单播和组播。 在单播的嵌套事务模型中。管理者对参与者进行逐个部署，即在同一时 间只财一个参与者进行部署，只有当该参与者执行成功后，才对下一个参与 者执行事务，依此类推。因而在单播的事务部署方式中，存在着对各个子事 务分配优先级心刚的问题。现有的主要分配策略有以下六种： 1 r p ：该策略，股不考虑事务的实时特性比如截止期、数值、时间槽等， 而是随意的分配优先级( h a t i t s ae ta 1 1 9 9 1 ) 。一个嵌套事务的不同子事务 可能被分配不同的优先级f 2 引。其优先级的分配公式为：尸( z ) 卜r a n d o m ( o ，0 0 ) l 2 ，l 2 l 1 乏，g m 弦谗 么 h e d h v e d r p 。导致这种结果的主要因素，首先是访问冲突的可能 性。一个嵌套事务如果有更多的叶子子事务，更大的事务大小，更深的层次， 则很可能会导致高的访问冲突。第二是子事务的时间槽。一个子事务拥有更 多的时间槽会更有可能达到截止期。在设计f h r n 调度策略时时间槽和形状特 征及其通信延迟都是考虑因素。 在组播的嵌套事务模型中，管理者对事务执行过程中所有需要执行的参 与者进行同步部署，即在同一时间对所有的参与者发出执行请求。 9 1 2 1 3从嵌套事务的子事务的部署方式出发 在嵌套事务中，一个父事务可以包含多个子事务，并且某些子事务具有 相同的功能，可以完成同一类任务，我们将这些具有相同功能的子事务集合称 为功能替代集。从功能替代集出发，我们可以把嵌套事务模型分成以下三类： ( 1 ) 预先准备子事务 该种方式下，系统在执行事务时，寻找好所有具有相同功能的子事务， 组成一个功能替代集，但同一时问内只执行其中的一个子事务，只有当该子 事务执行失败时，才在己寻找好的功能替代集中选择执行另一个新的子事务。 ( 2 ) 并发执行子事务 该种方式下，在执行个事务时，所有具有相同功能的功能替代子事务 集都同时进行事务的部署，但一次事务部署过程中只有一个子事务可以提交。 该方法增加了系统的开销，但当子事务失败率较高的情况下，节约了重新部 署备份子事务的时间。 ( 3 ) 动态准备子事务 该种方式下，在执行一个事务时，根据所有子事务在两阶段提交协议第 一阶段的响应( 成功或者失败) 动态生成相应失败处理策略。即选择最优路 径执行事务，不事先寻找功能替代子事务，当子事务部署失败时，再寻找具 有相同功能的子事务进行部署。 1 2 1 4从嵌套事务部署的目标出发 任意个事务的执行都需要一定的消耗，不管是时间花费或是资源上的 花费，并且不同的模型对花费的影响较大，因而研究嵌套事务部署时的花费 具有重大意义，我们从两个方面来研究。 ( 1 ) 考虑事务执行时间的嵌套事务模型。即在事务部署过程中特别是在 选择事务的调度方式的时候只考虑时间花费这个凶素，而不考虑其执行成本 1 0 上的花费。 ( 2 ) 考虑事务执行成本的嵌套事务模型。即在事务执行过程中当存在子 事务部署失败时，对于已执行部署的节点存在部署花费成本，同时对于那些 已经部署成功且提交的节点需要用补偿事务h 川剜拈2 1 部署来进行撤销，即需要 同时考虑部署花费成本和补偿花费成本。 1 2 2 嵌套事务的应用 1 2 1 节主要描述了嵌套事务模型中的相关概念，因而本节主要研究前人 关于嵌套事务模型在具体环境中的应用。 1 2 2 1实时嵌套事务 主动实时数据库广泛应用于财政市场的电子证券，股票市场，网络管理 和生产过程控制，在该数据库中由于事务可以触发其他任意深度、存在各种 依赖关系的实时事务，其事务处理非常复杂b4 1 5 1 。因而，一个事务的处理不 仅要弄清楚事务的截止期，同时还有其与其它事务的依赖关系1 35 1 。在传统事 务处理过程中，实时事务在预分析处理后就开始等待系统调度，如果由于某 种原因或者意外使得该事务失败了，则整个事务就执行失败，即使重新调试 执行该事务也可能由于事务超过了截止期而发生再次失败的情况。因而，在 嵌套的实时环境中采用传统的严格的二阶段事务提交策略会严重的影响实时 事务的成功率。因而为了提高实时事务在嵌套环境下的提交成功率，我们引 入了事务功能替代集的概念。 事务功能替代集是指一个具有相同功能子事务组成的事务集合，它由若 干个任务组成，每个任务都包含了一组具有功能等价的子事务，称为功能替 代集，那么由每一个任务中的一个成员组成的集合称为该事务的一个功能替 代，所有功能替代的集合称其为功能替代集。虽然这些功能等效的功能替代 事务的性能各不相同，但都能完成该事务所要达到的功能，因而只要其中一 个功能替代能成功提交，该实时事务就能成功提交心。 由于功能替代是实时事务的组成成员，它能完成所对应的实时事务的功 能，所以它也具备了实时事务的基本特性：定时限制、结构复杂性、结果补 偿性、语义相关性和执行依赖性等：同时一个实时事务可以有多个功能替代子 事务，在每一次事务部署过程中，只对一个子事务进行事务部署，如果在部署 该事务时发生失败，而整个事务的截止期未到，则系统可以选择另外个功 能替代子事务进行部署，只要有一个功能替代子事务成功执行，则该事务就 可以成功提交，只有当所有的功能替代子事务都部署失败时，该事务才可以 失败回滚1 。 所以，在嵌入式实时环境下实时事务t = ( s ，e ，r ，z t ，f c ) 的执行模型变为 t ( f a ，e ，r ，z t ，t o ) ，剐：= ilzi - m ，f x , ：； ei l 5 刀) 其中f a 为事务t 的 功能替代集，m 为t 的功能替代个数。 事务与功能替代之间的关系是对象和实例的关系，因此事务和功能替代 在结构上是同构的。对于图卜3 的实时事务t ，其中p ( 1 f 6 ) 是该事务t 的任 务，只有两种实现方式只，和只：。则该实时事务的功能替代集由图卜3 来表示。 功能替代的引入，可以极大地增强实时事务适应系统运行环境的能力， 提高实时事务的部署成功率。在实时事务参与系统调度之前，就分离出其功 能替代集，可以避免在系统调度时花费额外宝贵的时间开销，提高事务的执 行效率。分解的主要思想是从每一任务中选取一个子事务构成功能替代，直 至生成所有的功能替代剐。 1 2 图1 - 3 实时事务t 的功能替代集 1 2 2 2 移动嵌套事务( c e t ) 事务处理从集中式系统( g r a y r e u t e r 2 0 0 3 ) 和分布式系统 ( m a r s h 。2 0 0 0 ：v a l d u r i e z ，1 9 9 9 ：r a m ，d o ，d r e w ，1 9 9 9 ) 发展到了移动设备的事 务处 理，即称为移动事务 ( d u n h a m & k u m a r ，1 9 9 9 ：m a d r i a b h a r g a v a ，1 9 9 8 ：m u r t h y ，2 0 0 1 ：s e r r a n o a l v a r a d o ，r o n c a n - c i o & a d i b a ，2 0 0 1 ) 。目前，在固定的有线网络内，这些移动事务通 过数据库管理系统存取数据，集中式事务的数据管理是由当地的有线网络内 的d b m s s 负责的；同时，在分布式事务处理机制中，一个事务可以被分割成 子事务，这依赖于包含请求对象的节点位于哪个网络，因而协调者需要与请 求的节点位于同一个网络内旧1 。协调者使用二阶段提交协议，为了确保每个 子事务的执行，虽然整个事务的执行是在一个有线网络内，节点之间也有可 能是物理分离，可以从相差几英尺到更大的地理距离，但事实上，他们是通 过网络联结在一起的，而且他们的地址也是可以被获知的。 移动事务处理与分布式事务处理不| 一，它的物理地址会发生变化，l 一时， 一个移动设备的一个事务开始可能是由另一个地点的不同的节点来完成，除 此以外，对于相同的用户我们可能会启动不同的设备；但是，真正的事务处 理是由有线网络内的当地的数据库管理系统来完成的7 | 。在移动分布式计算 环境中，事务移动性和无线网络固有的缺陷使得传统的原予事务模型不足以 描述结构复杂的移动实时事务，而嵌套事务模型旧1 能较好地捕述该结构。该 模型的优点是放松了对事务a c i d 特性的要求，提高了根事务内部子事务执行 的并发度，能较好地支持分布式实时事务的执行，为了更好的适应移动实时 的特点，在嵌套事务模型的基础上提出了功能替代任务n 引乜引。 定义1 设任务t k , j 与啦。为不同的任务，若按应用语义，它们实现同一事务 t 的一个功能，则称r 七”和，七，。与t 的该功能等价，且称嘞和t k , 。为t 的功能替代 任务 定义2 由所有与事务t 的一个任务功能等价的任务组成的集合称为t 的 一个功能替代集，记为f a s i 。f a s i 中的每个任务都称为t 的一个功能替代子事 务 通常，一个f a s i 中的功能替代子事务是按选优次序逐个执行的，直到某一 个执行成功或该功能替代集所有子事务都夭折为止。但这种方式容易导致实 时事务超截止期，而应选择多个替代子事务同时在一个或多个结点上执行。此 时，只要一个替代子事务执行成功，相关的任务就成功。虽然这种并行调度方 式在一定程度上增加了系统开销，但整个系统的性能将由于提高了事务的成 功率而得到改善。 移动的嵌套事务模型： 一个m r t t 可能具有多个功能替代集f a s i ，i = l ，2 ，n ；每个功能替代集 f a s i 又可能由一个或多个功能替代子事务组成，这样就形成了一个嵌套结构 事务一个移动实时事务可定义如下： 定义3 一个移动实时事务m r t t 是一个四元组：m r t t ：= ( t s ，r ，z t ，c ) ，其 中， t s ：车 olw ，t i sa s u b t r a n s a c t i o ”f u n c t i o n a 砂p q u i v a l e 刀t t ot a s kt k , ，j = l ，2 ，m i ) 1 4 t k i ：2 f a s i = 勺h ，乞t i j i s as u b t r a n s a c t i o nf u n c t i o n a ll y r ：= as e to fr e s o u r c e sr e q u i r e db yt a s ki nt s 么f ：- f l t e m p o r a lo r d e r i n go nt s c ：= as e to fc o n s t r a i n so nt sa n dr 按照上述定义。只要每个功能替代集中有一个子事务可提交，则该m r t t 可 提交。故在此，m r t t 的提交原子性是指，当其提交时，它的每个功能替代集有 个也只有一个子事务提交：若有一个f a s i 不可提交，则该m r t t 夭折。在这种 意义上，m r t t 的原子性相对于传统原子性得到了放松，因为它只要求部分而 不是所有子事务都提交。显然，这种放松的原子性仍然能够保证移动实时事务 的正确性。 为了保证分布式事务的正确执行，需要一个协调者来协调各子事务的执 行。通常该协调者由始发场地上的子事务担任，但不可靠的无线网络使得发 出m r t t 的m h 上的子事务不宜作为m r t t 执行的协调者，而应由m h 所在无线单元 中的固定主机f h ( f i x e dh o s t ) 上的子事务承担。当m h 迁移到新的单元时，m r t t 的协调者乙也应迁移到新的单元，且有关提交的上下文信息应由老的协调者 传递给新的协调者，但是，由于乞。的位置可能发生变化，当采用协调者和参 与者两层结构提交时，一方面，为保持与当前协调者交换消息，每个参与者 都必须跟踪t 。位置的变化；另一方面，功能替代会增加m r t t 子事务数鼍，加重 协调者与参与者的通信负担，因此，带宽有限的无线通信信道可能出现阻塞。 如图卜4 所示，对于一个m r t t ，乙是m r t t 的总协调者；f ，是子事务( 参与 者) ；剐墨。，是每一个功能替代集的协调者，由任意一个在固定场地执行的子事 务兼任，负责收集其所在功能替代集中子事务的报告，并将该功能替代集的执 行结果向乙报告。这样，每个f a s c 。，o e rf a ，跟踪乙位置的变化，且也只需 一个子事务与乞通信，从而减轻了f c 。的通信负担。从图中可知一个移动实时事 务m r t t 分为三个任务置( 1 i 3 ) 。而其中每个任务又分为三个功能等价的 子事务0 ( 1 i n 3 ，l j 3 ) 。对于每个任务如s t 而言，只要其中任何一个f ，执 行成功，则表示该任务可完成：而只有当其所有0 都执行失败，则该毛不 可完成。显然嵌套事务模型中的功能替代增加了事务执行的可靠性。 t a s k 2 图卜4 移动实时事务的功能替代集 1 3 本文的内容和创新点 1 3 1 本文的研究内容与主要贡献 在f o r c e s 路由器中，存在多个c e ( 控制节点) ，其对f e ( 转发节点) 的 控制是分布式的。c e 在对路径上的各个f e 节点执行事务时，主要包括两个过 程：c e 与f e 之间的消息通信和f e 节点自身的计算过程。其通信与计算之间 存在一定的时间比例并且该比例不是一定的。凶而在第三章和第四章我们根 据通信与计算之间的花费比例关系来进行研究。 ( 1 ) 当通信时间大于计算时问时，即c e 发送消息给f e 时，我们几乎可 以忽略c e 的等待时间而直接收到了f e 的回复消息，因而当c e 对f e 进行一 个一个部署时，其可以在完成个f e 的部署后，再进行第二个节点的部署。 ( 2 ) 当通信时间远远小于计算时间时，f e 节点内的计算成本比较高，即 1 6 c e 每对f e 发送一个指令都要占用很长的c p u 资源，因而研究c p u 的调度问题 就有很大的意义。 同时由于c e 在执行一个事务时会发生f e 的执行失败甚至是重复失败的 问题，因而使用传统的事务模型执行事务的效率较低，本文通过分析研究， 在原有的嵌套事务模型的基础上提出了动态嵌套事务模型。同时，由于存在 多个节点，并且执行过程中会发生c p u 资源的占用，因而在嵌套事务模型的 基础上，为了进一步提高事务的执行效率，本文还将在前人研究的基础上提 出自己的事务的部署方式并加以证明。 本文共分为六个部分，主要内容如下： 第一章：研究f o r c e s 路由器的构成及其内部存在的事务类型。同时提出 了传统的事务模型的缺点及研究嵌套事务模型的必要性。通过阅读文献从多 个角度概括总结了嵌套事务模型的类型及其在现实生活中的应用。 第二章：在已有的嵌套事务模型的基础上，分析了在f o r c e s 路南器下提 出动态的嵌套事务模型的必要性，并给出了该模型的数学表示和算法分析， 通过两个实例使算法更容易理解。 第三章：首先分析并证明了f o r c e s 路由器中我们选择动态嵌会事务模型 的原因，然后通过数学公式严格地证明了动态的嵌套事务模型较传统的事务 模型的优势，在此基础上分别研究事务部署的节点个数和嵌套次数对这两种 模型的影响，并通过数字仿真实验使结果显得更为直观。 第四章：提出在f o r c e s 路由器巾存在的两类事务部署方式：单播方式和 组播方式。分析并证明了这两种部署方式的优缺点。综合两者的特点提出了 嵌套事务中的最优部署方法。 第五章：首先分析在f o r c e s 协议中已有的事务部署机制和心跳机制，在 此基础上对传统的事务和动态的嵌套事务两个模型给出了详细的设计流_ j i 旱及 函数分析。 1 7 第六章：总结了完成整篇论文所作的工作，并在此基础上对下一步工作 进行展望。 1 3 2 本文的创新点 本文的创新点主要有以下几点： ( 1 ) 提出了动态嵌套事务模型并证明了该模型适合f o r c e s 路由器的原因 及优势。 ( 2 ) 通过数学公式证明了动态的嵌套事务模型较传统事务模型的优越性 以及部署环境的变化对这两个事务模型的影响，最后通过数字仿真实验来呈 现结果。 ( 3 ) 分析和研究了两种事务部署方式在f o r c e s 嵌套事务中的优缺点，并 针对他们各自的特点提出了最优部署方法。 ( 4 ) 在f o r c e s 路由器中，对传统事务模型及动态的嵌套事务模型的进行 了实现的设计。 2f o r c e s 路由器中动态的嵌套事务模型 通过1 1 节和1 2 节对前人工作的研究，我们发现从传统事务模型到嵌 套的事务模型，其事务的执行效率得到了提高，本章将通过研究f o r c e s 路由 器的事务特点，提出适合该环境下的事务模型并对该模型进行分析。 2 1 提出动态的嵌套事务模型的必要性 从本文1 2 1 节和1 2 2 节的研究出发，在f o r c e s 路由器中，由于其本 身的环境与实时事务和移动事务存在着差异，因而本文在原来的嵌套事务模 型的基础上采用动态准备子事务的方式，称为动态的嵌套事务模型。采用该 模型的必要性及其优势主要从以下方面进行分析 1 f o r c e s 路由器中：一个c e 下存在多个f e ，c e 管理着f e 上的资源分 配及拓扑结构。因此这类事务可以按照路由并针) c = ! f 路由上各f e 节点的情况进 行子事务的划分，从而- 口j 以将子事务与具体f e 相绑定，该特点符合了嵌套事 务的事务分解特性。 2 在f o r c e s 路由器中，c e 对f e 的嵌套事务包括以下两类过程：路由路 径和资源预留。由于在路径部署过程中会发牛部分f e 的部署失败，从实时嵌 套事务和移动嵌套事务中我们也可以看出采用传统模型执行事务的效率较 低，因而在f o r c e s 路由器中我们采用嵌套事务模型并运用功能替代集的功能。 其优势体现在： ( 1 ) 提高了整个事务执行的成功率。采用嵌套事务模型时，当存在执行 失败的结点时，进行部分回滚并寻找其替代结点重新部署，减少了需要重新 部署的结点数目，从而提高了事务执行的成功率。而采用传统方式，由于每 次出现执行失败结点时，都要f 1 3 i 滚整个事务再进行重新部署，因而其整个事 务的执行效率较低。 1 9 ( 2 ) c e 的运行时间显著减少。c e 的执行时间与需要进行部署的节点的个 数有着密切的联系，在嵌套事务模型中对于每次新的事务，其传统的事务部 署路径与嵌套事务部署路径是相同的，而嵌套事务只需执行那些未执行过的 结点，因而在每次新的事务中，嵌套事务需要部署的节点个数少于传统的部 署方式下需要部署的节点个数，从而减少了c e 的运行时间。 ( 3 ) 减轻了c e 的运行负担。一个c e 管理着多个f e ，因而减少其需要重 新部署的f e 节点的数目也就减少了c e 运行的负担。 3 在f o r c e s 路由