（计算机软件与理论专业论文）移动数据库系统mdm3的缓存替换策略研究.pdf

华中科技大学硕士学位论文 摘要 移动客户机的缓存替换策略是语义缓存技术的关键，它的好坏直接关系到整个缓 存体系结构性能的优劣。在分析比较当前十一类典型缓存替换算法的基础上，在移动 数据库管理系统m d m 3 原型系统中，设计并实现了一种适合于移动客户端位置相关应 用的簇先段后缓存替换策略及其算法。 引入了更适合移动计算环境特点的语义簇的概念，给出了它的结构以及基于此结 构的缓存总体结构，提出了语义簇生成、合并方法。当新到奄询结果要存入缓存时， 综合考虑当前缓存中语义片段粒度的大小、引用频率等因素，按照先水平分割后垂直 分割的原则对语义片段进行分解，按照以新到查询结果为主的原则对语义片段进行合 j 二。c 如果新到查询结果与缓存中语义片段是语义无关的，那么就新生成一个语义簇， 该簇此时仅含有一个浯义片段；如果有多个语义簇中的语义片段与新到查询结果是语 义相关的，那么经过语义片段修整后，把这些语义簇合并到其中具有最新时间戳的语 义簇中，仅保留此语义簇，删除其他的语义簇。、4 、 簇先段后算法基于语义位置特性，它吸取了t w ol e v e ll r u 算法和f u r t h e s ta w a ? r e p l a c e m e n t 算法的优点又解决了它们的不足。它的思路是：采用t w ol e v e ll r u 算法 的簇机制，把语义相关或语义相邻的语义片段组织成语义簇；对语义簇使用f u r t h e s t a w a yr e p l a c e m e n t 算法，把语义簇分为两组，选择待淘汰的语义簇；当两个或多个语 义簇的查询绑定位置与当前客户机的查询绑定位置之间的语义距离相同时选择具有最 老时问戳的语义簇进行淘汰：在一个语义簇的内部，按照时间戳早晚选择要淘汰的语 义片段。 简化的运动轨迹模型用来预测移动客户机在足够短时阳j 段，后的运动状念，认为 在从当前时刻开始f 前后移动客户机运动方向及速率的改变与其在当l j l 时刻前f 的 后的改变相同，这样客户机在f 内在新方向上作匀加运运动。采用此模型比f u r t h e s t a w a yr e p l a c e m e n t 方法中使用当前时刻客户机的速度、在时阃段f 内作匀速运动来预 测客户机将来的位置更为精确。一j r 关键词：移动数据库；缓存替换策略：语义缓存；语义簇；运动轨迹模型 华中科技大学硕士学位论文 a b s t r a c t c a c h er e p l a c e m e n tp o l i c yb a s e do nm o b i l ec l i e n ti sak e yp a r t i ns e m a n t i cc a c h i n g r e s e a r c hf i e l d ，f o rt h a ti t sp e r f o r m a n c ed i r e c t l yd o e sag r e a td e a lt ot h ep e r f o r m a n c eo f c a c h e s t r u c t u r e b ya n a l y s i s o ft h e a d v a n t a g e s a n d d i s a d v a n t a g e s o fp r e s e n t t y p i c a l c a c h e r e p l a c e m e n tp o l i c i e s ，an e w c a c h er e p l a c e m e n tp o l i c yn a m e dc l u s t e r sf i r s ts e g m e n t sl a s t r e p l a c e m e n ta n d i t s a l g o r i t h m f o rl o c a t i o n d e p e n d e n ta p p l i c a t i o n s a r e d e s i g n e d a n d i m p l e m e n t e d b a s e do nm o b i l ed a t a b a s em a n a g e m e n ts y s t e mm d m 3 s e m a n t i cc l u s t e ri s i m p o r t e d f o rt h a t i ti sm o r ep r o p e rf o r a p p l i c a t i o n s i nm o b i l e c o m p u t i n ge n v i r o n m e n t ，i t ss t r u c t u r ea n dt h ew h o l ec a c h es t r u c t u r eb a s e do ni t a r eb r o u 【g h t f o r w a r d ，t h e nm e t h o d so fc l u s t e rg e n e r a t i n ga n dm e r g i n ga r eg i v e nt o o w h e nt h er e s u l to f a n e w q u e r yi sc o m i n g t a k i n gg r a n u l a r i t ya n d r e f e r e n c ef r e q u e n c yo fs e m a n t i cs e g m e n t si n t o a c c o u n t ，t h ep r i n c i p l e o fh o r i z o n t a ld i v i s i o nf i r s ta n dv e r t i c a ld i v i s i o nl a s ti su s e dt o d e c o m p o s et h es e g m e n t si n c u r r e n tc a c h ea n dt h ep r i n c i p l eo fr e m a i n i n gt h en e wc o m i n g r e s u l to fq u e r ya saw h o l ei su s e dt om e r g et h es e g m e n t sa f t e rd e c o m p o s i n g p r o c e s s i f t h e r e i sn os e g m e n tw h i c hi s s e m a n t i c a l l yr e l a t e dt o t h en e wc o m i n gq u e r yr e s u l t t h e nan e w s e m a n t i cc l u s t e ri sg e n e r a t e dw h i c ho n l yc o n t a i n sas e m a n t i cs e g m e n tw h i c hi st h ei n d e xor t h ed e wc o m i n gq u e r yr e s u l t a n di ft h e r ea r es o m es e m a n t i cc l u s t e r sw h i c hh a v es e v e r a l s e m a n t i c s e g m e n t s a r es e m a n t i c a l l yr e l a t e dt ot h en e wc o m i n gq u e r yr e s u l t t h e na f t e r p r o c e s so fd e c o m p o s i n ga n dm e r g i n g ，m e r g i n gt h ec l u s t e r s i n t ot h eo n eo ft h e mw h i c hh a s t h en e w e s t t i m e s t a m pa n dd e l e t i n gt h eo t h e r s c l u s t e r sf i r s t s e g m e n t sl a s tr e p l a c e m e n ta l g o r i t h me n a b l e st h e u s eo fad y n a m i c a l l y d e f i n e dv e r s i o no f s p a t i a ll o c a l i t yc a l l e ds e m a n t i cl o c a l i t yw h i c hd y n a m i c a l l ya d a p t st ot h e p a t t e r no fq u e r y a c c e s s t h i sp o l i c ya b s t r a c t st h em e t r i c so ft w ol e v e ll r u a l g o r i t h ma n d f u r t h e s ta w a yr e p l a c e m e n ta l g o r i t h m ，b u to v e r c o m e st h es h o r t c o m i n g so ft w ol e v e ll r u a l g o r i t h ma n df u r t h e s ta w a yr e p l a c e m e n ta l g o r i t h m i t si d e ai s ：f i r s t l y , i tm a k e sa l lt h e s e m a n t i c a l l yr e l a t e ds e m a n t i cs e g m e n t si n t o c l u s t e r su s i n gt h ec l u s t e rm e c h a n i s mo ft w o l e 、e ll r u a l g o r i t h m s e c o n d l y , u s i n gs e m a n t i cc l u s t e r s a sd i s p o s a lu n i t s m a k i n gu s eo f f u r t h e s t a w a yr e p l a c e m e n ta l g o r i t h m o ns e m a n t i cc l u s t e r s ，i t d i v e r g e st h e s e s e m a n t i c i i 华中科技大学硕士学位论文 c l u s t e r si n t ot w og r o u p sa n ds e l e c t st h ev i c t i m ( c l u s t e r ) f r o mt h e m w h e nt i e st h a tt w oo r m o r ec l u s t e r s s e m a n t i cd i s t a n c e sf o ri t s b i n d i n gp o s i t i o n t oc u r r e n t b i n d i n gp o s i t i o n o f m o b i l ec l i e n to c c t l r , i ts e l e c t st h ev i c t i mw h i c hh a st h eo l d e s tt i m e s t a m p i nac l u s t e r , e a c h s e m a n t i cs e g m e n ti sg e n e r a t e db yt h es e g m e n t s d e c o m p o s i n ga n dm e r g i n gb e f o r ei te m e r g e s a f t e rd e c i d i n gt h ec l u s t e rw h i c hh a st h es e g m e n t st ob er e p l a c e d ，i ts e l e c t st h es e m a n t i c s e g m e n t w h i c hh a st h eo l d e s t t i m e s t a m p a st h ev i c t i m s i m p l i f i e dm o v e m e n t t r a c km o d e li su s e dt of o r e c a s tt h em o v e m e n ts t a t u so fm o b i l ec l i e n t a f t e ri n t e r v a la t t h i sm o d e ld e e m st h a tt h ec h a n g eb e t w e e nt h em o v e m e n td i r e c t i o no f n o n c ea n dt h a to fi n t e r v a la tl a t e ri ss a m et ot h ec h a n g eb e t w e e nt h em o v e m e n td i r e c t i o n o fn o n c ea n dt h a to fi n t e r v a la tb e f o r ea n di ta l s od e e m st h a tt h ed i f f e r e n c eb e t w e e nt h e m o v e m e n ts p e e do fn o n c ea n dt h a to fi n t e r v a la tl a t e ri s e q u a lt ot h ed i f f e r e n c eb e t w e e n t h em o v e m e n t s p e e d o fn o n c ea n dt h a to fi n t e r v a la tb e f o r e t h e nm o b i l ec l i e n ta c c e l e r a t e s e q u a l l y i ni n t e r v a l a t u s i n gt h i s m o d e li sm o r ea c c u r a t et h a nu s i n gc u r r e n tm o v e m e n t d i r e c t i o na n dm o v e m e n ts p e e do fm o b i l ec l i e n ta n da s s u m i n gt h a tm o b i l ec l i e n tm o v e sa t e q u a ls p e e d i ni n t e r v a la ti nf u r t h e s ta w a y r e p l a c e m e n ta l g o r i t h m k e y w o r d s ：m o b i l ed a t a b a s e ；c a c h e r e p l a c e m e n tp o l i c y ；s e m a n t i cc a c h e ；s e m a n t i cc l u s t e r m o v e m e n tt r a c km o d e l - i i i 华中科技大学硕士学位论文 1 课题的来源、目的及意义 l绪论 移动计算( m o b i l ec o m p u t i n g ) 【1 j 系统是由固定结点和移动结点构成的分布计算系 统。在此系统中，客户不需要停留在固定的位置，可以携带着移动设备( 例如：计算 机) 自由移动，并在移动的同时通过移动通信网络保持与固定结点或其他移动结点的 连接。与基于固定网络的传统分布计算环境相比，移动计算环境具有移动性、频繁断 接性、网络条件的多样性、网络通信的不对称性等特点拉。】。移动计算的研究覆盖了移 动硬件设备、移动通信、移动联网技术、无线万维网访问、移动数据库技术和无线客 户服务器应用等研究领域。 与数据库技术密切相关的研究是移动数据库技术，即支持移动计算的分布式数据 库技术。传统分布式数据库技术方面大量的研究成果( 比如：分布式多媒体数据库管 理系统【6 】) 是移动数据库技术发展的基础。由于移动计算环境的新特点带来了许多新的 需求和应用，如：公共信息发布 7 】、移动办公1 8 l 、数字战场( 例如：美军的战场获知与 数据发布研究计划) 和位置相关查询等等，移动数据库技术已经成为国际数据库界一 个新兴的研究方向。 根据国家“通用信息处理平台”中的“国产数据库管理系统d m 2 适应性改造”分 系统以及国防预研项目“基于客户n 务器方式的分布式数据库管理系统( 项目编号： 1 5 4 1 ) ”的应用需求，在华中科技大学计算机学院青年基金移动对象的建模与查询 ( 项目编号：2 0 0 0 0 3 ) 的资助下，我们开展了移动数据库m d m 3 位置相关应用的缓存替 换策略研究，目的是使m d m 3 的移动客户端具有较高的缓存命中率，提高系统的整体 一瞄能， 12 国内外研究概况 移动数据库技术的研究领域相当广泛。要实现移动数据库系统必须解决移动计算 环境中断接性、移动性、通讯的不对称性等因素对数据库系统的影响，这决定了移动 数据库技术应包含移动事务处理、数据广播、数据复制缓存技术、移动查询等关键技 术。本文关注的是语义缓存技术研究的进展情况，但即使是局限于该领域，众多大学 和科研机构学术研究的起点、侧重点、范围及深度也不尽相同。 缓存技术根本的设计目的是在c a c h e 中可以存储那些访问频度较高的数据项，使 华中科技大学硕士学位论文 得系统能够减少输入输出次数以及降低客户端与服务器端的通信开销，以更快的速度 处理这些数据项，从而大幅提高系统的整体性能。这一机制的应用是基于程序执行过 程中对存储器访问的局部性这个基本事实。移动计算环境的特点决定了移动查询具有 对客户机位置的相关性和对存储器访问的局部性。 1 2 1语义缓存技术研究概况 语义缓存( s e m a n t i cc a c h i n g ) 技术已在集中式系统( c e n t r a l i z e ds y s t e m s ) f 9 ”j 、客户机 服务( c l i e n t s e r v e r ) - q ：境 1 1 , 1 2 】、移动计算旧1 4 】、在线分析处理( o n l i n ea n a l y t i c p r o c e s s i n g ) 系统【”1 、以及异种系统( h e t e r o g e n e o u ss y s t e m s ) 【1 6 】中广为运用。与传统缓存 技术缓存数据库的元组( t u p l e s ) 或页面( p a g e s ) 不同，语义缓存技术缓存查询的结果和查 询的语义描述信息，能够发掘蕴藏在查询谓词中的语义信息来组织查询结果，以达到 更有效管理客户机缓存的目的。语义缓存( s e m a n t i cc a c h e ) 是一些添加了相关语义描述 信息的数据项的一个集合，s h a u ld a r 等人称这些数据项为语义区1 ( s e m a n t i c r e g i o n s ) ，q u nr e n 等人则称之为语义片段【1 4 l ( s e m a n t i cs e g m e n t s ) 。李东等人把移动 纠算环境中的这种具有动态变化性以及时间和空间特性的语义缓存称为移动子集 ? 旧l ，它是具有时阍和空间描述能力的语义片段的集合。虽然逻辑上语义缓存被一个 使用拥有语义信息的索引来组织，语义缓存中每个被缓存数据项的物理存储信息也是 如此，但是存在若干不同的方法来物理存储这些数据项。s h a u ld a r 等人把元组组织成 语义区，以语义区形式存储；q u n r e n 等人则把语义片段组织到页面中，以页面形式存 储。上述各个系统或应用都是缓存查询结果而不是数据库元组或页面，它们的查询处 理策略非常相似：当来了一个新的查询时，查询分成两部分：一部分查询是从本地客 户枫缓存中能够直接或间接获得查询结果的那部分，称为试探查询( p r o b e q u e r y ) ：另 一部分查询是不能从本地客户机缓存中获得查询结果的那部分，称为剩余查询( r e m a i n q u e r y ) ，此部分需要发送到服务器端去处理。虽然与元组缓存一样，剩余查询的结果 被组织成页从服务器端返回给客户机，但是从服务器获得查询结果的机制是独立于索 引出现的。 1 2 2 缓存替换策略的研究概况 缓存替换策略是缓存技术的一个重要内容，它的优劣对缓存体系结构的性能有重 华中科技大学硕士学位论文 匕影响。传统的缓存替换方法有f i f o ( f i r s ti n f i r s to u t ) 眇2 ”、c l o c k 2 0 2 2 1 、g c l o c k ( g e n e r a t i z e dc l o c k ) 2 0 ，2 2 2 引、l r d ( l e a s tr e f e r e n c ed e n s i t y ) 吲、f b r ( f r e q u e n c e b a s e d r e p l a c e m e n t ) l z l 2 4 1 、l r u ( l e a s tr e c e n t l yu s e d ) 1 1 9 2 1 、l r u k 1 1 9 2 1 2 2 2 5 。、2 q ( t w oq u e u e ) i 0 2 2 1 和p b r ( p r i o r i t y b a s e dp e p l l a c e m e n t ) 2 2 , 2 6 l ，它们都是基于时态位霞( 即：最近被访 问的数据项很可能在不久的将来又被访问的特性) 的。随着语义缓存技术的出现，人 们认识到语义信息的重要作用，逐渐把它应用到缓存替换方法中，出现了基于时态位 置和空间位置( 即：与最近被访问的数据项在物理位置上接近的其他数据项很可能在 不久的将来又被访问的特性) 的m d f ( m a n h a t t a nd i s t a n c ef u n c t i o n ) 、d l r u ( d y n a m i cl r u ) c ”i 、f a r ( f u r t h e s ta w a yr e p l a c e m e n t ) 2 s l 和t l l ( t w ol e v e ll r u ) 1 4 1 等算 法。但是，目前在具体商业系统中没有看到相关的报道。 lf i f o 算法 f i f o 算法直接选择最早进入系统的数据项进行淘汰。该算法认为最早进入系统的 数据项在以后不再使用的可能性比后进入系统的数据项不再被使用的可能性要大。也 就是i 兑，进入系统的数据项是按照时间顺序逐一被访问地，数据项被访问的频度相同 并且在将来不再被访问。如此，数据项的访问局部性特性就不复存在或没有意义了。 2 c l o c k g c l o c k 算法 在c l o c k 算法中，将所有数据项( 在本算法中指页面) 通过一个循环链表相关联， 每个数据项和一个比特位( b h ) 相关联，用它来指示在最近一次选择指针的循坏中该 数据项是否被引用过。当需要替换数据项时，选择当前指针指向的数据项，如果与该 数据项相关的比特位为l 则将它置0 ，指针前进指向下一个数据项。第一个被找到的、 比特位为0 的数据项将会被替换。c l o c k 算法实质上是对l r u 算法的模拟，它们有着 相似的缓存命中率驯。 在g c l o c k 算法中每个数据项和一个计数器相关联，当数据项第次放入缓存时， 与之相关联的计数器被置于一个初始的权值，这个值可能随着数据项类型的不同而不 同。当数据项被引用时，计数器增加或重置。当需要替换数据项时，c l o c k 指针循环地 扫描链上的数据项，同时减少相关联计数器的计数值，直到找到一个计数值为0 的计 数器，与这个计数器相关联的数据项被作为替换项。当选择恰当的权值时，g c l o c k 算 法的性能比c l o c k 算法要好一些【2 3 1 。 3l r d 算法 华中科技大学硕士学位论文 l r d 算法来源于g c l o c k 算法，它使用了如下三个变量： 1 r c ( i ) ：表示数据项i 自从存入缓存后，被引用的次数； 2 g r c ：表示一个全局引用计数器，任何数据项的一次引用都使其计数值增大一； 3 f c ( i ) ：当数据项i 存入缓存时计数器g r c 的计数值。 每个数据项i 的引用密度( r e f e r e n c ed e n s i t y ) r d ( i ) 满足： 尼d f f l ： 墨g ! 塑 。 、 g r c f c ( i ) 当要淘汰数据项时，选择具有最小r d ( i ) 的数据项淘汰。为了避免出现两个或多个 数据项具有相同引用密度的情况，与每个数据项相关联计数器的计数值将在一定时f b j 间隔后被减少。l r d 方法比l r u 、c l o c k 和g c i o c k 方法要优越【2 0 1 。 4f b r 算法 f b r 算法的思想是：在一个较短时间内重复引用的数据项将获得一个较商的替换 值，由于淘汰数据项时首先替换具有最低替换值的数据项，因此缓存中在较短时m 内 反复被引用的数据项将保存更为长久。 f b r 的基础是l r u 算法，数据项被逻辑地组织成栈的形式，最近引用的数据项在 栈的顶部，最近最少引用的数据项位于栈的底端，最近最多引用的数据项在栈的顶端。 该栈被分为新区、中区、老区三个部分。新区是在栈最上面的部分，如果新区中数据 项被引用则它的引用计数不增加，因此短时间内反复被引用数据项的引用计数在这段 h t f j j 内保持不变。栈的底部是老区，需要替换数据时，老区中引用计数最少的数据项 将被替换。栈底中间是中区，中区中数据项的引用计数正常增加。当经过一个设定的 州脚段后，中区的数据项移到老区，新区的数据项移到中区，这样有效的解决了l f u l e a s tf r e q u e n t l yu s e d ) 算法可能导致的“c a c h e 污染 2 9 - 3 1 】”。 5 l r u l r u k 算法 l r u 算法假设将来的行为是现在行为的延伸，认为最近使用过的数据项在将来被 访问的概率较大，并且数据项最近一次被访问的时刻离现在越远，它今后被访问的可 能性也越小，越适宜被替换。 虽然l r u 算法在各种软件系统中被广泛应用，但是l r u 算法在做出替换决定时 利用的信息很少。比如，l r u 算法不能区分有较多引用计数的数据项和有较少引用计 数的数据项。数据项一旦被放入缓存中，l r u 算法就会给它一个很长的生命期，而不 4 - 华中科技大学硕士学位论文 管该数据项是否在将来不再被引用，这使得l r u 算法不能很好地适应可能存在大量随 机俘取的移动计算环境。 l r u k 算法解决了这一个问题。它利用更多的历史存取记录来做出替换决定，其 基本思想是：记录前k 次数据项的引用时刻，过去第k 次引用时刻距现在最远的数据 项将被替换。l r u k 算法能够有效隔离短期频繁访问然后不再使用的数据项的干扰， 对于容量较小的移动缓存系统有较大作用。虽然l r u ，k 比l r u 更有效，但是它需要 更多的处理开销，并且每个记录需要k 个存储时刻的空间。 6 2 q 算法 2 q 算法跟l r u 2 算法有一些类似，不过只有常数级的处理开销。2 q 算法将缓存 区组织成三个队列，a m 、a l i n 、a l o u t ，其中，a m 是一个l r u 队列，而a l i n 和a l o u t 队列都是f i f o 队列。当数据项第一次被引用时，它进入a 1 i n 队列中，去除短期行为。 如果a l i n 队列长度超过一定闽值，则在a l i n 首部的数据项进入a l o u t 队列。a l o u t 队刊中的数据项被认为是在将来不会再被引用，如果a 1 0 u t 中的数据项被引用则转入 a m 队列尾部，作为热点数据。 当需要替换数据项时，首先检测a l o u t 中的数据项，如果a l o u t 队列长度超过某 个阂值则淘汰a l o u t 队列头部的数据项。否则，从a m 队列头部开始淘汰数据项。 7 p b r 算法 与前面介绍的几种算法不同，p b r 算法利用了事务或者数据库结构的概念来给不 同的数据项分配优先级。该算法根据数据项的用途，将它们分为多个优先级，然后对 具有最低优先级的数据项集合采用l r u 等等通用替换算法选择淘汰项。例如： p r i o r i t y 。l r u 方法和p r i o r i t y d b m i n 方法【2 6 1 对具有最低优先缴的数据项使用l r u 方法 来淘汰数据项。 这类算法中，数据的优先级只能根据具体的应用来确定。该算法的处理器代价很 小，如果在移动缓存系统中应用得当也能产生较高的命中率，但是这种方式使得缓存 系统不能独立于具体的应用。 8m d f 算法 m d f 使用一个距离值函数为缓存中每个可能的替换单元( 本算法中是语义区) 分 配一个替换值，由这个值来选择淘汰项。在这个算法中，替换值是基于语义缓存当前 使黾的情况的。m d f 为每一个从客户机提交查询的结果在缓存中对应的语义区关联一 s 华中科技大学硕士学位论文 个值，这个值就是m a n h a t t a nd i s t a n c e 的相反数。m a n h a t t a nd i s t a n c e 是当前缓存中语义 片段语义区的几何重心到达当前最后一次被访问的语义片段语义区的几何重心之旧j 的 距离值。当要淘汰一个数据项时，选择具有最小替换值的数据项进行淘汰。 9 d l r u 算法 dl r u 算法是对l r u 方法的改进。当缓存中没有足够的缓存空间放置新的数据 项时，首先丢弃因位置改变而使数据失效的语义片段，如果存在多个因位置而失效的 语义片段，再按语义片段的时间标志早晚次序进行淘汰，直至缓存空间够用。若淘汰 完因位置变化而失效的语义片段后，缓存空间仍然不够，此时依次淘汰虽然位置变化 仍然有效语义片段中具有最“老”时间标志的语义片段直至满足缓存空间需求。 在本算法中，语义片段的使用频率越低，它的时间标志就越陈旧，从而将在以后 被优先替换。 1 0 f a r 算法 f a r 利用移动客户机的移动特性，用语义片段绑定位置之间的距离作为替换值， 对m d f 算法中计算m a n h a t t a nd i s t a n c e 替换值这一复杂的方法进行了改进，使得替换 值的计算更容易。通过简单的预测客户机的运动方向，把缓存中的语义片段分成两组： 在客户机运动方向上的分为一类，记为i n d i r e c t i o n ：不在客户仉运动方向上的分为一类， 址为o u t d i r e c t i o n 。当缓存空间不足时，先从o u t d i r e c t i o n 中淘汰查询绑定位置与当前 奁询绑定位置之间距离最大的语义片段，直到o u t d i r e c t i o n 为空。如果此时缓存空间仍 然不能满足需要，那么从i n d i r e c t i o n 中选择查询绑定位置与当前查询绑定位置之i h j e 离最大的语义片段进行淘汰，直到i n d i r e c t i o n 为空。 l lt l l 算法 7 f l l 足在l r u k 方法的基础上改进而来。它把当前缓存中的语义片段组织成一个 个的簇( c l u s t e r ) ，在簇内部按照各个语义片段最后被访问时间戳的早晚顺序构成一个 链表，每个语义片段属于且仅属于一个簇，每个簇具有最后一次被访问的时阳j 戳标记。 根据新到来的语义片段与当前各个簇中语义片段的语义关系，对之进行簇的分配。当 需要淘汰语义片段时，首先选择具有最“老”时间戳标记的簇作为待淘汰项，这是第 一级。然后从该簇中依次选取具有最“老”时间戳标记的语义片段进行淘汰，这是第 二级。如果此时的缓存空间仍然不能满足需要，那么，重复上述操作。如果该簇不再 含有任何语义片段，此簇不再存在，那么再找出当前具有最“老”时间戳标记的簇迸 华中科技大学硕士学位论文 f 亍淘汰。 此外，在上述这些方法的基础上添加或综合若干其他的替换标准，人们提出了各 种适合于特定系统环境的替换方法。e s c h e u e r m a n n 等人【3 2 1 在数据仓库系统中实现了智 能缓存：查询检索得到的集合被缓存起来，从平均引用率、大小以及与相关查询的执 行代价三方面考虑替换项的选择。此相似，a r t h u rm k e l l e r 等人b 2 1 为语义缓存开发了 一个基于效益的替换方案。p r a s e dm d e s h p a n d e 等人提出的语义缓存作用在块 t c h u n k ) 级，该系统使用基于效益的c l o c k 策略，效益度量标准主要涉及从一个块到 另一个块变化的执行代价。b y c h a n 等人【3 3 1 根据考察数据库历史预示的访问概搴来选 择被替换项。 1 3 本文的研究内容 本文的主要研究内容是研究、设计一种适合于移动客户端位置相关应用的缓存替 换策略及缓存替换算法，并在m d m 3 原型系统上实现之。 我们的研究思路是： 1 从m d m 3 的体系结构入手，围绕客户机的移动特性，研究m d m 3 客户机端 d b m sl i t e 及虚拟服务器中位置代理的结构与功能，结合移动查询的特征，分析比较 当前典型的缓存替换策略，得出m d m 3 缓存替换策略方案。 2 根据m d m 3 缓存替换方案，提出相关缓存结构的定义及构造方法，分析研究 在这些结构下的移动查询的处理过程和语义片段的处理方法以及相关缓存结构的处理 方法。研究一般的移动性模型，提出一种简化的运动轨迹模型，用来预测客户机在不 久将来的运动状态。在此基础上，详细描述m d m 3 的缓存替换思想及其算法。 3 对m d m 3 缓存替换策略的实现作详尽地阐述。从m d m 3 缓存替换总体流程入 手，依次给出实现该策略所必须的语义片段、客户机的历史状态等等相关的数据结构， 并对涉及这些数据结构的一些处理方法的实现给出详细的说明。在此基础之上，详细 阐述m d m 3 缓存替换算法的实现细节。 华中科技大学硕士学位论文 = = = = = = ；= = = = ；口= = ；= = = = = = = = = ；= ；= = = = 一 2 移动数据库系统缓存替换方案研究 本章从m d m 3 的体系结构入手，围绕客户机的移动特性，研究m d m 3 客户机端 d b m sl i t e 及虚拟服务器中位置代理的结构与功能，结合移动奁询的位置相关性和访问 局部性特征，分析比较当前典型的十一类缓存替换策略，得出m d m 3 缓存替换策略方 案。 2 1 系统结构 d m 3 是我们自主研制的主动型、分布式多媒体数据库管理系统d m 2 1 3 4 的升级版 本，它以成熟的关系数据库理论为基础，采用层次一关系模型，吸收面向对象的思想， 集先进的分布式处理技术、主动数据库技术、多媒体技术、多线索技术于一体。随着 移动计算的广泛应用，研制基于d m 3 的移动数据库系统具有十分重要的意义。为了使 之支持移动数据库的管理，我们在此基础上进行了扩展，把传统的c l i e n t s e r v e r 两层结 构改造成m o b i l ec l i e n t a g e n t s e r v e r 三层结构，中间层是虚拟服务器，它是具有各种功 能的代理( a g e m ) 的集合，包括：缓存代理、事务代理、位置代理和移动查询代理等 等。经改造后的移动数据库系统m d m 3 系统结构 1 7 , 3 5 , 3 6 1 如图2 1 所示。 固定网络 图2 1m d m 3 系统结构 其中：l d b m s ( l o e a ld b m s ) i 表示第i 个场地的数据库管理系统，电称为该场地 的中央服务器，它提供基本的数据库管理系统功能：a g e n ti 表示第i 个场地的虚拟服 务器，它的内部结构如图2 2 所示；m u ( m o b i l eu n i t ) 表示移动用户。 在移动数据库系统环境众多特点中，最为重要的是移动性。为了支持客户机的移 动，必须跟踪客户机的位置状态，以便让相应的服务器为客户机提供服务，这一 功能由位置代理来完成。图2 3 描述了位置代理的基本组成 2 4 1 ，图中虚线表示无线 连接，实线表示固定连接。 华中科技大学硕士学位论文 f 之冀。t 理是服务于二一个小区中客户机的局部管理系统，它拥有本地数爿 唪系统， ；圩 jj d f 蔓f 该小区中昕育移动设备的信息，包括宿兰地址( h o m e a d d r e s s 、i 恒i 理 懂拟眼毋器 位置代理 数据缓存代理 f移动事务代理 移动奁询代理 负钱平，嘶 蝙障处理 路出营理 图2 ，2 盘拟服务器系统结坛j 地址( h o m ea g e n ta d d r e s s ) 、通信能力，对网络暇务质量( q o s ) 的要求等。世胃代埋能 t ：客尸 几发出请求任务后，代表它完成剩余的操f 乍。它既能有效地支持客户日l 的断谩 按| 仨工能大幅减少中央数据库的负载，实现客j 。 几f 立雷管理的本地化，堤尚系统投 毒：、位置代理主要包括如图2 3 所示的：六个功能部件，与本丈密切相关 一 曾- 一一 i 针谜译卿 t 理簧全霄理 牟。h 【侈动暖式： ：羽 血胃代理 央玻掘“ 图2 3 够动客“h l 伊置葺埋系统结构 的是移动历史单元r u ( r e c o r d u n i t ) 。r l 7 用来z 录客户# l i 生过去一段时削内曾经丝翌的 b 域、状态信息以及在这段时间内有哪些代理访问了客户机i 及其波访问的；欠敷，川日j 段f j 选取可以因不同代理而不同。从r u 记录的客户机历兜状态中我们能够捩 导筹6 l 在桀时刻所在的位置、运动状态等信息。 目j 户在移动过程中，查洵的结果往往与位置是帽关的。也就是说，对个聋：台j 的 p - 答4 i 仅依据数据库的内容而且要袄据查询发生的位置( 它是时间的函数) 。为了有 效地支持客户机的移动( 本文中我们：肾移动通信设备、移动计算机等统称为移动霹户 j l 、必须提供相应功能的客户机端d b m s 。考虑到移动客户机资源的相对肓限，同时 慕 华中科技大学硕士学位论文 父要保证客户机具有足够的自治性，我们在d m 3 基础上进行了剪裁和扩充：保留本地 事务管理和数据操纵相关的功能，包括数据操纵、查询处理、记录管理、并发控制和 志及恢复管理；为了支持客户机的断接操作，我们重新设计缓存区管理模块，增加 断接管理、收集管理和重集成管理三个模块。m d m 3l i t e 系统结构如图2 4 所示。 图2 4 客户端d b m sl i t e 系统结构示意图 2 2 移动查询的两个特点 c a c h e 技术p 1 的实现是基于程序执行过程中对存储器访问的局部性这个基本事实， 它体现了一种层次存储思想【3 8 ，3 9 】。存放在存储器层次结陶中的信息满足三个重要特性： 包含性( i n c l u s i o n ) 、一致性( c o h e r e n c e ) 和局部性( l o c a l i t y ) ，与本文密切相关的是 局部性。访问的局部性是指c p u 对指令或数据的存取在时间、空间和次序上往往部集 中在一定范围内进行的特性。时间局部性是指最近的访问内容很可能在不久的将来再 次被访问；空间局部性则表示一种趋势，指的是一个进程访问的各个程序或数据项的 地址彼此相隔很近；顺序局部性则是指在典型程序中除非转移指令产生不按照次序 华中科技大学硕士学位论文 执行的转移外，指令都往往都集中在一定的范围内进行的特性。正是由于访问局部性 的存在，在c a c h e 中可以存储郧些访问频度较高的数据项，使得系统能够以更快的速 度处理这些数据，从而大幅提高系统的整体性能，这正是c a c h e 机制的最根本的设计 j 的。 移动计算环境的特点决定了移动查询 4 0 j 具有位置相关性和访问局部性。 1 位置相关性 先来看这样个例子。 铡2 1 假设你开车在一个陌生的城市里旅行，此时天色已晚，你想找一个最近的 汽车旅馆休息。个典型的查询请求是：“请显示我所在位置五公里范围内的所有汽车 旅馆信息”。如果没有符合你要求的旅馆，那么你一边开车一边提交同样的查询，不断 的接收返回的旅馆信息，直到找到一家满意的旅馆为止。 例2 1 中的查询条件中利用了查询用户所在的位置，查询的结果随着用户位置的不 同而变化。在本文中这种与移动用户位置相关的查询我们称为位置相关查询，它具有 位置相关性。位置相关查询的结果直接或间接的依赖于移动用户的位置。虽然传统数 据唪系统通过复杂的变换也能够处理这种查询，但是传统的系统没有考虑客户的移动 特性，所以当大量的位置相关查询的需求出现时，传统数据库系统不能或不能很好地 满足这种需求【