（计算机应用技术专业论文）移动实时数据库客户端数据管理.pdf

摘要 传统的分布式计算与分布式数据库的研究是基于有限网络和固定主机的，这 些都采用了一些默认的隐含假设，例如固定网络连接、对等通讯代价、主机节点 固定不变等。2 0 世纪9 0 年代以来，随着移动通讯技术和互联网技术的迅速发展， 加之移动计算的大量普及，许多计算节点可以在自由移动过程中与网络建立连 接，使上述假设条件不再成立，因而传统的分布式数据库中的技术不能完全地应 用到移动数据库中。于是，“移动计算”和“移动数据库”的概念应运而生，并 且正在成为国际数据库界一个新的研究方向。所谓移动实时数据库就是指移动计 算环境中的分布式实时数据库。本文着重探讨和研究移动实时数据库的客户端数 据管理相关技术，包括：数据广播、数据收集、数据缓存与一致性维护。 数据广播技术研究的关键问题是数据广播调度问题，而数据广播调度的关键 就是采用什么样的调度算法，如何确定广播的周期使数据库性能达到最优。本文 首先理论推导出衡量数据广播调度算法好坏的两个参数：访问时间和调谐时间的 最优值，然后通过比较说明多盘调度的优越性，为此设计了一种能在优化调谐时 间的同时仍保持较低访问时间的多盘调度算法，并解决该算法带来的分盘及广播 频率的问题。 数据收集技术是指在断接前把用户将来可能访问的数据预先存储到本地缓 存的一种技术。本文探讨并分析了基于优先级的视图更新算法( p i u 算法) 的优 缺点，在此基础上提出一种改进的p i u 算法，力求当网络断接或弱连接情况下， 在尽可能短的时间内移动主机视图获得尽可能大的数据新鲜度，有效地改善移动 实时数据库客，o 端数据的面向用户性、实时性和一致性，更好地为用户提供通过 无线网络访问服务器上数据库的服务。 移动计算环境特点决定了在移动实时数据库中，为了满足用户通过无线网络 访问服务器端数据库的实时l 生，有必要在移动主机端缓存数据，由此带来了数据 缓存和一致性维护相关问题。本文首先通过比较分析确定缓存的粒度，在此基础 上研究了缓存的工作机制。根据客户端数据缓存的弱一致性要求，给出了弱一致 件缓存管理协议，以解决发生在无线环境下由各种原因产生的断接，它通过广播 更新报告和发送更新报告相结合来节省网络带宽。 关键字：移动实时数据库，客户端数据管理，数据广播，数据收集，数据缓存与 一致性维护 机密文件 a b s t r a c t t h es t u d yo ft r a d i t i o n a ld i s t r i b u t e dc o m p u t i n ga n dd i s t r i b u t e dd a t a b a s ei sb a s e do n l i m i t e dn e t w o r ka n df i x e dh o s t i ta d o p t ss o m et o l e r a n tc r y t i ch y p o t h e s i s ，s u c ha s f i x e dn e t w o r kc o n n e c t i n g ，p e e rt op e e rc o m m u n i c a t i o nc o s t ，f i x e dh o s te t c w i t ht h e d e v e l o p m e n to fm o b i l ec o m m u n i c a t i o nt e c h n o l o g ya n di n t e r n e tt e c h n o l o g y ，a n dt h e p o p u l a r i t yo f m o b i l ec o m p u t i n g ，m a n yc o m p u t i n gn o d ec a nc o n n e c tw i t hn e t w o r ka s m e y m o v e t h e na b o v e m e n t i o n e dc o n d i t i o n sd on o te x i s ta n ym o r e t h et e c h n o l o g y o ft r a d i t i o n a ld i s t r i b u t e dd a t a b a s ec a n n o ta p p l yt om o b i l ed a t a b a s ea b s o l u t e l y s o t h e r eb r i n gt h ec o n c e p t so f “m o b i l ec o m p u t i n g a n d “m o b i l ed a t a b a s e ”，w h i c ha r e b e c o m i n gt h en e wr e s e a r c h i nt h ea r e ao fd a t a b a s e i nt h i s p a p e r , s o m er e l a t e d t e e h n o l o g ya b o u td a t am a n a g e m e n tf o rt h e c l i e n ti nm o b i l er e a l t i m ed a t a b a s ei s i n v e s t i g a t e d ，i n c l u d i n g d a t ab r o a d c a s t ，d a t ah o a r d i n g ，d a t ac a c h ea n dc o n s i s t e n c y m a i n t e n a n c e t h e p i v o t a lp r o b l e mo f d a t ab r o a d c a s tt e c h n o l o g yi st h ep r o b l e mo f d a t a b r o a d c a s t s c h e d u l i n g ，t h ek e ya r cs c h e d u l i n ga l g o r i t h ma n da s c e r t a i n i n gc y c l eo f b r o a d c a s tt o o p t i m i z e d a t a b a s e p e r f o r m a n c e i n t h i s p a p e r t h eo p t i m i z a t i o nv a l u e s o ft w o p a r r m e t e r s w h i c ha r ea c c e s st i m ea n d t u n i n g t i m e s c a l i n g f o rd a t ab r o a d c a s t s c h e d u l i n ga l g o r i t h m a r ed e d u c e d t h ea d v a n t a g eo fm u l t i d i s ks c h e d u l i n ga l g o r i t h m i sa n a l y z e db yc o m p a r i s o n am u l t i d i s ks c h e d u l i n ga l g o r i t h mw h i c hc a nk e e pl o w a c c e s st i m ea st u n i n gt i m eo p t i m i z e di sd e s i g n e d p r o b l e m sa b o u td i s kp a r t i t i o na n d b r o a d c a s tf r e q u e n c yb r o u g h tb v 恤i sa l g o r i t h ma r er e s o l v e d d a t ah o a r d i n gt e c h n o l o g ym e a n st h et e c h n o l o g yo fp r e f e t c h i n gd a t aw h i c hm a y a c c e s sb yu s e ra f t e rd i s c o n n e c t i o nl a t e rt oc a c h e i nt h i sp a d e r , m e r i t sa n dd e m e r i t so f p i ua l g o r i t h mw h i c hi sav i e wu p d a t ea l g o r i t h mb a s e do nt h ed y n a m i cd a t af r e s h n e s s p r i o r i t ya l ea n a l y z e d o nt h i sg r o u n d ，a ni m p r o v e dp i ua l g o r i t h mp r e s e n t e d ，i no r d e r t h a tv i e wa tm o b i l eh o s tc a ng e ta sm u c hf r e s h n e s sa sp o s s i b l ei na ss h o r tt i m ea s p o s s i b l ew h e nd i s c o n n e c t i o no r1 0 wc o n n e c t i o nh a p p e n s i te f f e c t i v e l yi m p r o v e st h e u s e r - o r i e n t e d r e a l t i m ea n dc o n s i s t e n c yp r o b l e mi nt h ed a t ao nt h ec l i e n to fm o b i l e r e a l t i m e d a t a b a s e ，p r o v i d i n gt h e s e r v i c eo fa c c e s s i n gd a t ao nd a t a b a s e t h r o u g h w i r e l e s sn e t w o r kf o ru s e r sb e t t e r c a c h ei s n e c e s s a r ya tm o b i l eh o s tt os a t i s f yt h er e a l t i m e o fu s e r s a c c e s s i n g d a t a b a s eo nt h es e r v e rt h r o u g hw i r e l e s sn e t w o r k i ti sd e t e r m i n e db vt 1 1 ec h a r a c t e ro f m o b i l ec o m p u t i n ge n v i r o n m e n t t h e nb r i n gt h ep r o b l e m so fc a c h ea n dc o n s i s t e n c y m a i n t e n a n c e i nt h i s p a p e r , c a c h eg r a n u l a r i t yi s a s c e r t a i n e db yc o m p a r i s o n t h e n c a c h ew o r k i n gm e c h a n i s mi si n v e s t i g a t e db a s e do n t h i s a c c o r d i n gt ot h er e q u i r e m e n t o fc a c h ew e a kc o n s i s t e n c y , w e a kc o n s i s t e n c yc a c h i n gi s p r o p o s e d t or e s o l v et h e d i s c o n n e c t i o nc a u s e di nw i r e l e s se n v i r o n m e n t i tr e t r e n c h e st h en e t w o r kb a n d w i d t h b y b r o a d c a s t i n gu p d a t er e p o r t sa n ds e n d i n gu p d a t er e p o r t s k e y w o r d s ：m o b i l er e a l t i m ed a t a b a s e ，d a t am a n a g e m e n tf o r t h ec l i e n t ，d a t ab r o a d c a s t ， d a t ah o a r d i n g ，c a c h ea n d c o n s i s t e n c ym a i n t e n a n c e 机密文件 浙江大学硕士学位论文 1 1 研究背景 第一章概述 上个世纪九十年代以来，随着移动通信技术的迅速发展和投入使用，加上可 移动计算机的大量普及，使得许多计算机可以在移动的过程中与网络节点建立连 接。在移动设备上嵌入移动数据库己成为许多行业的迫切需要。嵌入式移动数据 库市场在1 9 9 8 2 0 0 5 以1 2 的速度增长，移动实时数据库将移动计算与实时数据 库相结合成为新兴的热点研究领域。 与传统的分布式计算环境相比，由于移动实时计算环境是一种更加灵活的计 算环境，它可以支持更多类型的分布式应用，典型的应用有： ( 1 ) 实时公共信息发布 在信息社会中，现已出现并可以预见将会出现大量的移动用户。在移动环境 中，这些移动用户通过持有手中的无线信息收听装置或便携电脑访问各种公共信 息，如新闻、股票、天气等。通过车载嵌入式无线收听装置收听城市各条道路的 实时车流、交通状况，以决策指挥交通。 ( 2 ) 移动电子商务 公司管理人员、推销员等，使用笔记本电脑，在路途中的移动状况下，或在 异地存取公司服务器中的数据，完成商务交易。与传统分布式数据库应用对比， 移动电子商务要求当用户从一个移动单元转移到另一个移动单元时，“过区切换” 对用户透明。同时支持网络状况不佳甚至断接时的数据操作。 ( 3 ) 军事应用 未来战争是一场以信息技术为核心的“信息战”，从大的移动武器装备如航 空母舰，到小的装备如弹头，以至于战士的头盔都装有先进的信息接收处理设备。 服务器将指挥信息发送给各个战斗单元，指挥各个单元协同作战。 ( 4 ) 位置相关查询 位置相关查询是移动实时数据库应用中最具特色也最吸引人之处。设想一个 旅游者抵达一个陌生城市，他可以通过随身携带的移动设备查询许多信息，如最 近的餐厅在哪里，怎样去最近的医院等等。与传统的数据库查询不同的是，上述 机密文件 浙江大学硕士学位论文 查洵的结果是与位置相关的，同样一个问题在不同的地理位置得到的回答可能是 不同的。 此外，移动实时数据库技术配合g p s 技术，可用于智能交通管理、大宗货 物运输管理和消防现场作业等。移动实时数据库广泛的应用需求推动了对移动实 时数据库技术的理论研究。 1 2 移动计算环境及特点 计算环境先后经历了集中式计算环境、分布式计算环境、网络计算以及目前 受到广泛关注和研究的移动计算环境m 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 ) 和普 遍化计算环境p c e ( p e r v a s i v ec o m p u t i n ge n v i r o n m e n t ) 等多种计算模式。移动 计算的概念足对“任何时间，任何地点的立即通讯”的扩展。在分布式计算的基 础上，计算环境进一步扩展为包含各种移动设备、具有无线通信能力的服务网络， 构成了一个新的计算环境，即移动计算环境。 1 2 1 移动计算环境的网络结构 在传统的分布式计算机系统中各个计算机节点之间都是通过固定的网络连 接，并保持网络的持续连接性，而移动计算系统改变了这种条件。移动计算机系 统是由固定的节点和移动节点组成的分布计算系统，它将使用户不再需要停留在 固定位置不变，而是可以携带着计算机自由移动，并在移动的同时通过移动网络 保持与固定节点或其它移动节点的连接。在一个移动计算机环境中，网络由固定 主机f h ( f i x e dh o s t ) ，移动设备m u ( m o b i l eu n i t ) 和基站b s ( b a s es t a t i o r l ) 或 称为移动服务支持节点m s s ( m o b i l es u p p o r ts t a t i o n ) 组成。移动设备经无线通 道通过基站( 移动服务支持节点) 与固定网络连接。移动设备为电池供电的便携 电脑，在某一限定的区域内自由移动，此区域为所有基站覆盖的区域。为了支持 移动设备的移动性，整个区域被划分成许多称为单元( c e l l ) 的小区域，各个小区 域由特定的基站管理。每一个基站存储如用户的开工文件、注册文件、存取权限 和用户的私人文件等等。任何时刻，一个移动设备的通信不仅仅局限于它所注册 的基站，还支持移动设备在所有基站覆盖的区域自由移动，同时具有从任何单元 中存取所需数据的能力，移动环境的网络结构如图1 i 所示。 机密文件 2 浙江大学硕十学位论文 图1 1 移动计算环境的网络结构 在移动计算环境中，高速固定网络部分构成连接固定节点的主干，固定部分 的网络能提供带宽为i 0l o o m b p s 的高速以太网，或l o o m b p s 的f d d i ( f i b e r d i s t r i b u t e dd a t ai n t e r f a c e ) ，1 4 4 m 的a t m ( a s y n c h r o n o u st r a n s f e rm o d e ) 。 固定网络中拥有若干基站，每个基站建立一个无线网络单元，单元内的移动计算 机与基站之间通过无线网络连接，无线接口可以可能是带宽为i 0 2 0 k b p s 的蜂窝 网络或者是带宽为l o m b p s l o o m b p s 的局域网。 1 2 2 移动计算环境的操作模式 在计算进行时，移动设备可以改变位置和网络连接，在运动过程中移动主机 通过基站的无线连接支持保持网络连接，基站和固定主机在数据库服务器的支持 下进行事务处理和行使数据管理功能。基站提供通用的应用软件供移动用户下 载，在掌e 电脑或固定主机中运行。移动主机在分布式系统中可能担任不同的角 色，有服务器能力移动设备，可以通过使用局部并发控制和恢复算法进行计算。 装有非常慢的c p u 和非常小的内存的设备仅仅充当w o 设备，因此它们依赖于固 定主机。 当移动设备离开一个基站支持的单元，过区切换( h a n d o f ) 协议建立一个与 新的基站的通信连接，将正在进行的事务和数据库状态从一个基站迁移到另一个 基站。整个过区切换过程对移动设备透明。 传统的分布式系统中，主机处于两种操作模式中的一种：或者保持与网络的 连接，或者完全断开。在移动环境中，有下列几种操作模式： ( 1 ) 完全连接( 正常连接。c o n n e c t e d ) ： 机密文件 浙江大学硕上学位论文 ( 2 ) 完全断开( d i s c o n n e c t e d ) ； ( 3 ) 部分连接或弱连接( w e e kc o n n e c t e d ) 。如：终端以低带宽与网络连接。 为了节省能源，移动计算机可能进入一种节能状态，称之为休眠状态。移动 设备的休眠状态并不意味着断接后的故障。在休眠状态，时钟频率降低，不运行 用户程序。在移动计算环境中大多数断接可以预报。以下协议用来进行各种模式 之间的转换。 ( 1 ) 断接协议( d i s c o n n e c t i o np r o t o c 0 1 ) ：断接协议在移动主机从网络中物 理断开前执行。协议必须保证移动主机缓存足够的信息供在断开自主运行，它必 须将即将到来的断接通知相关部件。 ( 2 ) 部分断接协议( p a r t i a l l yd i s c o n n e c t i o np r o t o c 0 1 ) ：为移动主机在与 固定网络的通信带宽受限制的运行模式做准备，在移动主机中缓存一部分数据将 使未来的网络使用最小化。 ( 3 ) 恢复协议( r e c o v e r yp r o t o c 0 1 ) ：重新与固定网络建立连接，重新开始正 常操作。 ( 4 ) 过区切换协议( h a n d o fp r o t o c 0 1 ) ：过区切换指穿过一个单元的边界进 入另一个单元。过区切换协议收集移动主机应传输到新单元基站的信息。 各种模式的转换如图1 2 所示： o 精奠协饿 密肆骨瞄蕞罅骥 固饿置* 谖 图1 2 移动计算环境操作模式转换图 1 2 3 移动计算环境的特点 移动计算系统是一个动态的分布式系统，网络中节点之间的连接动态变化， 不依赖于一个固定的网络结构。许多分布式系统中的问题解决方法不能应用于移 动计算领域。移动计算环境与基于固定网络的传统分布式计算环境相比，具有以 机密文件4 浙江大学硕上学位论文 卜- 一些主要特点： ( 1 ) 移动性。 ( 2 ) 频繁断接性。 ( 3 ) 网络条件多样性。 ( 4 ) 网络通信的非对称性，下行链路与上行链路的通信带宽相差很大。 ( 5 ) 移动计算机的电源支持时间有限。 ( 6 ) 与固定网络相比可靠性低。 ( 7 ) 规模的可伸缩性。 由于移动计算环境的上述特点，使得传统的分布式实时数据库技术不能或不 能有效地支持移动计算环境。因此，移动实时数据库技术，即支持移动计算环境 的分布式实时数据库技术，己成为目前分布式数据库研究的一个新方向。 1 3 移动实时数据库的系统模型 移动实时数据库的目的就是有效地支持移动计算环境中的各种数据使用，满 足在任意地点任意时刻访问任意数据的要求。在上述移动计算环境的基础上，我 们建立一个移动实时数据库的系统模型如图1 3 。在系统模型中，移动数据库由 两部分节点组成： ( 】) 固定部分：数据库服务器位于固定节点上，每个数据库服务器维护一个 本地数据库l d b ( l o c a ld b ) ，服务器之间由可靠的高速网络连接在一起，构成一 个传统意义上的分布式数据库系统。 在固定部分还有固定主机f h ，可作为l d b 的客户机。另外还有位置服务器 位于各个m s s 上，对单元中的客户的位置进行管理。 ( 2 ) 移动部分：移动部分有移动主机m h ，它作为固定部分分布式数据库 的客户，移动主机的c p u 处理能力和存储能力相对于服务来说非常有限，具有移 动性。按c p u 的处理能力，将m h 分为两类，一类为具有一定数据处理能力的m ， 在这类m h 上，有一个r t d b m s ，可以利用缓存或复制数据( r e pd b ) 进行数据库操 作；另一类不具有数据处理能力，只是作为一个“哑终端”( d u m bt e r m i n a l ) 或 i o 设备，必须借助它所在单元的数据库服务器进行数据处理。 机密文件 浙江大学硕上学位论文 图1 3 移动实时数据库的系统模型 移动计算以及其具有的特点对传统的分布式数据库技术提出了新的要求和 挑战，一个理想的移动数据库系统应当实现阻下四个目标： ( 1 ) 可用性和可伸缩性( s c a l a b i l i t y ) ：在避免系统不稳定性的同时提供可 用性和可伸缩性。 ( 2 ) 移动性( m o b i l i t y ) ：允许移动计算机在网络断接的情况下访问或更新数 据库。 ( 3 ) 可串行性( s e r i a l i z a b i l i t y ) ：支持满足可串行性的并发事务的执行。 ( 4 ) 收敛性( c o n v e r g e n c e ) ：使系统总能收敛于一致状态。 1 4 本文的研究内容与组织 本文针对移动实时数据库的特点，解决客户端数据管理相关技术，包括数 据广播、数据收集、数据缓存与一致性维护。 本文的组织如下： 第一章，介绍研究背景、移动计算环境及其特点、移动实时数据库的系统模 型、本文的研究内容与组织。 第二章，综述移动实时数据库客户端数据管理的三种相关技术：数据广播、 数据收集、数据缓存与一致性维护。 第三章，研究数据广播的调度，分析多盘调度的优越性，为此设计一个多 盘调度算法，并解决该算法带来的分盘策略及广播频率的问题。 机密文件6 浙江大学硕士学位论文 第四章，研究基于优先级的数据收集，首先介绍分析基于优先级的视图更 新算法( p i u 算法) ，在此基础上提出种改进的p i u 算法。 第五章，研究数据缓存与一致性维护，分析确定缓存粒度，缓存工作机制， 介绍缓存弱一致性概念，并给出弱一致性缓存管理协议。 第六章，总结本文的工作，展望本研究的发展前景。 机密文件 浙江大学硕上学位论文 第二章客户端数据管理综述 为了满足1 3 节所述的移动数据库的四个目标，移动数据库系统与传统分布 数据库系统相比，在数据管理方面产生了一系列薪兴的研究项目。如数据广播、 收集、缓存。在这三个方面有如下的关键技术和研究成果。 2 1 数据的广播技术 数据广播是将热点数据通过共享无线信道发送给大量用户的一种传播方式。 在移动环境下，由于无线通信的低带宽和网络通信的非对称性，数据广播是一种 有效的数据发布方式。数据广播使下行带宽有了伸缩性，可同时满足大量用户的 信息获取而不出现网络的拥塞。 数据广播广泛应用于非对称的通信环境中，通信的不对称来源于以下两个因 素 1 ： ( 1 ) 通信网络的物理特性，如无线网络、有线电视网络等，在这些通信中，下 行带宽远远大于上行带宽； ( 2 ) t 作负荷的不对称，在c s 结构中，服务器要响应大量客户机的服务请求， 往往承担比客户机大得多的工作负荷。 p a g e b r o a d c a s ts c h e d u le 淳= 兴二! ) 一、 ( _ 曼县，) 图2 1 无线通讯中的数据广播系统 上图给出了无线通讯中的数据广播系统图 2 。服务器将共享数据组织起来， 通过无线信道连续性地进行广播。用户通过侦听信道获取自己需要的数据。与传 统的c s 联机数据请求方式相比，数据广播具有以下优点： 机密文件 浙江大学硕士学位论文 ( 1 ) 很好的伸缩性。数据广播最大的优点是它的开销跟移动主机的数量无 关。因此它可以以很小的代价支持大量的移动主机同时访问数据； ( 2 ) 节约有限带宽。移动主机从数据广播中获取数据，可以避免、减少与 服务器问的上行网络通信： ( 3 ) 适合不稳定的网络连接。在移动环境下，由于无线带宽的不稳定性， 移动主机会经常跟服务器断开连接。通过数据广播，即使在断开时，也允许移动 主机访问最新数据。 近年束移动数据广播技术已引起了广泛的研究，主要有广播模式、广播调度 策略和广播组织方式等方面的研究。 2 1 。1 广播模式 广播模式分为“静态”模式和“动态”模式。在“静态”模式下，服务器按 预定的内容进行数据广播而不考虑移动用户的需求。如广播盘技术将要广播的数 据根据存取概率组织，高频数据分配较多的盘数进行广播，这种广播技术首先要 知道各个数据的访问概率，广播的内容组织是既定的，实际是一种“静态”的广 播技术 3 4 。而“动态”模式，如“按需”广播模式，分配给移动用户少量的 上行带宽上传其需求，然后服务器按此需求动态组织数据并广播。“混合”广播 模式则是静态和动态，1 。播模式的结合。 2 1 2 广播调度策略和组织方式 广播数据的调度可以细化为两个方面：1 ) 选择广播数据；2 ) 按一定的顺序 组织广播数据。其实，这两方面在实际的研究中不可能完全分开。 在“静态”模式( 推方式) 下，服务器将需要广播的数据组织起来，通过无 线信道进行周期性的广播。服务器根据调度策略确定广播数据的广播顺序和频 率。主要包括以下四种典型的数据调度方式： ( 1 ) 均匀广播( n a tb r o a d c a s t ) 。最简单的数据调度策略就是均匀广播。在该方法 中所有的数据都以相同的频率进行广播，所有数据的访问时间都是广播周期的 1 2 。由于在多数情况下，用户的数据存取是非均匀的，因此均匀广播的总体性 能不高。 机密文件9 浙江大学硕上学位论文 ( 2 ) 基于概率的广播方式。为了适应数据访问的非均衡性，提出了基于概率的 广播方式。我们为每个数据设定一个基于访问概率的函数f ；，根据函数值确定数 据的广播顺序和频率。在文献 5 中，设置如一i - ： ，：鼻 2 一；。0 q i 其中，q i 是数据的访问概率，n 是数据项的总数。在该方法中，某些数据项的访 问时延可能会非常大。 ( 3 ) 广播磁盘( b r o a d c a s td i s k s ) 。将数据库中的数据分配到不同的“逻辑磁盘” 中，每个盘以不同的频率和速度广播。该方法类似于传统的存贮体系结构，因此 称为广播磁盘。 ( 4 ) 最优调度策略。文献【6 2 】【7 【5 研究了最优的广播调度，在文献 6 中给出 了最小化平均访问时间的平方根规贝, 1 1 ( s q u a r e r o o tr u l e ) 。该规则包括两个条件：1 ) 每个数据项的广播实例都是等间距的；2 ) 每个实例之间的间隔正比于数据项访 问概率的平方根，反比于数据项大小的平方根。如果广播调度满足这两个条件， 则平均访问时间可以取得理论最优值。但是这两个条件在实际应用中很难满足， 因此出现了很多近似的方法。 在“动态”模式( 拉方式) 下，用户向服务器提交请求，服务器根据用户的 请求查询所需的数据项，并将其返回给用户。与推方式不同的是，服务器可以获 得用户对数据的访问模式，因此比较容易设计调度策略。 机密文件 图2 2 “动态”模式下的调度模型 浙江大学硕士学位论文 图2 2 给出了采用拉方式进行广播调度的模型 5 】。根据用户的请求，服务器 选择某个数据项进行广播。服务器的决策过程可以用状态转换来描述。假设某个 时刻服务器处于状态 ( n l ，n 2 ，n n ) ，j 其中n i 表示等待数据项d i 的请求数 目( 0 n ，k ) ，j 表示服务器目前正在处理的数据项。如果j _ 0 ，表示服务器处 于空闲状态。在新的数据请求到达或者处理完某个请求后，服务器的状态发生转 换。假设服务器在上面的状态下，接受到一个新的数据请求r i ，则转换到如下状 态 ( n ，u i + 1 ，n n ) ，j 】。服务器处理完数据项d i 的请求后转换到状态【( n ， n ，= 0 ，n n ) ，j 】。服务器状态转换的关键是确定下一个需要处理的数据项请 求。有两种调度策略： 1 ) 经常访问的数据优先( m r f ，m o s tr e q u e s tf i r s t ) ：选择等待请求数最大 的数据项，即在上述状态中n i 最大的数据； 2 ) 等待最久的数据优先( l w f ，l o n g e s t w a i tf i r s t ) ：计算数据项的所有等待 时延，选择时延最大的数据。 在用户数目不大时，系统的平均访问时间跟调度策略关系不大。在数据项访 问概率相同的情况下，m r f 算法的效率高于l w f 。如果用户的数据请求符合z i p f 分布，则l w f 算法的平均访问时问小于m r f ，即在该情况下l w f 算法效率较 高【5 】。需要注意的是，构造l w f 算法的代价较高。 2 2 数据的收集技术 数据收集( d a t ah o a r d i n g ) 是将数据装入到移动客户机的缓存中，为即将发 生的断接作准备 8 9 。数据收集的目的是使客户机在断接期间能够使用本地数 据自主操作。在某种程度上，数据收集类似传统缓存机制中的预取过程，通过使 数据较快被存取来提高系统性能。预取与数据收集的主要不同之处在于前者是利 用网络通信量低的时候将未来使用可能性最高的数据传送到缓存：而后者的执行 不依赖于计划断接前网络的通信状况。上述两个过程具有不同的目标：预取试图 提高系统的性能，而数据收集试图提高数据的可用性。 2 2 1 数据收集要解决的问题 数据收集要解决的第一个的问题是：收集的单元( 粒度) 。从服务器传送到移 机密文件1 1 浙江大学硕士学位论文 动缓存的数据项的大小依赖于应用环境，可根据使用的数据模型而有不同的值。 在文件系统中，收集单元可能是文件：在关系数据库系统中，可能是属性、元组、 多个元组或整个关系；在面向对象的数据库系统中，收集单元为单个对象、多个 对象、整个类。 第：二：个问题是：收集哪些数据项? 即怎样预计在断按期间哪些数据将为移动 客户所需要。解决这个问题的困难在于：哪些数据项将被收集取决于系统的应用 设计。预计未来所需要的数据有两种解决途径：显式的和隐含的。前一种方法要 求用户显式指定哪些数据需要收集( 收集描述) 。后一种方法则根据以前操作的经 历( 数据存取经历) 推导关于数据项的信息。两种方法可以结合使用以获得更好的 性能。 第三个问题是：什么时候进行数据收集? 如果所有的或者大多数断接可预 报，数据收集可先于断接操作进行。另一个可能性是周期性进行数据收集，这样 可以使客户在不能预报或很少预报的断接时成功进行操作。实时数据库系统中， 事务和数据都有定时限制。收集时还要考虑数据的时效，对于一个断接周期，如 果数据的时效小于断接周期，这样的数据将不被收集。 2 2 2 数据收集相关关键性工作 数据收集最初是一个用于文件系统中的概念。大多文件系统中对断接操作的 支持是通过扩展缓存管理来实现的。第一1 个支持断接操作的是c o d a 文件系统 9 1 0 ，用户通过脚本语言指定感兴趣的文件，缓存管理器把这些文件和l r u 算法得到的缓存数据结合起来构成本地缓存。其收集过程需要用户的指导。另一 个文件系统s p y u t i l i t y 通过使用收集执行树自动进行收集处理 1 1 】，收集执行 树是基于文件引用路径建立的。s e e r 系统的自动预报数据收集是根据用户过去 的行为( 文件存取经历) 寻找文件系统间的语义关系。文件用一种称为语义距离的 度量聚集在一起，语义距离是对文件之间关联密切度的度n 1 2 1 3 。 在数据库系统中数据收集变得非常复杂。有下列原因： l 、对于文件系统，收集的单位为文件，它对应于关系数据库中的关系和面 向对象数据库中的对象类。但是，这个粒度并不合适，较小的粒度如属性、元组 或部分元组将更有意义并能获得更好的性能。 机密文件 浙江大学硕士学位论文 2 、使用过去引用的经历推导数据库项间的依赖比标识出文件之间的依赖复 杂。 = j 于文件系统是按层次组织的，找出文件间的相关相对容易。一般而言，同 一个目录下的文件比不同目录下的文件有更密切的关系。 一个文件系统下的用户通常只需要有限数量的文件( 整个文件系统的- - + 部 分) 来完成工作，而数据库系统的查询可能涉及大量的数据库。这意味着必须缓 存大量的数据以支持数据库系统的断接操作。 3 、在文件系统中，己有很好支持断接操作的系统实现。如收集算法、目志 优化、重新连接后的冲突检测与消解。在数据库系统中，这些问题正处于广泛研 究中，仅有为解决数据库断接操作的一些尝试。 文献 1 4 中，将数据挖掘技术引入到数据收集中，通过建立数据之间的关联 规则，提出了一种通用的自动数据收集算法。 文献 1 5 中，介绍一种在面向对象数据库中通过扩展缓存管理来支持断接操 作的方法。它使用了三种级别的粒度：属性缓存、对象缓存、混合缓存。试图在 缓存中保存经常查询的数据项。 文献 1 6 儿1 7 中，提出关系数据库的数据收集方法。数据库设计者定义收集 关键字( 期望用来获取典型的存取模式) 。按关键字关系分成水平段，以此作为收 集单元。其问题是既然收集段是数据库管理员基于收集关键字的定义而产生的， 收集段对于一些移动客户可能没有意义。 此外还有基于过去存取经历的收集方法 1 8 ，以及基于概率图的数据收集算 法e 1 9 。 2 3 数据缓存与一致性维护 通过数据收集，将事务存取的数据特别是经常存取的数据缓存在移动主机 上，这样减少移动主机与固定主机的通信，从而节省无线带宽。同时，在移动主 机卜缓存数据，使移动用户在断接时使用缓存数据完成事务处理，提高了数据的 可用性。因此，在移动主机上缓存相关数据是移动环境中提高系统性能的手段 2 0 2 1 2 2 2 3 2 4 2 5 之一。设计一个有效缓存机制包括以下几个重要问 题：( 1 ) 缓存什么，什么时候缓存，缓存多长时间。( 2 ) 什么时候以及如何使缓存 失效，以什么粒度。( 3 ) 以什么样的代价提供给用户数据一致性。e h 于移动主机 机密文件 浙江人学硕士学位论文 可与固定主机断接，并可关机。特别在长时间断接后，移动主机很难知道其缓存 的数据是甭有效。因此缓存的一致性管理是移动计算环境中的个难点。缓存的 致性( c a c h ec o n s i s t e n c y ) 是指移动客户缓存的数据与服务器中的数据保持一 致，服务器数据更新及时反映到移动客户中，移动客户对缓存的数据的更新及时 传送到服务器中，再由服务器传送到相关移动客户中。在移动实时数据库管理系 统中，数据具有定时限制，除了考虑通常的数据一致性外还要考虑数据库的一致 性及数据的时效。 2 3 1 缓存机制 依服务器是否保存客户的状态可分为保存状态策略( s t a t e f u l ) 和不保存状 态策略( s t a t e l e s s ) 。采用保存状态策略，服务器保存移动主机的状态，存有移 动客户机所缓存的数据信息。因此当数据库发生改变，固定主机发送失效信息到 那些缓存数据项改变了的移动主机。不保存状态策略，服务器不需要知道移动客 户机的缓存状态，只需明了数据更新经历，通过周期广播或当客户提出需求时提 供更新信息给移动主机。因为保存状态方法比较复杂，现有缓存策略大多基于不 保存状态策略 2 6 2 7 2 8 儿2 9 。 根据维护缓存一致性的方式，可分为同步广播失效报告和异步查询方法。现 有的在断接情况下维护缓存一致性的方法大多基于失效报告或称“回叫” ( c a l i b a c k ) 机制。这种机制的主要问题在于当客户在断接时，失效信息丢失了 3 0 2 7 3 1 。b a r b a r a 和i m i e l i n s k i 开发了个周期广播失效报告的方法。 采用此方法，服务器每隔l 段时间广播失效报告，报告包括所有在过去w = k l 时 问单元改变了的数据项。如果客户从网络中断开，失去了连续k 个报告，客户仍 然不得不放弃整个缓存。在过去l 时间段发出的用户查询仅仅当收到失效报告才 得到响应，这是因为自从断接后客户不能决定缓存内容的有效性，抛弃整个缓存 则失去了缓存的作用。现有的移动计算环境以低带宽的无线网络连接、经常与基 站断开、客户端的低能源供给为特征。低能源供给要求客户最小化上行链路查询 并且自愿从网络中断开以节省电池能源，经常断开的特征给在移动客户端维护一 致性的缓存的工作增加新的困难。因此，各种缓存维护协议必须优化使用有限的 带宽 3 2 儿3 3 3 4 。除了能容忍断接，这些协议应该有效利用能源和适应无线网 机密文件1 4 浙江大学硕士学位论文 络提供的q o s ( q u a l i t yo fs e r v i c e ) 服务 3 5 。 对，。播失效报告扩充的方法有：优化失效报告大小 3 1 ；根据查询频率和用 户断接时间凋整失效报告的周期 2 3 ；将广播限定，。播到邻近的客户。文献 3 6 中提出一个增强的方法，移动客户在长时间断接后向服务器发送回所有缓存的数 据连同其时问戳，服务器找出改变的数据项，返回有效报告。这个方法导致带宽 浪费和不必要的上行带宽请求，并没有解决任意长的休眠的问题，因为局部缓存 在断接时间长于w 时必须抛弃。文献 3 1 提出位串方法，失效报告连同时间戳用 二进制位串表示。位串结构比时间窗口w 包括更多更新历史信息，但在少量数据 改变的情况下仍产生较大的失效报告。如果数据库中一半数据项更新了，仍然不 得不放弃整个缓存。文献 2 3 提出一个自适应的算法，主要使用t s ( t i m e s t a m p t e r m i n a l s ) 和位串方法，在现有的失效和查询频率的情况下提供更优的调谐时 间。 这些基于同步广播失效报告具有下列特征：( 1 ) 他们假定服务器中不保留移 动用户的信息，没有考虑移动性。( 2 ) 如果客户断开的时间大于广播周期，整个 缓存失效。( 3 ) 大型数据库系统的伸缩性没有得到充分满足。 c o d a 文件系统提供多种机制，对共享文件系统的断接操作提供支持。c o d a 使用两种缓存一致性机制。当客户至少可与一个服务器连接，使用回叫( c a l l b a c k ) 机制。当断接发生，为了提高可用性，允许存取陈旧数据。重新连接时，只有不 产生冲突的客户的修改才能提交。在断接后使缓存有效的速度和失效的正确性的 平衡通过维护多版本时间戳来取得。但是，在每次重新连接后检验整个缓存对客 户造成不必要负担。而且c o d a 是一个分布式文件系统，假定服务器不保存客户 信息，因此不适于其它用途，如w e b 缓存。 文献 3 6 中提出异步查询数据失效报告的机制a s ( a s y n