（计算机软件与理论专业论文）一种面向活跃用户的web+cache替换策略.pdf

一种面向活跃用户的w e bc a c h e 替换策略摘要 论文题目：一种面向活跃用户的w e bc a c h e 替换策略 专业：计算机软件与理论 硕士生：林华尚 指导教师：倪德明副教授 摘要 c a c h e 是计算机系统中最成功的概念之一，其研究和应用的历史很长。在不同的 应用和访问请求模型特点下，分别发展出很多不同c a c h e 替换算法。流行的c a c h e 替 换算法有：利用访问序列的时间局部性的l r u 策略、利用空间局部性的l f u 策略以 及自适应的a r c 策略等，它们各有各自最优的应用场合。 本文研究类似s n sw e b 网络的对象访问请求序列模型下的c a c h e 替换算法。该模 型被称为u d m ( u s e r b e h a v i o rd r i v e nm o d e l ) 模型。在u d m 模型下，彼此互相关联 的活跃用户的活动决定了请求序列的特点。本文从系统中用户的关系网络入手，通 过挖掘w e b 访问日志记录对用户之间互相访问的概率进行计算。这个用户问互相访 问的概率称为用户引用率，用户引用率表明了一个用户在w e b 上活动期间访问系统 中其他用户的概率。用户之间通过原创、阅读和推荐等动作，对w e b 上的资源对象 进行访问，导致了活跃用户的资源对象在整个s n sw e b 系统的传播得更加深广；而 非活跃用户的资源对象的传播范围则非常有限。一个资源对象进入c a c h e 容器的价值 和该对象在整个用户关系网络中的引用率密切相关。传统的l r u 、a r c 和l f u 策略 都不能够捕捉到访问请求序列的特点。通过研究活跃用户关系网络在s n sw e b 中的 影响，本文定义了c a c h e 对象的影响度( f a c t o ro f l n f l u e n c e ) ，使用最小影响度( l f l ) 策略对c a c h e 对象进行淘汰。实验证明，l f l 算法较好地适应了u d m 对象访问请求的 特点，使c a c h e 系统能达到更高的命中率。 关键词：c a c h e 替换、模拟、马尔可夫链、s n sw e b 、l f i a c t i v eu s e r s b e h a v i o r b 救dw e bc a c h ep o l i c yf o rs n sw 曲a b s t r a c t t i t l e ： m a j o r ： n a m e ： a c t i v eu s e r s b e h a v i o rb a s e dc a c h er e p l a c e m e n tp 0 1i c y c o m p u t e rs o f t w a r ea n dt h e o r y l i nh u a s h a n g s u p e r v i s o r ：a s s o c i a t ep r o f e s s o rn id e m i n g a b s t r a c t c a c h ei so n eo ft l l em o s ts u c c e s s 亿ic o n c e p t si nc o m p u t e rt h e o 呵锄de n g i n e e r i n g t h e 舱i sal o n gl i s to fs t u d i e so nc h e 陀p l a c e m e n tp o l i c i e su n d e rd i 行e 佗n tr e q u e s t s t r e a mm o d e l s t h em o s tp r e v a l e n tp o l i c i e sa r el r u p o i i c yb 弱e do nt i m ei o c a l i 吼l f u p o l i c yb a s e d0 ns p a t i a l l o c a l 时锄da r c w h i c ht a k e sa d v a n t a g eo f b o t l lt i m ea n ds p a t i a l l o c a l i t y t h e s ep o l i c i e sa r eo p t i m a lu n d e rd i f 凫r e n te n v i r o n m e n t s n o 、v a d a y s ，t h em o s tp o p u l a rw e ba p p l i c a t i o ni ss o c i a ln e t w o r k i n gs e r y i c e s ( s n s ) d i 脏r e n t 舶mt h en o n n a lc a s e ，t h er e q u e s ts 骶a mm o d e lo fs n sw e bs y 咖mi s d e t e 肿i n e db yt h eb e h a v i o ro ft h ea c t i v eu s e r sa n dg r o u p s ，w hi c hw ec a lii tu d m ( u s e r b e h a v i o rd r i v e nm o d e l ) i ns n sw e bs y s t e m ，t h eu s e r sa r ec o n n e c t e dw i t he a c ho t h e r ，s o a r et h er e s o u r c e sb e l o n g e dt 0t h e m t h i sp a p e rm a k e su o f t h e 、v e bl o gt oc o n s t m c tt h e u s e rr e 佬r e n c er a t em a t r i x t h ee l e m e n t so ft h e 讯t em a t r i xd e f i n et t l ec o n n e c t i o nb e t w e e n 铆ou s e r s u s e r si ns n sc r e a t c 锄dr e a dt h er e s o u r c e si nt h es i t e a n df o n v a r dt h e mt o t h e i r 丘i e n d s t h er c s o u r c e sc r e a t e db yt h ea c t i v eu s e sw i l lb e 内r w a r dw i d e l y ，w h i l et h e 陀s o u r c e so fi s o l a t e du s e r sa r es e l d o mv i s i t e db yo t h e ru s e r s l r u ，a r ca n dl f ua r en o t c a p a b l e0 fc a p t u r i n gt h ep r o p e r t y 锄dt h ep e r f 0 咖a n c eo fc a c h es y s t e mb u i l to nt h e mi s n o t9 0 0 d i nt h i sp a p e r ii n t r o d u c ean o v e lc a c h e 陀p l a c e m e n tp o l i c yb a l s e do nt h ef a c t o r o f i n f l u e n c eo f e a c hc a c h eo b j e c t ，c a l l e dl f i p o l i c yh e r c t h ee x p e r i m e n t ss h o w t h a t ：i na r e q u e s ts t r e a mm o d e l 雒t h a to fas n s l i k es y s t e m ，l f io u t p e r f i ) 肿l r u ，a r c 锄dl f u p o i i c i e s l f ii ss u i t a b l ef o rs u c ha p p l i c a t i o n s k e yw o r d s ：c a c h er e p l a c e m e n t ，s i m u l a t i o n ，m a r k o vc h a i n ，s n s ，l f i u 学位论文原创性声明 本人郑重声明：所呈交的学位论文，是本人在导师的指导下，独 立进行研究工作所取得的成果。除文中已经注明引用的内容外，本论 文不包含任何其他个人或集体已经发表或撰写过的作品成果。对本文 的研究作出重要贡献的个人和集体，均已在文中以明确方式标明。本 人完全意识到本声明的法律结果由本人承担。 学位论文作者签名：聿术宰南 日期：肋吗年5 月2 0 日 学位论文使用授权声明 本人完全了解中山大学有关保留、使用学位论文的规定，即：学 校有权保留学位论文并向国家主管部门或其指定机构送交论文的电 子版和纸质版，有权将学位论文用于非赢利目的的少量复制并允许论 文进入学校图书馆、院系资料室被查阅，有权将学位论文的内容编入 有关数据库进行检索，可以采用复印、缩印或其他方法保存学位论文。 学位论文作者签名： 导师签名：仡琵略 日期：凇叩年岁月助日 一种面向活跃用户的w e bc a c h e 替换筑略 引言 引言 c a h c 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 容器。 为了解决c p u 和内存之间处理速度的差异，计算机在c p u 上应用了一级缓存和 二级缓存，一定程度上缓解了内存数据访问的矛盾；相对于内存来说，硬盘是慢速 的快设备，所以人们又在硬盘上加入了读写c a c h e ，大大提高了硬盘数据读写速度。 c p uc a c h e 和硬盘c a c h e 都是硬件，虽然只有数兆至数十兆字节大小，但如果这些 c a c h e 失效后，系统的性能将极大下降，可见c a c h e 的重要性。 数据库系统是结构化存储数据和提供一致的数据访问接口的软件系统，数据库 上也应用很多c a c h e 技术。r d b m s 系统把经常执行的s q l 语句、频繁访问的数据块 和数据表的i n d e x 信息保存在c a c h e 中，节省了s q l 语句的编译时间和磁盘访问次数， 提高数据库的查询响应速度。 在互联网应用服务中，c a c h e 的应用更加广泛和复杂。w 曲代理服务器在某种程 度上就是一种c a c h e ，局域网中的代理服务器有效的减少了对外请求的网络流量；很 多流行的w 曲服务器会把经常被请求的静态页面放在c a c h e 中，在w 曲服务系统架构 上，很多应用都不直接对底层数据库进行操作，在w e b 页面展现层和数据存储层中 加入一个c a c h e 接口层，负责底层数据的访问。现在，很多大型w e b 站点使用轻量级 的m e m c a c h e d 服务对w e b 对象进行缓存。 中间件应用服务器也大量使用c a c h e 技术。如j a v a e e 应用服务器会自动把访问频 度高的e j b 装载到内存中，提高调用速度；不仅如此，还常常对一个函数调用的结 种面向活跃用户的w e bc 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 访问c a c h e 的速度比直接访问原始数据的速度要快得多：访问c a c h e 通常比原 始存储快一个数量级以上。否者c a c h e 便失去了其意义。 2 c a c h e 的容量相比原始数据来说通常较小：一台典型的x 8 6p c 有l gb y t e s 的内 存，但由于缓存造价昂贵，c p u 的一级缓存和二级缓存加起来一般不足1 6 m ，c a c h e 和主存的比例不足1 。在w 曲应用中经常使用磁盘存储原始数据，利用内存做c a c h e 容器。由于内存的价格不断下降，w 曲站点的c a c h e 比例通常可以做到2 0 左右。但 无论如何，c a c h e 容器总不能把整个原始数据装下来。 3 c a c h e 是i j 缶时性的存储空间：c a c h e 容器中的对象会被修改，修改后需要在一定 程度上和原始数据进行同步。 4 频繁替换和读入：由于c a c h e 的大小非常有限，但原始数据的规模总是很大。 所以c a c h e 容器内的对象会动态地被系统换出或者读入。 5 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 命中率( h i t m t 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 算法能 在所有系统中都有最优化的表现。 在w 曲2 0 时代，s n s ( s o c i a ln e t 焖 r k i gs e r y i c e s ) w e b 系统大大丰富了人们的网上 交往活动。和传统w e b 系统不同的地方是：此类系统拥有规模大用户，存储和管理 着海量的用户资源和数据，而且平均在线用户数较多，w e b 内容大多是用户原创内 容u g c ( u s e rg e n e a t e dc o n t e n t ) ，用户之间互动比较多。为了降低用户等待延时，获 2 一种面向活跃用户的代bc a c 1 e 替换策略 引言 得更好的用户体验，需要设计出高效的c a c h e 系统；而一个有效的c a c h e 系统需要一 个优秀的c a c h e 替换策略。本文通过实验来比较l r u 、a r c 和l f u 策略各自的特点和 使用范围，发现它们都未能适应s n s 这类用户活动驱动的w e b 系统。在此，需要使用 一种基于用户对象影响度的新式的c a c h e 替换( l f i ) 策略。实验证明，l f i 策略在s n s 类w e b 系统的性能优于其他策略。 本文的内容安排为：第一章介绍了c a c h e 替换算法的相关研究工作，对各种算法 的特点进行介绍，重点介绍了基于时间局部性的l r u 算法、基于空间局部性的l f u 算法以及一种动态自适应的a r c 算法；第二章建立模型并模拟各种w e b 应用环境下 的对象请求序列，通过实验比较，研究了用户行为驱动( u d m ) 模型的s n sw e b 系 统下传统的c a c h e 替换算法的不足；第三章针对s n sw e b 系统的对象请求序列的特 点，设计一种新型的l f ic a c h e 替换算法；第四章使用实验的方法对l f i 算法的性能 进行测试和评价，还测试了算法在不同参数模型下性能的稳定性；最后，第五章对7 全文做出总结并提出今后研究的方向。 一种面向活跃用户的种bc a c h e 替换策略 第l 章c a c h e 替换算法的相关工作 第1 章c a c h e 替换算法的相关工作 本章对常用的c a c h e 替换策略的相关工作进行总结。按照时间时间局部性、空 间局部性和自适应性对c a c h e 替换算法进行大致的分类。简要介绍各种c a c h e 替换 算法适用的场合。 1 1c a c h e 替换算法的类型 按照c a c h e 对象的大小来划分，c a c h e 替换算法可以分为对象大小相同的替换算 法和对象大小不同的替换算法。 硬件和操作系统上使用的c a c h e 都管理固定大小的页面，以页面为单位进行数据 的换入和淘汰。w 曲c a c h e 管理的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 替换算法。对象独立的c a c h e 替换算法考虑 c a c h e 对象被的大小、最近读取时间、最近被读取的次数等等自身的因素，但没有考 虑到对象和对象之间的关系。在一般的系统中，c a c h e 对象之间往往存在着相互联系 的。这种相互联系在设计c a c h e 算法时有很重要的价值。文 1 】中研究一个文档查询系 统的c a h c e 算法，尽量淘汰当前语义相关度最低的文档，取得比l r u 、l f u 、s 亿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 容器中可能会被访问到的对象。 4 一种面向活跃用户的w e bc a c h e 替换策略 第l 章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 替换算法 的效果可能无法适应这种变化，导致效果变得很不理想。自适应的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 算法。 k r l s h n a m u r t h y 和r e ：o r d 归纳过【3 】，c a c h e 替换策略考虑的因素主要有： 崭新性：由对象最后的访问时间决定。 访问频度：对象被访问的次数； 大小：被c a c h e 对象的大小； 读入成本：从原始存储中取得对象的时间花销； 修改时间：对象的最后修改时间； 有效期：有效期已过的对象可以无条件淘汰； 以下介绍的替换算法大都使用了上述的一种或者多种特性来设计合理的c a c h e 替换算法。 1 2 访问时间敏感的c a c h e 替换算法 l r u ( l e a s tr e c e n t b ，u s e d ) 算法 l r u 算法维护c a c h e 对象最后的访问时间，总是淘汰c a c h e 容器中最旧的对象。 l r u 算法是基于对象访问的时间局部性假设：现在访问的对象在很短的将来很有可 能被再次访问。l r u 算法非常容易实现，而且是一种比较有效的c a c h e 替换算法。l r u 算法需要维护一个按照最后访问时间排列的堆结构，淘汰c a c h e 对象只需要从堆中删 除元素即可；如果访问请求序列变现出了很好时间局部性，即满足了文【2 】提到的 s t a c kd e p t hd i s t r i b u t i o n ，l r u 算法是最佳的c a c h e 替换策略。因为l r u 算法简单而且 种面向活跃用户的w e bc a c h e 替换策略第l 章c a c h e 替换算法的相关工作 高效，其在数据库查询c a c h e 、内存页面管理c a c h e 和w 曲对象c a c h e 方面都有很多应 用。流行的m e m c a c h e d 软件就是采用了l l 砌替换策略对( k e y ，v a l u e ) 类型的c a c h e 对象进行缓存，降低应用程序读写磁盘和数据库的次数，获得系统总体性能的提升。 众多的使用经验表明，l r u 替换策略基本能满足普通如新闻资讯、门户和论坛 等普通w e b 应用的需求。 l r u 算法的伪代码框架如下： a l g o r i t h m ：l r u 算法，当c a c h e 容器满的时候，淘汰c a c h e 容器f 1 最近最少使用 ( l e 觞tr e c t l yu s e d ) 对象 i n p u t ：对象访问序列r l ，眩，r 3 ，m m e t h o d ： 对任意t = l ，r t 为当前访问对象，将发生以下各种情况 c a s el ：r t 在c h e 容器中 在c a c h e 容器中移除r t 把r t 插入到c a c h e 容器m r u ( m o s t 代虻e n t l yu s e d ) 位置上 c a s e 2 ：n 不在既c h e 容器中 w h i l e 插入后c a c h e 容器超过最大容量 删除c a c h e 容器l r u 位置的对象 ) 将r t 插入到c a c h e 容器的m r u 位置上 表1 1l r uc a c h e 替换策略 根据不同的访问请求的特点对l r u 算法进行修改，产生了很多l r u 算法变种。 有的研究l r u 中的对象访问的序列，提出“冷页”和“热页”的概念和应用，另外有的 算法研究c a c h e 对象的大小对c a c h e 命中率的影响。冷热页的算法较多的应用在数据 库系统和操作系统等c a c h e 对象的大小相对固定的环境中；结合s i z e 的l r u 算法则较 多使用于互联网系统( 如c a c h ep r 0 x y ) 等环境中【4 】【5 】 6 】，因为它们要处理的c a c h e 对象的大小相差可能很大。 6 种面向活跃用户的w e be a c h e 替换策略第1 章c a c h e 替换算法的相关工作 l r u k 算法 文 7 提到一种重要的l r u k 算法，是简单l r u 算法的一个重要改进。l r u k 算 法在数据库页面c a c h e 中应用很广：包括m i c r o s o f ts q ls e r v e r 和m y s q l 等厂商都使用 这个算法进行数据库页面c a c h e 淘汰。该算法保留了最近k 次访问c a c h e 容器的时间， 使用时间信息估计c a c h e 对象被访问的时间间隔。l r u k 算法的实现并不复杂，带来 的簿记开销也相对较小。 假定有页面请求序列r l ，r 2 ，r t ，定义对象。的向后k 次路径为b 。( o ，k ) 为。到最近k 次访问页面集合的路径长度。长度用如下公式定义： 公式1 2l r u - k 算法向后k 次路径 l r u k 算法总是淘汰b o ，k ) 值最大的对象，如果该值为正无穷大，则使用另外 一种备用的c a c h e 淘汰算法( 如l r u ) 去选择页面进行淘汰。 经验表明l r u k 算法比单纯的l r u 算法( 实质上是l r u 1 ) 要好。而且这个算 法可以根据页面请求序列的变化进行自适应。可以针对系统特点对k 参数进行调节， 经验表明当k = 2 ( 即l r u 2 ) 的时候c a c h e 系统的性能通常都非常好。 2 q ( t w oq u e u e s ) 算法 2 q 算法是受到l r u k 算法的启发对l r u 2 算法进行改进，使算法的形式更加简 单更加高效【8 。2 q 算法首先承认了l r u - k 算法的优势：最近k 个被访问的页面优先 会被保留在c a c h e 容器确实提高了c a c h e 系统的命中率。k 取2 的时候，即l r u - 2 算法 的运行速度和命中率都非常高，是一种简单而高效的l r u k 算法。 2 q ( t w oq u e u e ) 将缓存中的页面分成冷页和暖页，分别维护两个f i f o 队列a l 和 a m ，a l 保存着c a c h e 系统的冷页，a m 记录着当前系统暖页。当个页面首次被访问 时，进入a 1 冷页队列；当访问的页面p 已经存在于a 1 中时，系统认为p 是可能是一 个暖页，将会把p 从a 1 移动到队列a m ，p 成为暖页。 7 一种面向活跃用户的w e bc a c h e 替换策略 第l 章c a c h e 替换算法的相关工作 2 q 算法的伪代码如下： a i g o d t h m ：2 q 算法。分别使用冷页和暖页两个队列来淘汰最近最少使用的页面 i n p u t ：对象访问序列r l ，r 2 ，r 3 ，m m e t h o d ： 对任意t = l ，n 为当前访问对象，将发生以下各种情况 c a s el ：r t 在暖页队列a m 中 在a m 中移除r t 把r t 插入到a m 队列的m r u ( m o s t r 。c e n t l yu s a g e ) 位置上 c a s e2 ：r t 在冷页队列a i 中 在a l 中移除r t 把r t 插入到a l 队列的m r u ( m o s tr e c e n t l y 憾a g e ) 位置上 c 觞e 3 ：r t 不在任何队列中 i f a l 队列长度 伽髑h o j d 删除a l 队列l r u 位置上的对象 ) d s e 删除a m 队列l r u 位置上的元素 ) 将r t 插入到a l 队列的m r u 位置上 表1 32 q c h e 替换策略 上面算法中的t h r e s h o l d 比较重要。如果t h r e s h o l d 值太小，系统太偏向于热页的处 理而忽略了冷页，在很多场合下是不适用的；如果t h r e s h o l d 过大，则导致系统对热 页的跟踪不够，和基本的l r u 算法效率相差不大。t h e o d o r e 和d e n n i s 【8 】给出的解决 方法是a 1 只保存一个页面指针值，可以维护一个较大的a l 列表，把更多的空间留给 a m 。 l r u m i n 算法 该算法偏好将较小的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 对象挪出更多空间。l r u m 烈算法需 要维护多个l r u 队列( 或者一个优先队列) ，如l r u l 表示大小为1k b ”e s 内的l r u 8 一种面向活跃用户的w e bc a c h e 替换策略第l 章c a c h e 替换算法的相关工作 队列，l r u 2 为lk b y t e s 一2k b y t e s 的l r u 队列等等。假设有l r u 队列l r u l l r u n ， 淘汰c a c h e 时先从l r u n 开始，如果l r u n 不为空，则选择l r u 页面进行淘汰，如果 l r u n 为空，则淘汰l r n n 1 依次进行下去，直至到l r u l 。l r u m 烈算法的考虑 了对象的大小，在c a c h e 对象大小差异较大的场合下有不错的表现【9 】【1 0 】。 i r i 卜t b r e s h o l d 算法 l r u - t h r e s h o l d 算法【1 1 】使用s i z e 作为一个重要的判断因素。该算法认为，既然s i z e 太大的对象进入c a c h e 容器会引起驱逐较多容器内的c a c h e 对象，对c a c h e 系统的命中 率造成了很大的影响，l r u - t h r e s h o l d 算法禁止s i z e 大于t h r e s h o l d 值c a c h e 对象进入 c a c h e 容器。这个算法在某些w 曲系统中对c a c h e 系统的提高有很大帮助，但问题是 t h 咒s h o l d 参数的选择对整个系统的影响较大。要使c a c h e 系统达到更高的可用，可能 需要其他辅助方法( 试探或者经验) 来得到合适的t h r e s h o l d 值。 s i z e 算法 对c a c h e 容器中的c a c h e 对象按照s i z e 排序，首先删除较大对象；对于大小相同的 c a c h e 对象，按照l r u 的策略进行淘汰。这个算法实际上是一个简化版本的l r u m i n 算法【1 2 】。 此外，还有l o g 2 一s i z e 1 3 】算法和p s s ( p y 豫m i d a ls e l e c t i o ns c h e m e ) 【1 0 】算法等， 它们都考虑了c a c h e 对象的大小对c a c h e 系统整体命中率的影响。得到的结论都类似 于l r u m i n 算法。 1 3 访问频度敏感的c a c h e 替换算法 访问时间敏感的l r uc a c h e 替换算法在对象请求的时间局部性很好的系统中非 常适用，但在w e b 系统中，有的c a c h e 对象访问的频度很高，有的则相对较低。频繁 访问到的c a c h e 对象应该尽量保留在c a c h e 容器中以提高c a c h e 系统的命中率 【1 4 】【1 5 】【1 6 】 1 7 】。这种系统的访问模式可以用独立的引用模型来描述( i n d e p e n d e n t r e 佬r c n c em o d e l ) 1 8 】：每个对象的访问概率是独立的，并遵守一个固定的概率分布 模型( 比如正态分布) 。在这种系统中，基于访问频度的c a c h e 替换算法l f u 的整体 9 一种面向活跃用户的w e bc a c h e 替换策略 第1 章c a c h e 替换算法的相关工作 命中率要比l r u 好。 l f u 算法 l f u 策略充分利用的访问序列的空间局部性( s p a t i a l l o c a l i t y ) ：频繁访问的c a c h e 对象将来很有可能会被继续访问。l r u 算法必须维护一个按照访问频度来排序的堆 结构。如果访问频度在c a c h e 对象开始进入c a c h e 容器才开始算，这种l r u 策略称为 i n c a c h el f u ：如果为c a c h e 对象维护一个离线( 离开c a c h e 容器后) 的频度计数，则 称为p e 睡c tl f u 策略 1 9 】。p e m c tl f u 的维护成本并不会比i n c a c h el f u 高太多，但 是在一些系统中p e 睡c tl f u 并不适用。历史访问频度高的c a c h e 对象，并不一定在将 来很长一段时间内都会被访问，该对象也可能“过时”后就很少被访问到了。一个明 显的例子是新闻资讯类的网站，某条热门新闻在一段时间内的访问次数可以被推得 很高，但是热度过了之后可能再也无人问津。所以p e 愉c tl f u 在某些情况下可能会 变得非常缺乏柔性。这个问题的解决是使用折衷的方案：只记录每个c a c h e 对象在一 段时间内的访问频度，其后访问频度即被重置为0 。 l f u ( b c a c h e ) 算法的伪代码如下： a l g o r i t h m ：l r u 算法，当c a c h e 容器满的时候，淘汰c a c h e 容器中l f u ( l e 雏tf r e q u u yu s 酣) 对象 i n p u t ：对象访问序列r l ，吃，r 3 ，m m e t h o d ： 维护一个龆c h e 堆结构，堆顶元素是访问次数最少的对象 对任意t = 1 ，r t 为当前访问对象，将发生以下各种情况 c a s el ：r t 在c h e 堆中 在c h e 堆找到r t 对应节点位置i r t 访问次数增l 在i 位置起重新调整堆 汹e 2 ：r t 不在c h e 堆中 w h i l e 插入后c a c h e 堆空间超过最大容量 删除c h e 堆顶元素，并调整堆结构 l o 一种面向活跃用户的w e be a c h e 替换策略 第l 章c 裙h e 替换算法的相关工作 将r t 插入c h e 堆得末尾 将堆顶元素和r t 互相交换 在堆尾开始调整堆结构 表1 4l f uc a c h e 替换策略 和l r u 算法相比较，l f u 算法的实现要复杂一些，算法时间复杂度也更大。单 一的l f u 算法也有不少缺点，一个重要的缺点是l f u 算法中访问频度值只会累加而 不会被减少。这个特点可能会导致短时间里得到大量访问的c a c h e 对象的频度升得很 高后，尽管以后再也不需要访问该对象，但因为对象的访问频度很高，所以迟迟不 会被淘汰出去，而白白占用的宝贵的c a c h e 容器空间。为了克服单一l f u 算法的这个 弱点，有很多l f u 的改进算法。 l f u - a g i n g 算法 顾名思义，l f u a g i n g 算法考虑了c a c h e 容器内对象的年龄。随着c a c h e 容器内对 象年龄的增长，系统想办法减少c a c h e 对象的访问频度值。这样长期没有被访问的对 象的访问频度值会被不断减少，直至被淘汰出去。文【2 0 】提到的l f u a g i n g 的算法的 实现思路是：维护一个系统平均访问频度值a v ，如果a v 超过事先规定的a v e r a g e t h r e s h o l d ，则把所有c a c h e 对象的访问频度减半，访问频度为1 的对象保持不变。另外， 规定一个m a xt h r e s h o i d 值，用于限制c a c h e 对象的最大访问频度，每个对象的访问频 度都不允许超过该值。l r u a g i n g 算法两个t h r e s h o l d 参数的选择非常重要，经常需要 根据系统的特点进行调节。 a - a g i n g 算法 文【2 l 】提到一个0 【- a g i n g 算法。a 是一个【o ，1 】之间的数字，用于减少c a c h e 对象的 访问频率。这个算法定义对每个c a c h e 对象定义一个访问频度值k ，再定义一个全局 的时间片值i n t e r v a l 。每次命中了c a c h e 容器内的对象后，k 值递增l ；在每个时间片 结束后，令k = q 宰k 。c a c h e 系统进行淘汰时，首先淘汰k 值较小的元素，从而保留k 值较大的元素，k 值一样时则使用l r u 策略进行淘汰。 一种面向活跃用户的w e bc a c h e 替换策略第1 章c a c h e 替换算法的相关工作 这种算法实际上是l f u 和l r u 算法的平衡。当诹较大值的时候算法强调访问频 度，更偏重于l f u 算法的特性，当0 【取较小值时访问频度削弱得很快，更强调l r u 算法的特性：特殊情况下，当萨0 时，算法退化为单一的l r u 算法；当a = l ，算法退化 为单一的l f u 算法。根据实际经验，选取合适的a 值应该可以找到一个平衡点，使得 c a c h e 系统的命中率到达较好的指标。 上面几个算法只是研究l f u 算法的访问频度老化的问题，下面的一个l f u 算法 则结合c a c h e 对象的s i z e 参数进行优化。 l f u 算法 l f u 算法在文 2 2 】中首次提出。作者对l f u 算法进行改进：进行c a c h e 对象淘汰 时，只会选择淘汰访问频度有l 的对象；如果将要进入c a c h e 容器的对象太大，淘汰 所有访问频度为1 的对象所释放的空间都不足以容纳它，c a c h e 系统会拒绝该对象进 入c a c h e 容器。l f u 幸算法能够防止访问频度低的大对象进入c a c h e ，解决了大c a c h e 对 象的问题，但也不能解决c a c h e 访问频度老化的现象。所以l f u 算法一般需要结合 l f u a g i n g 或口- a g i n g 来使用。 l f r 算法 文【2 3 】中介绍一种l f r 替换策略。l f r 和l f u 算法的算法框架类似，不同的是l f r 记录的不是c a c h e 对象被访问的次数，而是记录c a c h e 对象被移除的次数。当c a c h e 对 象p 被淘汰时，p 的移除次数k 增1 。当p 再次被访问时，除了把p 放入c a c h e 容器外，还 需要将c a c h e 容器中对象按照k 值来排序。当需要淘汰对象时，优先淘汰k 值较小的 元素，如果k 值相同，可以按照f i f o 或者l r u 策略进行淘汰。 l f r 算法可以和l f u 算法结合起来使用，称为l f r l 2 。l f r 2 使用l f r 1 中被淘汰 c a c h e 对象的k 值作为该对象下次进入c a c h e 容器的访问频度的初始值。 1 4 自适应的c a c h e 替换算法 上面介绍的c a c h e 替换算法都是基于一个固定的策略的。固定策略的c a c h e 替换 算法在对象请求模式固定的情况下很有效。然而，有些系统的对象请求模式不是一 成不变的，系统可能在不同的时间段内表现出不同的特征：有时候时间局部性特性 1 2 一种面向活跃用户的w e bc a c h e 替换策略第l 章c a c h e 替换算法的相关工作 较强，有时候空间局部性更明显。如果c a c h e 系统能够挖掘和识别当前的系统请求特 点，对c a c h e 策略进行自我调节，这样就形成了一个自适应的c h e 替换算法 【2 4 】 2 5 】【2 6 】。 在c a c h e 中使用两种不同模式的c a c h e 替换算法( 比如l r u 和l f u ) ，初始时适用 l r u 策略进行淘汰，如果在一定时间的观察期间，l r u 策略的命中率无法达到一定 的期望值，可能是系统的对象请求模式发生了变化，则尝试使用l f u 策略进行替换； 同样，如果l f u 策略的c a c h e 命中率无法满足预期要求则换用l r u 算法。使用这个策 略可能会提高c a c h e 系统的灵活性和c a c h e 命中率，但存在的问题是l r u l f u 这两种 模式进行切换的时机很难确定，以及两种模式的切换的资源的开销比较大。以下介 绍一种自适应的c a c h e 替换策略a r c ( a d a p t i v er e p l a c e m e n tc a c h e ) 【1 8 】。a r c 算法 的好处是它是完全自适应的，能够自动在l r u 和l f u 之间取得很好的平衡：当c a c h e 系统的对象请求的时间局部性很强的时候，它的表现能够和l r u 、2 q 等算法的效果 相当；当c a c h e 系统的对象请求的空间局部性较强的时候，它能够自动调节策略，达 到l f u 策略的效果；当c a c h e 系统的请求慢慢的发生改变时，a r c 算法可以逐渐进行 参数调节，保持c a c h e 系统较好的命中率。另一方面，a r c 算法的实现相对简单，时 间空间复杂性也较低。 a r c 策略维护两个l r u 列表l l 和l 2 ，l l 列表里面的c a c h e 对象仅仅被访问过1 次， l 2 列表里面的c a c h e 对象至少被访问过2 次以上。a r c 算法认为l 1 反映了c a c h e 对象的 时间局部性，l 2 反映了c a c h e 对象的空间局部性。 在最多容纳c 个对象的c a c h e 容器中，l 1 ，l 2 的总长度设置为2 c 。a r cc a c h e 替换 策略如下： ( 1 ) 系统初始化的时候，l 1 和l 2 都为空。 ( 2 ) 如果l l 内有c 个c a c h e 对象，淘汰l l 内的l r u 对象，否则淘汰l 2 中的l r u 对象 ( 3 ) 如果c a c h e 对象在l 1 或l 2 中，则该对象被移动到l 2 的m r u ( m o s tr e c e n t l y u s e d ，最后被淘汰) 位置上 1 3 一种面向活跃用户的w e bc a c h e 替换策略第l 章c a c