（计算机科学与技术专业论文）无线网络中移动数据缓存若干问题的研究.pdf

摘要 摘要 随着通信技术的发展，无线网络技术获得了长足的发展。蓝牙，8 0 2 1 l ( w i f i ) 等技术正得到越来越广泛的应用，无线通信也逐步成长为很重要的信息获取方 式。而自组织无线网络( a dh o e ) 是近年来兴起的无线设备连接方式。随着时间 的推移，合作式w 曲浏览，点对点( p 2 p ) 文件共享，p 2 p 流媒体，等应用也将在 白组织无线网络中得到极大的应用。 本文研究内容侧重于移动对等网络( m o b i l ep e e rt op e e r , m p 2 p ) 的应用层数 据服务，其基础就是a dh o c 网络。传统意义上的a dh o e 网络是由具有无线接口 的无线设备连接成的多跳无线网络。其组成设备可以是手提电脑甚至是传感器一 类的无线设备。尽管这种网络目前主要用于军事领域，但随着技术的发展，其应 用范围会越来越广阔。近年来，a dh o e 网络研究在民用和商业领域也受到了重视。 在民用领域，a dh o e 网络可以用于灾难救助。在发生洪水、地震后，有线通信设 施很可能因遭受破坏而无法正常使用，通过a dh o e 网络可以快速地建立应急通 信网络，保证救援工作的顺利进行，满足紧急通信需求。a dh o e 网络还可以用 于偏远或不发达地区通信。在这些地区，由于造价、地理环境等原因往往没有有 线通信设施，a d h o c 网络可以解决这些环境中的通信问题。a dh o e 网络还可以用 于临时的通信需求，如较远距离商务会议中需要参会人员之间互相通信交流，在 现有的有线通信系统不能满足通信需求情况下，可以通过这种网络来完成通信任 务。 a dh o c 网络具有独立性和动态变化的网络拓扑结构，具有有限的通信带宽， 另外还具有分布式、生存周期短、以及有限的物理安全等特点。因而，它的数据 输运效率比较低下。 此外，由于无线用户的个性选择、组网的移动设备类型多样、移动网络技术 提供商的异质性等特点，无线自组织网络需要将各种异质类型的设备有效组网。 解决这个问题的最有效途径是在网络节点上设置缓存以有效减少不必要的网络 数据传输。本文针对移动对等网络中的优化数据缓存存取问题进行研究，主要包 括：无线基站网络中自适应缓存数据更新，移动对等网络缓存数据发现，缓存数 据索引，异质移动对等网络及其缓存更新策略，移动对等网络中缓存布置和分布 式缓存更新。论文的主要贡献与创新如下： 1 ) 提出了基于演化计算的无线基站缓存更新算法参数优化方法e b h a ( e v o l u t i o nb a s e dh y b r i da l g o r i h t m ) ，解决无线基站数据缓存更新对动态用户请 求效率低下的问题。该方法利用演化计算这一优化方法，使得基站的缓存数据能 自适应于用户的请求。实验针对本文提出的e b h a 和l f u 、l r u 、f s r 等缓存 更新算法进行比较，结果表明本文算法是有效的。 摘要 2 ) 提出了一个启发式的缓存路径生成算法，为移动对等网络的数据发现服 务。该算法针对移动对等网络缓存数据查找效率低下的问题，利用生成的路径， 使得移动用户可以较快地从整个网络中获取缓存数据。实验比较了该方法与未考 虑节点异质性的缓存路径生成策略，结果表明了该方法是有效的。 3 ) 提出了异质移动对等网络上的缓存更新策略，解决异质移动对等网络环境 下分配缓存服务负载的问题。该策略首先将移动节点划分为三种类型：强节点、 中间节点和弱节点，然后分别使用不同类型的缓存更新方法，即为不同类型的缓 存终端设计不同的数据缓存算法。与常用的缓存更新方法l f u ，l r u ，f s r 的 实验比较结果表明所提出的方法是有效的。 4 ) 提出了基于搜索的启发式缓存数据发现算法s p f a ( s u p e r p e e r f i r s t a 木) ，以解决异质移动对等网络中由于网络中节点具有不同缓存空间、数据延迟 不同等内部属性时，如何快速发现所需缓存数据的问题。相应的启发式数据发现 策略可以自适应地快速发现数据。实验结果表明，与仅仅考虑异质节点特性的 s p f 算法、仅仅考虑路径最优特性的a 枣算法以及随机发现的方法r a n d 相比， 本文所提出的方法是有效的。 5 ) 研究了移动对等网络上的缓存n 本数据放置问题。该问题是一个经典的 n p 难问题，本文提出了组合缓存数据的启发式放置与缓存数据更新的综合方案， 该方案是将经典的数据放置方法用于移动对等网络环境，以及结合分布式缓存更 新的新策略。实验比较了全局放置、局部放置、基于聚类的放置以及随机放置的 优劣，验证了本文提出的数据放置结合集中式和分布式的启发式数据更新方法能 够带来效率上的提升。 关键词：移动对等网络，异质移动对等网络，缓存路径生成，缓存更新算法，缓 存副本放置。 a b s t r a c t a b s t r a c t n o w a d a y s ，m o b i l ea dh o en e t w o r kh a so b t a i n e dq u i c k l yd e v e l o p m e n ta n dl o t s o fa p p l i c a t i o nw i l lb ew i d e l yu s e di ns u c hk i n do fn e t w o r k b l u e t o o t h ，8 0 2 11 ( w i - f i ) a n ds oo nw i l lb ev e r y p o p u l a ri n t h ec i v i l i a n s p h e r e ，w h i c hm a k e s w i r e l e s s n e t w o r k i n gg r a d u a l l yg r o w ni n t oav e r yi m p o r t a n tp a r tt oo b t a i nd a t a a dh o cn e t w o r k i sp o p u l a rt h i sd a y , i ti so b v i o u st h a tm a n ya p p l i c a t i o n ss u c ha sc o o p e r a t i v ew e b b r o w s e r , a n dp 2 pf i l es h a r i n ga n dp 2 pm u l t i m e d i as t r e a m i n gs e r v i c ew i l lb ew i d e l y d e v e l o p e di ns u c hh n do fn e t w o r ke n v i r o n m e n t t h ef o u n d a t i o no fo u rr e s e a r c hi sa dh o cn e t w o r k ，w h i c hc a na l s ob ed e n o t e da s m o b i l ep e e rt op e e rn e t w o r k ( m p 2 p ) i na p p l i c a t o nl a y e r a dh o cn e t w o r ki saw i r e l e s s n e t w o r kw h e r ew i r e l e s sd e v i c e sa r ec o n n e c t e di n t oam u l t i h o pw i r e l e s sn e t w o r k i t s c o m p o s i t i o nc a nb eap o r t a b l ec o m p u t e rd e v i c es u c ha ss e n s o r so re v e na sw i r e l e s s d e v i c e s w h i l es u c hn e t w o r k sa r em a i n l yu s e di nm i l i t a r yf i e l d ，b u ta st e c h n o l o g y d e v e l o p s ，i t ss c o p eo fa p p l i c a t i o nw i l lb e c o m ei n c r e a s i n g l yb r o a d i nr e c e n ty e a r s ，a d h o cn e t w o r kr e s e a r c hi nc i v i la n dc o m m e r c i a lf i e l d sh a v ea l s ob e e nd u l yn o t e d i nt h e c i v i l i a ns p h e r e ，a dh o cn e t w o r kc a l lb eu s e df o rd i s a s t e rr e l i e f i nt h ee v e n to ff l o o d ， e a r t h q u a k e ，c a b l ec o m m u n i c a t i o n sf a c i l i t i e sa r el i k e l yt os u f f e rd a m a g ea n dc a nn o t n o r m a l l yc o m m u n i c a t e ，t h r o u g ht h ea dh o cn e t w o r kc a nq u i c k l ys e tu pa ne m e r g e n c y c o m m u n i c a t i o n sn e t w o r kt oe n s u r et h es m o o t hp r o g r e s so fr e s c u ew o r kt oc o m p l e t e t h ee m e r g e n c yc o m m u n i c a t i o n s a dh o cn e t w o r kc a nb eu s e df o rc o m m u n i c a t i o n si n r e m o t eo r u n d e r d e v e l o p e da r e a s i nt h e s ea r e a s ，b e c a u s eo fc o s t ，g e o g r a p h i c a l e n v i r o n m e n t ，o f t e nb e c a u s et h e r ei sn ow i r e dc o m m u n i c a t i o ni n f r a s t r u c t u r e ，a dh o c n e t w o r kc a ns o l v et h ec o m m u n i c a t i o np r o b l e m si nt h e s ee n v i r o n m e n t s i tc a na l s ob e u s e df o rt e m p o r a r yc o m m u n i c a t i o n sn e e d s ，s u c ha sb u s i n e s sm e e t i n g st h a tn e e dt o c o m m u n i c a t ew i t he a c ho t h e r w h i l ec o m m u n i c a t i o n b e t w e e nt h ep a r t i c i p a n t si nt h e e x i s t i n gw i r e dc o m m u n i c a t i o ns y s t e m sc a nn o tm e e tt h ec o m m u n i c a t i o n sn e e d so ft h e c i r c u m s t a n c e s ，i tc a nb ed o n et h r o u g ht h ea dh o cn e t w o r kc o m m u n i c a t i o nt a s k s t h i sn e t w o r kh a st h ei n d e p e n d e n c e ，d y n a m i cc h a n g e si nn e t w o r kt o p o l o g y , l i m i t e dw i r e l e s sc o m m u n i c a t i o nb a n d w i d t h ，t h en e t w o r kd i s t r i b u t e dc h a r a c t e r i s t i c s ， l i f e c y c l ei ss h o r t ，l i m i t e dp h y s i c a ls e c u r i t yf e a t u r e s ，t h a ti s ，i t sr e l a t i v e l yl o w e f f i c i e n c yo fd a t at r a n s p o r t ，h o wt os o l v et h i sp r o b l e m ? t h em o s te f f e c t i v ew a yi st o s e tu pt h en e t w o r kn o d ec a c h ei no r d e rt oe f f e c t i v e l yr e d u c et h en e t w o r kd a t a t r a n s r n i s s i o n i na d d i t i o n ，t h ew i r e l e s su s e r so w np e r s o n a lc h o i c ea n dm a n yo t h e rf a c t o r s ， n i a b s t r a c t m u l t i p l et y p e so fm o b i l ed e v i c e sa n dw i r e l e s sn e t w o r ke n v i r o n m e n t sw i l ln e e dt ob e f a s t n e t w o r k i n gd e v i c e s t ot h i se n d ，m o b i l ed e v i c e s ，m o b i l en e t w o r kt e c h n o l o g y p r o v i d e r sh a v eh e t e r o g e n e o u sc h a r a c t e r i s t i c s ，i no r d e rt oa d d r e s st h e s ei s s u e s ；w e f o c u so nm o s tf i e l d so fc a c h ei nm o b i l ep e e rt op e e r ( m p 2 p ) n e t w o r k s t h es t r u c t u r e o ft h i sp a p e ri so r g a n i z e da sf o l l o w s ： 1 ) f i r s t l y , w ed i s c u s sa l le v o l u t i o nb a s e da l g o r i t h mf o rp a r a m e t e r so p t i m i z a t i o n o fc a c h eu p d a t i n gi nw i r e l e s sn e t w o r kw i t hb o t hm o b i l ec l i e n ta n db a s es t a t i o n o u r s c h e m ei su s e dt os o l v et h el o we f f i c i e n c yo fd y n a m i cu s e rr e q u e s t sp r o c e s sp r o b l e m i nm o b i l eb a s es t a t i o n s e v o l u t i o nb a s e do p t i m i z a t i o nm e t h o di su s e dt om a k et h eb a s e s t a t i o nt o a d a p tt od y n a m i cu s e rr e q u e s t s o u re x p e r i m e n t sa r ec o n d u c t e db y c o m p a i n gt h ep r o p o s e de b h a ( e v o l u t i o nb a s e dh y b r i da l g o r i h t m ) 、i t hl f u ，l r u a n df s r 2 ) s e c o n d l y , ah e u r i s t i cc a c h ep a t hg e n e r a t i o na l g o r i t h mi sp r o p o s e df o rc a c h e d a t af i n d i n gi nam p 2 pn e t w o r k o p t i m i z a t i o na l g o r i t h m sh a v eb e e np r o p o s e df o r c a c h ep a t hg e n e r a t i o nf o rq u i c k l yc a c h e dd a t aa c c e s si nt h ew h o l en e t w o r kf o r e f f e c t i v ed a t a a c c e s s i n g o u re x p e r i m e n t sa r ec o m p a r e dw i t ht h e c a c h ep a t h g e n e r a t i n gs t r a t e g yw h i c ht a k e sn oc o n s i d e r a t i o no nt h eh e t e r o g e n e o u sp r o p e r t i e so f e v e r yn o d e b yt h ee x p e r i m e n t s ，t h ee f f i c i e n c yo ft h ep r o p o s e ds c h e m e mi sp r o v e d 3 ) t h i r d l y , ah e t e r o g e n e o u sw i r e l e s sn e t w o r ka n di t sc a c h i n gs c h e m e sa r e d i s c u s s e d t h ep r o p o s e ds h c m es o l v et h ep r o b l e mo fe f f e c t i v e l yd i v i d et h ec a c h ed a t a i n t od i f f e r e n tk i n d so fn o d e s a sm o b i l en o d e si ns u c hk i n do fn e t w o r kh a v ed i f f e r e n t i n n e rp r o p e r t i e ss u c ha sc a c h es i z e ，d a t at r a n s m i s s i o nd e l a ya n ds oo n t h em o b i l e n o d e sa r ed i v i e di n t ot h r e ek i n d sw h i c hc a nb ed e f i n e da s “s u p e rn o d e s ”，“m i d d l e n o d e s a n d “w e a kn o d e s ”d i f f e r e n tk i n d so fc a c h es c h e m eh a v eb e e na d a p t i v e l y d e s i g n e d f o rd i f f e r e n tk i n d so fm o b i l et e r m i n a l si nt h en e t w o r k an u m b e ro f e x p e r i m e n t sa r ec o n d u c t e dt ob ec o m p a r e dw i t hd i f f e r e n tk i n d so fc a c h eu p d a t i n g s c h e m e sa s ：l f u ，l r ua n df s r t h e nt h ee f f i c i e n c yo ft h ep r o p o s e ds c h e m ei s p r o v e d 4 ) i nt h ef o u r t hp a r t ，o u rt h e s i sp r o p o s et h ec a c h ed a t af i n d i n ga l g o r i t h mi n h e t e r o g e n e o u sn e t w o r k ，s u c hk i n do fa l g o r i t h mi sb a s e do na 宰h e u r i s t i ca l g o r i t h mi n m o b i l ep e e rt op e e rn e t w o r k t h ep r o p o s e ds c h e m es o l v et h ep r o b l e mo nh o wt o q u i c k l yf i n dt h en e e d e dd a t ai nh e t e r o g e n e o u sm o b i l ep e e rt op e e rn e t w o r kw h i c h c o n t a i n st h en o d e s 、 ，i t hd i f f e r e n tk i n d so fi n n e rp r o p e r t i e s t h ep r o p o s e ds c h e m ei s n a m e da ss p f - a 幸( s u p e rp e e rf i r s ta ) ，i no u re x p e r i m e n t ，t h ec o m p a r e da l g o r i t h m s i v a b s t r a c t a r et h a to n l yc o n s i d e rt h ed i f f e r e n tp r o p e r t i e so ft h em o b i l en o d e ( s p f ) ，o ro n l y c o n s i d e rt h eo p t i m i z a t e dp a t hg e n e r a t i o n ( a 木) a n dr a n d o mf i n d i n g ( r a n d ) b yt h e e x p e r i m e n t s ，t h ee f f i c i e n c yo ft h ep r o p r o s e ds c h e m e si sp r o v e d 5 ) a tl a s t ，ah e u r i s t i cd a t af i n d i n ga l g o r i t h mi sd e s i g n e dt oa d a p tt os u c hk i n do f n e t w o r k c a c h e r e p l i c a t i o np l a c e m e n ta l g o r i t h mh a sb e e nw i d e l ys t u d i e da sa c l a s s i c a ln p - h a r dp r o b l e m f o re x a m p l e ，i ng r a p ht h e o r yl o t so fw o r kh a sb e e n c o n d u c t e d ，h o w e v e r , f e ww o r k sh a v e b e e nd e s i g n e df o rt h ec a c h e r e p l i c a t i o n p l a c e m e n ta l g o r i t h mc o m b i n i n gw i t ht h ec a c h ed a t au p d a t i n gf o ro p t i m i z a t i o no f m o b i l ed a t aa c c e s s t h ec o r r e s p o n d i n gs c h e m ei s d e v e l o p e da sac o m b i n a t i o no f c a c h ep l a c e m e n ta n du p d a t i n g o u rr e s e a r c hp r o p o s e sc o m b i n e dh e r i s i t i cc a c h ed a t a p l a c e m e n ta n du p d a t i n gi nm o b i l ep e e rt op e e re n v i r o n m e n t t h er e s e a r c hi sd e v o t e d t o t h ep r o b l e mo fu s i n gt r a d i t i o n a ld a t ap l a c e n m ti nm o b i l ep e e rt op e e rn e t w o r k e n v i r o n m e n ta n dc o m b i n gp l a c e m e n ta n du p d a t i n gi ns u c hk i n do fn e t w o r k t h e e x p e r i m e n tc o m p a r et h ea l g o r i t h m so fg l o b a lp l a c e m e n t ，l o c a lp l a c e m e n t ，c l u s t e r b a s e dp l a c e m e n ta n dr a n d o mp l a c e m e n t ac a c h es e r v i c es t r a t e g yb a s e do nd i s t r i b u t e d c a c h ep l a c e m e n ta n dd i s t r i b u t e dc a c h eu p d a t i n gi sp r o p o s e di nt h em p 2 pn e t w o r k ， a n de x p e r i m e n ts t u d i e sh a v ev a l i d a t e dt h ee f f i c i e n c yo ft h es t r a t e g y k e yw o r d s ：m o b i l ep e e rt op e e rn e t w o r k ，h e t e r o g e n e o u sw i r e l e s sn e t w o r k ，c a c h e p a t hg e n e r a t i o n ，m o b i l ec a c h eu p d a t i n g ，m o b i l ec a c h ep l a c e m e n t v 本人声明所呈交的学位论文，是本人在导师指导下进行研究工作所取得的 成果。除己特别加以标注和致谢的地方外，论文中不包含任何他人已经发表或 撰写过的研究成果。与我一同工作的同志对本研究所做的贡献均已在论文中作 了明确的说明。 中国科学技术大学学位论文授权使用声明 作为申请学位的条件之一，学位论文著作权拥有者授权中国科学技术大学 拥有学位论文的部分使用权，即：学校有权按有关规定向国家有关部门或机构 送交论文的复印件和电子版，允许论文被查阅和借阅，可以将学位论文编入有 关数据库进行检索，可以采用影印、缩印或扫描等复制手段保存、汇编学位论 文。本人提交的电子文档的内容和纸质论文的内容相一致。 保密的学位论文在解密后也遵守此规定。 ， 吁公开口保密( 年) 导师签名： 签字日期： 铀f ，若 第一章绪论 1 1 研究背景 第一童绪论 移动对等网络( m o b i l ep e e rt op e e r , m p 2 p ) 是由无线信号连接的基于a dh o c 网络的分布式网络。从物理层上看它就是一个a dh o c 网络，但其研究内容偏重 于网络应用层相关技术的设计与实现。a dh o e 网络无论在应用还是在理论上均 为我们所熟知，在a dh o e 网络上有许多相关研究，如路由、拓扑控制、覆盖问 题和网络容量等等，这些工作多集中于优化带宽利用率，有效包路由，如何减少 能量消耗以及如何有效地处理诸如内部节点频繁移动导致的丢包等问题。在研究 这类问题的过程中产生了大量有价值的工作，但它们并不直接与移动对等网络的 应用层关联，本文则主要研究如何在移动对等网络的应用层上提供高质量的移动 数据服务，该问题与无线网络的重要评估参数一用户的服务质量( q u a l i t yo f s e r v i c e ，q o s ) 有着很自然的联系。本文使用的方法包括缓存路径生成、启发式缓 存数据更新、缓存的放置等等。本章将介绍a dh o c 网络及移动对等网络相关的 技术，以及与移动对等网络中数据缓存、数据更新、缓存放置相关的研究工作。 1 1 1 无线自组织网络 a dh o c 网络( m a n e t s ) 是一种由移动设备组成的自组织网络，从应用层的 角度考虑也被称之为移动对等网络( m o b i l ep e e rt op e e rn e t w o r k ，m p 2 p ) 或移动 网状网络，其组网协议为i e e e s 0 2 1 1 协议 1 1 1 2 1 ，它是无线自组织网络的基础， 下面将简要介绍这个协议。 1 ) 8 0 2 1 1 协议家族的简要描述。8 0 2 1 1 系列协议是移动自组网的基础。 8 0 2 1 1 系列包括了空中调制技术，这系列协议使用相同的基本协议。最流行的 定义是8 0 2 1 l b 和8 0 2 1 l g 协议。基于对原标准的修订，1 9 9 7 年提出的8 0 2 1 1 是 第一个无线网络标准，但8 0 2 1 l b 是第一个得到普遍接受的协议，然后是8 0 2 1 l g 和8 0 2 1 l n 。8 0 2 1 l n 是一个新的多流调制技术。协议家族中的其他标准( c f h d ) 则是对基本服务的修订和延长或对以前规格的更正。 8 0 2 1 1 b 和8 0 2 1 l g 使用2 4g h zi s m 频段。在这个频段，8 0 2 1 l b 和g 的设 备可能会偶尔遭受微波信号、无绳电话和蓝牙设备的干扰。8 0 2 1 1 和蓝牙控制使 用扩频调制作为抗干扰技术。蓝牙采用跳频扩频信号的方法( f r e q u e n c yh o p p i n g s p r e a ds p e c t r u ms i g n a l i n gm e t h o d ，f h s s ) ，8 0 2 1 l b 和8 0 2 1 l g 则采用直接序列扩 第一章绪论 频信号( d i r e c ts e q u e n c es p r e a ds p e c t r u ms i g n a l i n g ，d s s s ) 和正交频分复用 ( o r t h o g o n a lf r e q u e n c yd i v i s i o nm u l t i p l e x i n g ，o f d m ) 的方法。8 0 2 1 1a 使用5 g h z 的u n i l 频段，这为世界的许多地方提供了至少1 9 个非重叠信道，而不仅 仅是3 个工作在2 4g h zi s m 频段提供的信道。依据环境的不同，这些频段在较 高或较低的频率( 频道) 上可能会实现更好或更坏的性能。 2 ) 8 0 2 1 l b 。根据原标准中的定义，8 0 2 1 1 有一个最大的原始数据速率达到 1 1 m b i t s 的并使用相同的媒体访问方法。2 0 0 0 年初，8 0 2 1 l b 产品出现在市场上， 8 0 2 1 1 是在原标准中定义的调制技术的直接延伸，8 0 2 1 1 吞吐量的急剧增加以及 价格的大幅度降低导致8 0 2 1 l b 无线局域网技术最终被快速接受。然而，8 0 2 1 l b 设备容易受到在2 4g h z 频段运行的其他产品( 如：微波炉，蓝牙设备和无绳电 话等等) 的干扰。 根据原标准中的定义，8 0 2 1 1 使用和c s m 刖c a 相同的媒体访问方法。由于 c s m a c a 的协议开销，在实践中8 0 2 1 l b 应用程序的最大吞吐量可以达到约 5 9 m b i t s ( 使用t c p 协议) 和7 1 m b i t s ( 使用u d p 协议) 。根据原有标准中 的定义，8 0 2 1 l b 是一个扩频直接延伸( 直接序列扩频) 调制技术。技术上讲， 该协议使用互补码键控( c c k ) 标准作为其调制技术。 自组网中的每个设备可以自由地向任何方向独立移动，结果会频繁地改变它 到其他设备的连接。每一节点都必须转发与自己无关的数据包，因此每个节点也 是一个路由器。移动自组网建设的主要挑战是每个设备要持续地保持所需的正确 路线的路由信息。自2 0 世纪9 0 年代中后期，笔记本电脑和8 0 2 1 l w i f i 无线网 络的增长使得无线自组织网络得到了广泛的研究。许多学术论文评估协议的传输 能力首先要假设移动节点具有不同的移动模型和移动空间。通常所有节点都在其 它节点的几跳范围内，而且节点以常数率传输数据。不同的协议根据包的丢失率、 路由协议的开销和其它度量方法来加以评估。 1 1 2 数据缓存 缓存技术已被广泛应用于计算机的数据存储。根据定义，缓存是重复地收集 数据的场所，这些原始数据若分散储存在其它地方，其获取代价将十分昂贵( 例 如：访问时间较长) 且比读取缓存成本要高。换言之，缓存是一个临时存储区域， 经常访问的数据存在这里可快速地被访问。一旦数据被存储在缓存中，它可以被 用在未来访问，而不是重新获取或重新计算原始数据。缓存技术已被证明是极为 有效的，因为典型的应用程序的访问模式具有本地化的特性。缓存是一种可能被 再次使用的临时存储数据的存储块。除了c p u 和硬盘驱动器经常使用高速缓存， w e b 浏览器和w e b 服务器也经常使用缓存技术。缓存是由一组条目组成的。每 2 第章绪论 个条目有一个数据作为部分内部存储数据的副本。每个条目有一个标签指定在其 中所存备份的原始身份。 当客户端缓存( 一个c p u ，网络浏览器，操作系统) 要访问后台数据，它 首先检查缓存。如果缓存中的数据可以匹配客户端的需求，则使用缓存中的相应 数据，这种情况被称为缓存命中。例如，w e b 浏览器程序可能会检查磁盘上的本 地缓存，看看它在某一特定的u r l 的网页的内容的本地副本。在这个例子中， 网址是标签，网页的内容是原始数据。缓存的命中率就是命中缓存的比值。另一 种情况下，当缓存中不包含所期望的数据，称为缓存未命中。先前后备存储的数 据会被复制到缓存中，为下次的访问做好准备。在缓存未命中时，通常c p u 会 弹出一些条目，以弥补缓存空间容量的不足。可用启发式方法来选择缓存数据的 进入和或弹出，称之为缓存替换策略。例如，最近最少使用( l i m ) 策略会取 代最近最少使用的条目。更有效的缓存权重计算不仅考虑存储内容的使用频率， 缓存和后台存储的延迟和存储吞吐量都会加以考虑。 高速缓存管理之间的数据保持一致的通信协议被称为一致性协议。缓存不一 致的情况十分普遍，例如：一方面，内部存储的数据可能会改变，但原因并非高 速缓存的变化，在这种情况下，缓存中的副本可能是过期的。另外，当客户端更 新缓存中的数据时，其它缓存中的副本数据又会过期。为了保持缓存良好的一致 性，当数据被写入缓存时需要考虑它是否也必须被写入到存储器，这种数据写入 的时间控制策略被称为写策略。当从缓存删除数据时，这些位置的数据才会写回 存储这些数据的存储器，这种一致性维护方式被称为惰性写入。而在一个一致性 很强的控制策略下，写入缓存的数据必须被立即写入到存储器。但是，在回写( 或 后写) 高速缓存一致性控制策略下，数据不会立即写入存储器。相反，缓存跟踪 已写了的位置( 这些位置被标记为“脏”) 。 已经在计算机领域得到广泛应用的缓存技术有： 1 ) c p u 缓存。小型的接近c p u 的的小缓存的速度可远高于主内存。大多数 c p u 自8 0 年代以来已使用一个或多个缓存，个人电脑内的现代微处理器可能有 多达五六个，每一个都用于执行程序时的不同分工。 2 ) 磁盘缓存。c p u 缓存一般管理完全是由硬件完成的，而其他缓存的管理 则多是由软件。在主存内的页面缓存，就是一个磁盘高速缓存的例子，通常是由 操作系统的内核来管理。实际上，快速的本地硬盘也可用于高速缓存更慢的数据 存储设备，如远程服务器( 网页缓存) ，本地磁带机或光盘唱机。这样的策略， 正是分层存储管理的主要思想。 3 ) w e b 页面的缓存缓存。w e b 页的缓存广泛存在于w e b 浏览器和w e b 代理 服务器，w e b 浏览器会缓存以前的服务器数据。网络缓存 3 1 1 4 1 1 5 1 1 6 是研究最广 3 第一章绪论 的缓存技术，且对后来的无线网络的缓存技术有着深远的影响。网络缓存减少了 需要在整个网络传输的信息量，使得以前存储在缓存中的信息可以重新使用。网 络缓存不仅能降低带宽和减少对w e b 服务器的处理请求，而且有助于改善网络 程序对用户的反应。现代的w e b 浏览器内置w e b 缓存，一些互联网服务供应商 或组织还利用高速缓存代理服务器，它是一个可被网络之间的所有用户共享得 w e b 缓存。另外，还有一种缓存技术是在p 2 p 网络上的缓存，要求在对等应用 程序中使用，以加速点对点传输 7 】【8 】 9 】。 l a r g e r , s l o w e r , 狮d c h e a p e r ( p e rb y t e ) s t o r a g e d e v i e e 晤 图1 1 数据缓存的层次 图1 1 显示了在传统的计算机硬件和网络环境下的数据缓存的层次，各个层 次分别被划分为l o ，l l ，l 2 ，l 3 ，l 4 和l 5 共六层，在这个体系中，上一层的 缓存容量总是比下一层要小，也比下层的每单位的价格更加昂贵，但是却有比下 一层更快的数据存取速度。也就是说，上层是作为下一层的缓存来实现。图中的 l o ，l l ，l 2 ，l 3 ，l 4 层都是本地使用的缓存，有了这种层次化的计算机内部数 据处理架构，整个计算机系统才能够高效地运行。特别值得注意的是层次l 5 ， 这个层次的缓存架构与无线对等网络上的缓存十分的类似，它不是对本地数据的 缓存，而是一种网络数据的缓存。因为要考虑网络拓扑结构和分布式缓存节点间 的交互作用所带来的影响，分布式网络缓存在缓存数据选择，缓存代价的计算， 4 枫砌一脚娜一 第章绪论 缓存更新算法的设计方面都更加复杂。 l e v e lk + 1 口 d a t ai sc o p i e db e t i e v e l si nb l o c ks i z c l a r g e r ，s l o w e r , c h e a p e rs t o r a g e d e v i c ea tl e v e ik + li sp a r t i t i o n e d i n t ob l o c k s 图1 2 缓存层次结构细节 如图1 2 显示了缓存替换的细节，每个层的缓存空间被划分成大小相同的块， 层次之间按照单元块的大小传输数据。上层的缓存空间缓存下层所有数据的一个 子集。上层的存储设备更快，更昂贵，更小。而下层的缓存块更大，更慢，但是 要更便宜。 图1 3 显示了内存高速缓存的块选择( 索引) 机制，右边的是内存高速缓存， 它分为s 个集合，每个集合里有2 个缓存行，缓存定位机制把内存地址划分为t , s ，b 的b i t 串，这三个b i t 串分别用于选择缓存行，选择缓存集合，选择每行的块偏 移，从而可以唯一的将l 1 缓存