（计算机应用技术专业论文）移动计算环境下事务一致性研究.pdf

摘要 随着计算机技术和无线网络技术的进一步发展，移动计算环境下的应用也越来越普 及。数据量和处理复杂度不断增加，移动应用要求在移动设备上有合适的d b m s 来管理。 嵌入式移动数据库就此应运而生，它可针对移动商务的要求而定制，是移动计算环境下 基于数据库应用的基础和核心。 移动分布式数据库中结点间的连接是一种弱连接，这给传统的事务处理提出了新的 挑战。为了提高移动计算机的效率，事务执行通常采用乐观复制的方法，它的不足之处 是要依赖用户对应用数据和节点行为的知识，难以适应移动计算环境下网络连接和配置 的动态变化。 本文以移动数据库系统s w i f t d b 为基础，面向具体应用，详细分析了移动事务冲突 检测准则、移动结点嵌入式数据库状态等问题，重点阐述了移动事务一致性实现策略， 包括基于概率方法的动态服务质量算法和移动结点延迟更新传播时间的求解算法等主 要问题，最后给出了采用一般时间序列法短期预测参数 的简单流程。 关键字：移动数据库，事务一致性，双向同步复制，服务质量，基于概率方法 a b s t r a c t w i t ht h ef u r t b e rd e v e l o p m e n to fc o m p u t e ra n dw i r e l e s sn e t w o r kt e c h n o l o g y ，b u s i n e s s a p p l i c a t i o n si nm o b i l ec o m p u t i n ge n v i r o n m e n t a r eb e c o m i n gm o r ep e r v a s i v e t h ea m o u n to f d a t aa n dt h e i n t r i c a c y o fp r o c e s s i n ga r ei n c r e a s i n g ，a n dm o b i l ea p p l i c a t i o n sd e m a n da n a p p r o p r i a t ed b m s t os u p p o r tt h e i rd e p l o y m e n t e m b e d d e dm o b i l ed a t a b a s es y s t e me m e r g e s ， a n di tc a nb ec u s t o m b u i l ta c c o r d i n gt os p e c i f i cm o b i l eb u s i n e s s i ti sb a s i sa n dc o r eo f d a t a b a s ea p p l i c a t i o n si ns u c ha ne n v i r o n m e n t ， i nm o b i l ed i s t r i b u t e dd a t a b a g e s t h ec o m m u n i c a t i o n sb e t w e e ns i t e so n l yp r o v i d ew e a k a n du n s t a b l e c o n n e c t i v i t y w h i c h m a d et r a d i t i o n a lt r a n s a c t i o n p r o c e s s i n g m o d e l sn o t a p p r o p r i a t ea n yl o n g e r t oi m p r o v e t h ee f f i c i e n c yo fm o b i l ec o m p u t e r s ，o p t i m i s t i c r e p l i c a t i o n a p p r o a c h e sa r eu s e da sc o m m o n m e t h o d sf o rt r a n s a c t i o np r o c e s s i n g t h es h o r t c o m i n g so ft h e a p p r o a c h e s a r et h a t t h e yr e l y o nu s e r s k n o w l e d g ea b o u tt h ea p p l i c a t i o n sd a t a a n ds i t e s b e h a v i o r i ti sd i f f i c u l tf o rt h ea p p r o a c h e st ob ea d a p t i v et ot h ed y n a m i cc h a n g e so fn e t w o r k c o n n e c t i o na n d c o n f i g u r a t i o ni nm o b i l e e n v i r o n m e n t s i nt h i s p a p e r ，a na p p l i c a t i o n o r i e n t e d a n d p r o b a b i l i t y b a s e d m e t h o di s g i v e n f o r t r a n s a c t i o nc o n s i s t e n c yp r o c e s s i n gi nm o b i l ed a t a b a s es y s t e m ss u c ha ss w i f t d b t h i sp a p e r i n t r o d u c e st h r e ek i n d so fm o b i l et r a n s a c t i o nc o n f l i c td e t e c t i o nr u l e sa n df o u rt y p e so fs t a t e so f e m d bi nm o b i l es i t e s t h ep r o b a b i l i t y b a s e da p p r o a c h e so fm o b i l et r a n s a c t i o n a lc o n s i s t e n c y p r o c e s s i n g a r e s t u d i e d ，i n c l u d i n gq u a l i t y o fd y n a m i cs e r v i c ea r i t h m e t i ca n d c o m p u t i n g a r i t h m e t i co fl i n g e r i n g u p d a t i n g t r a n s m i s s i o ni n t e r v a li nm o b i l e s i t e s ，t o g e t h e r w i t ht h e p r e d i c t i o nf l o w o f p a r a m e t e r a p p l y in gg e n e r a l ti m es e r ie sm e t h o d k e yw o r d s ：m o b i l ed a t a b a s e ，t r a n s a c t i o n a lc o n s i s t e n c y ，b i l a t e r a ls y n c h r o n i z a t i o n & r e p l i c a t i o n ，q u a l i t yo fs e r v i c e ，p r o b a b i l i t y b a s e dm e t h o d 东南大学学位论文 独创性声明及使用授权的说明 一、学位论文独创性声明 本人声明所呈交的学位论文是我个人在导师指导下进行的研究工作及取得的研究成果。尽我所 知，除了文中特别加以标注和致谢的地方外，论文中不包含其他人已经发表或撰写过的研究成果， 也小包含为获得东南大学或其它教育机构的学位或证书而使用过的材料。与我一同工作的同志对本 研究所做的任何贡献均已在论文中作了明确的说明并表示了谢意。 - 、 签名：! 匣11 型垦日期：鲎! ：! ：! ! 二、关于学位论文使用授权的说明 东南大学、中国科学技术信息研究所、国家图书馆有权保留本人所送交学位论文的复印件和电 子文档，可以采用影印、缩印或其他复制手段保存论文。本人电子文档的内容和纸质论文的内容相 一致。除在保密期内的保密论文外，允许论文被查阅和借阅，可以公布( 包括刊鸯) 论文的全部或部 分内容。论文的公布( 包括刊登) 授权东南大学研究生院办理。 签名：缸，堂萎k 导师签名 第幸0 i 苦 1 1 研究背景 第一章引言 随着网络和计算机技术的迅速发展，人们希望能在任何时间、任何地点、访问任何 数据的需求已逐渐成为现实，信息系统正在走出传统的机房与桌面，帮助用户随时随地 获取相关信息，做出正确决策。要实现这种崭新的移动计算模式，必须得到移动数据库 系统的支持。这将使得移动计算不再只是一些简单的应用，也可以进行一些数据库系统 特有的事务处理随时获得企业数据库中的最新数据，同时将已经修改的数据复制到企 业数据库中，从而使企业信息系统具有移动计算的能力。 移动计算环境的一个显著特点是移动节点与基节点之间的弱连接方式低带宽、 氏延迟、不稳定和经常性断开；同时，移动计算环境中的嵌入式移动数据库系统 e m d b m s ( e m b e d d e dm o b i l ed b m s ) 又具有处理失配、事务处理复杂等特点，移动数据库可 能因断接而与中心数据库服务器上的关联数据发生一致性偏差，数据同步复制是消除偏 差、保持数据一致性的主要技术”j 。j i m g r a y 给移动复制提出了四个目标，即可用性与 可伸缩性、移动性、可串行性、收敛性f 2 j 。这四个目标决定了移动计算环境下事务执行 通常应该采用乐观复制的方法，即系统允许移动主机在断开连接的情况下存取本地副本 并提交事务操作。从而造成系统短暂的不一致；重新连接时进行数据同步处理，使系统 重新收敛于一致性的状态。乐观复制方法在一定程度上可以提高系统的效率，减少事务 平均响应时间，但依赖于用户对应用数据和节点行为的知识，在系统工作负荷增大时， 会带来不可接受的回滚事务数量，引起系统性能急剧下降。 为了降低通信量，提高系统效率和减少事务平均响应时间，要尽可能延迟更新传播。 但若延迟时间过长，又会引起数据冲突可能性增大，导致回滚事务数量急剧上升。如何 确定一个合适的延迟更新传播时间t ，以达到系统效率和事务平均响应时间与事务回滚 代价之间的平衡点，成为移动计算领域一大难题。因此，移动计算环境下事务一致性实 现策略应充分考虑移动计算环境的特点，面向具体应用，根据用户提出的服务质量要求， 通过用户和系统协商的方式决定最佳的事务处理方法和协调时间，以提高系统效率和应 用可靠性。 移动数据库应用领域十分广阔，市场空间很大，有着大量的个性化的应用需求。虽 然数据库厂商己先行一步，但由于嵌入式移动环境下的软件开发更注重与应用的结合， 查塑查堂堡主兰竺堡茎 更注重融入本地化的特征，所以不可能由几个通用的系统垄断。对国内软件业来说，是 一个难得的可以大有作为的良好机遇，我们完全能够占有自己的一席之地。 1 2 移动计算环境特点 在传统的计算环境中，各个节点都是依靠固定网络连接在一起的，并始终保持网络 的持续连接性。而在移动计算环境下，用户不再需要停留在固定的位置，他们可以携带 移动设备自由移动，同时通过移动通信网络保持与固定节点和其他移动节点保持连接。 与传统环境相比，移动计算环境具有以下特点： 1 用户的移动性。 用户可以在移动过程中进行各种操作。 2 网络带宽的不对称性。 下行( 中心服务器到移动终端) 带宽大予上行( 移动终端到中心服务器) 带宽。移 动终端甚至可以在不能发送信息的情况下仍可以接收到中心服务器发送给它的信息。但 即便如此，下行带宽一般也只有l o 2 0 k b s ，无线局域网可能可以达到l o m b s 。 3 频繁断接。 移动终端可能因为用户为了节省电源、节约通讯费用而主动关机或由于通信故障而 间歇性地入网、断接。 另外，移动设备也有其特殊之处： l - 电源能力有限。 移动设备一般电池供电，因此电源一般只能维持4 6 小时。因此在查询优化的代 价估算时就应该考虑，应该把运行时问很长的查询放到中心数据库做。 2 计算能力有限。 目前移动设备的最高主频是4 0 0 m h z ，难以执行复杂的查询。 3 存储能力有限。 4 屏幕面积小。 i 3 移动计算环境下事务处理特点 传统数据库系统中的各种事务处理模型较好地解决了传统应用环境下事务的并发 控制问题，但不能有效地支持移动计算环境。由于移动计算环境是传统的基于固定网络 的分布式计算环境的扩展，所以除了必须解决传统分布式计算环境的所有问题外，还必 2 翌二堇! | 妻 一 须同时考虑移动计算环境与移动设备的特点。与传统的分布式数据库事务处理相比，移 动事务处理存在特殊的要求，主要表现为以下几点： 1在移动数据库中，固定主机和移动终端均能发起事务，其中移动终端发起的事务称 为移动事务。由于有限的通信带宽以及频繁断接操作的影响，移动事务通常属于长事务； 2由于网络的频繁断接，移动数据库支持用户在离线状态下提交暂态事务，从而使得 移动端与远程企业数据库的数据不一致无法避免，因此移动数据库系统只能满足允许松 一致性的应用； 3移动终端可以以多种方式连接中心数据库，当移动终端采用无线通信方式连接中心 数据库时，还要考虑移动终端的位置移动问题。在移动事务执行的过程中，移动终端位 置的改变会带来复杂的过区切换问题；移动事务执行时要访问更加复杂的数据资源，更 容易出错【3 】； 4低带宽要求事务处理时应尽量减少网络通讯量； 5 由于移动设备资源与处理能力的限制，事务处理相关计算应尽量在服务器端完成。 移动事务的上述特点对移动计算环境下数据库系统的事务管理提出了新的挑战。 1 4 国内外相关研究现状 在移动事务管理方面，人们已经进行了大量的研究，已有不少文献或原型系统对此 进行了探讨，但它们基本上都是从改变目前已有数据库事务管理模式的角度进行探讨， 即提出各种移动事务模型。其中，有的要求移动终端一次性地将事务的所有操作发送给 协调器，因此不能提供对交互式移动事务的支持，如m d s t p m 模型【7 】：有的虽然提供了灵 活的移动事务发送方式，但在操作序列结果返回之前移动终端不能离开当前网络，而且 由于采用了两段锁协议，数据可能会被长时间上锁，不能很好地支持断接性和长事务特 性，如0 2 p l m t 模型【8 】；有的支持交互式移动事务，解决了对移动性的限制，如0 2 p c m t 模型i 9 。此外，其它一些模型如集群事务模型 i o l 、k a n g r o o 事务模型n 1 、自适应移动事 务模型、m o f l e x 事务模型“3 1 等，对事务的a c i d 性质作了一些折衷或者重新定义，因 此不能完全保证事务的可串行性和数据库的一致性。尽管对于许多移动数据库应用而 言，将可串行性作为正确性的标准可能过于苛刻，但许多重要的应用仍然需要用可串行 性作为标准来保证数据库的一致性。 然而，上述模型实际上都没有真正地解决如何确定合适的延迟更新传播时间t 的 问题。 东南大学硕士学位论文 鉴于上述分析，本文并不试图提出一种所谓的移动分布式事务模型，而是以我们自 行开发的移动数据库系统s w i f t d b 为基础，在仔细分析移动计算环境的特点和移动应用 需求的前提下，面向s w i f t d b 上开发的具体应用，对乐观复制方法进行了改进，根据用 户提出的服务质量要求，通过用户和系统协商的方式决定最佳的事务处理方法和协调时 间以提高系统效率和应用可靠性。本文提出了移动计算环境下事务处理的基于概率方 法，着重对s w i f t d b 中的移动事务处理系统结构、移动事务一致性模型和移动事务一致 性动态实现策略做深入的分析。本文后续部分的结构如下：第二章介绍s w i f t d b 移动事 务处理系统结构，第三章介绍移动事务一致性模型，第四章阐述移动事务一致性动态实 现策略，第五章介绍 短期预测方法，最后是结论。 4 苎：兰壁垫至墨竺堡墨竺竺塑 第二章移动事务处理系统结构 2 1 移动数据库系统组成结构 在面向行业的移动计算环境中，数据库系统一般都采用主从层次型的结构。在移动计算环境 下，移动数据库系统组成结构可以用图2 1 描述，它由三类结点组成： 图2 1 移动数据库系统组成结构 1 中心数据库服务器( c d b s v r ) 一般为固定结点，每个服务器维护一个本地数据库。服务器可以是彼此独立的，也 可以由可靠的高速互联网络连接在一起，构成一个传统意义上的分布式数据库系统。服 务器可以处理客户的联机请求，并可以保存所有请求的历史记录。 中心数据库可以是任意的大型数据库系统，如o r a c l e ，s y b a s e ，d b 2 ，s q ls e r v e r 等，也可以是集中式数据库、分布式数据库，甚至是联邦式数据库。中心数据库如果是 集中式数据库，则虚线框中就只有一个数据库；如果是分布式数据库，则虚线框中多个 物理上分布的数据库构成一个逻辑上统一的中心数据库。 2同步服务器层( m s s ) m s s 也位于高速网络中，并具有无线联网能力，它们用于支持一个无线网络单元 ( c e l l ) 内的通信。该单元内的移动客户端既可以通过无线链路与m s s 通信，从而与整个 固定网络连通，也可以接收由m s s 发送的广播信息。中心数据库服务器与m s s 可以是同 一台机器。 s 东南大学硕上学位论文 作为三级复制模式的中间层，同步服务器的作用是进行分布式事务处理、控制移动 数据库( e m d b ) 和中心数据库( c d b ) 之间的数据交换。同步服务器负责接收来自移动 终端的操作请求并提交给中心数据库服务器，然后将执行结果在传送给移动终端。对中 心数据库服务器来说，它的客户端就是同步服务器，它看不到移动终端。因此，同步服 务器的引入屏蔽了中心数据库系统的异构性。 3 移动客户端( 眦) m c 的处理能力与存储能力相对于服务器来说非常有限，且具有移动性( 即可以出现 在任意一个无线单元中) 。可能是任何一种移动终端，比如笔记本、p d a 、掌上电脑、 手机等。 移动终端有嵌入式的移动数据库( e m d b ) 系统支持，并具有嵌入式数据库系统的事 务管理功能。移动终端上保存中心数据库的一部分副本，并通过e m d b 对本地数据进行 管理。e m d b 。表示移动终端i 上的嵌入数据库，它是中心数据库中用户i 所感兴趣的部 分数据的复制，能够和中心数据库保持双向同步。移动计算设备是单用户，它们通过同 步服务器访问中心数据库，因此中心数据库系统的异构性对它们是透明的。 2 2 移动终端与中心数据库的连接方式 为了讨论移动计算环境下的数据库事务管理，还必须仔细分析移动终端接入中心数 据库系统的方式，因为不同的接入方式所需解决的问题也不同。一般来说，移动终端与 中心数据库的连接方式主要有三类： 1 局域网方式 移动终端利用网卡直接接入中心数据库系统服务器的局域网。移动终端应用环境不 具备移动计算环境特点，传统的基于多层结构的数据库应用系统的事务管理模型已能很 好解决。 2 拨号方式 移动终端利用m o d e m ，通过公共电话网( p s t n ) 或移动通讯网( 如g s m 网) 拨号接 入系统，移动终端与中心数据库服务器连接不稳定和经常性断开( 由于通信故障或为了 节约连接费用) ，因而这种连接方式也存在长延迟特点。若移动终端通过移动通讯网接 入，尽管移动终端在不停地移动，但中心数据库系统服务器感觉不到它的移动，移动性 被移动通讯网屏蔽了；若通过固定电话网接入，就更不存在移动问题了，因此不需要考 虑事务执行期间移动终端的位置移动问题。 第- _ = 章移动事务处理系统结构 3 无线通信方式 移动终端利用无线网卡通过无线局域网、无线广域网、无线因特刚等接入中心数据 库系统服务器的局域网。这种连接方式不仅要考虑低带宽、长延迟特点，还要考虑事务 执行期间移动终端移动到不同的无线通信单元( c e l l ) 的问题。 【6 中指出，可以通过接入代理层来屏蔽移动终端的移动性，从而简化移动计算环境 下的数据事务管理。因此，为简化问题，本文假设移动事务在同一无线通信单元( c e l l ) 内完成，不考虑事务执行期间移动终端的过区切换问题。 2 3 面向行业应用的移动计算环境总体结构 s w i f t d b 系统支持面向行业的移动计算，如图2 2 所示。图中的中心数据库c d b 就 是企业信息系统的数据服务器，它可以是集中式数据库、分布式数据库、甚至是联邦式 数据库。企业的移动办公人员使用的移动终端( 如p d a 、掌上电脑等这类移动计算设备) 上安装有嵌入式数据库( e d b m s ) ，并通过同步服务器层( m s s ) 访问中心数据库，c d b 的异构性对它们是透明的。m s s 、c d b 和s d b 可以处于固定网络中同一台物理的服务器上， 也可以分别处于不同的服务器上。 s w i f t d b 系统在传统的两级复制基础上引入同步服务器，采用三级复制模式，即嵌 入式数据库一一同步服务器一一中心数据库，移动终端通过同步服务器访问中心数据库 并与其同步。在该系统中，可信部分由固定网络以及固定网络上的固定主机( 基结点) 组成。其中固定主机又可分为两类，一类是不带无线通信接口的主机，如中心数据库服 务器：另一类是带有无线通信接口的同步服务器( m s s ) ，每个m s s 支持一个无线网络 单元。无线网络单元内有多个移动终端( m c ) ，每个m c 上也有数据库的一个副本，有本 地e m d b m s 进行管理，m c 可通过m s s 连入固定网络。有了e d b m s 和m s s 的支持，移 动终端上的应用就可以在网络断接的情况下离线访问已经复制到移动端上的数据库，并 可以保持一定的同步，使得企业用户的工作场所的范围大大扩大。 在基结点中，各个数据库副本之间通过固定网络保持持续性的连接，可利用传统分 布式数据库系统中的副本控制方法( 如r o w a ) 保证它们的一致性，因此可以将它们视 为一个逻辑实体。各个移动结点之间以及移动结点与基结点之间保持弱一致性，需要一 定的机制对它们进行控制。基结点通过加锁机制实现并发事务( 包括基结点自身提交的 事务以及由移动结点发起的同步处理事务) 的可串行化调度执行。基结点上的事务满足 执行的原子性、功能上的保持一致性、彼此的隔离性、作用的持久性( 这四个性质又称 查壹叁堂堕圭兰竺堡兰一 为事务的a c i d 准则m 1 ) ，但移动结点上的事务提交时仅处于本地提交状态，需要在基结 点上验证通过后方能全局提交，将其所做的数据更新写入中心数据库。 图2 2 面向行业应用的移动计算环境总体结构 在实际应用中真正的移动分布式事务处理需求并不多，所以没有必要将问题复杂 化。实际上，由于移动分布式事务管理客观上的复杂性，已有文献提出的各种模型都不 能完全解决这一问题，难以实用。 1 4 中指出，在移动计算环境下，如果将中心数据库 中的某些数据复制到多个e 肋b 中，而且允许它们随意地同时被修改，则在严格的a c i d 准则下，保证数据的一致性事实上是不可能的。因此，为了简化问题，不妨假设系统中 所有的更新类移动事务均由e 物8 产生，并通过m s s 进行全局提交。同时，移动结点i 的用户只访问e m d b i 或通过m s s 直接访问中心数据库。这样关键问题就变成如何在充 分利用已有事务管理模型的基础上，解决如何确定合适的延迟更新传播时间t 的问题。 第三章移动事务致- 盹模型 第三章移动事务一致性模型 3 1 移动数据库系统事务管理 1单机情况 对一些非常简单的应用，不需要中心数据库的支持，也不需要双向数据同步，只在 移动终端上单机运行，这时本机的嵌入式数据库系统的事务管理即可解决。 2 联机实时访问 移动终端与中心数据库系统建立连接，移动用户直接访问中心数据库，这时要求连 接不能中断，否则事务就要夭折( a b o r t ) 。移动终端可以通过拨号网络( 有线网或无线 网) 或局域网接入系统，这时的应用实际上就是传统的c l i e n t s e r v e r 结构，只不过现 在的客户端在移动终端上，但不存在位置移动的问题；如果移动终端是通过无线局域网 接入系统的，则必须利用接入代理层，屏蔽移动终端在事务执行过程中在不同的无线通 讯单元( c e l l ) 间移动的问题。 3 数据复制及双向数据同步 移动用户将最常用的数据下载到移动终端上的嵌入式数据库( e n ) b ) 中，这样即使 在与中心数据库系统断开连接，离线的情况下仍能访问所需的数据，并可在必要的时候 重新与系统建立连接，将离线期间中心数据库上发生变化的相关数据重新下载，将离线 期间对移动终端上的嵌入式数据库( e m d b ) 所做的修改上载到中心数据库中，从而与中 心数据库上的数据重新达到一致，即双向数据同步。 数据复制及双向数据同步方式的实质是移动用户发起的事务首先在移动终端本地 局部提交，经过延迟更新传播时间间隔t 后重新连接中心数据库系统，并进行全局提 交。当t = 0 时，数据复制及双向数据同步方式实际上就是联机实时访问方式。可见， 联机实时访问方式是数据复制及双向数据同步方式的一个特例。因此，本文后续部分将 在数据复制及双向数据同步方式下讨论移动事务一致性问题。 为便于讨论，本文给出了数据复制及双向数据同步方式下移动事务相关定义如下： 定义偿筠髟笋，基事务只在对象的主结点上执行，并更新对象的主拷贝，它运行 时可以涉及多个基结点。 启戈2r 考蓉弯髟 暂态事务对本地数据复本操作，得到暂态数据。暂态事务中被 访问到的数据对象的主结点必须是基结点或发出该事务的移动结点本身。暂态事务只在 移动结点上进行。 q 奎堕查兰竺圭兰些堡兰 移动结点在断接状态下继续工作，生成若干暂态事务，这些暂态事务对本地暂态数 据操作生成新的暂态数据，操作的结果也都是可以被该移动结点看到的。在重新与基结 点连接时，移动结点首先将本地的暂态事务序列传送给基结点。基结点依次对暂态事务 进行冲突检测，对于通过检测的则将以基事务的形式重做每个暂态事务，并将成功提交 的事务结果返回给移动结点。如果暂态事务未能通过检测，该事务夭折，基结点将有关 失败信息返回给移动结点。 此外，在移动结点断接时，数据的主拷贝对该移动结点上的数据副拷贝的更新事务 被延迟，因此，在移动结点重新与基绐点连接时，基结点把这些更新事务发送给它，从 而更新了移动结点上的数据副拷贝。 定戈? ( ，膏慈每劈裘! 芟) 暂态事务的提交分为两部分：一是局部提交，在本地完 成，其修改只对本地的其他事务可见；二是全局提交，在重新连接或网络条件转好时进 行，要满足事务的a c i d 特性。 暂态事务的引进，提高了数据可用性，减少了事务的平均响应时间，但是它同时也 带来了潜在的数据冲突。暂态事务中的读操作有可能读的是1 日的数据版本，暂态事务中 的写操作所作的修改有可能与其它结点上的修改冲突，因此暂态事务在全局提交时需要 一个检测和解决数据冲突的机制来维护移动事务一致性。此外，由暂态事务生成的基事 务可能在与其它基事务并发执行时，经过串行化后，读到的数据与暂态事务不同而产生 不同的结果。因此基事务必须遵循一个可接受性准则：若它产生了与暂态事务不一样的 结果，如果该结果能够通过准则测试，那么就是可按受的。可接受性准则实际上放宽了 对一致性的要求，因而减少了基事务失败的几率，但是仍保证了事务执行的正确性。 詹必4 ( ，长事努夕长事务是从移动结点上一次连接时读取最新数据开始，直到重 新连接提交暂态事务时所做的所有事务操作序列。断接时执行的暂态事务是长事务的子 事务。 移动结点用户提交的长事务与向中心数据库提交的其它所有事务( 包括其它移动结 点用户提交的长事务和固定网络用户提交的实时事务等) 一起并发执行。 3 2 移动事务冲突检测准则分析 当移动结点重新与基结点连接并提交暂态事务，基结点将暂态事务转化为对应的基 事务时，应进行全局检测。根据不同的全局检测强度可以定义不同的潜在冲突即读集冲 突、写集冲突和可接受性准则冲突。 兰三芏堑塑皇墨二塾竺堡型 1 读集冲突检测 菇火1 徽膨自蝶夕事务t 执行时，所有被读到的元组的集合，记为r e a d s e t ( t ) 。 定义2 ( ，旋集渺突暂态事务t ，其对应的基事务b t ，若r e a d s e t ( t ) = r e a d s e t ( b t ) ， 则发生了读集冲突，即t 的读集在被t 读出后，又被其他事务改写过。 若检测出读集冲突，表明t 的原有语义不能在c d b m s 中重现，基事务b t 不能保持 t 原有语义，则不能提交b t 。 读集冲突检测可以保证暂态事务t 的读集在被t 读取后未被其他事务改写，从而从 全局的角度严格地保持t 的a c i d 性质。 2 写集冲突检测 定义了r 勃肟写橥) 事务t 执行时，所有被增加、删除或修改的元组的集合，记为 w r i t e s e t ( t ) 。 启火4 ( ，写9 等护宛) 暂态事务t ，其对应的基事务b t ，若w r i t e s e t ( t ) # w r i t e s e t ( b t ) ，则发生了写集冲突， 若未发生写集冲突，也就保证了b t 与t 的写集一致，保证了b t 与t 的执行结果的 一致，提交b t 。若发生写集冲突，则说明在移动结点断接时，暂态事务t 写集中的某一 数据对象x 被其它事务做了改写，而x 也被t 改写，也就是说发生了写写冲突，则不 提交b t 。所以，写集冲突检测可以保证两个并发事务共享的数据只会被其中的一个事务 改写。 与读集冲突检测比较，写集冲突检测不能保证数据对象在被一事务读取后又被另 事务改写，即不能避免事务读取脏数据。不过，移动环境自身的特点导致了数据不一致 无法避免，即使采用了读集冲突检测，也不能减少暂态事务读取脏数据的可能性。因此， 基于移动环境的应用必须能容忍暂时的数据不一致，允许事务有读取脏数据的可能，在 这样的应用中使用写集冲突检测准则是可行的。 写集冲突检测的准则虽然弱化了事务的全局a c i d 性质的要求，但是这样的弱化是 合理的，同时可以提高系统同步的成功率。 3 可接受性准则检测 移动环境本身就与弱一致性有着天生的联系，允许移动结点执行暂态事务而又要求 暂态事务的读集、写集不被改变，保持严格的a c i d 性质，这对于大多数系统来说是相 当难以保证的。冲突检测强度的选择必须在的严格性和系统的性能之间寻找平衡。合理 地减弱全局检测的强度会带给系统更好的性能。 东南大学硕十学位论文 数据库服务器d b m s n o d e ln o d e 2 图3 1 更新冲突 由暂态事务生成的基事务在与其它基事务并发执行时，经过串行化后，读到的数据 与暂态事务不同而产生不同的结果。如图3 所示，假设数据库的某数据x 初值为5 ，被 同时下载到n o d e 。和n o d e 。并按图3 1 所示分别被修改。将暂态事务t ，、t ：分别用读、写 操作序列来表示： n o d e l 上执行的t l ：r x ，w x = x + 1 ： n o d e 2 上执行的t 2 ：r x ，w x = 2 * x 。 t 。、t ：在n o d e ：、n o d e 。上独立执行的结果分别是6 、1 0 ，丽t 。、t ：经过d b m s 串行化 后执行，得到x 的结果分别是1 2 、n 。显然，t 、t 。在n o d e ，、n o d e ：上分别独立执行的 结果与经过d b m s 串行化后执行的结果不一致。 有一类暂态事务，如商品销售、机票订购等，被处理的数据对象即暂态事务的读集、 写集( 如t 。、t 。中的x ) ，容许暂时的数据不一致，如容许t 。、t 。在n o d e 。、n o d e 。上分别 独立执行的结果与经过d b m s 串行化后执行的结果不一致。只要通过可接受性准则检测， 如商品的库存数量不能为负，剩余机票的数量不能为负等，就认为是可接受的。也就是 说，在一定的时间间隔t 内。允许暂态事务读取脏数据，允许更新冲突、写一写冲突， 忽略读集冲突检测和写集冲突检测。 常见的可接受性准则示例如下： 1 ) 银行账号的剩余金额不能为负； 2 ) 订票座位必须是靠近走廊的： 3 ) 商品的库存数量不能为负； 12 蔓三兰壁垫童墨二塑堡堡型 4 ) 剩余机票的数量不能为负； 因此，由暂态事务生成的基事务必须遵循一个准则：若它产生了与暂态事务不一致 的结果，而该结果能够通过准则测试，那么就是可接受的。可接受性准则实际上放宽了 对一致性的要求，减少了基事务失败的几率，却仍保证了事务执行的正确性，一定程度 上提高了系统的性能。 3 3 移动结点e m d b 状态分析 中心数据库服务器( c d b s v r ) 上的事务满足a c i d 性质，并通过两段锁协议保证事务 调度的可串行性，但移动结点( m c ) 上的事务提交时仅处于本地提交状态，需要在c d b s v r 上验证通过后方能全局提交，将其所做的数据修改写入c d b s v r 。m c 共有四种状态，即 一致性状态( c o n s i s t e n ts t a t e ) 、次一致性状态( s u b c o n s i s t e n ts t a t e ) 、积累状态 ( a c c u m u l a t i n gs t a t e ) 和消解状态( r e s o l v i n gs t a t e ) ，并依次在这四种状态之间进行转 换。 1 一致性状态( c o n s i s t e n ts t a t e ) m c 与c d b s v r 进行同步后，双方均己根据对方新近( 延迟更新传播时间t 之内) 所做的修改刷新了本地数据，因此对应的元组在m c 和c d b s v r 上具有相同的值，此时m c 处于一致性状态。 在该状态下，m c 上的暂态事务日志为空，各数据对象在m c 和c d b s v r 上是同一版本。 2 次一致性状态( s u b c o n s i s t e n ts t a t e ) 同步处理过程结束后从m c 与c d b s v r 断开连接开始，直到眦开始在本地副本上 执行暂态事务止，在这段时间内的状态为次一致性状态。 在该状态下，凇上的暂态事务日志为空，各数据对象在艟c 与断接前的c d b s v r 上是 同一版本。 3 积累状态( a c c u m u l a t i n g s t a t e ) m c 与c d b s v r 断开连接并在本地副本上执行暂态事务后，直到m c 与c d b s v r 重新连接并启动同步处理过程止，m c 在这段时间内的状态为积累状态。移动用户执行 的暂态事务由e d b m s 维护，在每次移动用户成功执行暂态事务后，e d b m s 将该暂态 事务记录入暂态事务日志。暂态事务可以并发执行，由e d b m s 中的并发控制机制( 如 时间戳方法、两段锁协议等) 保证事务调度满足可串行性准则，即其执行结果等价于某 查堕查主竺圭兰些丝兰 个串行调度的结果。s w i f t d b 系统中的e d b m s 支持s q l ，因此暂态事务可以用一个s q l 语句序列来表达。暂态事务目志文件格式如图3 2 所示。 在该状态下，m c 上的暂态事务日志逐渐变大，m c 和c d b s v r 上版本不同的数据 对象的个数逐渐变多。 个 事 务 事务数 s q l 语句( 以o 结尾) 下一s q l 语句 事务间隔标记 下一事务 图3 , 2 暂态事务日志文件格式 4 消解状态( r e s o l v i n g s t a t e ) 当m c 重新与c d b s v r 连接时，启动同步处理过程，此时它处于消解状态。移动结点 首先将本地的暂态事务序列传送给基结点。基结点依次对暂态事务进行冲突检测，通过 检测的事务在c d b s v r 上全局提交将不会破坏数据库的致性，因此对于通过检测的则 将以基事务的形式重做每个暂态事务，并将成功提交的事务结果返回给眦。如果暂态事 务未能通过检测，该事务夭折，基结点将有关失败信息返回给。最后，m c 根据本次 积累状态下( 时间间隔t 之内) c d b s v r 所做的数据更新刷新本地数据库副本，从而与 c d b s v r 保持一致。 在该状态下，m c 和c d b s v r 上版本不周的数据对象的个数逐渐变少，m c 上的暂态事 务目志逐渐变小。直到同步处理过程结束后，m c 上的各数据对象与c d b s v r 上版本相同， m c 上的暂态事务日志被清空，m c 又回到一致性状态。 5 几点假设 为使问题简化，本文作以下几点假设： ( 1 ) 由于s w i f t d b 系统中的m c 上执行的暂态事务由e d b i s 负责管理与维护，因 此不妨假设m c 上各暂态事务串行执行。 ( 2 ) 假设当m c 重新与c d b s v r 连接时，启动同步处理过程中m c 上没有其他暂态 事务。阻此，m c 在由消解状态转换为一致性状态期间，不能执行其他暂态事务。 第三章移动事务一致件模犁 ( 3 ) 当m c 重新与c d t 3 s v r 连接并启动同步处理过程时，m c 将本地的暂态事务日志 中的全部暂态事务组成序列传送给基结点进行同步处理。 ( 4 ) 同步处理过程结束后，与m c 相关的所有数据对象在该m c 上的数据副本与 c d b s v r 上版本相同，m c 回到完全一致性状态。 基于上述几点假设，移动事务一致性实现策略关键问题就变成解决移动计算环境下 移动结点上执行的暂态事务应何时与基结点连接并启动同步处理过程，以提高系统效率 和应用可靠性。 3 4 移动事务一致性问题的p r t _ 系统模型 谓词变迁系统简写为p r t 一系统，其中，t 表示变迁，谓词p 表示其中个体的当前 状态，谓词中的标识是由个体组成的集合。个体集称为系统的论域，用d 表示。如果p 等同于一个固定的子集，则p 为静态谓词，否则p 为动态谓词。谓词p 所等同的子集又 称为p 的外延，静态谓词有固定的外延，动态谓词则有可变外延 1 5 】。 假设c d b s v r 上与m c 相关的数据对象为a ，b ，c ，则移动事务一致性系统的论域 d = f a ，b ，c ) ；变迁分为四类：a - 与c d b s v r 断开连接，b - - - 执行暂态事务，c - - - 与c d b s v r 重新连接并启动同步处理过程，d - - - 同步处理过程结束；论域d 上的可变谓词集兀= c o n s i s t e n t ，s u b c o n s i s t e n t ，a c c u m u l a t i n g ，r e s o l v i n g ) ；v = x ) 为d 上的变 量集。分别定义d 上的两个一元运算f i ”、g m 如下： 1 若胍上基于一元组( x ) 的暂态事务可以成功全局提交的概率大于预先设定值， 则印( x ) = t r u e ；否则，对于一元组( x ) 。f ( 1 ( x ) _ f a l s e 。 2 若m c 上基于a ，b ，c 的任意一个暂态事务可以成功全局提交的概率小于预先设定 值，则g ( 1 ( a ) = g ( 1 ( b ) = g ( 1 ( c ) = t r u e ；否则，对于一元组( x ) g ( 1 i ( x ) ：f a l s e 。 图3 3 是移动事务一致性问题的p r t _ 系统模型，其中初始标识和a p ，a t ，a f ， 均以图示的方法给出，不再给出定义它们的公式。 东南大学硕十学位沦文 s u b c o n s i s t e n t r e s o l v i n g 图3 3 移动事务一致性问题的p r l 系统模型 1 6 t l n g 第四章移动事务一致性交现繁略 第四章移动事务一致性实现策略 4 1 数据分类及权限控制 一个不加任何限制的乐观复制方法( u p d a t ea n y w h e r e a n y t i m e - a n y w a y ) ，当系统 负荷增加时性能不稳定，死锁或需要冲突解决的事务数量随结点的增加成立方增长口i 。 在移动计算环境下，结点通常分为移动结点和基结点，移动结点一般是通过不可靠 网络进行连接的，如无线连接，它会经常性地处于断开的状态；而基结点则是通过可靠 网络连接的。多数的主副本在基结点上，也有少数主副本在移动结点上，对暂态事务的 数据操作加以权限控制以降低数据冲突的可能性。 1 数据分类 在移动计算环境下，用户规模和有限的通信带宽给系统性能造成了极大的制约，如 果不加选择地在中心数据库服务器( c d b s v r ) 上处理所有的暂态事务的全局提交请求， 系统的性能将是不可想象的。为简化移动环境下事务处理的复杂性，将移动终端( m c ) 与c d b s v r 之间传递的数据进行分类，并采取相应的同步处理簧略。m c 与c d b s v r 之间传 递的数据大致可以分为以下三类： ( 1 ) 私有数据( p f i v a t ed a t a ) 这类数据专属于某个移动用户，其他移动用户没有存取权限；c d b 上的用户可以读 这类数据，但不具备写权限。 ( 2 ) 公共数据( p u b l i cd a t a ) 这类数据由c d b 上的用户进行维护，移动用户只能读这类数据。 ( 3 )