【doc】一种新的优化WEB缓存一致性的进化算法

【doc】一种新的优化WEB缓存一致性的进化算法 一种新的优化WEB缓存一致性的进化算法 第22卷第8期 2001年8月 小型微型计算机系统 MINI—MICRoSYSTEM 文章编号:1000-1220(2001)O8—0940-03 一 种新的优化WEB缓存一致性的进化算法 铁玲诸鸿文戎蒙恬 Vol22No.8 Aug.2001 (上海交通大学电子工程系上海200030) 擅要:在WEB服务暮和客户之间引凡WEB缱存可咀缱解网络的拥塞,降饭客户请求延时WEB缱存的一致性是 WEB缓存研究的堆点之一,其决定缱存的可用性和正确性.奉文提出了一种用进化计算采优化WEB缱存一致性的方 法,奎局搜索出最新鲜的宴律八缱存,使得缱存中的敷捂和服务暮的数据曩一致.奉文采用的实验教捂是圆外实验室 的TRACE敷捂.通过甘真,进化算法&善了缱存的一致性 美?词:WEB缓存I进化计算f遗传算法I一致性 中田分类号:TN929.5ITNgl3.24ITN9l3.?文献标识码A 1引言 www的引人使得INTERNET成为世界上最快速增长 的媒体,并引起网络上负载的动态增长.由于服务器访问的瓶 颈,用户访问延时增加,网络拥塞.为改善性能,在WEB服务 器和客户方之间增加放置服务器内容的缓存,并放在靠近客 户方;当用户请求相同的WEB内容时,可以不必访问服务 器,而只要访问缓存.这样在很大程度上减少INTERNET网 的拥塞,降低网络流和访问延时.通过模型分析,www流的 访问特性呈现”短期局部性,即在一段时间内.在用户提交的 访问请求中,先后出现相同请求的概事比较高.这种短期局部 性为我们设计缓存机制提供了理论根据.? WEB缓存力求保持数据的新鲜程度.当服务器中的一页 被修改时,而缓存的页没有被恪改,引起了发送到客户的页的 内容将与服务器的内容不一致,这就是一致性问题.目前最简 单地实现一致性问题的方法n是使用每一页的存活时闻 (TTL),当一个客户请求在TTL后到达缓存,缓存送一个 I~Modified-Since(1idS)信息到服务器,来决定放置在缓存 中的版本是否有效.TTL的设置报重要,如果足够小,缓存的 一 致性能得到保证,但额外增加了网络负担.TTL过大,缓存 的一致性难于保证.另外一种方诖0是服务器跟踪所有的客 户,在页进行改变以后,通知客户.并发送内容无效信息到缓 存在有限的生存期,这种策略是有效的,但这将增加服务器 用来保留每一页上每一客户的状态的花费,并且可扩展性不 好另外还有一些方法,其把1rL和服务器通知结合起来. 由于缓存的内容巨大,用简单的一致性算法不船达到全 局最优解进化计算已经被用于解决许多最优化问题和自 适应改变的环境的计算问题,其对数据规模巨大的问题求解 有良好的性能.遗传算法是进化计算的一种主要的方法.本文 给出了一个基于进化计算的WEB缓存的优化模型,其采广泛地用于组织优化,机器学习,自适应控制,规划设计 和人工生命等领域.遗传算法是具有”生成+检测”的迭代过 程的搜索算法. 图l遗传算法过程 遗传算法是一种群体型操作,该操作群体中的所有个 体为对象,选择,交叉,和变异是遗传算法的3个主要操作,使 得遗传算法具有了其他传统方法没有的特性.遗传算法中包 括如下5个基本要素:1)参数编码;2)初始群体的设定;3)适 应虚函数的设计}4)遗传参数设计5)控制参数的设定 标准 excel标准偏差excel标准偏差函数exl标准差函数国标检验抽样标准表免费下载红头文件格式标准下载 的GA产生一初始群体,其在每一新的代中进行修改在当前 的群体的个体被解码,并按前预先定义的质量策略来评价 每个适应度评价是一报重要的参数,通常作为问题的描述.遗 传算法的操作主要有两种t(1)交叉通过在两个实体之间,接 旦塑兰二蔓里营奠研究生主要从事11~网方面的研究.堵鸿文教授.博士生导师研究方向宽带阿培和阿培安生技术及平流层通信?或簟恬,教授博士生导师.研究方向竟带用培性能分析和优化.……一 铁玲等:一种新的优化WEB缓存一致性的进化算法 一 定的概率来执行,标记两个实体其交换父串的部分父串 部分的交换通过在特定的位裁减来执行.其尾部交叉产生两 个新的串(2)变异被介绍用来阻止局部最优解,其通过随 机采样,在交叉后,通过小的概率来改变.GA已经被正确 实现.群体将进化到有最好的适应度的全局最优的结果,其 过程如图1. 3遗传算法缓存一致优化模型 采用遗传算法实现缓存一致优化主要有以下两个主要的 原因:(1)遗传算法的基本观点是基于群体的进化,其策略是 适者生存,缓存通过这种技术来选择最适合的信息实体}(2) 遗传算法对超大空间有很好的性能,而缓存一般包括上亿条 实体,在规模上更加适舍用遗传算法. 为建立缓存一致性进化模型,我们采用以下的假设: ? 缓存是个体的群体}每个实体用一文件名标记. ? 每一宴体被分配一适应值,来 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 示实体的新鲜度. ? 缓存一致化算法能按规定的时间间隔对数据进行修 改,并产生全新的缓存数据.缓存一致性的进化模型是一NP 完全问题,其数学模型可用如下方法来表现: 设服务器中的有数目为n,尺寸为S={St,&….,S)的 实体.缓存的容量为C,要求找出n十物体的一十子集使得其 在满足晟大新鲜度的前提下,尽可能多的填满容量为C的缓 存设W—fW,W.,?)是文件被存取的有最大新鲜度 的收益. 9t1 遗传编码的方磕采用二进制编码 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ,其编码变量为x, 长度等于n,表示服务器中的n十实体是否放入缓存,咒一1 表示该物体装入缓存,X,=o表示不装入缓存. 缓存一致性优化的模型为 MAX?x(1)?一1 满足厶&x.<=c(2) 其中x?{0.1)1??(3) 一 设缓存一致性优化的吕标函数为J(x)=乙xw-按照 惩罚函数处理约束条件的方法,我们所构造的缓存问题的适 应度函数,(x)如下式,(x)=,()+g(x)式中g(x)为 x在超越约束条件下的惩罚函数,惩罚函数”可以构造如下: 0 g(x)一 1腿(c一?X.s), C一?五s>=o._ () C一?X矗<0 式中点1-为wt/Si(1=<i<=n)的最大值,为合适的 惩罚函数对于其中的收益w,可以通过计算一收益函数 (ts--f..)来实现.其中f:最后一次被引用后所经历 的时间}S:文档的大小}ft远程检索该文档所需要的时 间}rUl:瑗置的文档最后一敬被修改的时间.:最后一敬被 引用的时间,表达式嘟如下; …,, 1(】f口+2s,)+(3+?s,)/C,r砒).当埋存中的文档未过时 „“„„„兰1—1,当缓存中的文档已过时 这里的,,s,.为常数,其值决定于优化吕标.这样的最好的选择..在本设计不但考虑其新鲜称度,还考虑诸 些目标可能使得某些专门的文档的命中率最大.也可能使任如尺寸等方面的因素. 意用户直观上感觉上的检索时间最短,或者是新鲜度最大.其具体实和变异的概率. par2<=se[ecdon(popsize.fitness,old--pop) ?f(arl,parZ,o【d-pop,new-p~ptp一08) mutationtnewpop?口mrate) staostiea[——report(new——pop) old—poP<一newpop generation<generadon+1 圉2基于遗传算珐的缓存一致优化模型 针对不同的目标,用拉牿朗日方法对w,进行逼近求解,即可 得到适合的w值.何如-当出现极端的情况.w一w产w一 w?0对-就为w~ti/(rt一rtt1.),文本的相应新鲜程度对于一 致性算祛-在进行进化计算时.缓存的各代按特定的与实体效 益相美的适应度函数来进化.我们采用WEB的squid和 NSCAlog文件字段来计算实体教益,并作为实体的适应度函 数.所需的宇段为datehdr(f):HrTP的访同时间Ireal—len (.):HTTP的尺寸~]astmod(fz):HTTP的最后修改时同; expires:实体的生存期.由于适应度函数驱动遗传种群的进 化-标记缓存实体的新鲜度的适应度函数将是对缓存策略遮 4仿真结果 仿真器被测试并且通过NSCA及SquidTraces和相应 O5oo100口1500200025?3000 In?- 图3用户检索时闻 小型般型计算机系统 的LOG文件来 证明 住所证明下载场所使用证明下载诊断证明下载住所证明下载爱问住所证明下载爱问 其有效性.所采用的TRACE参考1997 年Oct到Dec阶段的信息并且有信息实体其参照l0天的 TRACE阶段.遗传算法在命中率降低时应用于缓存种群其 中,=500hytas/s,2=100,岫=2000hytes/s.一lOs, 共开设2M的缓存.我们设定交叉概率为0.6,变异概率为0. 0333,通过实验可知.平均的适应度函数将降低,这样缓存能 有更新鲜的实体适应度.经过进化,g讧和jpeg类型将是每一 代最经常使用的实体.用户的命中率可以用用户检索时间表 示.其性能有所提高如图3. 5结论 本文通过使用进化计算中的遗传算法,研究了保持缓存 的一致性的最优化方法.仿真过程几乎包括了TRACE文件 中研究此模型的所需要的所有参数遗传算法被证明是非常 有效的. 在夸后的工作中.主要是定义不同的适应度选择策略,以 及其对缓存一致性的彤响.其他的进化计算策略(如模拟褪火 算法,阀值接收)也将用于缓存一致性问题.并比较它们对其 性能的彤响. 参考文献 2001年 1Cate.V.A1缸.AgloDlefilesystem[C].Inproceesingsofthe 199ZUSENIXFile曲8t~:mWorkshop(AnnArbor,MItMay 1992) 2V且bdat,,eA~tham,PandAaderson,T.WebFS;Aglobal cachecoherentm删y3健加[R]Tech.rep.DeptolEECS.UC BerkeleyDBC,1996 3D.Gold~gIGenericAlgorithmsiaS~arch,Optimization,and MachineLeamingCM]Addison~Wesley1989 4M.Baentsch=EnhancingtheWeb8lnfr~structureIFrom CachingtORepliactioaCJ3IEEEInternetComputing,Mar-Apr 19971(2),18,27 5A.BestAvrc~.RL.C&rt…dM.CrovellaIApplication-leveldoe— umentcachingintheinternet(C]Proceedingsof2I力tnational WorkshopinDistributedandNetworkedEnvironments.SDNE 1995 6J.GwcnmnanandM.Seltzer:ridWideWchcachecoasisten cy[C].ProceedingsoftheUSENIX1996AnauelTechnics[Con ference.SanDingo,C且nfornia.Jan1996141,l5l 7T.Starkweath~,D.WhideyandKMachias:Optimizationusing distributedgeneticalgorithmsIparallelprobtemsolving【M] SpringerVerlng1991 8D.WesselsIInte[1igentcachingworid—widewebobjeelsCC3.P ceedingsoltheINET95ConferenceJ肪1995 ANEWKINDOFEVOLUTIONARYALGORITHM FOROPTIMIZINGWEBCACHINGCONSISTENCY TIELingZHUgong-wenRONGMeng-tian (脚 lEgectronlcEngeeringShanghaiJiaotongUni~frsity,Shanghai200030.China) AbstractIntroduciggWEBCachebetweenserverandclientwillavoidnetworkcongestion.reducec[ientrquestdelav.WEB cacheconsistencyisoneofthemostdifficuhquestionintheresearchareaofwebcache,ItcJRnresultintheperformanceofthe avafiahfikyandrealityofwebcache.Inthispaper,Weproposeakindofevolutionaryalgorithmtooptimizethewebcachec0n— sistency?andsearchtheIX?f0Stfreshobjectputintocache.WeUSetheTRACEdataoftheforeigntabThroughsimulation,We canfindthatthisalgorithmimprovethecacheconsmtencv. KeyndsWEBcacheIEvolutionaryalgorithm~GA|Consistency