（计算机软件与理论专业论文）无线网络cache写策略及其替换算法研究.pdf

无线网络c a c h e 写策略及其替换算法研究 计算机软件与理论 硕士生：余士元 指导老师：林小拉教授 摘要 客户端数据缓存技术是解决无线网络数据访问效率的一项重要技术，它通过 减少无线网络的通信量，降低数据访问延迟，很好的解决了无线网络的效率问题。 过去的相关研究都集中在数据从服务器到客户端的分发，而很少考虑客户端对数 据的写操作对整个缓存管理效率的影响。 本文首先在传统的c a c h e 写策略的基础上，加上对无线网络特殊性的考虑， 提出一种新的改进写回法( i m p r o v e dw r i t eb a c k ) ，在保证网络数据一致性的基 础上，尽量的减少客户端的上传通信量和延迟，同时保证c a c h e 的高效性。 然后针对改进写回法，提出一种基于朋i n n 数的r w u s 替换算法。这一算法 综合考虑了每个数据项的读频率、写频率、服务器端更新频率、数据项大小、是 否为脏数据项等因素的影响，来决定在可用空间不够时移出c a c h e 的数据项。并 且提出上述所需的各个参数的估算方法。 最后通过模拟实验，对比研究了写直达法、改进写回法与r w u s 算法、l r u 算法之间的四种组合在访闯延迟和上传通信量两个方面的表现，并检验结果对 c a c h e 大小、上传带宽、写操作比率、数据更新频率、数据访问密集度等主要参 数变动的敏感程度。实验结果表明，本文提出的改进写回法( i 、v b ) 在访问延迟 和上传通信量两个方面的表现都明显优于写直达法( 、】v t ) ，而本文针对改进写回 法提出的r w u s 替换算法更是明显优于l r u 替换算法，更好的发挥了改进写回法 的优势。 关键词：写策略，替换算法，无线网缓存 a ne f f i c i e n tc a c h ew r i t es t r a t e g ya n di t s r e p l a c e m e n tp o l i c yf o rw i r e l e s se n v i r o n m e n t c o m p u t e rs o f a r ea n dt h e o r y n a m e ：y us h i y u a n s u p e r v i s o r ：l i nx i a o l a a b s t r a c t d a t ac a c h i n ga tm o b i l ec l i e n t s ，w h i c hr e d u c e st h ea c c e s sl a t e n c ya n dt h e a m o u n to ft r a f f i co v e rt h ew i r e l e s sc o m m u n i c a t i o nc h a n n e l ，i sa ni m p o r t a n t t e c h n i q u ef o ri m p r o v i n gt h ep e r f o r m a n c eo fw i r e l e s sd a t aa c c e s s i n g m o s to f t h ep r e v i o u ss t u d i e sf o c u s e do nd a t ad i s s e m i n a t i o nf r o ms e r v e rt oc l i e n t s ，w i t h l i t t l er e s e a r c ho nt h ew r i t es t r a t e g yo ft h ed i e n t sa n di t se f f e c t so nt h ec a c h e s y s t e m i nt h i st h e s i s ，an e ww r i t es t r a t e g y ，c a l l e di m p r o v e d - w r i t e - b a c k ( i 、b ) ，i s p r o p o s e db a s e do nt h et y p i c a lc a c h ew r i t es t r a t e g i e sa n dt h es p e c i a l c h a r a c t e r i s t i c so fw i r e l e s se n v i r o n m e n t s i nt h ep r o p o s e ds t r a t e g y ，u p l i n k t r a f f i ca n da c c e s sl a t e n c yw i l lb er e d u c e da sm u c ha sp o s s i b l eu n d e rc a c h e c o n s i s t e n c y a g a i n - b a s e dc a c h er e p l a c e m e n tp o l i c y ，r w u s ，i sa l s op r o p o s e dt o f u r t h e ri m p r o v et h ep e r f o r m a n c eo ft h ec a c h em a n a g e m e n te f f i c i e n c yu n d e r i w b r w u sc o n s i d e r ss e v e r a lf a c t o r st h a ta f f e c tc a c h ep e r f o r m a n c ew h e n t a k i n ga c c o u n to fc l i e n t s w r i t i n ga c c e s s ，n a m e l y ，r e a d i n gp r o b a b i l i t y ，w r i t i n g f r e q u e n c y 。u p d a t ef r e q u e n c y ，d a t as i z e ，a n dw r i t t e nf l a g i na d d i t i o n ，a n e x p o n e n t i a la 9 i n 9m e t h o di su s e dt oe s t i m a t et h ev a l u e sf o rt h e s ep a r a m e t e r s f i n a l l y ，as e r i e so fs i m u l a t i o ne x p e r i m e n t s a r ec o n d u c t e dt ot h o r o u g h l y e v a l u a t et h ep e r f o r m a n c eo fi w ba n dr w u su n d e rd i f f e r e n tc a c h es i z e s ， u p l i n kb a n d w i d t h s ，w r i t i n gr a t i o s ，u p d a t ef r e q u e n c i e s , a n dd a t aa c c e s s i t s k e w n e s s t h es i m u l a t i o nr e s u l t ss h o wt h a t ，w i t ht h ep e r f o r m a n c em e t r i c so f a c c e s sl a t e n c ya n du p l i n kt r a f f i c ，t h ei w bw r i t es t r a t e g yi si n c o m p a r a b l y s u p e n o r t ot h ew r i t e 。t h r o u g hs t r a t e g y ，a n dt h er w u s r e p l a c e m e n tp o l i c y s u b s t a n t i a l l yo u t p e r f o r m st h el r uu n d e ri w b k e yw o r d s ：w r i t es t r a t e g y ，r e p l a c e m e n tp o l i c y ，w i r e l e s sc a c h e 1 1 1 1 1 研究介绍 第1 章序言 随着移动设备、无线应甩标准、无线高速网络以及相关软件技术的快速发展， 无线网络的商业应用变得越来越普遍。但是，无线网络自身诸如带宽、有限的用 户资源等等的限制大大制约了无线网络的完全应用。而客户端数据缓存技术 ( c a c h e ) 通过减少无线网络的通信量，降低数据访问延迟，很好的解决了无线 网络的效率问题。 由于无线网络的特殊性，就导致了无线网络环境下的缓存技术具有与普通的 操作系统或数据库环境下的缓存技术不同的特点【l 】，【2 】： 1 缓存数据大小不一致； 2 不同的数据对象会由于广播机制的不同而检索延迟差异较大； 3 数据可能在服务器端不断的被更新： 4 无线网络的带宽限制； 5 客户端的电池能量的有限性； 所有这些特点都导致了无线网络下的缓存技术更加难以设计和管理。在设计 无线网络的c a c h e 管理机制的过程中，一般有三方面的问题需要考虑： 1 缓存替换算法：当一个新的数据项需要缓存而缓存空问不够时，怎么决定 哪些已缓存数据项需要从缓存删除或移出。因为数据项大小不一致、 不同数据项失效的损失不一样，所以命中率将不能成为评价缓存效果 的依据。而且在考虑替换策略时，传统的l r u 等替换算法不能取得较 好的效果，要综合考虑上面各种因素的影响。 2 缓存预存取机制：将那些未来可能会处理的数据项从服务器端预先下载到 缓存中以便等待处理。因为无线网络带宽的有限性，以及上面各种因 素的影响，所以预存取也就更加复杂。 3 缓存一致性策略：当某些数据项需要更新时，用于保持缓存的数据项在服 务器端和客户端缓存之间的一致性。因为数据项可能在服务器端不断 的被更新，所以这个机制的有效性就显得特别重要。 在过去的研究中，无线网络缓存的一致性问题已经有大量的研究，而关于缓 存的替换和预存取策略则相对受到比较少的关注。但是由于移动用户的缓存资源 有限，后两者的研究对于无线网络效率的提高有着更显著的效果和更实用的意 义。 1 2 研究目的 过去对于无线网络缓存技术的相关研究很好的结合了无线网络数据项大小 不一致，数据可能在服务器端不断的被更新，无线网络的带宽限制，客户端的电 池能量的有限性等等特点，提出了各种适用于无线网络环境的c a c h e - - 致性策略 和替换算法。 但是过去的相关研究都集中在数据从服务器到客户端的分发，而不考虑客户 端对服务器数据的写操作。随着无线网络应用的发展，数据在服务器和客户端之 间的互动越来越多，客户端对数据的写操作也不断增多。虽然传统的缓存替换算 法并不考虑写操作的影响，也不针对写操作做特别的优化，但是在无线网络的特 殊环境中，我们却不得不面对这个问题。 首先，无线网络的带宽非常有限，而上传带宽远远小于广播带宽，所以写操 作将引起更大的操作和传输延迟。其次，无线网络中客户端的电池能量非常有限， 而上传操作相对接收操作将耗费客户端更多的电池能量，所以写策略必须能保证 相对少的上传通信量。 所以写操作在无线网络中的丌销和影响将比在传统环境大得多，使得在设计 无线网络环境的缓存算法时不得不考虑缓存写回服务器时所占用的上传带宽、数 据项的写频率等问题。 本文将通过在保证数据一致性的基础上，改进传统的写策略，使其适用于无 线网络环境。同时通过对写策略本身的改进和相应c a c h e 替换算法的设计，尽量 的提高c a c h e 管理在写操作条件下的效率，并尽量减少客户端的上传通信量，节 约客户端电池能量。 1 3 本文创新点 过去对于缓存的替换算法的相关研究都集中在数据从服务器到客户端的分 发，假设客户端对服务器端的数据只有读操作，对数据的更新操作只发生在服务 器端。而本文最大的创新点则是通过放开这一假设，考虑客户端对服务器端数据 的写操作对整体c a c h e 管理效率的影响，并透过对写策略和c a c h e 替换算法进行有 针对性的改进和设计提高c a c h e 效率。 本文首先在传统的c a c h e 写策略的基础上，加上对无线网络特殊性的考虑， 提出一种新的改进写回法( i m p r o v e dw r i t eb a c k , i w b ) ，在保证网络数据一致性 的基础上，尽量的减少客户端的上传通信量，同时保证c a c h e 的高效性。 然后再在前人研究的基础上，针对提出的改进写回法，提出一种基于舻加函 数的新的c a c h e 替换算法r 、矾，s 算法。在这一算法中，综合考虑了每个数据 项的读频率、写频率、服务器端更新频率、数据项大小等因素的影响，来决定在 可用空间不够时移出c a c h e 的数据项。通过i w b 写策略和r w u s 替换算法的配合， 最大程度的减少了客户端写操作可能引发的上传通信量和上传瓶颈带来的客户 端数据操作的访问延迟。 最后提出所需的各个参数的估算方法，通过模拟实验结果比较评价改进写回 法和写直达法，以及r w u s 算法与传统的最近最少使用法之问的性能差别，并检 验结果对各个主要参数变动的敏感程度。 1 4 文章结构 本文共分为六章，第1 章为序言，介绍研究的目的和创新点。 第2 章主要介绍无线网络c a c h e 研究必要的背景知识和研究现状。 第3 章提出本文的主要研究内容和观点。其中3 1 提出一种基于无线网络的改 进写回法( i w b ) ；3 2 探讨在考虑写操作情况下的c a c h e 替换算法的设计原则； 3 3 提出本文最主要的设计r w u s 替换算法；3 4 提t b g w u s 算法所需参数的 3 估算和维护方法。 第4 章提出本文模拟实验的模型，包括模型的基本假设、客户端和服务器端 模型和算法对比组的设计以及评价指标的选取。 第5 章在第4 章提出的模拟模型上进行实验，主要验证改进写回法、r w u s 算 法相对传统的写直达法、l r u 算法的优越性，以及检验结果对各个关键参数的敏 感性。 第6 章总结本文的研究结果并作研究展望。 4 第2 章无线网c a c h e 介绍及相关研究 2 1 无线网c a c h e 背景介绍 2 1 1 无线网络介绍 图2 1 显示了一般的无线网络结构。它一般包括一个固定的主干网，主干网 上连接着两类节点：移动基站和固定终端。移动基站配备有收发器能支持一个单 元网( c e l l ) 范围内的移动单元( m u ) 的通信工作。在一个单元网内，存在两 种最基本的通信通道：从m u 到m s s 的上传信道( u p l i n k ) ，和从m s s 到m u 的广播信道( b r o a d c a s t l i n k ) 。客户端在进行上传通信时要花费比下载通信多得多 的电池能量，所以在通信时应该尽量避免进行上传操作。 ，、 m 6 - j 、 j2 m b l ，。一， 7 0 m u , oj 、：曼0 图2 - l 无线网络结构图 在一个单元网内，m s s 和m u 的连接方式最普遍的是服务器客户端方式。 两者之间有两种最基本的数据传输方式： p u s h - b a s e d 模式：数据从服务器端通过广播信道定期的客户端进行多播。客 户端接受和处理数据不需用到上传信道，只需要通过监听广播信道，并对接收到 的数据流进行过滤获得自己需要的数据即可。 o n d e m a n d 模式：客户端通过上传信道向服务器发送对具体数据的请求，服 务器端对请求进行响应，将数据通过广播信道发送给客户端。 实际上，p u s h b a s e d 模式可以看作是特殊的o n - d e m a n d 模式，当上传成本为 0 而数据在整体存取的模式上进行调度。 2 1 2o n d e m a n d 模式c a c h e 管理机制 本文接下来的研究主要针对o n d e m a n d 模式，所以下面进一步介绍一下 o n - d e m a n d 模式的体系结构和c a c h e 管理机制。 服务器 幽2 - 2o n - d e m a n d 模式单元网体系结构幽 图2 - 2 是一个o n - d e m a n d 模式的单元网体系结构图，如图所示，客户端通过 上传信道向服务器发送对具体数据的请求，服务器端对请求进行响应，基于一定 的调度算法安排对各个请求的响应顺序，然后将数据通过广播信道发送给客户 6 端。而客户端则通过监听广播信道来过滤获得他们需要的数据。 如图2 - 2 所示，客户端会有一个缓存管理机制。当客户端的应用程序需要访 问数据时，本地缓存管理器首先检查所求数据是否已缓存。如果命中缓存，则缓 存管理器需要进一步检查当地缓存中的数据是否和服务器上的数据一致。如果经 过检查证明数据是和服务器上的最新数据一致的，则返回数据给应用程序。如果 缓存命中但是数据不一致，或者缓存不命中，缓存管理器将通过上传信道向服务 器发送数据请求。当请求的数据通过广播到达，缓存管理器将其返回给应用程序， 同时在本地缓存的保存备份。如果此时本地缓存的可用空间不够，将要根据一定 的缓存替换策略决定哪些已缓存数据项需要从缓存删除或移出。 在检查数据的一致性时，现在一般采用的是失效报告技术( i n v a l i d a t i o n r e p o r t ， i r ) 【3 】，【4 】，【5 】。失效报告是穿插在广播数据中定期在广播信道进行广播的，相 对于其它数据，失效报告具有最高的广播优先性。一个失效报告中一般包括最近 w 个广播间隔服务器的更新纪录( w 可以是常数也可以是变量) 。每个客户端都 保留有最后一次做有效性检查的时间戳t l ，每当从广播信道中接收到来自服务器 的失效报告，客户端都会检查t l 是否在失效报告的覆盖范围之内。如果是，则 根据该失效报告进行一致性检查；如果不是，则使整个c a c h e 失效( 在w 为常 数的情况下【3 】，【4 p ，或者忽视该失效报告，并向服务器传递t l 以便下个失效报 告能覆盖t j ( 在w 为变量的情况下【5 】) 。 2 1 3 服务器端数据调度算法 一般来说，c a c h e 技术能有效的减少访阿等待时间、提高数据可用性。同时 因为它能减少客户端对服务器的数据访问请求进而改变客户端的访阀形势，所以 又会对服务器的广播调度产生很大的影响。而反过来c a c h e 策略又会受到广播调 度算法的影响，因为对于一样的数据请求，不同的调度算法可能会带来不一样的 数据检索延迟。所以在设计c a c h e 管理机制的时候不得不考虑广播调度算法的影 响。 对于o l 卜d 锄l l d 广播束说，广播调度算法对于系统的性能就表现的更为重 要。一个好的广播调度算法要能平衡个体和整体的表现，同时应该能适应不同的 数据集大小、客户端数量、广播带宽等等。在过去的研究中，很多有效的 o n - d e m a n d 广播调度算法已经被提出，像最长等待优先( l w f ) 【6 】，r x w 7 ， 最小服务时问优先( s s t f ) 【8 ，最大整体s t r e t c h 值优先( l t s f ) 【9 等。下面 我们将逐一作简略的介绍： 先到先服务【6 】( f i r s t c o m e f i r s t s e r v e d ，f c f s ) ：按照请求到达的顺序安排相 应数据项的广播次序。在点对点的情况下，这种方法能降低最大访问延迟。但是 在广播网络的情况下表现不佳。 最长等待优先【6 】( l o n g e s tw a i tf i r s t ，l w f ) ：数据项的总等待时间越长将越 早被广播。其中总等待时间指所有要求该数据项的等待请求的等待时间总和。此 算法的缺点是复杂性随着规模的扩大而增大，实施代价高。为了克服这个缺点， 相关研究提出了一些改进算法( 如r x w 7 1 ) ，减, b t 复杂性，但是相应的降低了 边际有效性。 最d , n 务时间优先 8 】( s h o r t e s ts e r v i c et i m ef i r s t ，s s t f ) ：数据项的服务时 间越小，被广播的优先性就越高。 最大整体s t r e t c h 值优先【9 】( l o n g e s tt o t a ls t r e t c hf i r s t ，l t s f ) ：具有最大整 体当前s t r e t c h 值的数据项将最优先被广播，其中一个等待请求的当前s t r e t c h 值 定义为该请求在系统中停留时间和它的服务时日j 的比率。l t s f 作为o n - d e m a n d 广播调度算法，在没有客户端c a c h e 机制时它显示出了良好的表现。 2 1 2c a c h e 机制表现评价标准 在传统的操作系统和数据库系统的c a c h e 管理机制中，被缓存的数据项通常 是一样大小的( 例如一个数据页或数据项) ，而且c a c h e 失效开销也一样，所以 命中率标准就和访问延迟标准一致，例如命中率越高，整体访问延迟就越小。因 此在传统的c a c h e 管理机制中，命中率就常常被用来衡量c a c h e 替代机制的效率。 但是当数据项大小不一时，c a c h e 命中率就很显然不再是可靠的衡量标准。 在以前的研究中，有人提出用字节命中率，即命中的总字节数与请求的总字节数 的比率，来作为新的衡量标准。但是在无线网络的c a c h e 系统中，当应用的广播 机制不同时，不同的数据项会出现不同的失效开销。所以字节命中率并不能很好 的反映整体的系统表现。一般来讲，有以下两种方法可以衡量c a c h e 管理机制的 表现： ， 访问延迟：一个请求从提交到得到响应的时间差，这是最常用的一种评价指 标。 s t r e t c h 9 比率：一个请求的访问延迟和服务时间的比率。其中服务时间为系 统空闲时该请求的访问延迟，定义为数据项的大小和广播带宽的比率。 s t r e t c h 比率实际上是针对用户感知方面对于访问延迟的一种改进，它基于以 下假定：对于一个比较小、服务时间比较短的数据项，用户期望能获得较小的访 问等待；相反，对于一个比较大的数据项，用户相对能忍受更长的访问等待。访 问延迟这一指标没有考虑到数据大小和服务时问的不同，而通过s t r e t c h 比率就 能针对无线网络环境数据项大小不一的特点进行改进。但是在考虑客户端写操作 影响的情况下，因为写操作使用的将是上传带宽，所以s t r e t c h 比率中的服务时 间定义将不适用。故在本文后面的实验中，我们将选取访问延迟作为评价指标来 比较算法的优劣。 2 2 无线网c a c h e 一致性问题 2 2 1 一致性策略基本设计方法 一般来讲，设计一致性策略有三种基本的方法： 1 强服务器端，即服务器知道哪些数据被哪些客户端所缓存，当数据更新 时，服务器发送失效通知到缓存这一数据的客户端。这一方法要求服务 器能定位客户端。因为断歼连接的移动客户端不能被服务器联系到，也 就意味着断歼连接后重新连接的客户端先前的c a c h e 内容全部失效。而 且当客户端移动到另外一个单元网时，必须通知服务器。所有的移动、 重新连接、数据更新都必须产生上传信道和广播通信量： 2 客户端在使用c a c h e 数据之i ； 向服务器请求核对一致性。这种方法会产 生大量的上传信道通信量； 9 3 弱服务器端，即服务器不了解客户端的c a c h e 状况，也不了解客户端的 位置和连接情况。服务器只是定期广播失效报告，报告罩包括最近更新 的数据项。客户端通过监听失效报告来确定c a c h e 内容是否失效，当发 现c a c h e 失效才+ 用到上传信道。 2 2 2 失效报告种类 因为我们接下来要介绍的c a c h e 一致性策略都基本基于失效报告( i r ) ，所 以在这里先介绍一下一般用到的不同形式的失效报告。 按照服务器发送失效报告的方式可分为： 异步方式( a s y n c h r o n o u s ) ：当数据项发生更新时马上广播失效报告。失效报 告可能只包括发生更新的数据项，也可能包括其他数据项的最后更新时问戳等信 息。 同步方式( s y n c h r o n o u s ) ：在这种方式下，失效报告周期性的进行广播。 按照失效报告包含的内容可分为： 基于状态的( s t a t eb a s e d ) ：失效报告包含数据项更新后的最新值的信息。一 个典型的基于状态的失效报告可以包含自上次报告之后发生更新的数据项的值。 基于历史的( h i s t o r y b a s e d ) ：失效报告包含数据项何时更新的信息。一个典 型的基于历史的失效报告可以包含过去w 秒( w 为算法参数) 发生更新的数据 项的标识( i d ) ，以及它们最后一次更新的时闻戳。 按照失效报告的信息组织方式可分为： 未压缩的：失效报告包含单个的数据项的信息。 压缩的：失效报告包含的是数据项子集的集合信息。 2 2 3 无线网c a c h e 一致性相关研究 在移动环境中的缓存问题最早是b a r b a r a 和i m i e l i n s k i 3 ， 4 1 提出，他们提出 0 了三种基于失效报告( i r ) 的机制：t s ( b r o a d c a s t i n g t i m e s t a m p s ) 、a t ( a m n e s i c t e r m i n a l s ) 、s i g ( s i g n a t u r e s ) 。三者针对弱服务器的假设使用不同的失效报告机 制。这些算法的有效性基于一定的条件，即客户端的断开连接的时间不超过一定 的算法参数( 如广搔窗口w 广播间隔l ) ，或者更新的数据项数目不超过一定的 算法参数。但是实际上，即使客户端断开了很长时间或者服务器更新了很多数据， 有些c a c h e 数据还是可能有效的。所以这种方法不能非常有效的利用带宽。 j i n g 1 0 提出一种b s 机制，在这个机制中，失效报告包含一个二进制字节序 列集合和一个辅助的时间戳集合。只有当客户端c a c h e 中超过一半的数据项在服 务器被更新时，客户端才失效它的整个c a c h e 。因为不要求特别的算法参数，所 以工作量参数的变化对算法的表现几乎没有影响。但是这种机制相对于t s 或者 a t 方法来说要求更大的失效报告，特别是当数据库很大时。 w u 1 q 在t s 或者a t 算法的基础上通过在客户端重新连接时引入c a c h e 有 效性检查来提出一种新的机制。这种方法的副作用是需要u p l i n k 带宽，同时需要 指定一个过去w 个广播间隔的更新历史窗口，而这就引发了和t s 一样的问题 ( 如当断开连接的时自j 超过w ，所有c a c h e 内容将无效) 。 q i n g l o n gh u 5 等在前人的基础上，提出了三种自适应的失效算法：a f w 、 a a wt s 、a a wa t ，在这些算法中，服务器根据数据更新和查询的几率和形式， 以及客户端的断开时间来广播不同的失效报告，比较好的解决了之前一些算法的 缺点。 之后提出的一致性机制都是在这个i r 机制的基础上进行改进和变化，只要 是在i r 的内容和u p l i n kc h e c k i n g 的机制上不同( 如 1 2 1 ，【1 3 1 ，【1 4 ，【i s ，【1 6 ，【1 7 1 ， 【1 8 1 ) 。所有这些算法都会因为在使用数据之前进行有效性检查而引发一些有效 性延迟。 2 3 替换和预存取策略 2 3 1 传统c a c h e 替换算法介绍 根据程序局部性规律可知：程序在运行中，总是频繁地使用那些最近被使用 过的指令和数据。这就提供了替换策略的理论依据。传统的替换策略一般有随机 法、先进先出法、最近最少使用法等。 i 随机法( r a n d 法) 随机法是随机地确定替换的存储块。设置一个随机数产生器，依据所产生的 随机数，确定替换块。这种方法简单、易于实现，但命中率比较低。 2 先进先出法( f i f o 法) 先进先出法是选择那个最先调入的那个块进行替换。当最先调入并被多次命 中的块，很可能被优先替换，因而不符合局部性规律。这种方法的命中率比随机 法好些，但还不满足要求。 3 最近最少使用法( l r u 法) l r u 法是依据各块使用的情况，总是选择那个最近最少使用的块被替换。这 种方法比较好地反映了程序局部性规律，是传统的c a c h e 替换算法中使用最多的 一种，在本文的实验部分将选用它作为参照算法。 实现l r u 策略的方法有多种。下面介绍一下计数器方法，这一方法将在本 文后面的模拟实验中用到。 在计数器方法中，缓存的每一块都设置一个计数器，计数器的操作规则是： ( 1 ) 被调入或者被替换的块，其计数器清“0 ”，而其它的计数器则加“l ”。 ( 2 ) 当访问命中时，所有块的计数值与命中块的计数值要进行比较，如果 计数值小于命中块的计数值，则该块的计数值加“l ”；如果块的计数值大于命 中块的计数值，则数值不变。最后将命中块的计数器清为0 。 ( 3 ) 需要替换时，则选择计数值最大的块被替换。 2 3 2 无线网c a c h e 替换算法相关研究 无线网络数据缓存最早是在b r o a d c a s t d i s k s ( b d i s k ) 项目中被提到。在这个 项目中，a c h a r y a 1 9 ，【2 0 提出了一种名为p 的缓存替换算法。在这个算法中， p x 值最小的数据项将被替换，其中p 是数据项的存取概率，x 是它的广播频率。 也就是说被替换的数据项要么存取概率比较低，要么检索延迟小。在一个后续的 研究中，a c h a r y a 等 2 h x 提出了预存取策略来进一步提高c a c h e 访问的效率。 t a s s i u l a s 和s u 2 2 提出一种基于时间槽( t i m es l o t s ) 的算法，试图使平均访 问延迟最小化。在这一算法中，广播信道被分成相等的时间槽，每个时间槽等于 单个数据项的广播时间。算法定义数据项i 在时间槽n 的时间相关r e w a r d 函数 为：，( 帕= 五( n ) + 4 2 ，其中丑为数据项f 的访问率，( n ) 为从时间槽h 到 数据项i 的下一次传送之间的时问差。算法在时间槽n 时，将提前计算矿步， 在保证从时间槽到n + w 的平均r e w a r d 函数总和最大的基础上做出c a c h e 替换 选择。时间窗口矿越大，c a c h e 替换算法的效果越好，相应的，计算复杂度也越 大。 i ( a t l a n n a 和l i b e r a t o r e 2 3 针对b d i s k 系统提出了新的g r a y 算法。他们假设客 户端无法获得关于未来数据请求和存取概率的信息，主要考虑存取历史和检索延 迟的影响。通过理论证明，在最坏情况下，g r a y 算法比l r u 优先的比例系数为 c a c h e s i z e l o gc a c h e s i z e 。 以上的研究都是基于p u s h b a s e d 的广播系统的，j i a n l i a n gx u 2 等针对 o n - d e m a n d 的广播系统提出了s a i u 缓存替换算法。这个算法考虑了数据项大小、 数据检索延迟、存取概率、更新频率，并引入了一个印加函数： 删归格 其中厶、4 、墨、u 分别代表数据项i 的访问延迟、存取概率、数据项大小、更 新频率。 在缓存数据项更新的时候，系统将g a i n 函数值最小的数据项移出直到空问足够 容纳新的数据项。 之后，j i a n l i a n g x u 2 4 等叉在之前的基础上，提出新的针对o n - d e m a n d 广播 系统的m i n s a u d 算法。在这个算法中，他提出了新的评价函数： 酬垆詈，咯一d 其中只、焉、鸟、分别代表数据项i 的存取概率、数据项大小、检索延迟、更 新率和存取率的比率：v 代表缓存有效性检查延迟。 此算法考虑了更多的影响因素，因而更加接近实际环境。经过理论验证和模 拟试验，论文证明了此算法比传统的l r u 算法和之前的s a l u 算法更优。 上述所有研究都基于客户端只对服务器数据进行读操作的假设，所以在对替 换算法进行优化时虽然考虑了无线网络的各种特殊因素和特点，但是没有考虑客 户端写操作对替换算法效率的影响。本文j 下是在这一点上进行研究，在设计新的 替换算法时加入写操作的考虑因素，使替换算法更加全面、更符合实际情况。 2 4 无线网络c a c h e 写策略 2 4 1 传统写策略介绍 传统的c a c h e 写策略主要有两种： 写直达法( w r i t et h r o u g h ) ：写直达法是指在执行写操作时，不仅将信息写入 c a c h e 中相应的数据项，而且也写入下一级存储器中相应的数据项。 写回法( w r i t eb a c k ) ：写回法只把信息写入c a c h e 中相应的数据项。该数据 项只有在被替换时，才被写回下一级存储器。 为了减少在替换时数据项的写回，常采用写标志位，即为c a c h e 中的每一个 数据项设置一个写标志位，用于指出该数据项是否为脏数据项( d i r t y d a t a i t e m ) 。 替换时，若被替换的数据项是不是脏数据项，则不必写回下一级存储器，因为这 时下一级存储器中相应块的内容与c a c h e 中的一致。 写回法和写直达法各有特色。两者相比，写回法的优点是速度快，写操作能 以c a c h e 存储器的速度进行。而且对于同一单元的多个写最后只需一次写回下一 级存储器，有些写只到达c a c h e ，不到达下一级存储器，因而所使用的存储器频 带较低。这使得写回法对于多处理机很有吸引力。写直达法的优点易于实现，而 且下一级存储器中的数据总是最新的。后一个优点对于i o 和多处理机来说是重 要的。1 t 9 和多处理机经常难于在两种方法之间取舍：它们既想要减少访存的次 数，又想要保持c a c h e 和下一级存储器的一致性。 4 由于写访闯不需要用到所访问单元原有的数据。所以，当发生写失效时，是 否调入相应的数据项，有两种选择： 按写分配法( w r i t ea l l o c a t e ) ：写失效时，先把所写单元所在的数据项调入 c a c h e ，然后再进行写入。这与读失效类似。 不按写分配法( n o w r i t ea l l o c a t e ) ：写失效时，直接写入下一级存储器而不 将相应的数据项调入c a c h e 。 虽然上述两种方法都可以应用于写直达法和写回法，但写回法c a c h e 一般采 用按写分配法，这样以后对该数据项的写操作就能命中c a c h e ：而写直达法一般 采用不按写分配法，因为以后对该数据项的写仍然要到达下一级存储器，所以没 有将数据项保留在c a c h e 中的必要。 2 4 2 无线网写操作相关研究 关于无线网c a c h e 写策略的相关研究比较少，有限的一些研究主要集中在客 户端断开连接后写操作引发的一致性问题。 k i s t l e r 和s a t y a n a r a y a n a n 开发的c o d a 文件系统提供了对断开连接的写操作 的支持【2 5 】。移动客户端只要通过标准的u n i x 文件系统接口就能运行在c o d a 系 统之上。c o d a 系统通过一个运行于客户端的叫v e n u s 的c a c h e 管理器来实现对 断开连接的写操作的支持。在客户端断开连接期间所作的写操作，都将通过操作 日志的方式进行保存，通过一个优化的冗余备份控制策略来保证更新操作的异步 进行。当重新连接上服务器之后，将由v e n u s 将它的c a c h e 和服务器进行同步化。 如果v e n u s 检查到有分歧，则通过应用专用解决器( a p p l i c a t i o ns p e c i f i cr e s o l v e r , a s r ) 来消除不一致。如果a s r 也解决不了，则会触发一个在客户端的手动修 复工具束处理。可以看出，该c o d a 系统虽然提供了一种支持断- 丌连接写操作的 方法，但是算法复杂，处理过程中占用大量带宽，而且也没考虑到处理过程可能 对c a c h e 效率的影响。 m a z e r 和b r o o k s 2 6 在他们的c a u b w e b 工程中提出了怎么在实时的w e b 浏览 器服务器机制中支持客户端断开连接时对w e b 页面的更新。该机制主要是在客 户端提供一个h t t p 客户代理，当客户端断开连接时就向该代理提交更新请求。 l s 当客户端重新连接时，则通过该h t t p 代理一次性向服务器端提交断开期日j 的所 有更新请求。在客户端向h t t p 代理提交请求时，h t t p 代理将保留两个版本： 修改前的原始数据和修改后的最终版本。当重连接后h t t p 代理向服务器提交请 求时，将在一定的更新策略的基础上，通过这两个版本数据来判断更新是否被服 务器接受。虽然在c a u b w e b 工程中提出了不同断丌的客户端同时更新同一数据 项可能引发的冲突，但是并没有提出有效的解决方法。 在1 e t f 的w e b d a v 工作组中，也提到了对断开连接的写操作的支持的解 决方法 2 7 1 ，【2 8 ，【2 9 。在每次提出更新请求时，必须指明该更新的原始版本。如 果该原始版本已经在服务器端被更新，则该更新请求被拒绝。此时客户端必须从 服务器下载新的数据项，并锁定该数据项，以避免同时更新的发生。虽然 w e b d a v 提供了避免并行更新的方法，但是并没有很好的考虑到一些可能的设 计需要，例如在上传更新时最小化带宽占用和最大化更新有效率等等。 可以看出，对于无线网络c a c h e 的写策略的研究基本上集中在断开连接特殊 情况下的一致性问题上，而且一般只考虑解决方案的可行性，很少研究由此引发 的效率问题。而关于写策略可能引发的对c a c h e 替换算法效率的影响则尚未见到 相关的研究。本文接下来将着重研究考虑客户端写操作情况下，为了保证c a c h e 管理的高效性，对写策略的改进和c a c h e 替换算法的重新设计。为了简化研究， 本文将暂不考虑客户端断开连接的情况，在保证写策略一致性的基础上，着重研 究写策略引发的对c a c h e 管理效率的影响和优化。 1 6 第3 章i w b 写策略和r w u s 替换算法研究方案 3 1 优化写策略一改进写回法 3 1 1 无线网络中的写直达法 由于传统的写策略是在非网络环境下设计，当我们考虑无线网络的c a c h e 写 策略时，必须结合无线网络的网络特征和o n - d e m a n d 的数据传送方式对传统的 写策略进行重新设计才能使其适用于无线网络。 写直达法拥有较高的一致性性能，符合强一致性模型，可以较简单的适用于 无线网络。下面我们针对无线网络环境对其进行重新设计，按照惯例，我们将其 与不按写分配法相配合。 客户端：当客户端应用程序有写操作请求时，c a c h e 管理器将查询本地c a c h e ， 若命中，则更新c a c h e 相应内容，同时更改该数据项的时间戳为当前时间，然后 通过上传信道向服务器端发送更新请求，并开始向服务器传送更新后的数据项。 如果查询本地c a c h e 后不命中，则不需对本地c a c h e 进行任何操作，而直接通过 上传信道向服务器端发送更新请求，并开始向服务器传送更新后的数据项。 服务器端：在接收到客户端通过上传传来的更新请求后，将该数据项失效， 同时开始接收从客户端传来的更新后数据。如果在接收期间有对该数据项的读请 求，则让该请求等待。如果对同一数据项的写请求冲突，则根据客户端更新后的 时间戳来选择最新的版本进行接收。接收完毕后去除该数据项失效标志，并更新 其时阿戳。 1 7 图3 1 写直达法的客户端流程图 无线网络下写直达法的客户端算法如下： i fr e a d a c c e s s i f c a c h eh i t w a i tf o rt h el rf r o ms e r v e ra n dc h e c kd a t av a l i d a t i o n ； i ft h el o c a i l t e mji sv a l i d a t i o n a d j u s ti t e mi sp o s i t i o ni nt h ei t e mh e a p ； e l s e s e n dar e q u e s tf o ri t e mit ot h es e r v e r ； m o n i t e rt h ea r r i v a io fi t e mif r o mt h eb r o a d c a s tc h a n n e l ； u p d a t ei t e m nt h ei o c a lc a c h e ； a d j u s ti t e mi sp o s i t i o ni nt h ei t e mh e a p ； e n d i f e l s e s e n dar e q u e s tf o ri t e mit ot h es e r v e