（计算机应用技术专业论文）移动数据库缓存技术的研究.pdf

移动数据库缓存技术的研究 中文摘要 目前，我们已经进入了以网络计算为中心的时代，人们迫切需要在任何时候、 任何地点访问所需要数据，移动计算为之提供了手段。它是无线通信、网络技术 与移动计算设备相结合的产物，是一种更加灵活、复杂的分布式计算环境。移动 数据库技术是指支持移动计算的分布式数据库技术；同时移动代理技术由于其固 有的特点逐渐在分布式计算领域占据重要的地位，也成为当今软件技术研究的一 个热点。 缓存技术是提高数据访问性能的经典技术，已经在计算技术的多个方面得到 了成功的应用。在移动计算环境中，由于设备和网络资源的限制，缓存将发挥更 加重要的作用。缓存失效策略是充分利用缓存技术的首要保证，目的在于维护缓 存数据与服务器上数据的一致性。本文根据移动数据库的特点和目标，将移动代 理技术结合起来，设计出基于移动代理的移动数据库模型，在此基础上提出了基 于移动代理的缓存失效策略，该策略能够较好地处理移动计算环境中由于频繁断 接造成移动设备无法接收失效报告的问题。 关键字：移动计算；移动数据库；移动代理；缓存；失效报告 h i 移动数据库缓存技术的研究 c u n e n t l y , w ea r ei n t h ee r ao fn e t w o r kc o m p u t i n g p e o p kh o p et oa c 淌 i n f o r m a t i o na n y w h e r ea n da n y t i m e m o b i l ec o m p u t i n g , w h i c hi sc o h 忙i n t oe x i s td u e t ot h er a p i de x p e n d i n gt e c h n o l o g yo fc o m p u t e r , w i r e l e s sc o m m u n i c a t i o na n dn e t w o r k t e c h n o l o g i e s , m a k ei tp o s s i b l ef o rm o b i l et l r m o b i l ec o m p u t i n gi s am o r ef l e x i b l e ， c o m p l e xd i s t r i b u t e dc o m p u t i n ge n v i r o n m e n t ，t h em o b i l ed a t a b a s e st e c h n o l o g yi sa d i s t r m u t e dd a t a b a s e st e c h n o l o g yw h i c hs u p p o r t st h em o b i l ec o m p u t i n ge n v i r o n m e n t a n da tt h es a m et i m e ，t h em o b i l ea g e n tt e c h n o l o g yh a sg r a d u a l l yp l a y e dam o r ea n d m o r ei m p o r t a n tr o l ci nd i s t r i b u t e dc o m p u t i n gf i e l d sd u et oi t si n h e r e n tc h a r a e t e r i s t i e s m o b i l ea g e n th a sb e e nt h eh o t s p o ti i lc u r r e n ts o f t w a r et e c h n o l o g yr e s e a r c l l c a c h i n gi sac l a s s i c a lt e c h n o l o g yt oi m p r o v e t h ep e r f o r m a n c eo fd a t aa c o ：s a i th a s b e e ns u c c e s s f u l l ya p p l i e dt od i f f e r e n tf i e l d so f c o m p u t i n g t e c h n o l o g y c a c h i n gw i l lb e e v e nn l o r ei m p o r t a n ti nm o b i l es y s t e r n sb e c a u s eo fr e s o u r c e sl i m i t a t i o n so fm o b i l e d e v i c e sa n dw i r e l c s sn e t w o r k t oa s s u r et h a ta p p l i c a t i o n st a k ef 0 1 1a d v a n t a g eo fc a c h e 。 w eu s ec a c h ev a h d a t i o na l g o r i t h mt od e t e r m i n ew h e t h e rd a t ai nl o c a lc a c h ei s c o n s i s t e n tw i t ht h ep r i m a r yc o p yo nt h e5 c r r c e l 瞰a r t i c l ei sb a s e do nt h e c h a r a c t e r i a t i ca n d a i mo fm o b i l ed a t a b a s c s ，a n dam o b i l ed a t a b a s eb a s e do nm o b i l e a g e n tm o d e li sd e s i g n e d i tc a nb eu s e dt os o l v em a n yt h ep r o b l e m sr e s u l t i n gf r o m t h ed i s c o n n e c t i o no fm o b i l eh o s ti nm o b i l ec o m p u t i n ge n v i r o n m e n t s u c ha sr e c c i v i n g i n v a l i dr e ：p o r t k e y w o r d s ：m o b i l ec o m p u t i n g ；m o b i l ed a t a b a s e s ；m o b i l ea g e n t ；c a c h e ；i n v a l i d a t i o n r e p o r t s 移动数据库缓存技术的研究 原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导 下，独立进行研究所取得的成果。除文中已经注明引用的内容 外，本论文不包含任何其他个人或集体已经发表或撰写过的科 研成果。对本文的研究在做出重要贡献的个人和集体，均已在 文中以明确方式标明。本人完全意识到本声明的法律责任由本 人承担。 论文作者签名：盟日期： 关于学位论文使用授权的声明 本人完全了解贵州大学有关保留、使用学位论文的规定，同 意学校保留或向国家有关部门或机构送交论文的复印件和电子 版，允许论文被查阅和借阅；本人授权贵州大学可以将本学位论 文的全部或部分内容编入有关数据库进行检索，可以采用影印、 缩印或其他复制手段保存论文和汇编本学位论文。 ( 保密论文在解密后应遵守此规定) 论文作者签名：量查筮导师签 移动数据库缓存技术的研究 第一章绪论 1 1 本文研究的背景和目的 随着移动通信技术的迅速发展和移动设备( 手机、p d a 、笔记本电脑) 的普 及，使得人们在任何时候、任何地点访问信息的需求得以满足。移动数据库已经 得到广泛的关注，在零售业、智能交通、航天航空、医疗卫生等领域展现了广阔 的应用前景，为人类带来了巨大的商业和社会价值。可以预见，未来的绝大部分 计算机都将配备以无线网络为主的移动联网设备，以支持移动用户访问网络中数 据的需求。这将是一种比传统的分布计算环境更加灵活、复杂的分布计算环境， 我们称之为移动计算环境。移动计算环境中的分布式数据库称作移动数据库，由 于移动数据库的应用大都被嵌入到移动通信设备中，因此移动数据库有时也称作 嵌入式移动数据库。缓存技术已经在分布式系统中得到了广泛的应用，是提高系 统性能的有效途径在移动环境中，缓存可以有效地消除移动网络中对数据访问 性能的影响，并且是支持移动设备断连操作的主要途径。由于移动数据库自身的 移动性、断接性、带宽有限性、网络通信的非对称性以及电源电量有限等特性， 决定了移动计算环境不同于分布计算环境，传统的缓存技术不能适用于移动计算 环境，必须寻求更好的缓存策略，本文以缓存技术作为背景，并着重解决缓存数 据的一致性问题。 1 2 国内外研究情况 o s z u 和d u n h a m 等人提出了移动数据库系统的概念，认为移动数据库系统可 以看作是传统分布式数据库系统的扩展。一个移动计算系统必然包含固定网络部 分和移动单元，其中固定网络部分可能构成传统的分布式系统。移动数据库在一 般意义上属于异构多数据库系统的范畴，但是也可以简单构建在分布式数据库之 上。目前移动数据库的研究和实践一般基于这个定义来开展，如何有效地对缓存 进行管理，使其发挥最大的性能，是学界研究的重点。目前提出的缓存管理模型 有：c o d a 系统、t t r 三层复制体制结构等。 1 3 论文的工作和组织结构 第l 章，对本文的研究背景以及当前国内外的研究情况做了简单介绍，并阐 明了本文的主要研究内容和意义。 第2 章，介绍移动计算环境、移动数据库的概念以及移动数据库的关键技术， 并着重介绍了现有的复n 缓存技术。 第3 章，介绍移动代理的概念、特性，阐述移动代理技术的基本思想，分析 移动代理在分布式计算环境下的优势。 第4 章，介绍缓存失效的基本概念，缓存失效策略的类型，并重点介绍了两 种算法的实例。 第5 章，本章提出一种适合于移动计算环境的缓存管理方案：基于移动代理 移动数据库缓存技术的研究 的缓存失效方案，首先介绍基于移动代理的移动数据库体系结构以及该结构下的 缓存模型，并详细分析缓存失效策略，最后应用数学模型分析不同策略的性能。 第6 章，总结论文的研究工作和取得的成果，并对下一步的工作进行了展望。 2 移动数据障缓存技术的研究 第二章移动数据库技术概述 2 1 移动计算环境 移动设备的大量普及和无线通信技术的迅速发展是移动计算出现和成为主 流技术的前提和基础。事实上，移动构件在整个信息基础中正在扮演重要的角色。 今天，我们的日常生活和工作中，各种各样的移动设备正发挥着它们各自的 作用。移动电话正以前所未有的速度迅速普及，不断改进的芯片设计和集成技术 正在这种小型设备不断增添更多功能。手持p c 和个人数字助理p d a 在保证通信 能力和便携性的基础上，加强了计算能力，侵入们可以更加便捷地管理个人数据 和进行通信。在计算和存储能力方面可以与台式机相匹敌的笔记本计算机，使专 业人士实现了跨越地域限制进行办公。可以看到，各种面向不同类用户不同需求 的移动设备己经成为当今信息社会的重要组成部分。 近年来无线通信技术的发展，也是推动移动计算技术走向实际应用的重要力 量。在无线广域网方面，新的标准不断推出，从早期的模拟蜂窝系统到现在被广 泛使用的“第二代”数字蜂窝系统，处于测试阶段的第三代，乃至正在制订中的 第四代移动通信系统。无线广域网通信技术在带宽和质量方面都有了很大的提 升。而其他的无线通信技术，包括卫星网络，无线局域网，红外技术等，也都有 了迅速的发展。 用户需求和技术进步的双重驱动使移动计算成为分布计算的一个重要拓展。 移动计算环境( m o b i l ec o m p u t i n ge n v i r o n m e n t ) 就是移动设备通过无线或固定网 络与固定或其他移动设备连接的计算环境，移动计算( m o b i l ec o m p u t i n g ) 是分布 计算在移动计算环境上的扩展。由于移动计算环境的特点，使数据库领域的查询、 事务处理等问题变得与查询客户的物理位置，网络连接情况，甚至电源供应情况 密切相关起来，因此传统的分布式数据库、客户服务器数据库不能或不能有效支 持移动计算环境。移动数据库技术就是支持移动计算环境的分布式数据库技术， 包括复制与缓存、位置管理、查询及其优化、数据广播、安全机制、移动事务处 理以及人机界面等技术。 2 2 移动数据库的运行环境 移动数据库是在移动计算技术和无线通信技术的基础上发展起来的，其典型 的运行环境如下图2 - 1 所示： 为了简化问题的描述而又不失一般性，我们假设： ( 1 ) 固定网络中所有固定主机都充当移动支持基站m s s ( m o b i l es u p p o r t s t a t i o n ) ； ( 2 ) 每个m s s 拥有全局数据库管理系统，能响应所在单元内移动主机的事务 请求并正确返回结果： ( 3 ) 移动主机姗( m o b i l eh o s t ) 上拥有本地数据库管理系统，能管理本地执 行的数据库事务及维护本地数据库的一致性。 在移动计算环境下，m s s 之间通过固定网络相互通信；m s s 通过无线接口与 位于它所负责的无线通信单元内( c e l l ) 的移动主机州通信，传递本地洲与固定 3 移动数据库缓存技术的研究 网络的数据与消息；每个删在任何时刻只能同一个m s s 通信：m h 之间不直接通 信，丽是通过所在单元内骼s 中转； 与基于固定网络的传统分布式计算环境相比，移动计算环境具有如下特点： 移动性：在移动计算环境中，同一台移动计算机可以在不同的地方连通网络， 这种计算平台的移动性可能导致系统访问布局的变化和资源的移动性。 频繁断接性：由于设备移动性所带来的网络环境的变化，以及昂贵的无线通 讯费用，移动计算环境中的移动信息设备和移动支持站之间可能会经常处于主动 或者被动的断连状态。 带宽多样性：通讯设备的移动性使得不同时间可用的网络带宽与服务质量是 变化多端的，甚至相差悬殊：移动计算机可以联入高带宽的固定网络，也可以工 作在低带宽的无线网络，甚至有时候无法联入网络。显然移动数据库的查询优化 等机制必须针对不同的网络条件选择最合适的策略。 网络通信的非对称性：在固定结点可以拥有强大的发送设备，而移动信息设 备的发送能力非常有限，于是下行链路( 从固定服务器到移动结点) 的通信带宽和 代价与上行链路相差很大。 m u ：m o b i l eu n i t 移动结点 m s s ：m o b i l es u p p o r ts t a t i o n 移动支持站，带有无线通讯援口 f h ：f i x e dh o s t 固定主机，没有无线通讯接口 图二j 移动计算环墙的典犁结构 移动设备资源有限性：目前的便携式移动信息设备，在计算能力、存储能力、 电源和屏幕显示等方面资源还十分有限。 安全性：由于移动计算平台可以远程访问系统资源，从而带来了新的不安全 因素。另外，由于设备的便携性，使得移动设备比固定设备更容易遗失和损坏。 2 3 移动数据库的体系结构 移动数据库系统是分布式数据库系统的扩充和发展，所以其结构尖似卡分布 4 移功数据库缓存技术的研究 式数据库系统。通常在移动数据库系统中，一般包括两大部分：部分是固定位 置的主机和运行在其上的通用数据库管理系统，另一部分是移动设备和小型的嵌 入式数据库管理系统。这两个部分通过中间层，例如移动支持站( m s s ) 或者基 站( b s ：b a s es t a t i o n ) 连接在一起。图2 2 所示的是一个移动数据库系统的 参考结构。 d b ：数据库d b s ：数据库服务器h l r ：h o m el o c a t i o nr e 百s t c r p s i n ：公共交换电话网络v l r ：v i s i t o r l o c a t i o n r e 百s t e r m s c ：移动交换中心 b s c ：基站中心b s ：基站m u ：移动结点f l e dh o s t ：固定主机 图2 - 2 移动数据库体系结构 在图示的系统结构中，移动结点哪只能通过基站b s 连接到网络中。移动结 点可以是任何带有无线通讯接口的可移动的便携式设备，它所具有的计算能力和 存储能力范围不等，可以从手机、p d a 到笔记本电脑，并具备无线网络接口，可 以通过无线或有线的方式通过b s 与固定网络进行连接。 在固定网络中，运行着一个或者多个数据库服务器，这些数据库服务器构成 了一个分布式的数据库系统。所有业务相关的数据都保存在这些数据库服务器管 理的数据库中，移动用户可以通过中间层组件的支持来访问这些数据库。在移动 结点上，通常运行个小型的嵌入式数据库管理系统( e d b m s ) ，用于管理缓存在 移动设备上的本地数据。 2 4 移动数据库与分布式数据库的区别 移动数据库是为了适应移动计算环境而产生的，一般认为，具备有如下结构 特征和功能特性的系统可以称之为一个移动数据库系统； 1 ) 带有移动连接性的分布式系统； 2 ) 具有完整的数据库系统功能； 3 ) 能够支持完全的空间移动性； 4 ) 能支持无线和有线的网络连接； 结合图2 - - 2 的移动数据库系统结构，我们可以看出，移动数据库系统和传 5 移动数据库缓存技术的研究 统的分布式数据库管理系统有很多相似的方面。我们也一般都把移动数据库系统 看作是分布式数据库管理系统的继承和发展，是对分布式数据库的延伸和推广； 而分布式数据库管理系统则可以看作是移动数据库系统的一种特殊形式。 如图2 - - 2 的系统结构所示，移动数据库系统的固定网络部分实际上就是 个分布式数据库系统。而移动部分的加入，使得分布式数据库系统中主机位置固 定的假设条件不再成立，从而能够支持设备的移动性。这两者的结合体使得原有 的许多技术可以直接或者间接应用到移动数据库系统中，例如对于移动事务处理 及并发控制、移动查询处理及优化、移动复制技术、移动数据库的数据分片、以 及故障恢复技术等都矗接或间接地借鉴了分布式数据库系统的研究成果；但对于 涉及移动性的部分，则需要改进原有的一些技术，或者甚至需要提出一些新的解 决方案。 下表( 表2 1 ) 列出了移动数据库和传统分布式数据库之间的一些主要区别 j l m 9 6 ： 涉及的数据库技术移动数据库和分布式数据库的差别 应用程序1 ) 可能是位置相关的 2 ) 需要适应可变的系统环境 事务处理1 ) 需要能够描述结点移动性的新模型 2 ) 事务的跨区切换( h a n d o f f ) ，即如何处理结点 在不同基站覆盖范围之间的移动所带来的问题 故障恢复1 ) 移动结点和网络的断连不能认为是系统的故障 2 ) 移动性可能要求更多的日志记录 3 ) 在跨区切换时如何从短暂断连中恢复的技术 数据复制1 ) 不同程度的一致性约束( 弱一致性或可变一致 性) 2 ) 频繁的断连使移动设备的缓存刷新必须采用新 技术 查询处理1 ) 可以是位置相关的 2 ) 要考虑不同的代价因素( 如网络带宽、花费、 电源消耗等) 3 ) 由于结点的移动性，查询结果可能需要返回到 不同的位置 4 ) 需要可适应性技术，以适应例如网络条件的变 化等 表2 一l 移动数据库和分布式数据库的主要区别 2 5 移动数据库的关键技术 移动数据库涉及到数据库技术、分布式计算技术、移动通讯技术以及嵌入式 技术等多个学科领域，已经受到多个领域的研究者关注，从而使得对移动数据库 技术的研究成为新的热点。大体上来说，当前的研究领域主要集中在这几个方面： 数据的复制和和缓存处理，移动事务处理，数据广播。移动a g e n t 技术等等。 1 、数据复制缓存技术 数据复制的主要目的是提高分布式数据库的可用件、可靠件以及访问件能。 6 移动数据库缓存技术的研究 而缓存技术是通过在客户机上缓存部分数据，达到减少访问数据库服务器的目 的。传统的复制技术主要考虑在服务器之间的复制，并假设服务器是经常连接且 复制位置固定不变。传统的缓存技术要求客户机保持与服务器的连接以维护缓存 的一致性。因此对于经常断接且位置经常变化的移动客户机来说，必须研究和开 发新的数据复制与缓存策略。文献 j i m 9 6 详细分析了现有数据复制技术在移动 计算环境中存在的问题，并针对移动客户机频繁断接的特点，提出了一种两级复 制机制。它假设移动数据库系统由两类结点组成：基结点与移动结点。每个基结 点联结在固定网络中，都维持数据库的一个复制( 第一级复制) 。而移动结点有时 通过无线网络与基结点相连，有时处于断接状态，它们也保存数据库的复制( 第 二级复制) 。c o d a 系统是一种支持移动计算的分布式文件系统。与上述两级复制 机制不同，c o d a 使用两种不同而又互补的机制来获得高度可用性：一是服务器 复制，允许文件卷在多个服务器上拥有读写复制；另一个是客户机缓存，允许客 户机在断接时通过访问本地缓存完成用户请求。为维护缓存的有效性，文献 b a r b a 9 4 提出了一种缓存失效报告广播技术：服务器定期或异步广播缓存失效 报告，保持移动客户机上的缓存同步。( 有关复制缓存技术在2 7 节具体分析) 2 移动事务处理 移动事务处理是移动数据库技术研究的重要内容。当前对移动事务处理的研 究大多从传统的数据库事务模型出发，针对移动事务的不同特点提出相应的处理 机制或策略，从而形成适应性较强的移动事务处理模型。比如：k a n g a r o o 模型 d u n i a 9 9 侧重于解决移动性问题，引入了”跳跃”( h o p ) 属性来描述移动事务随 着移动设备从一个基站移动到另外一个基站的特点，且事务的移动性通过分裂事 务获得。簇( c l u s t e r i n g ) 模型 p i t o u 9 5 将数据库分为多个簇，并为此定义两 级一致性来处理频繁的、可预见、变化的断接性。为支持移动计算，该模型将移 动事务分为强事务和弱事务，要求强事务必须严格遵守可串行化标准，而弱事务 允许存取局部缓存的不一致数据，并局部提交。若出现不一致，则通过执行补偿 事务进行恢复。r e p o r t i n g c o - t r a n s a c t i o n 模型 c h r y s 9 3 通过引入了 r e p o r t i n g 和c o t r a n s a c t i o n 事务的概念，提出一种开放的嵌套事务模型来描 述移动计算机与基站计算机事务的交互。该模型的缺点是不支持弱连接和断接状 态时操作。自适应的乐观移动事务处理模型a o p - m t 支持移动客户机的断接自治 操作，允许用户随意移动，并提供对交互式事务的支持，很好地消除了移动计算环 境给数据库应用和事务处理带来的不利影响。此外，还有p r o - - m o t i o n 模型、基 于语义的模型，i o t 模型等 w a l b 0 9 7 。 3 数据广播 由于移动客户机经常处于断接状态，而且与服务器的通信( 特别是客户机向 服务器发送信息的上行信道) 的网络带宽也很有限，因此数据库服务器可将大多 数用户频繁访问的数据( 热点数据) 组织起来，以周期性的广播形式提供给移动客 户机访问。这种数据发布方式称为数据广播技术移动数据广播的相关技术已引起 了广泛的研究。主要表现在广播模式、广播调度策略和广播组织方式等方面。广 播模式分为“静态”模式和“动态”模式。在“静态”模式下，服务器按预定的 内容进行数据广播而不考虑移动用户的需求，而“动态”模式如“按需”广播模 式是分配给移动用户少量的上行带宽上传其需求，然后服务器按此需求动态进行 数据组织并广播。“混合”广播模式则是静态和动态广播模式的结合，如基于广 播盘的数据调度策略，该策略有利于移动客户较快获得高频数据。已有的关于移 动数据广播组织方式的研究几乎都采用基于b + 树的索引结构。b + 树是为因记录 7 移动数据库缓存技术的研究 的频繁查、增、删两减少访问磁盘的次数丽设计的一种索引结构，它有利于提高 磁盘的访问效率。 4 移动查询处理 移动计算环境的查询处理包括两种类型：一种是仅仅涉及到数据库内容；另 一种是可能涉及到位置相关数据或与移动主机移动方向相关。在移动计算环境 中，位置相关信息的更新与查询是一个重要应用，文献 d u n h a 9 8 对移动环境中 位置信息的更新策略与查询优化问题做了讨论。文献 l o n s 9 2 给出了一个适合 于移动数据库应用、基于q b i ( q u e r yb yi c o n s ) 模型的查询处理工具，该工具 考虑了移动环境的固有缺陷，它允许查询语句无任何数据库结构及其位置的相关 知识进行查询。查询处理的其他研究还包括减少查询位置数据的费用，节约电源 等。 5 移动a g e n t 技术 a g e n t 的研究起源于人工智能领域。移动a g e n t 是一个能够在异构网络中自 主地从一台主机迁移动另外一台主机，并可与其它a g e n t 或资源交互的程序，实 际上它是a g e n t 技术与分布式技术的混血儿。移动a g e n t 具有自主性、移动性、 协作性、安全性、智能性等特性 传统的分布式计算基于c l i e n t s e r v e r 体系结构，其带宽耗费严重，网络负 载不均衡，容错能力较差。移动a g e n t 作为全新分布式计算工具，通过将自身代 码、状态传送到远程主机。并在远程主机执行的方式克服了c 1 i e n t s e r v e r 方案 的不足之处，因而成为分布式计算的主要发展方向之一。 基于移动a g e n t 嵌入式移动数据库改革了传统的远程查询数据库的s q l 查询 方法，把查询任务存储到一个可通过网络进行移动的a g e n t 上，a g e n t 将移动到 服务器上，执行查询并再做结论，然后返回到用户并打印结果。在这个过程中， 我们把查询任务分解为单个的查询方法，而这些指令在网络上的合适地点会被唤 醒并执行。通过将移动a g e n t 技术引入嵌入式移动数据库中，有助于实现嵌入式 移动数据库查询优化。 2 6 移动数据库典型应用 移动数据库技术的许多特性都与信息时代的需求特点相吻合，因此在许多领 域获得了成功的应用。下面我们仅列举几个已经或是将要出现的典型移动数据库 应用，以说明研究移动数据库技术的必要性及其应用前景。 ( 1 ) 公共信息发布 在移动计算环境中，大量的移动用户将通过笔记本电脑、掌上电脑、p d a 、 车载平台等移动设备的无线通讯接口获取各种各样的公共信息，如股票行情、天 气状况和交通信息等。以交通信息发布为例，一个大城市的移动信息系统将同时 为1 0 万个以上的移动用户提供服务。 ( 2 ) 实时数据采集 以保险业务员为例，目前许多保险业务员都使用笔记本电脑或掌上电脑管理 有关客户和保单数据。在外出联系业务的途中，业务员需要随时从总部调出最新 的数据资料，并随时查询某个客户的信息；完成交易后，他又需要将最新输入的 保单信息即时反馈给总部。这种模式摆脱了时间、地点和场合的限制，克服了传 统数据处螳力式造成的延误和混乱，提曲，数据管土里的效率。 8 移动数据庠缓存技术的研究 ( 3 ) 位置相关查询 位置相关查询是移动数据库应用中最具特色也是最吸引人之处。设想一个旅 游者到达一个陌生的城市，他可以通过随身携带的移动设备查询许多信息，如最 近的餐厅在哪里，怎样去最近的医院等等。与传统的数据库查询不同的是，上述 查询的结果是与位置相关的，同样一个问题在不同的地理位置得到的回答可能会 是不同的。 ( 4 ) 未来战场应用 在军事领域，移动计算有广泛的应用前景。如在战场医疗信息系统，携带移 动设备的医护人员常常要查询战区士兵的健康状况、病历等数据，也可能需要访 问后方医院的资科。战场战术数据的查询和分发是建立数字化部队，构建数字化 战场的关键技术之一，一个部队可能经常需要向上级数据库系统查询其所在战区 的地形、敌情、雷区、气象等各方面的情报，以支援其作战。 此外，移动数据库技术配合6 p s 技术，可以用于智能交通管理、大宗货物运 输管理和消防现场作业等。移动数据库技术还在零售业、制造业、金融业、医疗 卫生等领域展现了广闻的应用前景。 2 7 移动环境下数据管理 2 7 1 缓存技术 缓存是计算机科学中的经典技术之一，已经在多个领域中证明了其成功性， 包括体系结构、单机操作系统和分布式系统等。在分布式系统中，客户可以把经 常访问的数据缓存在本地上，后续对这些数据的访问就可以直接从本地响应，而 不需要向服务器发出数据请求。缓存的效果主要取决于后续操作有多少可以命中 本地缓存中的数据，即缓存的命中率( r a t e ) 。l r u 算法合理地利用了数据访问的 局部性特点，具有较高的命中率，保证了缓存的效果可以得到充分的发挥。 分布式系统中的缓存技术通过以下三种方式来提高系统性能： 缓存命中的请求不会产生网络请求和响应，从而减少了系统的通讯开 销，提高了网络的吞吐量； 由于本地磁盘的访问速度远远快于网络传输速度，所以直接从本地响应 请求可以极大地降低用户操作的延迟； 客户端的缓存管理器对于甘陵务器屏蔽 r 部分数据请求，减少了服务器的 负载，由于服务器往往是分布式系统的性能瓶颈，因此缓存可以提高系 统的可扩展性。 在移动计算系统中，由于移动网络的带宽窄，数据传输速度慢，出错率高， 通讯费用昂贵的限制，缓存技术所带来的好处会更加充分地得到体现。另一方面， 在移动环境中系统不能假定网络连接始终是可靠的，因此，通过把服务器上的数 据缓存在本地缓存中还可以提高数据的可用性。例如。在移动客户处于断连状态 时，系统只能依赖本地缓存中的数据响应用户的请求。而在网络时断时续的弱连 接状态下，传送一个中等大小的数据或多媒体几分钟到十几分钟，这对于用户是 不可忍受的。而如果该文件已经缓存在本地缓存中，则系统就可以在用户期望的 时间内响应 a g r a w 9 9 。 综上所述，缓存不仅可以提高移动数据访问的性能，还可以提高系统地可用 9 移动数据库缓存技术的研究 性。因此它是解决无线网络约束，尤其是支持断连操作的一个有效途径。 在移动环境下，早期的缓存技术的研究主要是针对文件系统，如c o d a 系统 和s e e r 系统，近年来出现了针对移动数据库的缓存研究。以下介绍几种最具有 代表性的研究成果。 c o d a 系统 c o d a 系统是由美国卡耐基一梅隆大学研制的一种支持移动计算的分布式文 件系统。是至今为止对移动环境下缓存技术研究最详细，成果最被人们广为引用 的项目 k i s t l 9 3 。c o d a 的缓存粒度是文件级，每个客户都有本地磁盘用于缓存 与两级复制机制不同，c o d a 只在客户机上缓存部分对象，而不是整个文件系统 的复制。在每个c o d a 客户机上，都有一个缓存管理器负责获得并缓存文件卷的 映象信息。c o d a 使用两种不同而又互补的机制来获得高的可用性。第一种机制 是服务器复制，允许文件卷在多个服务器上拥有读写复制。另一种机制就是断接 操作，允许客户机在断按时，v e n u s 可以通过本地缓存来访问数据。v e n u s 有三 个工作状态：收集( h o a r d i n g ) 、仿真( e m u l a t i o n ) 和重集成( r e i n t e g r a t i o n ) 。 当客户机与服务器联机时，c o d a 的缓存管理处于收集状态，它能够访问服务器 上的数据，并收集在断接期间可能需要的数据。当客户机断接时，v e n u s 进入仿 真状态，它相当子一个伪服务器，代理了服务器的作用，并将在缓存数据上的操 作记录在日志中，直到客户机停止断接并重新联机为止。当客户机重新联机时， v e n u s 根据日志记录，将其缓存数据与服务器上的数据重新同步。 c o d a 使用基于优先级的缓存管理算法来缓存有用的数据到本地。缓存对象的 优先级由显式优先级信息和隐式优先级信息共同决定。隐式信息包括文件最近的 引用历史随着新的引用产生而不断被更新。显式信息由用户提供。当缓存空问不 够时，拥有最低优先级的对象被选出并从缓存中删除。由于缓存对象的优先级随 时可能发生变化。缓存中的数据需要定期评估称为“h o a r dw a l k ”。在断接期间 所有被更新过的对象拥有最高优先级，以免这些对象在重新连接前就被替换出缓 存。 c o d a 使用基于回调的缓存一致性协议但为了保证可用性一致性、可伸缩性以 及支持断接，它对该策略进行了改进。做法是将取更新版本同“h o r a dw a l k ”结 合起来，对目录、文件和符号连接使用不同的策略。 缓存是c o d a 的关键技术，c o d a 的研究结果说明缓存不仅可以被用来提高性 能，也可以用来提高数据可用性。但c o d a 是文件系统的缓存研究不适用于数据 库环境。 缓存失效策略 i m i e l i n s k i 和b a r b a r a 等人，提出了一种新的缓存技术，称为缓存失效报告 技术 b a r b a 9 4 b a r b a 9 5 ：即服务器定期或异步地广播缓存失效报告，该报告 中包含了最近被更新的对象，根据报告内容，客户可使缓存中被更新对象失效， 以保证缓存的有效性。 在该算法的基础上，针对不同的情况，又提出了许多改进算法，例如，j i n g 和a h m e d 等人提出的一种基于位序列( b i t - s e q u e n c e s ) 的自适应缓存失效策略 j i 9 7 ，它将数据库中的数据组织成具有一定结构的位流，并加上时间戳，形 成失效报告。c a i 和t a n 等人提出了一种能有效节约移动主机电能的缓存失效策 略 c a l 9 9 ；缓存失效策略是本文的研究重点之一，我们将在第四章中进行详细 的分析和讨论。 语义缓存 移动数据库缓存技术的研究 语义缓存是一种基于客户查询语句之间语义相关性而建立的缓存，语义缓存 的内容由以往查询的结果以及查询描述构成，缓存命中通过将查询语句同缓存中 的各个缓存项描述匹配判断。客户通过语义缓存可以实现动态的数据复制并动态 的定义他所感兴趣的数据空阳n 在现实世界中，大量应用所发出的查询具有很强 的语义相关性，例如：一个企业的部门经理，他通常对他所负责的部门情况更加 感兴趣，因此对企业数据库的查询多是与该部门相关的数据，这些查询之间的语 义相关性就高。 相比其他以对象或元组为粒度，基于空间局部性和时间局部性的缓存，以查 询结果为缓存粒度、基于查询语义局部性和时问局部性的语义缓存更适用于关联 查询访问，而且当数据存放的聚集度不好时，也能保证缓存效率。文献 d a r 9 6 将语义缓存同以页和元组为粒度的缓存进行性能比较，通过实验验证了语义缓存 较另两种缓存对关联查询处理具有更少的通信开销和更快的响应时间；文献 g u 0 9 6 研究了匹配紧密相关的布尔表达式相交以及包含的判断问题；文献 k e l l e 9 6 侧重讨论了缓存完整性和缓存一致性方面的设计和性能的考虑；文献 p , e n 9 9 讨论了基于语义的缓存替代策略。 基于语义内容的数据缓冲管理方法是一种很有效的方法，主要有以下特点： 客户端具有缓存数据的语义描述。在查询处理时，客户端使用语义信息 决定本地数据是否可以满足查询条件。通过修改查询条件，向服务器发 出本地缓存不能满足的部分数据的查询请求，从而减小通信开销。 缓存替换策略信息存储在一个可动态调整的语义区中。其优点是不用维 护每一个元组的替换信息，而是通过语义信息维护一组元组的替换信 息，极大地减少了物理存储开销。 可以使用复杂函数来决定缓存替换的条件。 由于本文的重点不在语义缓存上，所以我们简单的介绍一下基于语义缓存的 查询导出，其基本思想是：首先确定与当前查询作用在相交关系上的缓存项，再 从这些相关的缓存项中判断有无查询的精确匹配或包含可导出匹配。如果有，查 询结果可从该缓存项描述的缓存块中通过投影、选择查询操作获取；若没有，但 缓存项与查询是可查询裁剪相交的，也可对查询进行裁剪，将裁剪后的查询送到 服务方处理，连同缓存中获得的部分查询结果一起构成查询结果。 2 7 2 数据复制技术 复制是指在多个节点上完成数据的备份，包括服务器的中心数据库的复制以 及在移动主机中保存数据库的复制，其目的是保持数据库系统各节点中数据状态 的一致性。迄今为止人们己经提出了多种移动复制算法：如两级复制算法、t t r 三层复制体系结构。 l 、两级复制 j i mg r a y 等人在中提出了适应移动计算环境的两级复制算法 j i m 9 6 。这是 一种移动计算环境下极具代表性的算法，其主要贡献是引入了将系统进行分级的 思想。该算法充分考虑了典型的移动计算环境中可信部分和移动部分的性能差 异，将整个移动计算环境分为两级，第一级为通过固定网络保持连接的基结点， 每个基结点维护数据库的一个副本：第二级为时常处于断接状态的移动结点，也 存有数据库的部分副本。第一级复制是基结点之问的复制；第二级复制是指移动 结点与基结点之间的复制。这样，可信部分总能保持传统分布汁算环境下的若干 u 侈动数据阵缓存技术的研究 特征，而不会因为移动计算的引入对系统性能产生不良影响。 在两级复制算法中，j i mg r a y 引入了基本事务( b a s et r a n s a c t i o n ) 与暂态 事务( t e n t a t i v et r a n s a c t i o n ) 的概念。在移动结点上，每个数据对象都保存有 两个版本：主版本( m a s t e rv e r s i o n ) 和暂态版本( ( t e n t a t i v ev e r s i o n ) 。在移动 结点和网络断开连接时，所有对数据的存取作为暂态事务在暂态版本的数据副本 上执行，并产生新的暂态版本数据。当重新和网络连接时，所有的暂态事务将提 交给m s s ，并转化为相应的基本事务在基结点上重新执行，系统要比较暂态事务 和对应基事务的执行结果，如果结果相同，则暂态事务提交成功，暂态版本数据 转化为主版本数据，否则，要回滚暂态事务的结果。为了提高暂态事务在基结点 上提交的成功率，系统可以规定若干约束条件，系统将比较试验事务与基本事务 结果间的差异，如果差异不违反这些约束条件，则认为事务成功完成，事务的结 果永久性地写入到数据主版本中；否则，事务宣告失败，服务器会向删通知失 败原因，同时所有其他读取该事务写集的事务也宣告失败。 两级复制机制是解决移动计算环境下支持断接操作的一种可行办法，系统采 用分级的方法提高了系统的可扩展性，用户可以自行定义暂态事务与基本事务执 行结果的可接受差异范围，增加了系统的灵活性。但是所有的事务都要作为暂态 事务和基本事务两次在移动结点和基结点上重复执行，系统开销较大。在同一个 移动结点上，暂态事务的执行结果对其他暂态事务来说是可视的，这在某种程度 上提高了系统的可用性，但也增加了级联回滚的可能性。 2 、三级复制 将数据广播技术纳入到移动数据库复制机制中，提出了三级复制的体系结构 l 1 9 7 ( t h r e e - t i e rr e p l i c a t i o na r c h i t e c t u r e ，t t r ) ，即服务器复制、空中 复制和客户机缓存复制。其结构如图2 3 所示，它能灵活有效地支持各种类型 的移动数据应用、实现上面提到的移动数据库的四个基本目标。 服务器级复制 图2 - - 3 三级复制体系结构图 移动羲姑库缓存技术的研究 第一层复制是指服务器之问利用传统的复制技术在固定高速网络中所进行 的复制，称之为“服务器级复制”。为了支持移动计算环境，一股采用一种弱一 致性服务器级复制机制( w e a k l yc o n s i s t e n ts e r v e rr e p l i c a t i o n ，简称w c s r ) 。 这种策略让每个复制服务器都支持查询与更新操作，并且允许各个复制之间存在 暂时的不一致。因此，一个用户在访问数据库时，只需要访问一个复制服务器即 可，而且不仅可以执行查询事务，还支持更新事务。服务器接到一个查询事务之 后，根据本地数据库的状态返回查询结果，对于更新事务，服务器则将其记入暂 时事务日志中，在本地数据库上执行，并立即返回给用户其标志符和结果。用户 不必等待服务器将该事务的结果传递给其他复制服务器，因此具有较短的响应时 间。为了降低通信开销，提高可靠性，w c s r 采用了一种周期成对同步的方式， 即每个服务器周期地选择另一个服务器，两个服务器之间交换各自的暂时事务日 志，经过有限次的成对同步过程，最终使所有数据库状态达成一致。 第二层复制是指服务器利用无线网络固有的广播能力将数据库中经常被大 部分用户访问的公共热点数据组织起来，经由m s s 向无线网络单元内的所有m c 广播，这实际上是在无线广播信道上做数据复制，称之为“空中复制”，空中复 制充分利用了无线网络非对称性的特点。首先，因为无线网络特有的广播能力与 普通网络中的广播显著不同，它可以支持大量m c 同时接收，而且不管接收的客 户数有多少，m s s 的广播代价并不改变，这就允许大规模的移动用户同时访问被 广播的热点数据，极大地提高系统的可伸缩性；其次，由于m c 可以从空中复制 取得常用的热点数据，使得其向服务器发送访问请求的频率也大幅减少，甚至没 有必要再与服务器联机，这不仅可以使眦更有效地使用上行链路或避免代价较 高的无线通信，而且减少了服务器处理每个联机m c 的开销，进而使服务器可以 同时接收更多联机m c 的访问。可见，空中复制是一项开销不大，但却很有实际 应用意义的技术。 第三层复制是为了支持移动用户的断接操作，眦利用本身的处理和存储能 力缓存数据库中部分数据，称之为“客户机缓存”。由于m c 的存储容量无法与数 据库服务器相比，而且普通用户也不需要在断接期间访问整个数据库系统，因此 在t t r 体系中一般采用一种支持数据库的子集缓