（计算机软件与理论专业论文）移动事务管理中的若干关键问题研究.pdf

a b s t r a c t 摘要 移动数据库的研究是当前计算机领域的一个热点。作为移动数据库的基础性 技术之一，移动事务管理在移动环境网络不稳定、主机节点移动性等条件下实现 数据库访问的一致性、可用性和高性能。 本文分别针对移动环境的本地事务管理、事务内部并发控制和移动分布式事 务提交等移动事务管理的核心内容，给出如下研究成果： 一、本文给出了一个应用于高质量集中式移动环境的本地并发控制方法 a s g t 。本文指出：高质量移动环境支持基于阻塞的并发控制方法，但其固有的 带宽波动特征将导致阻塞率上升，因而影响事务管理性能。a s g t 具有显著的低 阻塞特征，能够改善系统的并发度、吞吐量和峰值负载。a s g t 通过一种新的验 证方式后向验证能够预测未来的冲突，并据此提f i 发现并撤销相应的冲 突事务。a s g t 的调度代价与两阶段锁方法( 2 p l ) 具有相同的复杂度，但阻塞 率、预测能力和撤销事务的选择性等主要指标都优于2 p l 。本文通过基于概率的 理论分析模型和完整实现事务调度的模拟器说明了a s g t 的性能优势。 二、本文基于a s g t 给出了适应于复杂结构事务的t a s g t 方法。a s g t 的 后向验证方式可能在复杂结构事务中产生误撤销现象，t a s g t 除实现a s g t 的 基本执行模式，还能够在执行过程中对发现并动态剪枝确定不执行的分支，减少 了后向验证时误撤销的发生概率。 三、本文将静态、并行事务等领域适用的i n t r a t r a n s a c t i o n 方法引入k a n g a r o o 事务，实现子事务的并发执行。k a n g a r o o 是移动环境中一种适应性较强的事务 模型，但其内部的串行执行方式对效率造成不利影响。本文对k a n g a r o o 模型进 行改进，给出i k c c ( i n t r a k a n g a r o oc o n c u r r e n c yc o n t r o l ，k a n g a r o o 内部并发控 制) 方法。i k c c 满足事务内部并发的原则并保持事务内部的全局一致性。i k c c 基于静态2 p l ，并充分利用事务内部非严格调度的灵活性，通过分割、传播和合 并等三个步骤，实现子事务在不同站点的分布执行和同一站点的并发执行。与现 有静态调度的i n t r a t r a n s a c t i o n 方法相比，i k c c 在事务执行和切换过程中动态给 出并发调度顺序。 四、本文针对移动节点参与分布式提交的效率和稳定性问题，提出了一种结 合移动层固定层提交的原子提交协议：两层两阶段方法( 2l a y e r2 p c ，2 l 2 p c ) 。 2 l 2 p c 充分利用基本提交方法p r c 的性质和固定层的支持作用，在两层同时发 起提交，并因此免除部分磁盘操作和信息传送导致的阻塞，显著降低提交的时间 复杂度。2 l 2 p c 在全局撤销时提前结束全局协调者，改善了朴质的p r c 在撤销 a b s t r a c t 情况下的低效率性质。针对提交过程中的切换问题，2 l 2 p c 通过在切换过程中的 h o p - i n h o p o u t 匹配删除和全局决策的m a t c h i n g 方法，在相当程度上避免对 切换路径的追踪，有效减少切换事务的执行代价。本文根据提交代价衡量的般 方法，得出2 l 2 p c 的主要性能指标和有效性结论。 关键词：移动数据库、移动事务、并发控制、性能、事务内并发、全局提 交、一致性 a b s t r a c t m o b i l ed a t a b a s ei so n eo ft h eh o t t e s tf i e l d si n c o m p u t e rs c i e n c e b e i n gt h e i n f r a s t m c t u r a lt e c h n o l o g y , m o b i l et r a n s a c t i o nm a n a g e m e n ts h o u l db ei nc h a r g eo f h i g h e f f i c i e n ta n dc o n s i s t e n ta c c e s st od a t a b a s eu n d e rt h ec o m p a c to fm o b i l e e n v i r o n m e n t s ，s u c ha st h ei n s t a b i l i t yo fw i r e l e s sc h a n n e la n dt h em o b i l i t yo fm o b i l e u n i t s t h i sp a p e rp r o p o s e dt h ea c h i e v e m e n t sm a d ei naf e wk e yr e s e a r c hf i e l d so f m o b i l et r a n s a c t i o n m a n a g e m e n t 一一l o c a l t r a n s a c t i o n m a n a g e m e n t ， i n t r a - t 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 dg l o b a lc o m m i t m e n to fm o b i l eu n i t s f i r s t l y ，a na p p r o a c h ，c a l l e da s g t , t oc o n c u r r e n c yc o n t r o lo fl o c a lt r a n s a c t i o n si n ah i g h - q u a l i t yc e n t r a l i z e dm o b i l ee n v i r o n m e n ti sp r o p o s e d t h eh i g h - q u a l i t ym o b i l e e n v i r o n m e n tf u l f i l l st h eu s a b i l i t yo ft r a d i t i o n a lb l o c k b a s e dm e t h o do fc o n c u r r e n c y c o n t r o l ，h o w e v e r , t h i sw i l lr e s u l ti nah i 。g hb l o c k i n gr a t ed u e 幻b a n d w i d t hf l u c t u a t i n g o fw i r e l e s sc o m m u n i c a t i o n s p o s s e s s e da no u t s t a n d i n gl o wb l o c k i n gp r o p e r t y , a s g t c a n s u b s t a n t i a l l yi m p r o v et h ec o n c u r r e n c y , t h r o u g h p u ta n dt r a s h i n go fm o b i l e t r a n s a c t i o n ，a n ds t i l lc o n f i r m st h es t r i c tc o n s i s t e n c y an e ws c h e m a ，c a l l e da f t e r w a r d v a l i d a t i n g ，i si n t r o d u c e di n t oa s g tt op r e d i c tt h ef u t u r ec o n f l i c t sa n da b o r tt h e c o r r e s p o n d i n g t r a n s a c t i o ni na d v a n c e a s g t , w i t ht h es a l n e c o m p u t a t i o n a l c o m p l e x i t yo fs c h e d u l i n gc o s ta s2 p lc a np r o d u c ear e m a r k a b l ep e r f o r m a n c e w e d e m o n s t r a t et h ee f f i c i e n c yo f a s g t b yb o t ha n a l y t i cm o d e la n ds i m u l a t i o nr e s u l t s a n dt h e n ，av a r i a t i o no fa s g t , c a l l e dt a s g t , s h o r t e n e d b yt a s g t , i sp r o p o s e d t os u r v i v et h ei m p a c to fc o m p l e xs t r u c t u r e so nm o b i l et r a n s a c t i o np r o c e s s i n g t h e s c h e d u l i n go fa s g ti nat r a n s a c t i o nw i t hc o m p l e xs t m c t u r e sm a yl e a dt ot h e m i s a b o r t i n gat r a n s a c t i o nf o rt h ep r e d i c a t i o nm a n n e ro ff o r w a r dv a l i d a t i n g t a s g t c a na v o i dt h em i s a b o r t i n gb yp r u n i n gt h eo v e r l o o k e db r a n c h e sd y n a m i c a l l yd u r i n g p r o c e s s i n go ft r a n s a c t i o n s t h i r d l y , w ei n t r o d u c et h ei n t r a - t r a n s a c t i o nm e t h o dt r a d i t i o n a l l yu s e di nt h ef i e l d s o fs t a t i co rp a r a l l e lt r a n s a c t i o nm a n a g e m e n ti n t ot h em a n a g e m e n to fk a n g a r o o t r a n s a c t i o nm o d e l b e i n go n eo ft h em o s ta p p l i c a b l em o b i l et r a n s a c t i o nm o d e l s ， k a n g a r o oi sh e a v i l yi m p a c t e db yt h es e r i a lm a n n e ro fs u b t r a n s a c t i o np r o c e s s i n g a n a p p r o a c h ，c a l l e di k c c ( i n t r a k a n g a r o oc o n c u r r e n c yc o n t r 0 1 ) i si n t r o d u c e dt o i m p l e m e n tt h ei n t m - t r a n s a c t i o ns c h e d u l i n gi nak a n g a r o ot r a n s a c t i o n b a s e do na s t a t i c2 p li k c cc a nt a k ef u l la d v a n t a g eo fn o n s t r i c tm a n n e ri ni n t r a - t r a n s a c t i o n a b s t r a e t a c c e s s i n ga n dp r o d u c et h ev a l i d a t e ds c h e d u l i n gh i s t o r yd y n a m i c a l l yb ys p l i t t i n g ， p r o p a g a t i n ga n dm e r g i n gs t e p s l a s t l y , a na t o m i cc o m m i t t i n gp r o t o c o l ，c a l l e d 2 l a y e r2 p c ( 2 l 2 p c ) ，i s d e v e l o p e dt os u r v i v et h em o b i l eu n i t sf r o mi n s t a b i l i t ya n di n e f f i c i e n c yi n 百o b a l c o m m i tb yc o m b i n i n gt h ec o m m i tp r o t o c o lo ff i x e dl a y e rw i t ht h a to fm o b i l el a y e r b a s e do nap r e s u m e dc o m m i t2 p c ( p r e ) ，2 l 2 p cc a nm a k et h em o s to ft h e u n d e r l y i n gc o m m i tp r o t o c o la n dt h es t a b i l i t yo ff i x e dn o d e st oi n i t i a t i n gt h ec o m m i t c o n c u r r e n t l yf r o mb o t ht w ol a y e r s ，h e n c ei tc a ns a v eaf o r c ew r i t el o ga n d ar o u n do f m e s s a g e s ，w h i c hc a nr e m a r k a b l yi m p r o v et h et i m ec o m p l e x i t yo fc o m m i tp r o c e s s 2 l 2 p cc a nf r e et h eg l o b a lc o o r d i n a t o ri na d v a n c et oa m e n d i n gt h ei n h e r e n td e f e c to f p r ci na b o r t i n gc a s e s i ft h eh a n d o f fp h e n o m e n o nt a k e sp l a c ed u r i n gt h ec o m m i t t i n g ， 2 l 2 p cc a na v o i dt r a c k i n gt h eh a n d o f fp a t hi nal a r g ed e g r e eb yd e l e t i n gt h e h o p - i n h o p o u tp a r e so fi n f o r m a t i o na n de x e c u t i n gam a t c h i n ga l g o r i t h mi n g l o b a ld e c i s i o n ，w h i c hc a ne f f i c i e n t l ys m o o t ht h ec o s to fh a n d l i n g t h eh a n d o f f a c c o r d i n gt ot h eg e n e r a lm e a s u r e m e n to fc o m m i tc o s t ，t h ee f f i c i e n c yo f2 l 2 p ci s s h o w nb yc o m p a r i n gt oa ne x i s t e dc o m m i tp r o t o c o li nm o b i l ee n v i r o n m e n t ，a n dt h e e f f i c i e n c yo fh a n d o f fp r o c e s s i n gi n2 l 2 p ci sa l s od e m o n s t r a t e db yc o m p a r i n gt ot h e e x i s t e da p p r o a c h e s k e yw o r d s ：m o b i l ed a t a b a s e ，m o b i l et 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 l ， i n t r a t r a n s a c t i o n ，g i o b a ic o m m i t ，c o n s i s t e n c y 第一章绪论 第一章绪论 1 1 立题背景和研究意义 从8 0 年代开始，计算机领域内提出了一个新的思想：“网络就是计算机”， 基于网络的计算方式成为计算机发展的基本思想，而通信领域的发展也成为推动 计算机发展的最重要的动力之一。 进入9 0 年代，在应用和技术的相互作用下，移动通信获得了巨大发展和迅 速普及。这同样对计算机领域产生了深远的影响，使得网络计算开始摆脱有线通 信方式的束缚，进入基于移动通信的时代。网络计算因此变得更加灵活、高效和 快捷，产生了一种新的网络计算形式移动计算( m o b i l ec o m p u t i n g ) i b 9 4 ， d h a 9 9 】。 1 1 1 无线与移动通信技术的发展 1 、无线与移动通信技术 无线与移动通信网络是移动计算的基础，现有的无线与移动通信技术主要有 以下几种 i b 9 4 ，d h a 9 9 ： ( 1 ) 无线局域网 无线局域网是指以无线信道作为传输媒介的计算机局域网络( w i r e l e s s l o c a la r e an e t w o r k ，简称w l a n ) 。它突破了有线网络中布线接点位置的限制， 使计算机能够以无线互联的方式实现资源共享。w l a n 能够实现较高的数据传输 速率( 大于1 m b p s ) 和可靠性，但它的使用范围有限，如在一个校园或厂区内。 8 0 2 1 l 标准族 i e e e8 0 2 1 l 是最早提出、也是发展最快的无线局域网标准族。1 9 9 7 年6 月公布的8 0 2 1 1 标准工作频段为2 4 g h z 的i s m 频段( i n d u s t r i a l ，s c i e n t i f i c ， a n dm e d i c a l ，工业，科学与医疗频段，这个频段是无需申请许可、能够自由使 用的免费频段) ，最大传输距离为l o o m ，数据传输速率为1 m b p s 和2 m b p s 。其中， 8 0 2 1 l b 在i s m 频段，并达到i 1 m b p s 的数据传输速率，成为迄今为止现实中应 用的主流标准。其它标准如8 0 2 1 l a ，8 0 2 1 l g ，8 0 2 1 l e 和8 0 2 1 l f 能够分别解 第一章绪论 决带宽、兼容性、q 0 8 和漫游等问题。8 0 2 1 1 标准族的实现为两个射频方式( r f ) 和一个红外方式( i r ) 。 h o m e r f h o m e r f 是美国家用射频委员会领导的h o m e r f 工作组在1 9 9 8 年制定的面向 家庭网络的标准。h o m e r f 工作频段为2 4 g h z 的i s m 频段，传输速率为1 m b p s 一 2 m b p s ，最新建议为l o m b p s 。h o m e r f 是i e e e 8 0 2 1 1 与d e c t ( 数字无绳电话标准) 结合的产物，但与8 0 2 1 l b 并不兼容，并与8 0 2 1 l b 和蓝牙工作频段冲突，具有 较大局限性，主要应用于家庭网络。 蓝牙( i e e e 8 0 2 1 5 短距离无线网络) 蓝牙( b l u e t o o t h ) 是由东芝、爱立信、i b m 、i n t e l 和诺基亚于1 9 9 8 年5 月 共同提出的近距离无线数字通信的技术标准。蓝牙的工作频段为2 4 g h z 的i s m 频段，传输距离为1 0 i 0 0 米，数据传输速度为1 m b p s 。作为8 0 2 1 1 的重要补 充，蓝牙主要应用于信息家电、移动通信等小型及嵌入式设备，目的是实现低成 本、低功耗、大容量、近距离和安全的无线数字通信。蓝牙的移动性比8 0 2 1 1 更强，能够在移动中灵活地接入局域网和广域网，甚至支持全球漫游，还能够支 持点对点和点对多点的连接。 红外无线局域网 红外传输采用波长小于l 微米的红外线作为传输媒体。红外传输的优势是应 用广泛( 估计至少有1 亿台设备具有红外端口) ，价格低廉，安全性高，不受管 制，其传输速率可以达到4 m b p s ，最新的扩展能够达到1 6 m b p s 。但红外传输要求 较强的方向性，限于视距传输( 3 8 m ) ，并且易受干扰。所以，在实际应用中， 红外局域网也是作为8 0 2 1 1 在近距离的重要补充。 ( 2 ) 卫星通信 卫星通信是以卫星中的转发器作为中继站转发无线电波，实现两个或多个地 球站之间的通信，具有无缝覆盖，覆盖面广，通信距离长，通信线路稳定，通信 频带宽、容量大等优点。但是，卫星通信也面临高延迟、安全性( 人人可接收) 和成本等问题，这些问题导致了著名的“铱系统”的失败。卫星通信主要用于广 域网，提供在广阔地域、特别是人口稀少和恶劣地理条件地域的通信服务，如微 软的t e l e d e s i c ，可提供2 m b p s 上行链路和6 4 m b p s 下载链路等，休斯的s p a c e w a y ， 提供6 m b p s 上行链路和1 6 m b p s 下载链路，等等。 ( 3 ) 数字蜂窝通信系统 数字蜂窝通信是移动通信中发展最迅速、研究最活跃也最普及的领域。蜂窝 概念的提出使得系统能够实现频率复用，解决了带宽与系统容量之间的矛盾，成 为移动通信最重要的发展方向。第一代移动通信系统( 1 “g e n e r a t i o n ，1 g ) 为 2 第一章绪论 基于模拟制式的蜂窝通信系统，频宽为1 2 5 至3 0 k h z 。第二代移动通信系统( 2 “ g e n e r a t i o n ，2 g ) 称为窄带数字通信系统，如g s m 。g s m 的传输速率为9 6 k b p s ， 并作为g p r s 的基础应用分组技术实现高达1 7 1 2 k b p s 的移动数据通信。 3 g ( 3 “g e n e r a t i o n ，3 g ) 能够实现2 0 0 0 k b i t s 的传输速率，并能够满足多种 业务提供、高安全性和高容量等要求。其制式有w c d m a 、c d m a 2 0 0 0 和 t d s c d m a 等三种李2 0 0 3 1 。 移动通信在中国的发展非常迅速，已经逐渐接近、并在某些领域达到国际领 先水平。1 9 8 7 年开始模拟蜂窝系统的运行( 己于2 0 0 1 年1 2 月3 1 日关闭) ；1 9 9 3 年开始运行g s m 系统；1 9 9 8 年制定g p r s 标准；1 9 9 9 年6 月大唐电信代表中 国提出t d s c d m a 。现在，中国己成为拥有移动用户最多的国家，2 0 0 4 年底， 中国有移动用户3 3 5 亿户，普及率超过1 4 。随着t d s c d m a 的研究，中国也 成为在移动通信技术领域的领先国家之一。因此，开展基于移动通信的相关领域 研究，对我国技术和经济发展具有非常现实的意义。 2 、移动与无线 无线通信与移动通信的概念既有联系又有区别。无线通信指通信的媒介是无 线信道，移动通信则指移动节点在位置变化的同时，能够不重启和不中断地进行 正常工作。在大多数无线局域网的应用中，终端虽然与服务器通过无线连接，但 工作时仍处于静止状态。因此，对于实现终端的移动性，移动通信显然具有更重 要的意义。 3 、移动通信发展方向与特征 在下游应用技术和学科自身需求的推动下，移动通信表现出如下显著的发展 方向与特征： ( 1 ) 稳定性： 移动通信的一个重要问题是稳定性差。 一断接 在早期的移动通信中，稳定性问题主要表现在较高的断接发生率。许多基于 移动通信的研究不得不以高断接率作为研究的前提条件和衡量标准，如基于1 0 或者更高的断接率。在经过多年的技术和建设的发展后，断接率已经大幅度改 善。语言通信相对于数据通信而言，要求在物理层具有更低的断接率( d r o p r a t i o ，掉话率) 。在2 0 0 1 年的中国城市移动通信质量测试中，已经实现了静止 0 3 3 ，运动0 9 7 的断接率，在断接最常发生的切换过程中，综合断接率也达 到1 以下。而在3 g 中，进一步通过诸如“软切换”等技术内容保证了更低的断 接率。在此物理基础上，以包交换为主要传送形式的数据通信还可以通过重发等 方式保证通信的连续性。因此，断接在现在及未来的高质量网络环境中不应该继 3 第一章绪论 续被视为稳定性的主要标志。 无线带宽波动 尽管断接问题已经不再严重，但由于无线方式本质的特征，移动通信不可能 达到如固定信道一样的稳定性，主要表现为无线通信中的带宽波动。无线带宽的 波动是由i ) 天气和城市地形：i i ) 小区用户数变化而导致的。在3 g 中， 为保证服务质量而应用自适应方式，在调整小区用户容量的同时也加剧了每个用 户所享有的带宽波动。与断接问题不同，因为天气、地形和用户移动是必然的客 观因素，所以带宽波动作为移动通信的本质特征将长期存在 b k p 0 3 。 ( 2 ) 高带宽： 高带宽是移动通信最重要的发展目标，是发展其它所有高端应用的基础。从 g s m 的9 6 k b p s 到g p r s 的1 7 1 2 k b p s ，几乎每一种移动通信技术的出现都是以 提高传输速率为目的的。3 g 的带宽2 m b p s 与互联网中宽带概念的带宽相吻合， 这并不是巧合，它意味着移动通信的目标是实现与固定网络同样的服务质量与内 容。 ( 3 ) 高容量： 从模拟蜂窝通信到3 g ，另一个显著进步就是容量的提高。对于一个区域的 覆盖能力，c d m a 比g s m 所需基站数少8 0 。而t d s c d m a 还可以应用智能 天线技术进一步提高容量。高容量提高了服务用户数，使得移动通信可以更加普 及，应用领域更加广泛。 ( 4 ) 服务质量自适应： 在移动通信的研究中，带宽和容量是一对矛盾，特别是在因用户移动而导致 小区内数量变化幅度较大的情况下。在3 g 中，采取了一种折中的思想，即在保 证基本通信需求的基础上，如果小区内用户数超过一个阈值，则降低每个用户的 服务质量( 带宽) ，以保证容量的需求 x s m 0 3 。 ( 5 ) 综合服务能力： 移动通信从模拟蜂窝发展到3 g ，它所提供的服务已经从单一的语音发展到 语音、数据和多媒体等多种内容。不同的服务对通信方式和质量的要求是不同的， 如语音通信不要求带宽，但对延迟的要求很严格，而数据通信则相反。3 g 将这 些目标很好地融合在一起，针对不同服务内容提供最佳的方式。 1 1 2 移动计算与移动计算机 移动计算机是指具有较大内存与较强处理能力的移动计算设备，如笔记本电 脑、个人数字助理( p e r s o n a ld i g i t a la s s i s t a n t ，p d a ) 和智能移动电话( s m a r t 4 第一章绪论 p h o n e ) 等。现在的移动计算机不但在处理能力、内存与磁盘等方面足以和同类 台式机相媲美，更在移动通信的支持方面表现出丰富而强大的能力。如笔记本电 脑普遍具有无线网卡、红外和蓝牙等设备，新一代i n t e l 处理器还具有迅驰技术 支持。因此，移动计算机越来越能够适应于较大规模的计算、存储领域，如数据 库等。 主要基于移动计算机，并通过无线网络为主的移动联网设备，形成一种能够 支持移动用户访问网络中数据的分布式网络环境，称为移动环境( m o b i l e e n v i r o n m e n t ) ，相应的计算方式称为移动计算( m o b i l ec o m p u t i n g ) i b 9 4 。 1 、移动计算研究领域 移动计算包含的内容很广泛，从i s oo s i 的分层理论角度，包括从下到上物 理层( 移动硬件设备、移动通信) ，数据链路层、网络层和传输层( 移动i p 技术) ， 以及应用层( 如无线w w w 访问、移动数据库和移动文件访问、移动客户服务器 应用等) i b 9 4 ，s a t 9 9 。 2 、移动环境的类型 移动环境按照其网络逻辑结构，可以分为下面三类 s e y 9 9 ： ( 1 ) 集中式移动环境( c e n t r a l i z e dm o b i l ee n v i r o n m e n t ) 如图1 1 ( a ) 所示，集中式环境中包括两类节点：移动单元( m o b i l eu n i t ， m u ) 可以任意漫游并能够由一个小区移动到另一个小区在每个小区中存在一 个移动基站( m o b i l es u p p o r ts t a t i o n ，m s s ) ，为小区中的m u 提供服务。基站 通过有线网络连接，所以也被称为固定节点( f i x e dh o s t ，f h ) 。一般地，m s s 之间的连接被认为是代价较低、稳定的连接，而m u 和对应小区中m s s 的连接 则通过无线信道实现，被认为是代价较高的、不稳定的连接。当m u 移动的范 围跨越两个小区的边界时，相关的两个m s s 必须交互以实现跨区切换( h a n d o f f ) ， 如图( b ) 所示。 图1 1 集中式移动环境：a ) 网络结构：b ) m u 切换过程 在集中式移动环境中，一般假设全部或可信计算( 如主副本) 位于m s s 上， 5 第一章绪论 从全部固定网络的角度，m s s 作为分布计算的一个节点。m u 的计算能力较弱， 与其所属的m s s ( 在小区内) 或分布式系统( 全部固定网络空间) 构成c l i e n t s e r v e r 关系。有的研究者也假定m u 具有根据缓存数据进行本地计算的能力，但不具 有分布计算节点的功能。 ( 2 ) 分散式移动环境( d e c e n t r a l i z e dm o b i l ee n v i r o n m e n t ) 在分散式移动环境中，不假定节点的固定特征，认为所有节点都可能发生移 动。根据节点的存储、处理和通信能力，将节点分为强节点( s t r o n gn o d e ) 和 弱节点( w e a kn o d e ) 。在强节点上进行的计算被认为是可信计算，计算结果可被 其它节点直接共享：在弱节点上进行的计算被认为是不可信的计算，计算结果可 以被本地其它应用共享，但只有经过验证( 如全局提交或强节点验证) 或发送至 强节点上才能被全局共享。 ( 3 ) 完全分散式环境( f u l l y d e c e n t r a l i z e dm o b i l ee n v i r o n m e n t ) 完全分散式环境中所有的节点都具有相同的存储、处理和通信能力，都具有 移动性。节点之间的计算具有对等性质( p e e r t o p e e r ) 。 3 、移动环境的特点 与传统的基于固定网络的分布计算环境相比，移动计算环境有许多明显的特 点，除提供计算的灵活性外，还表现在如下方面的限制： ( 1 ) 移动单元限制 与固定网络中的客户端相比，移动计算环境中的移动单元的计算速度、内存 和辅助存储器都因其便携性而产生较大的限制。有的移动单元，如p d a ，甚至没 有辅助存储器。移动单元还具有有限电源的限制。 ( 2 ) 通信限制 在固定网络中，能够保证一个稳定的、持续的通信连接。而在移动计算环境 中，通信连接呈现出无线通信代价高、低稳定性和上下行不对称( 上行：从客户 端到服务器，低速率；下行：从服务器到客户端，高速率) 等特点。 ( 3 ) 切换 移动单元在计算过程中可能发生切换。这对于网络的稳定性、通信代价和计 算复杂性都提出了挑战。例如，m u 可能在一个数据库事务的执行过程中发生切 换，则事务的发起和结束将不在同一站点上，这无疑增加了移动事务的复杂性， 对于事务的a c i d 性质的保证也提高了难度 b e j 0 4 。 从上述无线通信和移动环境的特征，我们可以看出，移动计算环境的许多特 点在已有一些领域都可以找到对应情况。m u 的限制与早期集中式系统中的“哑” 终端类似 u 1 1 8 8 ，d h 9 5 ，b a r 9 9 ，通信的限制在i n t e r n e t 事务处理中也存在 b z g 9 5 ，s a l p + 9 6 ，而跨区切换可以类似于移动a g e n t 中的服务器切换 p i t 9 8 ， 6 第一章绪论 p s 0 4 。因此，移动计算中的方法往往基于具有类似环境特征的计算领域。 另一方面，上述移动环境的特征只是一个模糊的、总体的描述。在实际中， 上述特征并非全部同时出现在每种移动环境中，以本文所针对的移动数据库事务 为例，在现有模型中，还尚未有一种模型完全考虑上述全部特征。一般的，每种 模型都是基于某种特定网络环境，解决该种环境中突出的一种或有限几种问题， 而忽略或弱化其它方面。 需要注意的是，上述移动环境的分类依据是逻辑结构而非物理层的无线通信 系统结构 s e y 9 9 。在蜂窝系统中也可以建立分散式或完全分散式的移动环境， 如在移动通信系统中建立的v p n ：而在所有节点均为移动节点的通信系统中也 可以建立集中式的移动环境，如在战场上的指挥车与个人通信设备之间的关系。 移动环境结构还可以形成嵌套结构，如顶层为集中式系统而下一层为分散式系统 等。当然，出于实现的方便，多数移动环境的逻辑结构与其物理层通信结构是相 对应的。在本文中如不特殊说明，则移动环境的逻辑与物理结构是一致的。 1 1 3 应用背景和研究意义 数据库几乎是每一个现代信息系统中不可或缺的平台。在移动通信、移动计 算机的技术进步和商业普及成为现实的今天，越来越多的信息系统开始采用或部 分采用移动网络结构，而越来越多的移动网络也主动向数字化和综合服务发展。 所以，在移动网络上开展数据库的应用成为非常自然和重要的方向。事务管理作 为数据库的核心内容，是保证数据库一致性和效率的基本技术。所以，移动数据 库的能力和前景在很大程度上取决于移动数据库的事务管理技术，即移动事务的 发展。下面，本文将从移动事务管理的角度介绍几种移动数据库的典型应用。 1 、移动办公系统 霸 一 圈圆圈圈圈圉圉 图1 2 移动办公事务 移动保险人员的办公系统是移动数据库最典型的案例 i b 9 4 1 。如图1 2 所示， 7 第一章绪论 一个保险检查员服务于美国某大型汽车保险公司，他的职责是负责检查汽车受损 情况，并结合各种信息预估需要赔付的金额。在赶往事故现场的途中，他发出一 个移动事务请求，服务器按照交互方式执行该事务。按照传统事务执行方式，这 些操作属于一个扁平事务，因此必须串行执行。如果其中一个操作暂时无法执行， 则该事务将被阻塞。但是我们可以发现，“查询保险金额”与“检查警察记录” “获得事务报告”不构成依赖或冲突关系，我们完全可以在“检查警察记录” “获得事务报告”的同时，进行“查询保险金额”。这种调度顺序显然可以改善 图1 2 中交互事务的执行效率。 2 、金融领域应用 假定中国一个大型证券公司，为了即时把握瞬息万变的金融市场变化，建立 了基于移动网络的信息系统，使得该公司的证券交易人员能够在任何时间、任何 地点进行证券交易。如果在固定网络中，这显然是一个典型的c l i e n t s e r v e r 结构： 任一个交易人员都即时地访问公司的银行帐户数据库，从帐户中提取资金购买股 票，或售出股票将资金纳入帐户，即执行更新操作。在交易人员很多、分布很广 的情况下，如果按照传统基于阻塞的并发控制方法，如2 p l ，将会出现很多事务 在热点数据上以长锁雍塞的现象，性能将很差。这个问题的一种解决方法是预先 将数值型的交易帐户划分成多个帐户，其访问权限分别赋予不同的交易人员，使 得交易人员能够在本地数据库( 即m u 上) 高效、实时地完成全部操作。 上述两个应用中，第一种将并发控制扩展到事务内部的操作中；第二种将传 统数据库中基于语义的l e a s e 方法扩展到移动数据库中。大多数事务管理技术 对于用户来说都是透明的。事务管理提供了事务在保证一致性的前提下能够以并 发形式执行，是数据库的正确性和效率的基础保证。传统事务管理技术已经得到 了充分的发展，但在移动环境中还有许多问题有待研究。 随着移动通信技术的成熟和3 g 技术进入实用，特别是中国自主提出的 t d - g c d m a 的逐渐成熟，未来的移动通信将能够获得更加稳定高速的信道、智能 天线技术所提供的多向频率重用与方向定位、3 g 中与定位相关的如移动性管理 等更多高质量服务 李0 3 。这将促进移动数据库的更大发展和更深入的应用。 移动事务管理作为移动数据库的核心技术和基础结构，必将越来越凸现出其不可 或缺的重要意义。 1 2 移动数据库研究领域与现状 从2 0 世纪9 0 年代初期开始，移动数据库成为一个新的研究领域 i b 9 4 ， d h a 9 9 。移动环境的独有特征使得数据库领域的许多技术都有了新的含义。随着 8 第一章绪论 移动通信的技术进步和商业普及，移动数据库越来越成为现实关注的焦点。因此， 无论从移动计算的角度，还是从数据库领域的角度，移动数据库技术也已经成为 一个研究热点 d h 9 5 ，g r a 0 0 ，b r a 9 9 1 。 在移动数据库领域中，国外的一些著名研究机构如美国的r u t g e r s 大学、 b r o w n 大学、卡内基一梅隆大学( c m u ) 、佐治亚理工学院、澳大利亚m o n a s h 大 学等已经在许多方面给出了开创性的成果，国内的一些研究机构如中国人民大 学、复旦大学和华中理工大学也在自己已有数据库成果的技术基础上针对移动数 据库给出新的成果何唐李o o 。但是，移动数据库不但是一个尚未充分发展的领 域，它的关键技术还将随着移动通信技术的发展而发展，因此移动数据库技术的 本质和发展还需要进行更多的深入探讨。有关移动数据库的主要研究方向如下： 1 、复制与缓存技术 数据复制是传统数据库中为提高分布式系统可用性、访问性能的一个重要方 法。移动环境中的复制必须自动适应用户访问范型，即能够根据当前m u 的分 布与访问情况，动态调整数据分布布局和策略，使m u 能够就近访问到所需数 据，提高访问性能。在集中式移动环境中，g h o s 9 6 给出了两级复制( t w o - t i e r r e p l i c a t i o n ) 技术，一级复制在服务器之间进行，第二级复制在m u 上保存数据 库上的复制( 即缓存) ，实现高断接情况下的可用性。而在分散式移动环境中， 多应用基于主动复制的方法 b k 9 7 ，p i t 9 6 ，p b 9 5 b ，w 0 1 0 2 ，l l s g 9 2 】。 在高断接的环境中，在m u 上缓存所需的数据是一种自然的选择 l h y 9 9 ， m p c 0 1 1 。在移动文件系统c o d a 中，应用主动方式进行缓存更新 k s 9 1 ，s a t 0 2 ， h o n 0 2 1 。而在 l c l a 0 0 ，l c l 0 4 1 中，应用基于数据广播的缓存更新方法，具有 较好的伸缩性。 2 、移动数据库的事务管理 移动事务可以视为分布式事务或c l i e n t s e r v e r 事务基于移动环境的扩展。在 移动计算环境中，移动事务通常具有客户端移动性、高阻塞率和易错性等性质， 并且这些特征还将随着移动环境的发展而发展。这使传统的事务模型和事务管理 不能很好地描述移动事务。研究者针对不同移动环境特征和问题域，提出了相应 的事务模型 b a r 9 9 ，s e y 9 9 ，s r a 0 1 1 。为了实现一致性与可用性的折中，【g l 0 3 ， p b 9 5 a 给出了弱一致性的范围和在移动事务中的应用。移动事务管理中的切换以 一种非透明的方式通过两个m s s 的协作实现 d a s 9 7 1 。 并发控制是移动事务管理中的核心内容。在主要针对断接问题的模型中，一 般应用乐观方法( o c c ) 【n o b 9 8 ，p h a 9 9 ，