（计算机应用技术专业论文）移动广播环境中分布式实时事务并发控制机制的研究.pdf

摘要 由于大量潜在的移动计算应用的服务需求 例如实时交通监控系 统和移动股票交易 移动分布式实时数据库系统 m o b i l ed i s t r i b u t e d r e a l t i m ed a t a b a s es y s t e m s m d r t d b s s 已经受到了越来越多的关 注 而且随着不同种类网络的迅速发展 移动计算技术将会引起未来 信息系统在使用 设计和发展等一系列的技术变革 移动计算技术一 直是当前计算机网络与通信技术领域内的前沿和重点研究课题 因 此 展开对移动计算技术的有关理论与应用技术方面的研究有非常重 要的理论意义和实际意义 一般来说 移动计算环境是一个分布式的动态运行环境 而且其 传输带宽是不对称的 从服务器到移动主机 m o b i l eh o s t s m h s 的 传输容量要远大于从m h s 到服务器的传输容量 由于无线传输带宽 的限制和频繁地断接 传统的并发控制协议已经不再适应于这种不对 称的传输带宽环境 在m d r t d b s s 中广播数据已经成为广泛接受的 方法 目前移动广播环境中的移动分布式实时事务处理是移动计算理 论与应用的重要研究方向 而移动广播环境中的并发控制机制则是 m d r t d b s s 的一个最主要的核心技术 有鉴于此 本文对移动广播环境中分布式实时事务并发控制机制 进行了深入的研究和探讨 论文的主要研究工作和贡献体现在以下几 方面 1 提出了m v i r v i n m u l t i v e r s i o n i n v a l i d a t i o nr e p o r t v a l i d a t i o n i n f o r m a t i o n 数据广播协议 给出了多版本广播通道结构 服务器在 广播周期开始时 广播上一个广播周期在服务器提交事务的有效性确 认信息v i n m h 通过接收服务器广播v i n 对移动实时事务进行 局部预有效性确认 2 提出了多版本动态调整串行次序方法 在移动广播环境中重 启动一个移动事务开销较大 通过多版本动态调整事务串行次序 可 以避免不必要的事务重启动 在多版本机制写 写操作对不再是冲突 的 因为它们产生不同的版本 3 提出了移动分布式实时多版本两阶段有效性确认方法 在 m h s 上所有事务进行局部预有效性确认 如果移动事务通过局部预有 效性确认 必须提交到服务器进行局部最终有效性确认 如此提前进 行数据冲突检测 有效地节省了处理时间和通信资源 4 提出了关于m d r t d b s s 的三层提交协议结构 保证了移动分布 式实时事务的原子性 在低层 如果移动只读事务所有读数据项通过 预有效性确认 即可提交 移动只读事务的响应时间大大降低 在中 间层 如果移动实时更新事务在服务器上通过最终有效性确认 则可 局部提交 而在项层 移动分布式实时事务需要进行全局有效性确认 以保证分布串行性 5 提出了移动广播环境中d m v o c c m d a 2 p l v d i s t r i b u t e d m u l t i v e r s i o n o p t i m i s t i cc o n c u r r e n c y c o n t r o lw i t hm u l t i v e r s i o n d y n a m i ca d j u s t m e n tu s i n gt w o p h a s el o c a lv a l i d a t i o n 并发控制协议 处理移动分布式实时事务 m h s 上所有事务使用向后有效性确认机 制执行局部预有效性确认 与上一个广播周期在服务器提交的事务进 行有效性确认 通过局部预有效性确认的事务 提交到服务器进行局 部最终有效性确认 新协议消除了移动只读事务和移动更新事务之间 的冲突 使用多版本动态调整串行次序 避免了不必要的事务重启动 移动只读事务能阻塞提交 大大降低了移动只读事务的响应时间 增 加了m h s 与广播通道断开的容忍度 6 证明了本文所提出的d m v o c c m d a 2 p l v 协议的正确性 并对所提出的d m v o c c m d a 2 p l v 协议进行了模拟实验 模拟结 果表明提出的新并发控制协议在延误截止时间率 重启动率 提交率 等方面性能要优于其它协议 在高系统负载下 m h s 与网络高断接 概率下 d m v o c c m d a 2 p l v 协议性能也显著优于其它协议 本文的研究工作对m d r t d b s s 的设计与研究具有重要的理论和 实践意义 关键词 移动分布式实时数据库系统 多版本乐观并发控制 多版本 动态调整 局部预有效性确认 多版本数据广播 i i a b s t r a c t t h er e s e a r c hi nm o b i l ed i s t r i b u t e dr e a l t i m ed a t a b a s e s y s t e m s m d r t d b s s i sr e c e i v i n gg r o w i n ga t t e n t i o nd u et oal a r g en u m b e ro f p o t e n t i a l m o b il e c o m p u t i n ga p p l i c a t i o n s s u c h a sr e a l t i m et r a f f i c m o n i t o r i n gs y s t e m sa n dm o b i l es t o c k w i t ht h er a p i dd e v e l o p m e n to f d i f f e r e n tk i n d so fn e t w o r k s m o b i l ec o m p u t i n gt e c h n o l o g yl e a d st oat r u e m u t a t i o ni nt h eu s e d e s i g na n dd e v e l o p m e n to ff u t u r ei n f o r m a t i o n s y s t e m s m o b i l ec o m p u t i n gt e c h n o l o g yi sa l lt h r o u g hv e r yi m p o r t a n t r e s e a r c ht o p i ci na r e ao fc o m p u t e rn o t w o r ka n dc o m m u n i c a t i o n t h u s t h e r e s e a r c ho fm o b i l ec o m p u t i n gt e c h n o l o g yi nt h e o r ya n da p p l i c a t i o nh a s v e r yi m p o r t a n tt h e o r e t i c a la n dp r a c t i c a ls i g n i f i c a n c e m o b i l ec o m p u t i n ge n v i r o n m e n t sa r ed i s t r i b u t e dd y n a m i c l yr u n n i n g e n v i r o n m e n t s t h ec o m m u n i c a t i o nb a n d w i d t hi s a s y m m e t r i c t h e b a n d w i d t hf r o mm o b i l eh o s t s m h s t ot h es e r v e ri s v e r y l i m i t e d c o m m u n i c a t i o nc a p a c i t yf r o mt h es e r v e rt om h si s r e l a t i v e l ym u c h g r e a t e rt h a nf r o mm h s t ot h es e r v e r o w i n gt ol i m dw i r e l e s sb a n d w i d t h a n df r e q u e n td i s c o n n e c t i o n s t r a d i t i o n a lc o n c u r r e n c yc o n t r o lp r o t o c o l sd o n o ts u i tf o rm o b il eb r o a d c a s te n v i r o n m e n t b r o a d c a s td a t ah a sb e c o m ea w i d e l ya c c e p t e da p p r o a c ho fc o m m u n i c a t i o ni nm d r t d b s s n o w m o b i l ed i s t r i b u t e dr e a l t i m et r a n s a c t i o n p r o c e s s i n g i sv e r yi m p o r t a n t r e s e a r c hd i r e c t i o no f m o b i l ec o m p u t i n gt h e o r ya n da p p l i c a t i o ni nm o b i l e b r o a d c a s te n v i r o n m e n t s t h ec o n c u r r e n c yc o n t r o lm e c h a n i s mi sc r u c i a l t e c h n o l o g yi nn f d m b s s t h e r e f o r t h et h e s i ss t u d i e s t h o r o u g h l yc o n c u r r e n c y c o n t r o l m e c h a n i s mf o rd i s t r i b u t e dr e a l t i m et r a n s a c t i o n si nm o b i l eb r o a d c a s t e n v i r o n m e n t s t h em a i nc o n t r i b u t i o n sa r ea sf o l l o w s 1 m v 二i r v i n m u l t i v e r s i o n i n v a l i d a t i o nr e p o r t v a l i d a t i o n i n f o r m a t i o n i sp r e s e n t e d w r ei n t r o d u c em u l t i v e r s i o ns t r u c t u r eo f b r o a d c a s tc h a n n e l a tt h eb e g i n n i n go fe v e r yb r o a d c a s tc y c l e t h es e r v e r b r o a d c a s t sv a l i d a t i o ni n f o r m a t i o n v r n o fc o m m i t t e dt r a n s a c t i o n si nt h e l a s tb r o a d c a s tc y c l e t h em h sp e r f o r ml o c a lp r e v a l i d a t i o nf o rm o b i l e r e a l t i m et r a n s a c t i o n sb yr e c e i v i n gv i n 2 t h em u l t i v e r s i o nd y n a m i ca d j u s t m e n to fs e r i a l i z a t i o no r d e ri s p r e s e n t e d t h ec o s to fm o b i l et r a n s a c t i o nr e s t a r ti sv e r yh i g h t h em a i n p u r p o s eo fm u l t i v e r s i o nd y n a m i ca d j u s t m e n to fs e r i a l i z a t i o no r d e ro f t r a n s a c t i o n sa tv a l i d a t i o ni st op r e v e n tu n n e c e s s a r yt r a n s a c t i o nr e s t a r t s t h e r ei sn o tw r i t e w r i t ec o n f l i c ti nm u l t i v e r s i o nm e c h a n i s mb e c a u s e t r a n s a c t i o n sw r i t ed a t ai t e m so nd i f f e r e n tv e r s i o n s 3 t h em u l t i v e r s i o nt w o p h a s ev a l i d a t i o ni sp r e s e n t e d a tt h em h s a l lm o b i l et r a n s a c t i o n sh a v et o p e r f o r m a1 0 c a l p r e v a l i d a t i o n t r a n s a c t i o n st h a ts u r v i v ei n1 0 c a lp r e v a l i d a t i o nm u s tb es u b m i t t e dt ot h e s e r v e rf o rl o c a lf i n a lv a li d a t i o n s u c ha ne a r l yd a t ac o n f l i c td e t e c t i o n f e a t u r ec a ns a v ep r o c e s s i n ga n dc o m m u n i c a t i o nr e s o u r c e s 4 at h r e e t i e rc o m m i ts t r u c t u r ei sa l s op r o p o s e d w h i c hc a n g u a r a n t e et h ea t o m i c i t yo ft h em o b i l ed i s t r i b u t e dr e a l t i m et r a n s a c t i o n s i nb o t t o ml a y e r am o b i l er e a d o n l yt r a n s a c t i o na tm hc a nb ec o m m i t t e d i fi tp a s s e sa l lt h el o c a lp r e v a l i d a t i o ni nc o u r s eo fi t se x e c u t i o n r e s p o n d t i m eo fm o b i l er e a d o n l yt r a n s a c t i o n si sg r e a t l yi m p r o v e d i nm i d d l el a y e r i fm o b i l eu p d a t et r a n s a c t i o n sc a np a s sf i n a l l o c a lv a l i d a t i o n t h e yc a nb e c o m m i t t e dl o c a l l y i nt o pl a y e r m o b i l ed i s t r i b u t e dt r a n s a c t i o n sa r en e e d e d a g l o b a lv a l i d a t i o nf o rd i s t r i b u t e ds e r i a l i z a b i l i t y 5 d o c c a 2 l p v d i s t r i b u t e d m u l t i v e r s i o no p t i m i s t i c c o n c u r r e n c yc o n t r o l w i t hm u l t i v e r s i o nd y n a m i ca d j u s t m e n tu s i n g t w o p h a s el o c a lv a l i d a t i o n p r o t o c o li sd e s i g n e df o rp r o c e s s i n gm o b i l e d i s t r i b u t e dr e a l t i m et r a n s a c t i o n si nm o b i l eb r o a d c a s te n v i r o n m e n t s a t t h em h s a l lm o b i l et r a n s a c t i o n s p e r f o r m l o c a l p r e v a l i d a t i o n o f t r a n s a c t i o n sb yu s i n gb a c k w a r dv a l i d a t i o nm e c h a n i s m t h e l o c a l p r e v a l i d a t i o np r o c e s si sc a r r i e do u ta g a i n s tc o m m i t t e dt r a n s a c t i o n sa tt h e s e r v e ri nt h el a s tb r o a d c a s tc y c l e t r a n s a c t i o n st h a ts u r v i v ei nl o c a l p r e v a l i d a t i o nm u s tb es u b m i t t e dt ot h es e r v e rf o rl o c a lf i n a lv a l i d a t i o n t h en e wp r o t o c o lc a ne l i m i n a t ec o n f l i c t sb e t w e e nm o b i l er e a d o n l ya n d m o b i l eu p d a t et r a n s a c t i o n s a n dr e s o l v ed a t ac o n f l i c t sf l e x i b l yu s i n g m u l t i v e r s i o n d y n a m i ca a j u s t m e n t o fs e r i a l i z a t i o no r d e rt oa v o i d u n n e c e s s a r yr e s t a r t so ft r a n s a c t i o n s m o b i l er e a d o n l yt r a n s a c t i o n sc a l lb e c o m m i t t e dw i t hn o b l o c k i n g a n dr e s p o n dt i m eo fm o b i l er e a d o n l y t r a n s a c t i o n si sg r e a t l yr e d u c e d t h et o l e r a n c eo fm o b i l et r a n s a c t i o n so f d i s c o n n e c t i o n sf r o mt h eb r o a d c a s tc h a n n e l i si n c r e a s e d 6 t h ec o r r e c t n e s so ft h ec o n c u r r e n c yc o n t r o lp r o t o c o lp r e s e n t e d d m v o c c m d a 2 p l v i sp r o v e d as e r i e so fe x t e n s i v es i m u l a t i o n e x p e r i m e n t sh a v eb e e np e r f o r m e dt oe v a l u a t et h ep e r f o r m a n c eo ft h en e w p r o t o c 0 1 t h es i m u l m i o nr e s u l t ss h o wt h a tt h ec o n c u r r e n c yc o n t r o l p r o t o c o lp r o p o s e do f f e r sb e r e rp e r f o r m a n c et h a no t h e rp r o t o c o l si nt e r m s o fm i s sr a t e r e s t a r tr a t e c o m m i tr a t e u n d e rh i g hs y s t e ml o a da n dh i g h d i s c o n n e c t i o n d m v o c c m d a 一2 p l vp r o t o c o li sa l s o o f f e r sb e t t e r p e r f o r m a n c et h a no t h e rp r o t o c o l s t h er e s e a r c hi nt h et h e s i s p r o v i d e sat h e o r e t i c a la n dp r a c t i c a l s o l u t i o nf o ri m p l e m e n t i n gc o n c u r r e n c yc o n t r o li nm d r t d b s s k e yw o r d s m o b il e d is t r i b u t e dr e a l t i m ed a t a b a s e s y s t e m s m u l t i v e r s i o n o p t i m i s t i cc o n c u r r e n c yc o n t r o l m u l t i v e r s i o nd y n a m i c a d j u s t m e n t l o c a lp r e v a l i d a t i o n m u l t i v e r s i o nd a t ab r o a d c a s t v 图目录 图1 1 移动分布式数据库体系结构 2 图2 1 广播磁盘 2 2 图2 2 数据广播 2 3 图2 3 使用f i r 广播快速更新的数据 2 4 图2 4 广播通道 2 5 图3 1 实时事务的分类 2 9 图3 2m h 过界切换 3 0 图3 3 三并发事务执行历史片段 3 l 图4 1 移动分布式实时数据库三层提交结构 4 8 图5 1 模拟系统结构 5 7 图5 2 延误截止时间率与移动事务间隔时间关系曲线 5 9 图5 3 重启动率与移动事务间隔时间关系曲线 5 9 图5 4 提交率与移动事务间隔时间关系曲线 6 0 图5 5 延误截止时间率与移动事务间隔时间关系曲线 5 0 写概率 6 1 图5 6 重启动率与移动事务间隔时间关系曲线 5 0 写概率 6 2 图5 7 提交率与移动事务间隔时间关系曲线 5 0 写概率 6 2 图5 8 延误截止时间率与移动事务间隔时间关系曲线 2 0 断接概率 6 4 图5 9 重启动率与移动事务间隔时间关系曲线 2 0 断接概率 6 6 图5 1 0 提交率与移动事务间隔时间关系曲线 2 0 断接概率 6 5 表目录 表1 1 主要移动事务模型的基本特性 8 表1 2 主要移动事务模型保证事务a c i d 特性的方法 1 1 表1 3 主要移动数据库产品及基本特性 1 7 表5 1 模拟系统参数设置 5 8 x 原创性声明 本人声明 所呈交的学位论文是本人在导师指导下进行的研究 工作及取得的研究成果 尽我所知 除了论文中特别加以标注和致谢 的地方外 论文中不包含其他人已经发表或撰写过的研究成果 也不 包含为获得中南大学或其他单位的学位或证书而使用过的材料 与我 共同工作的同志对本研究所作的贡献均已在论文中作了明确的说明 储繇盥缸嗍蹲年二月竺日 学位论文版权使用授权书 本人了解中南大学有关保留 使用学位论文的规定 即 学校 有权保留学位论文并根据国家或湖南省有关部门规定送交学位论文 允许学位论文被查阅和借阅 学校可以公布学位论文的全部或部分内 容 可以采用复印 缩印或其它手段保存学位论文 同时授权中国科 学技术信息研究所将本学位论文收录到 中国学位论文全文数据库 并通过网络向社会公众提供信息服务 醐 孕年s 月 i f i ti st i m et ob r o a d c a s ti r m hr e c e i v e si r l o a di ri nc a c h e w h i l e e n do fc u r r e n tb r o a d c a s tc y c l e i f i ti st i m et ob r o a d c a s tf i r m hr e c e i v e sf i r l o a df i ri nc a c h e i f i ti st i m et ob r o a d c a s td a t a m hr e c e i v e sm u l t i v e r s i o nd a t a l o a dm u l t i v e r s i o nd a t ai 1 1c a c h e 第2 6 页 博士学位论文第二章多版本数据广播 m h s 通过接收服务器广播v i n 对移动实时事务进行预有效性确认 在m h s 尽可能早地检测数据冲突 节省了处理和通信资源 降低了移动事务的响应时间 2 6 本章小结 本章提出了m v i r v i n 数据广播协议 服务器在广播周期开始时 广播上 一个广播周期在服务器提交事务的有效性确认信息v i n m h s 通过接收服务器 广播v i n 对移动实时事务进行局部预有效性确认 减少了处理和通信开销 对 于变化频率大的数据 m v i r v i n 广播机制设计了快速失效报告f i r f i r 包 含在i r 周期快速更新的数据 由于大多数快速更新的数据项很小 广播这些数 据不需增加太多的开销 f i r 在一个广播周期中可多次广播 m v i r v i n 数据广 播协议增加了m h s 与广播通道的断开的容忍度 并确保数据一致性 第2 7 页 博士学位论文第三章移动分布式实时事务处理策略 第三章移动分布式实时事务处理策略 本章研究的内容是在移动广播环境中移动分布实时事务处理的特点和策略 主要包括移动分布式实时事务的特征 多版本乐观并发控制机制 有效性确认方 法 多版本动态调整串行次序 全局有效性确认方法 提交处理策略 3 1 移动分布式实时事务的特征 移动分布式实时事务具有传统分布式实时事务所具有的特征 如实时性 分 布性等 但是 由于受移动计算环境的影响 它还具有传统分布式实时事务所不 具有的特点 如移动性 其主要特征有 1 实时性 实时事务具有截止时间约束 事务执行的正确性不只是数据库的一致性问 题 还必须考虑是否会延误截止时间 根据截止时间实时事务可分为三类 1 0 1 1 软实时事务 s o f tr e a l t i m et r a n s a c t i o n 事务在截止时间之后完成 它的价值减少了 并随着延误截止时间的增长 其价值趋于零 2 固实时事务 f i r mr e a l t i m et r a n s a c t i o n 事务一旦到达截止时间 其价值立即降为零 此后固定为零 也不会为负值 3 硬实时事务 h a r dr e a l t i m et r a n s a c t i o n 事务执行超过截止期会对系统造成危害 导致严重后果 图3 1 中 a b c 分别给出软实时事务 固实时事务和硬实时事务的示意 图 其中v a l u e t i m e d e a d l i n e 分别表示价值 时间和截止时间 在移动计算环 境中 大多数移动分布式实时事务为软实时事务和固实时事务 事务执行超过截 止期不会对系统造成危害 2 移动性 在移动计算环境中m h s 可以从一个无线蜂窝移动进入另一个无线蜂窝 根 据移动的距离分为两种移动 微移动和宏移动性 微移动是指m h s 仍然在同一 个无线网络中 宏移动是指m h s 进入不同的网络 移动分布式实时事务的执行 随m h 移动而移动 3 分布性 移动分布式实时事务r 乃 乃 瓦 由多个子事务组成 如果发起移动 第2 8 页 博士学位论文第三章移动分布式实时事务处理策略 分布式实时事务丁的m h 不能处理丁所有子事务 抽出能处理的子事务乃 送 其余的子事务给m s s 上的协调者t o o t o o 收到子事务乃后 分配弓到m h 或f h 处理完成 v a l u e v a l u e d e a d l i n et i m ed e a d l i n et i m e v a l u e a 软实时事务 b 同实时事务 c 硬实时事务 图3 1 实时事务的分类 4 优先性 移动实时事务具有优先级 在解决数据冲突时必须要考虑事务的优先级 应 有利于高优先级事务完成 5 断接性 m h s 通常受到电池能量 处理能力和存储能力的限制 m h s 自愿或不自愿 地与网络断开 断开状态应该作为正常状态而不是错误状态 m h s 的断开状态 可能是节约电池的消耗 3 2m h 过界切换处理 当m h 移动到另一个无线蜂窝时 m h 必须向新的m s s 请求注册 在上个 m s s 注销自己 断开上一个m s s 连接 m h 通过新的m s s 与固定网络连接 并接受新的m s s 上的服务器广播的数据 m h 最初注册的m s s 称为本地m s s m h 过界切换方法如下 1 每个m s s 周期地广播一个分组 宣布它的存在以及地址 一个新的m h 可能会等待这样的消息 2 m h 的信号接受器发现新的m s s 信号比当前m s s 强时 启动m h 过界 切换 向新的m s s 请求注册 m h 提供自己的主地址和安全信息 3 新的m s s 与m h 的本地m s s 进行联系 通知本地m s s 其属的一个 第2 9 页 博士学位论文 第三章移动分布式实时事务处理策略 m h 在此请求注册 4 本地m s s 对安全信息进行检查 如果安全检查通过 则本地m s s 告诉 新的m s s 可以继续进行 5 当新的m s s 得到了来自本地的m s s 确认之后 在地址表中加入一个表 项 并通知m h 注册已经完成 6 将事务的状态信息从上一个m s s 转移到新的m s s 图3 2m h 过界切换 3 3 多版本乐观并发控制机制 每个活跃事务乃赋予一个时间戳t s 功 对于每个数据项x 有一个版本序列 q x 2 p 与之关联 每个版本溉包含三个数据字段 1 x k 版本值c o n t e n t 2 w t s x 3 r t s x k 其中n f r s x k 表示创建x i 版本的事务时间戳 r t s x k 表示所有成功读取敬版本的事务的最大时间戳 更新事务执行分为三个阶段 读阶段 有效性确认阶段和写阶段 1 0 2 1 在读 阶段 假设更新事务乃发出r e a d x 或w r i t e x 操作 令搬表示x 的版本 其写 时间戳小于暇乃 的最大写时间戳 如果乃发出r e a d x 则返回x k 的值 并 把溉放入乃读集r e a d s e t t j 中 其理由是一个事务读取在它之前的最近的版 本 如果兀发出w r i t e x 操作 且若t s t 3 r t s x i 则乃重启动 否则创建x 的一个新版本而 并把而放入兀预写集p r e w r i t e s e t t i 中 同时将创建的新版 本x i 存储在瓦的私有工作空间中 在乃结束之前对其他事务是不可见的 其 理由是如果死试图写入其它事务读取的版本 不允许该写操作成功 在有效性 第3 0 页 博士学位论文第三章移动分布式实时事务处理策略 确认阶段中 确认乃的有效性 即确认乃是否与其他事务有冲突 如果乃通 过有效性确认 乃进入写阶段 在写阶段 若乃通过最终有效性确认 则实际 的更新就可写入数据库中 只读事务读最近提交的数据项版本 只经过读阶段和有效性确认阶段 3 4 多版本动态调整 在移动广播环境中重启动一个移动事务开销较大 通过多版本动态调整事务 串行次序 避免不必要的事务重启动 考虑三并发事务乃 乃和乃的执行历 史片段日 令n m 和w 融 分别记为事务乃读数据项x 版本x k 和写数据项x 版本而 功和c 分别记为瓦有效性确认和提交 x o w l x t 吻 朋w i y l v ic 乃卜 叫 r2 xo v c2 7 2 r 3 y o w 3 y s 乃卜 一中止 图3 3 三并发事务执行历史片段 月 r l x o 您b o w l x l r 3 y o r e v o w 3 y s w i 陟力1 jv 2c q 这个多版本历史片段日不是串行的 乃和乃在乃有效性确认时重启动 仔细分析执行历史片段h 乃与乃只有在数据项x 上读 写冲突 因此 只要 调整串行次序为乃一乃 乃不需要重启动 乃与乃有读一写和写 读两种冲突 乃不得不重启动 在多版本机制写 写操作对不再是冲突的 因为它们产生不同 的版本 1 0 3 1 多版本动态调整串行次序在下列二种情况发生 1 如果进行有效性确认事务巧与事务乃有读一写冲突 即 r e a d s e t t o f l p r e w r i t e s e t t g o 调整串行次序为瓦 乃 乃的写不应影响兀的 第3 l 页 博士学位论文第三章移动分布式实时事务处理策略 读阶段 2 如果进行有效性确认事务兀与事务乃有写 读冲突 即 p r e w r i t e s e t t v a r e a d s e t 功 1 2 i 调整串行次序为乃 瓦 瓦的写不应该影响乃 读阶段 每个活跃事务乃分配一个有效性确认间隔v l 驴 场 u b 用于调整事务串 行次序 如果事务乃被串行在乃之前 即乃 乃 则乃的有效性确认间隔 t b 甜m 和乃的效性确认间隔 l b j 甜明必须满足u b i l b j 每个事务乃在开始执行时赋 予有效性确认间隔为 0 叫 如果事务乃的效性确认问隔为空 则乃不可能 再串行调整 必须重启动 3 5 有效性确认 乐观并发控制机制有效性确认有两种方法 向后有效性确认 b a c k w a r d v a l i d a t i o n b v 和向前有效性确认 f o r w a r dv a l i d a t i o n f v 1 1 0 4 j 1 矧 在向后有效 性确认中 有效性确认的事务与所有已提交事务进行冲突检测 在向前有效性确 认中 有效性确认的事务与所有并发运行且尚处于读阶段的事务进行有效性确 认 移动事务处理分两阶段 第一阶段在m h s 上处理 进行局部预有效性确认 第二阶段在服务器上处理 如果所有移动事务直接提交到服务器进行有效性确 认 对于没有通过有效性确认的移动事务 m h s 需等待服务器的通知很长时间 才知道这些事务需要重启动 此策略会导致移动事务处理不可容忍地延时 在 m h s 进行局部预有效性确认 m h s 能及时确定事务由于数据冲突需重启动 如 此早地检测数据冲突 节省了处理和通信资源 m h s 上没有完整的和最新冲突事 务的数据视图 例如 m h s 不知道在当前广播周期开始后提交到服务器的某些 冲突事务的提交信息 m h s 可能自愿或不自愿与移动网络断开 错过接收服务 器广播的有效性确认信息 造成m h s 上的数据过时 因此 如果事务通过预有 效性确认 必须提交到服务器进行最终有效性确认 在m h s 使用向后有效性确认 m h s 上所有移动事务 包括移动只读事务和 移动更新事务 与在服务器上一个广播周期提交事务进行有效性确认 提交事务 要串行在进行有效性确认的移动事务之前 因此 数据冲突检测是检查进行预有 效性确认移动事务的读集与提交事务的写集是否相交 m h s 上没有完整的和最新冲突事务的数据视图 例如 m h s 不知道在当前 广播周期开始后提交到服务器的某些冲突事务的提交信息 因此 如果移动事务 通过局部向后预有效性确认 必须提交到服务器进行局部最终有效性确认 如果 第3 2 页 博士学位论文 第三章移动分布式实时事务处理策略 移动只读事务所有读数据项通过局部预有效性确认 则不需要执行局部最终有效 性确认 即可提交 在m d r t d b s s 中数据冲突检要有利于移动事务 高优先级事务 在服务器 进行有效性确认的事务有移动事务和服务器事务 向前有效性确认提供灵活的数 据冲突解决方法 可选择有效性确认事务或冲突事务重启动 甚至可以通过强迫 有效性确认事务在有效性确认阶段等待来避免一些事务的回滚1 1 叫 1 0 刀 因此 在 服务器使用向前有效性确认 数据冲突检测是检查进行预有效性确认的移动事务 写集与服务器事务的读集是否相交 进行有效性确认的移动事务串行在所有并发 运行且尚处于读阶段的事务之前 3 6 在m h s 上事务处理策略 3 6 1 读 写请求处理方法 m h s 处理移动事务的读写请求和调整有效性确认间隔 当移动事务进行读 或写请求时 它的有效性确认间隔被调整 以反映移动事务与提交事务之间的串 行关系 令x k 表示x 的版本 其写时间戳小于珊乃 的最大写时间戳 移动事 务瓦发出读数据项x 选择读其版本瓤 v i t b r 3 被调整 即置呱瓦 v i t o r r t s x 叫 同时将x k 版本放入乃的读集r e a d s e t t i 中 移动事务乃 发出写数据项x 如果t s t 3 r t s x 则乃重启动 否则创建工的一个新版本 而 劢被调整 即置呱乃 v j t 3 n w t s x k 叫n 陋酬 并放入乃预 写集p r e w r i t e s e t t j 中 3 6 2 预有效性确认方法 在m h s 进行预有效性确认 使用向后有效性确认机制 以保证没有任何移 动事务与上一个广播周期在服务器提交事务有数据冲突 服务器在广播周期开始 时广播上一个广播周期在服务器事务有效性确认信息 事务有效性确认信息由 c o m m i t s e t a b o r t s e t c tr e a d s e t 和c tw r i t e s e t 组成 其中c o m m i t s e t 为通 过服务器最终有效性确认并提交的移动事务集合 a b o r t s e t 为未通过服务器最终 有效性确认并中止提移动事务集合 c tr e a d s e t 为所有提交的事务读数据项集 合 c tw r i t e s e t 为所有提交的事务写数据项集合 移动事务与提交事务进行预 有效性确认 如果移动事务预有效性确认失败 移动事务不得不重启动 事务调 度器按移动事务优先级调度 移动事务乃对于己提交的事务瓦进行有效性确 认 满足下面条件之一 1 疋在乃开始之前已经结束 2 否则 r e a d s e t r l f n w r i t s e t 瓦 0 且瓦的写阶段在乃开始其有效性确认阶段之前完 第3 3 页 博士学位论文第三章移动分布式实时事务处理策略 成 1 如果r e a d s e t t i mw r i t s e t t o 调整串行次序为瓦 瓦 这意味着虽 然疋在乃之前提交 乃的读应放在瓦写之前 调整瞰功使得 6 t 3 t s t c 即置 瞰驴瞰兀 n 双功 叫 移动只读事务如果所有读数据项通过预有效性确认 则可提交 串行在当前 广播周期前提交的事务之后 当前广播周期后提交的事务之前 移动更新事务如 果通过局部向后预有效性确认 必须提交到服务器进行最终有效性确认 因为移 动更新事务串行在它到达有效性确认阶段之前提交的事务之后 所有活跃事务之 前 移动事务兀提交时将提供下列信息 取兀 v i 功 p r i o r i t y t v d e a d l i n e 兀 r e a d s e t t v 和p r e w r i t e s e t 功 其中p r i o r i t y t v d e a d l i n e t v 分别表示乃的优 先级和截止时间 3 7 在服务器上事务处理策略 m h s 上没有完整的和最新冲突事务的数据视图 例如 m h s 不知道在当前 广播周期开始后提交到服务器的某些冲突事务的提交信息 因此 如果移动事务 通过局部预有效性确认 必须提交到服务器