（计算机软件与理论专业论文）移动实时数据库的一致性维护.pdf

华中科技大学博士学位论文 摘要 f 无线通讯技术的新进展使得用户可以在任何地方的任何一台计算机( 移动的或 非移动的) 上访问各种各样的共享信息服务。在诸如移动电子医疗、移动实时交通 信息管理及其浏览系统、移动电子拍卖系统、移动因特网股票交易系统等许多新颖 的移动应用系统中，移动用户需要使用他们的掌上电脑、膝上电脑、个人数字助手 ( p d a ) 、以及笔记本电脑来迅速访问各种实时信息。移动计算技术改进了信息的分布 性与流动性，然而，通过移动网络访问短暂有效信息有赖于对实时数据的有效管理 以及事务的实时处理。移动计算强烈需要实时数据库技术的支持；而有穿啪理事务 的执行以保证一致性是数据库管理系统最基本、最核心、最关键的任务彳论文针对 移动实时数据库及其应用的特征，从事务模型、事务并发执行的正确性准则、并发 控制机制、外部一致性维护方法等方面详细研究了移动实时数据库的一致性维护问 题。 在移动实时数据库中诸如网络延迟长、不对称通讯、频繁断接等移动环境的 显著特征、事务的移动性和时间性、事务多样化的一致性需求等都使得传统事务模 型无法适用于移动实时数据库。为此，提出并形式化定义了适宜于移动实时数据库 的分片段事务模型。 传统可串行化正确性准则对许多移动实时应用显得过于严格且不必要，而现有 的放松可串行化正确性准则都会引起数据库受限不一致。基于事务并发执行的经历 模型，在分析可串行化、若可串行化、可串行化、准一致性可串行化正确性准则 的基础上，针对移动实时环境和应用的特征，提出使用弱可串行化和伪可串行化两 种新的正确性准则。在给出形式化定义后，证明了它们都比传统可串行化宽松，且 都能始终保证数据库的内部一致性。并且，分别给出并证明了保证弱可串行化和伪 可串行化的充分必要条件。 研究了移动实时事务并发控制机制。首先，采用改进的优先级夭折与优先级继 承混合方法，给出了种适宜于拉式数据发布系统的、保证伪可串行化的并发控制 华中科技大学博士学位论文 机制。进而，由于需要连续不断的双向通讯来协调事务的分布执行，现有分布式实 时并发控制机制无法适用于不对称通讯的广播环境。从尽可能减少用于并发控制的 上行通讯量出发，分别给出了适宜于实时广播环境的可串行化、弱可串行化、伪可 串行化并发控制协议。 研究了如何更有效地维护移动实时数据库的外部一致性。为此，首先提出了一 种新颖的l s 算法。 某些条件下能产生最 仔细分析和考察，发现其在 也能得到可用结果。分析和 实验表明，l s 方法有效可行。y 进而，考虑到移动实时数据库事务的一致性需求呈现多样化，许多移动实时数 据库应用中外部一致性更重要，移动实时数据库事务的调度就不能仅仅考虑数据库 的内部一致性或将内部、外部一致性同等着待。为此，提出了一种对由现有调度技 术生成的事务队列进行调整的d t 方法。 关键词：移动实时数杂彭7 移动实i 辑务处理一蠡轻维护 移动实时并发控制移动实时事务调度 x , 华中科技大学博士学位论文 a b s t r a c t r e c e n ta d v a n c e si ne l e c t r o n i ct e c h n o l o g i e ss u c ha sp o r t a b l ec o m p u t e r sa n dw i r e l e s s c o m m u n i c a t i o nn e t w o r k sh a v el e dt ot h er e a l i t yo fd i s t r i b u t e dm o b i l ec o m p u t i n gs y s t e m s ， a n du s e r sa r ea b l et oa c c e s sac o l l e c t i o no fd a t a b a s es e r v i c e sa n y t i m eu s i n ga n yc o m p u t e r ( m o b i l eo rn o n - m o b i l e ) a ta n y l o c a t i o n al o to f m o b i l ec o m p u t i n gs y s t e m s ，s u c ha sm o b i l e e l e c t r o n i c a lm e d i c a lt r e a t m e n ts y s t e m s ，r e a l - t i m et r a n s p o r t a t i o ni n f o r m a t i o nm a n a g e m e n t a n d n a v i g a t i o ns y s t e m s ，a n d m o b i l ei n t e r a c ts t o c k t r a d i n ss y s t e m s ，a f er e a l - t i m ee s s e n t i a l l y t h en e e do f r e a l - t i m ed a t ar n a n a g e m e n ts y s t e n l sf o rt h e s em o b i l ec o m p u t i n ge n v i r o n m e n t s i ss t r o n g i ti st h eb a s i c ，c r i t i c a la n dc o r ef u n c t i o no fad a t a b a s em a n a g e m e n ts y s t e mt h a t t r a n s a c t i o n sa l ep r o c e s s i n ge f f i c i e n t l yi no r d e rt om a i n t a i nt h ec o n s i s t e n c yo ft h ed a t a b a s e a r e ri n v e s t i g a t i n gt h ec h a r a c t e r i s t i c so fam o b i l er e a l - t i m ed a t a b a s es y s t e m , t h et h e s i s f o c u s e so nc o n s i s t e n c ym a i n t e n a n c eo fam o b i l er e a l - t i m ed a t a b a s es y s t e m ，a n dr e s e a r c h t h ei s s u e ss u c ha st r a n s a c t i o nm o d e l ，c o r f e c l n e s sn o t i o n , c o n c u r r e n c yc e n t r e lm e c h a n i s m s ， a n ds c h e d u l i n g t e c h n o l o g i e sf o re x t e r n a lc o n s i s t e n c y i nam o b i l er e a l - t i m ed a t a b a s es y s t e m i nam o b i l er e a d - t i m ec o m p u t i n ge n v i r o n m e n t , b e c a u s en e t w o r kd e l a yi sp r o l o n g e d ， a n dp r o c e s s i n go fat r a n s a c t i o nm a yi n v o l v ei n t e r a c t i o n , m o s tt r a n s a c t i o n sa r el o n g r i v e d o d e s m o r e o v e r , t h o s et r a n s a c t i o n sw o u l db eb r o k e nm a ds e n t t oi n d i v i d u n ls i t e sf o r e x e c u t i o n t h e r e f o r e ，t h ep i e c e dt r a n s a c t i o nm o d e li sp r o p o s e da n df o r m a l l yd e f i n e df o r m o b i l er e a l t i m ea p p l i c a t i o n s s e r i a l i z a b i l i t yi st o os t r o n gf o rm a n ym o b i l er e a l - t i m ea p p l i c a t i o n sb e c a u s eo ft h e l i m i t a t i o no f c o n c u r r e n c y a l l o w e d b y s e r i a l i z a b l e e x e c u t i o n s ，w h i l e a l lo f e x i s t i n g c o r r e c t n e s sn o t i o n so f r e l a x i n gs e r i a l i z a b i l i t ys u c ha se p s i l o ns e r i a l i z a b i l i t ya n ds i m i l a r i t y s e r i a l i z a b i l i t ya n dq u a s ic o n s i s t e n ts e r i a l i z a b i l i t y nr e s u l ti nb o u n d e di n c o n s i s t e n c yo f d a t aa f t e rd i s c u s s i n gc o r r e c t n e s sn o t i o no ft r a n s a c t i o n s ，w e a ks e r i a l i z a b i l i t ya n dp s e u d o s e r i a l i z a b i l i t ya r ep r e s e n t e d f o r m a ld e f i n i t i o n sa r eg i v e na n dt h en e c e s s a r ya n ds u f f i c i e n t 华中科技大学博士学位论文 c o n d i t i o n sa r ep r o v e d a l t h o u g ht h e y a r em o r er e l a x i n gt h a nt r a d i t i o n a ls e r i a l i z a b i l i t y , c o n s i s t e n c yo f a m o b i l er e a l - t i m ed a t a b a s ei sm a i n t a i n e d n e x t ，c o n c u r r e n c yc o n t r o lp r o t o c o l sf o rm o b i l e r e a l - t i m ee n v i r o n m e n t sa r eo u t l i n e d am o b i l er e a l - t i m e c o n c u r r e n c yc o n t r o lp r o t o c o l f o ro n - d e m a n ds y s t e m si s p r e s e n t e d t r a d i t i o n a ld i s t r i b u t e dr e a l - t i m ec o n c u r r e n c yc o n t r o lm e c h a n i s m sa r ei n a p p l i c a b l ef o rr e a l t i m eb r o a d c a s te n v i r o n m e n t sb e c a u s et h e yn e e db i - d i r e c t i o nc o n t i n u o u sc o m m u n i c a t i o n s e v e r 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 sf o rr e a l - t i m eb r o a d c a s te n v i r o n m e n t sr i og i v e na n d e v a l u a t e d b ys i m u l a t i o ne x p e r i m e n t s t h e n ，t h ep r o b l e m h o wt oe f f i c i e n t l ym a i n t a i nt h ee x t e r n a lc o n s i s t e n c yo f m o b i l er e a l t i m ed a t a b a s es y s t e m si se x a m i n e di nd e t a i l l st h a ti s0 , 1 1e x q u i s i t em e t h o di sp r o p o s e d a n da n a l y z e di ti ss h o w nt h a tt h em e t h o dl sw o u l dp r o v i d e 雅e x p e c t e dr e s u l tu n d e r s e v e r a ll i m i t e de n v i r o n m e n t so rv a l i dr e s u l t si ng e n e r a l t h ee x p e r i m e n t a lr e s u l t ss h o w t h a t t h el sm e t h o di sa ne f f e c t i v em e t h o dt h a tc a nh e l pm o r et r a n s a c t i o n st om e e tt h e i r d e a d l i n e sw h i l ea s s u r i n gc o n s i s t e n c yo fm o b i l er e a l - t i m ed a t a b a s em a n a g e m e n ts y s t e m s b e r e r c o n s i d e r i n g t h a ti nam o b i l er e a l - t i m ed a t a b a s e s y s t e m , d a t ac o n s i s t e n c y r e q u i r e m e n t so ft r a n s a c t i o n s a l ed i v e r s i f i c a t i o n t h e r e f o r e ，t r a n s a c t i o n s s c h e d u l i n gi n a m o b i l er e a l t i m ed a t a b a s es y s t e ms h o u l dn o tc o n s i d e ro n l yi n t e r n a lc o n s i s t e n c yb u ta l s o e x t e m a l c o n s i s t e n c y t h e r e f o r e ，at e c h n o l o g y c a l l e d d tm e t h o d i s p r e s e n t e d f o r m a i n t a i n i n gt h ee x t e r n a lc o n s i s t e n c yo f m o b i l e r e a l - t i m ed a t a b a s e s k e yw o r d s ：m o b i l er e a l - l i m e d a t a b a s e sm o b i l er 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 c o n s i s t e n c ym a i n t e n a n c e m o b i l er e a l - t i m ec o n c u n e n e yc o n t r o l m o b i l er e a l t i m et r a n s a c t i o ns o h e d u l e i v 华中科技大学博士学位论文 1 绪论 1 1 引言 当人类阔步迈进二十一世纪之际，移动通信技术正在以史无前例的高速度迅猛 地发展与普及。据统计，进入九十年代以来全球移动通信以每年平均超过1 0 0 的增 长率发展：移动通信技术的更新换代也越来越快i l l 。始于八十年代中期，采用模拟调 制和频分多址技术，被称为第一代移动通信系统的模拟蜂窝系统，由于其业务种类 单一、频谱利用率低、用户移动范围有限而早已被淘汰【2 j 。九十年代中期发展起来的 数字蜂窝系统即第二代移动通信系统尚在使用。它采用数字编码技术，具有很高的 鲁棒性和智能，可以灵活地与有线数字网络集成，降低了r f ( r a d i of r e q u e n c y ，射 频) 发射功率，可以对私有通道加密，支持更大的用户容量，可以提供各种语音与 数据服务。但是第二代移动通信没有统一的国际标准。全世界存在三种标准：一是 欧洲十六个国家共同制定的标准，二是北美标准，三是日本标准。这些第二代移动 通讯系统彼此互不兼容，在实现全球联网漫游方面给用户带来很多不便1 3 l 。当前，第 三代移动通信系统已经走入我们的生活1 4 1 。它可实现全球无缝漫游、支持多媒体数据 传输，并且具有高频谱效率、高服务质量、低成本、高保密性等。事实上，已经出 现了以正交多任务分频技术( q f d m ) 为核心、支持高达2 2 0 m b p s 数据率的第四 代移动通信系统俐。 另一方面，自二十世纪九十年代以来，越来越多的用户开始拥有各种便携的计 算设备，小的如掌上型的个人数字助理( p d a ) 或个人通信器( p e r s o n a l c o m m u n i c a t o r ) ，大一些的如装备较大内存和较强处理能力的笔记本电脑等，它们被 统称为移动计算机( m o b i l ec o m p u t e r s ) 。据有关资料介绍，1 9 9 8 年美国商用p c 机销 售量中约6 0 都是移动计算机栩f 8 j 。而且，随着半导体技术的飞速发展，移动计算机 的处理能力、存储容量等性能指标正以每1 8 个月翻一番的速度提高( 摩尔定律) ， 其中高档的移动计算机足可与同类台式机相媲美。如今，移动计算机已经有能力管 理在不久前还被看作是“超大规模”的数据库，支持复杂的数据管理任务嗍【】。 华中科技大学博士学位论文 迅速发展并逐渐成熟的移动通信与移动计算机技术的结合使得移动计算已经成 为现实。可以预见，未来的绝大部分移动计算机都将配备移动联网设备，以支持移 动用户访问无线网络中数据的需要献”】。这将是一种更加灵活、复杂的分布式计算环 境【8 1 。 由于传统分布式数据库技术不能支持或不能有效支持移动计算环境，人们研究 了移动数据库技术即支持移动计算环境的分布式数据库技术。事实上，许多移动数 据库应用本来就是实时的，例如移动电子拍卖、移动股票交易、交通信息浏览与导 航系统、移动电子医疗、战场管理系统等等【l l 】【1 州1 3 1 【“】。它们都涉及如何给众多客户 机有效发布大量高度动态、随着时间快速变化的实时信息。这些应用一方面要求维 护大量的共享数据；另一方面其应用活动有很强的时间性，比如源自移动客户机的 事务具有截止期约束。如果移动客户发出的股票交易事务不能在截止期内完成，便 会造成经济以及财经机遇的严重损失；移动电子医疗系统中事务超截止期将导致人 员生命的损失。同时，它们所处理的数据，诸如股采价格、拍卖竟价、检测数据等 是“短暂有效”的，即只在一定的时间范围内有效，过时则对当前的决策或推导无 意义。这些系统中的客户迫切需要及时访问到流行且一致的数据。 由于移动计算系统中数据管理的基本需求是维护数据一致性且支持对实时数据 访问的实时响应，移动计算系统中的数据管理非常需要实时数据库技术的支持，这 就需要研究移动实时数据库管理系统l l l l l l 习l 。时间约束下的内部一致性及短暂有效 实时数据的外部一致性维护【3 】i 1 6 1 ，这个实时数据库研究的核心问题在不对称通讯、 带宽更窄、可靠性和可预报性更差( 与有线网络相比) 的无线移动通讯环境中变得 更为复杂【1 6 】。尽管移动数据库管理系统和实时数据库管理系统的研究都已经有十余 年1 7 】 1 8 】2 0 】【2 1 】【2 2 】1 1 ”】【2 5 】，但是移动实时数据库的研究直到最近几年才刚刚受到越来越 多的关注“】。尽管移动实时数据库管理系统的研究需要充分吸收移动数据库和 实时数据库领域的研究成果，但绝不是在概念、方法、技术上的简单迭加。移动计 算系统独有的许多特点使得需要在系统理论与实现技术上进行全面的研究，关键是 针对移动计算环境和移动实时应用的特征，在事务模型、正确性准则、并发控制机 制、外部一致性维护方法等方面作深入细致的研究，为移动实时数据库管理系统寻 2 华中科技大学博士学位论文 = = = = = = = j = = = j t = = = = = = = j = 目_ = l 自，_ _ l = _ - _ = = = _ # = = _ = _ 目= ；目_ j = 自_ i ；= = = 求有效的一致性维护措施【1 1 郾棚【2 8 】。 1 2 移动数据库研究 目前，移动数据库技术的研究主要包括复制与缓存技术、广播技术，查询技术、 移动事务处理以及a g e n t 技术等1 8 】【1 哪。 1 2 1 复制与缓存技术 数据复制与缓存可以提高分布式数据库系统的可用性、可靠性以及访问性能。 然而，传统的数据复制与缓存技术均假定客户机与服务器始终保持连接，这种静态 策略不能适用于移动环境 8 p j o l 。 jg t a v 等提出了两级复制技术例：以主副本更新复制协议为基础，它假设移动 数据库系统有两类节点构成：一类是基节点，他们连接在固定网中，每个基节点都 维护数据库的一个副本( 即第一级复制，并且是大部分数据对象的主节点；另一类 是移动节点，他们有时通过无线网络与基节点连接，有时处于断接状态，它们也存 有数据库的副本( 即第二级复制) ，可以在断接时提交暂态( t e n t a t i v et r a n s a o t i o n ) 事 务。一个移动节点也可以是部分数据对象的主节点。 图1 1v e n u s 状态转换圈 由美国卡奈基梅隆大学研制的一个支持移动计算的分布式文件系统c o d a 中使 用了一种支持客户端断接操作的缓存技术0 0 1 。c o d a 使用服务器复制，允许文件卷在 多个服务器上拥有读写副本。为了提高性能，客户机可以缓存部分对象，缓存管理 3 华中科技大学博士学位论文 器( v e n u s ) 使用一种回叫机制来保证每个打开的文件内容都是最新的。所谓回叫机 制，就是当客户机的某个缓存对象已被服务器更新时，由服务器通知客户机该缓存 对象已不再有效。v e n u s 具有三个工作状态：收集、仿真、重集成。图11 给出了这 三个状态以及他们之间的转换过程。 d b a r b 眦和ti m i d m s k i 提出了一种新的缓存失效报告广播技术【3 l 】：服务器定 期或异步的广播缓存失效报告，使移动客户机的缓存保持同步。缓存失效报告可由 最近一定时间内被更新的数据对象的最新时间戳构成。移动客户机联机时，保持接 听这些报告，并更新缓存的状态。对于缓存中的每一个对象，如果失效报告中该对 象的时间戳比缓存中对应的时间戳要新，则从缓存中清除该对象( 已失效) ；如果失 效报告中没有该对象的时间戤，则将缓存中该对象的时间戳更新为此次失效报告的 时间戳。缓存失效报告也可只包括上次广播以来被更新数据对象的标识符】【3 3 埘) 。 1 2 2 数据广播 在移动计算环境中，从服务器到移动客户的下行通信带宽一般要远大于从移动 客户机到服务器的上行通行带宽，而且移动客户机从服务器接收数据的开销也远小 于发送开销，因此，在大部分场合，即使是处于断接状态的移动客户机也可以选择 接收从服务器发送的下行广播信息。于是，可以利用这种网络的非对称型，由数据 库服务器把大多数用户频繁访问的数据( 即热点数据) 组织起来，按周期性的广播 形式提供给移动客户机访问。这种数据发布方式称为数据广播技术p q 【蚓m ，它的优 点在于；1 ) 因为服务器广播数据的开销与接收广播的客户机数是无关的，因此它可 以以很小的代价支持大量移动客户机同时访问数据。2 ) 移动客户机可以不需要数据 缓存。3 ) 即使在断接时，也允许移动客户机访问到最新数据。4 ) 移动客户机不再 需要预测未来的数据请求。 数据广播技术在移动计算环境中有着非常好的应用背景，如公共信息的发布( 股 市、交通) 、军事应用( 如美军o b s 系统) 等鲫嗍。目前对数据广播的研究主要集 中在数据广播的调度问题：如何组织数据广播信道中的数据，使之适合于移动计算 机访问? 对现有数据广播调度的研究可以根据不同的角度分类如下： 华中科技大学博士学位论文 1 ) 按被广播数据的覆盖范围可分为：全集、子集。 2 ) 按广播内容的实时性可分为：静态的、动态的。 3 1 按是否广播索引可分为：带索引广播、无索引广播。 4 1 按广播数据流的组织形式可分为：平坦调度、偏斜调度、多盘调度。 5 ) 按客户机的查询方式可分为：主动的、被动的。 衡量这些数据广播调度算法好坏的参数主要有两个眇】： 1 ) 访问时间：从移动客户机提出数据访问请求开始，到客户机从数据广播中得 到结果所需的时间。访问时间决定了移动用户查询的响应时间。 2 ) 调谐时间：在完成一个访问请求期间，移动客户机保持接昕广播的总时间。 调谐时间决定了移动客户机的电源消耗，因为在不接听广播的时间里，移动客户机 可以转入休眠模式，此时消耗的电源相对于激活状态可以忽略不计。 数据广播的研究可以分为服务器方和客户机方两个问题。服务器方主要考虑如 何组织广播数据，即数据广播的调度；客户机方则主要考虑如何利用缓存技术进一 步减少查询广播数据的响应时间。服务器必须根据所有移动客户机的需要来组织广 播程序。可将所有接听数据广播的客户机所需要的数据对象简单地并在一起，由服 务器周期地广播，每个周期里任意对象都出现一次且只有一次。数据广播可以看作 客户机存储层次中的一个附加“磁盘”，它位于客户机本地存储器的下一层。也就是 说，当客户机上的应用程序请求一个数据对象时，它首先试图从本地内存或磁盘中 查询，如果没有找到，就开始接听数据广播，直到从这个广播“磁盘”中获得该对 象为止。 s a e h a r y a 等提出的数据广播多盘调度算法是一种典型的访问时间优化算法t ”】。 多盘调度算法构造一个广播调度程序的过程为： 1 ) 将所有数据对象按照访问概率递减捧序，即从热点数据拌到冷门数据。 2 ) 将这些数据对象依次分割到置个相邻的组，称为“磁盘”。定义盘e 的容量 c ，为数据对象的个数。 3 ) 确定各盘的相对广播频率z ，即各盘对象在广播中所占带宽之比。，必须是 华中科技大学博士学位论文 互质的正整数，i = 1 , 2 ，足。 4 ) 产生调度程序： ( i ) 将每个盘分割为若干块：首先，求得所有盘的广播频率的最小公倍数 上c m ；然后，将每个盘占，分割为删一c h u n k ( i ) ：垒竽个相同大小的块，记为c f ， ， - ，= l ，h u m c h u n k ( i ) 。若b ，不能整分，则在不满的块中填充空闲数据。 ( i i )按如下程序交错广播各盘中的块，生成广播调度； 扣，o = o ；f p r i o r i 秒( t ) t h e n b l o c k ( t 。) ； b r o a d c a s t u p d a t e p r i o r i t y ( t ，p r i o r i t y ( t 。) ) f da l ls i t e s 华中科技大学博士学位论文 b l o c k ( t ) 由于低优先级事务可能涉及多个节点，需要将其优先级进行广播，算法如下： u p d a t e p r i o r i t y ( t ，p r i o r i t y ) 伊p ri o r i t y ( t ) p r i o r i t y t h e n t h e p r i o r i t yo ft h sp a r t i c i p a n t s = p r i o r i t y ) 放松可串行化的并发控制技术有可串行化p 2 1 1 5 3 1 、a 一可串行化l 堋”1 、准一致性 可串行化m 。e 可串行化允许一个事务未提交的结果被另一事务读。每一事务有 一与其相关的引入月i 出不一致性界限。一调度是e 可串行化的只要任何事务的引入 引出不一致性界限没有被打破，且去除查询后该调度是可串行化的。一可串行化 是采用“相似性”概念下正规可串行化的扩展，即认为在实时数据库环境中，数据 对象的值表示现实世界中实体的不同状态，对于实时应用，在时间和精确性上有略 微差别的数据可以彼此替换地作为事务的读数据。准一致性可串行化也是允许一定 限度内的不一致性。不管是e 可串行化、一可串行化、还是准一致性可串行化， 其目的都是放松正规可串行化的严格性，减少数据竞争以提高并发度来加速事务处 理。 1 3 2 数据复制 关于复制控制，目前主要研究了以下五种方法及其实时性脬跏f 刎【“1 1 6 2 】： 集中加锁：所有对数据元素的加锁请求都要送到位于某个节点的集中式锁管 理器。所有封锁和解锁请求都在此节点处理。该协议实现简单，但通讯开销也最大。 主副本更新：选择一个副本来作为主副本，所有数据项的更新操作都指向其 主副本，然后，由主节点将更新向其它副本广播。它对那些读操作不要求完全一致 或最新数据的应用系统，可更好地满足时间约束，但主节点易成为瓶颈。 基于令牌：允许各副本轮流担任主节点或存在多主节点，即依令牌持有者为 主节点，这可提高更新操作的性能。 l o 华中科技大学博士学位论文 一致同意原则：协调节点向所有其它节点发送更新请求，只有协调节点收到 所有副本所在节点回答的准备好消息，才开始执行更新，否则，更新被拒绝而不在 任何接点上进行。它保证了所有数据项的副本都是正确的并且也是最新的。 大多数投票：对某一数据项的读写请求需发送到大多数副本上，只有收到超 过了某个给定数目的可以读写的应答，读写操作方可进行。 1 3 3 提交处理 一个分布式实时事务往往需要分解为若干个予事务并发送到多个节点上协同运 行。为了保证事务的原子性，需要原子提交协议以保证各参与节点上的子事务要么 全部提交要么全部不提交，即保证执行事务的各节点在事务执行的最终结果上取得 一致【6 3 6 4 j 1 “】。传统分布式数据库中保证分布式事务原子提交特性的标准方法是两阶 段提交三阶段提交( 2 p c 3 p c ) 协议。但是因它们的不可预报性及过高的时间耗费 而不适合于实时数据库环境。对于分布式实时数据库系统，目前提有两种方案： 设计一种自适应的提交协议：它可在不同负载条件下，动态改变到不同的提 交策略。比如必要时可采用放松了原子性的提交方法。 使用补偿事务：各子事务自由提交，之后对不正确提交的事务用其补偿事务 进行基于语义的u n d o 操作。这是一种乐观的提交方法。 1 4 移动实时数据库及其一致性维护 1 4 1 移动实时数据库 移动实时数据库是国际数据库研究领域的新课题1 4 】【6 1 ，这方面的研究才刚刚 开始。文献【1 4 1 提出了一个实时交通信息导航系统r e t i n a 的方案：文献o 提出了一 种支持无线网络频繁断接的软实时事务调度策略：文献【醴】基于事务漫游方法m ，提 出了一种移动实时事务可串行化并发控制协议；文献p ”提出了一种广播环境中的 并发控制协议( b s g - c ) ，使用的是可串行化正确性准则、且仅在客户端支持只读事 务。与这些研究相同，本文的研究基于如图1 2 所示的移动实时数据库模型。整个平 台类似于一分布式数据库系统，但在数据处理上是移动与实时性的。一组通用计算 l l 华中科技大学博士学位论文 机通过高速有线网络互连。这些计算机分为固定主机( f h ) 和基站( 移动支持基站 b s ) 。移动设备( m u ) 是由电池供电的便携式计算机，它可在称之为“地理上的移 动区域”( g ) 的范围内自由移动，g 是由所有b s 覆盖的区域。为了挖掘频率复用、 支持m u 的移动性，整个g 被分作许多叫单元( c e l l s ) 的小区域。每个单元由专门 的b s 管理，且被分配了一组用于通讯的频率。移动性要求m u 必须在g 内( 单元间) 无限制移动，且必须能在任意单元中访问需要的数据。m u 穿越单元的界限从一个 单元进入另一个单元叫转交( 过区切换) 。过区切换的处理对m u 是透明的。固定主 机通过固定网络通信，而移动设备在基站支持下通过无线信道与其它主机通信m 。 系统中包含有实时数据库服务器( r t d b s ) 。包含r t d b s 丝毫不影响移动网络的 基本功能。r t d b s 可安装于b s 或f h 。不失一般性，对r t d b s ，m u 的功能做如 下假设： m u ：移动设备；b s ：移动支持基站ff i - i ：没有无线接口的固定主机： 、。+ 、 ：无线连接； 一) 无线单元。 图12移动实时数据库体系结构 r t d b s 是有线网络上一个独立的数据处理节点，可有多个r t d b s 。 r t d b s 提供全部数据服务，它仅通过b s 与m u 通信。 b s 能通过有线网络到达任意r 肛) b s 。 华中科技大学博士学位论文 假定有恰当的缓存模式维护缓存一致性。每一m u 的功能可能会有一些差 异，但所有m u 都有事务处理能力。 r t d b s 可以拉式和推式两种形式发布数据【，o 。客户显式地从服务器请求数 据；服务器接收到一个数据请求，查找到相关信息，并返回给客户机，这种形式的 数据发布叫做拉式数据发布。客户没有数据请求，而由服务器重复的广播数据给大 量客户机，各个客户从到达广播信道的信息中检索出自己感兴趣的数据，这种形式 的数据发布叫做推式或广播式数据发布。移动实时数据库中，一般采用广播发布大 量公共需求信息，同时支持客户请求特定特殊信息( 拉式) 。 1 4 2 移动实时数据库的一致性概念 在移动实时数据库系统中，数据库服务器就是一个实时数据库系统，其中的数 据只在一定时间内是“流行”的，其值随外部环境状态变化而频繁地改变，所以不 能只考虑数据库内部状态的一致性，还必须考虑外部状态与内部状态之间的一致性； 也不能认为使用数据时，简单的提供其最新值就是最合适的，还必须考虑它与其它 被使用数据间的相互一致性【“1 1 1 6 1 1 7 1 】m 】。 定义1 1 一个移动实时数据库的数据对象为一个四元组；d 。其中 d 为数据对象标识，分量d ，为d 的当前状态或值；d ，为d 的观测时标( o b s e r v a t i o n t i m e s t a m p ) ，即采样d 对应的现实世界对象的值的时间；d 。为d 的外部( 绝对) 有效期( e x t e r n a lv a l i d i t yi n t e r v a l ) ，即自d 。算起或具有外部或绝对外部一致性的 时间长度：d t 表示d 的位置，如其位于数据库服务器中或者位于某移动设备缓存区 并随移动设备而移动。 定义1 2 ( 内部一致性) 当且仅当d 满足所有预先定义的完整性和一致性限制时， 数据d 是内部一致的。 定义1 3 ( 外部一致性) 数据d 是外部( 或绝对) 一致的，当且仅当 ( r ，一d 。) d 。( l 为当前或检测时间) 。 1 3 华中科技大学博士学位论文 定义1 4 ( 相互一致集) 用来作决策或导出新数据的一组数据对象称为一个相互 一致集，记为r 。每一这样的r 都有一与之相联的有效期，记为r 。 定义1 5 ( 相互一致性) 设r 是一个相互一致集，d r 。d 是相互( 或相对) 一 致的，当且仅当w r i 一d p | s r 。 定义1 6 ( 时间一致性) 若一个数据既是外部一致的又是相互一致的，则说它是 时间一致的。 定义1 7 ( 数据的正确状态) 当且仅当一个数据同时是内部一致和外部一致的， 才说它具有正确的状态。每一数据都具有正确的状态，则说数据库有正确状态。 1 4 。3 移动实时数据库的致雠护 一致性维护是数据库管理系统最基本、最核心、最关键的任务，移动实时数据 库管理系统也不例外l “】f “1 。 在传统数据库系统中，为了有效管理事务对数据库的操作以保证数据一致性， 人们引入了具有a c i d 特性的事务概念嗍f 7 5 1 f 7 删。事务是一系列的数据库操作，是 数据库应用程序的基本逻辑单元。事务的原子性要求事务中包括的诸操作要么都做， 要么都不做。事务的一致性要求应用程序所定义韵事务( 在单个事务正常执行完成 时) 是使数据库从一个一致性状态变到另一个一致性状态。如果数据库系统运行中 发生故障，有些事务尚未完成就被迫中断，这些未完成事务对数据库所做的修改有 一部分已经写入数据库，这时数据库就处于一种不正确的状态，或者说是不一致的 状态。可见，一致性与原子性密不可分。当多个事物同时对数据库进行更新时，即 使每个单独的事务都是正确的，数据的一致性也可能被破坏。事务的隔离性就要求 一个事务的执行不能被其它事务干扰。考虑到系统中可能的各种故障，事务的持续 性( 也称永久性) 要求一个事务一旦提交，它对数据库中数据的改变就应该是持久 性的。接下来的其它操作或故障不应该对其执行结果有任何影响。可见，保证了系 统中一切事务的原子性、一致性、隔离性和持续性，就保证了传统数据库的一致性。 如前所述，移动实时数据库的一致性具有更为丰富的内容：不仅包括内部一致 性，还包括外部一致性( 至于相互一致性，其实质相当于多版本并发控制机制中的 i 4 华中科技大学博士学位论文 版本选择问题【- ，1 【1 ”，鉴于传统数据库中已有较多研究”】 ”】【，本文不予考虑) 。这就 是说，要有效地管理移动实时数据库事务，以使每个事务( 具有截止期约束) 使用 并产生内部及外部一致性数据。为了保证内部一致性，需要深入研究适宜于移动实 时数据库的并发控制机制；关于外部一致性维护问题，在集中式实时数据库、分布 式实时数据库中就已经存在。然而直到目前为止，实时数据库( 包括分布式) 中的 研究仅仅专注于“时间约束下的内部一致性维护”，外部一致性维护方法的研究近乎 空白儿7 。由于带宽有限、不对称通讯特性等限制，在移动实时数据库中，外部一 致性维护问题更突出、更困难【l l 】【“】。比如，在某些环境中，实时数据库服务器中短 暂有效的实时数据是由来自移动设备的周期性事务不断刷新的【1 1 】【l q 。现有的h h 方 法( 详见5 1 节) 不仅占用过多的处理资源，还将占用过多的通讯资源，尤其是十分 昂贵的上行带宽。因此，衙要研究能有效维护外部一致性的方法【8 】i “l 【“】。 总之，必须针对移动实时数据库及其应用的特征，研究相应的事务模型、事务 并发执行的正确性准则、并发控制机制、外部一致性维护方法等，为移动实时数据 库寻求合适有效的一致性维护措施。 1 5 移动实时数据库原型系统a r t s - m d b 在我们课题组完成的“9 5 ”国防预研重点资助项目主动实时数据库管理系统 研究( 项目编号为a 1 5 4 1 ) 中实现的原型系统a r t s - i i 的基础上，进一步实现了一 个移动实时数据库原型系统a r t 。- m d b ( 如图1 3 所示) 。 1 5 1a r t s - m d b 体系结构 a r t 。- m d b 是由一个s c r v o r 和