基于多查询特性的搜索引擎缓存替换策略研究

房耘耘（同济大学电子与信息工程学院，上海　201804）

基于多查询特性的搜索引擎缓存替换策略研究

房耘耘
（同济大学电子与信息工程学院，上海201804）

0　引言

互联网飞速发展，对人们工作和生活影响日益加深。搜索引擎作为从互联网海量信息获取有效信息最快捷的方式，获得广泛使用且重要性日益提升。面对互联网上存在高速膨胀的海量信息，为了返回用户准确全面的查询结果，搜索引擎需要爬取和处理较以往更大数据量的网页。搜索引擎查询计算过程中读取磁盘上的查询词的索引文件涉及大量I/O操作，合并查询词索引、查询词与网页相关性计算以及查询结果排序等涉及大量计算。为了保证用户的搜索体验，搜索引擎需要求实时返回查询结果，高并发用户请求带来的大量计算给搜索引擎系统带来了巨大的挑战。伴随搜索引擎发展不断出现新的技术以解决挑战，其中包括大规模并行处理、提前停止、索引压缩和缓存技术等。

缓存作为一种高效的技术广泛应用在计算机各领域中，如CPU Cache、操作系统内存页缓存、Web缓存和数据库缓存等，同样缓存作为增强搜索引擎性能的高效方式得到业界广泛应用和学术界关注。搜索引擎缓存通过把一些查询结果保存在速度较快的内存，许多查询可以从缓存直接返回结果，避免了查询处理过程中的大量计算和I/O操作，显著节省计算量，减轻搜索引擎后台查询处理压力，增强搜索引擎的响应性，节省硬件资源并提升系统效能。

缓存随着命中率提高优势愈加显著，缓存命中率为：Hit=Requestcache/Request，即被缓存满足的查询请求次数除以总查询请求次数。带缓存的搜索引擎系统的平均响应时间定义为：Taverage=T1×Hit+T2×（1-Hit），其中T1表示缓存服务器查询请求响应时间，T2表示搜索引擎查询处理服务器响应时间，由于T2远大于T1，因此提高缓存系统命中率可以大幅减少搜索引擎系统查询结果返回时间。随着缓存满足查询请求次数的增多发送到搜索引擎后台的查询请求比例会降低，搜索引擎查询服务器的工作负载会降低，搜索引擎系统在单位时间内可以响应更多的查询请求，因此可以提高搜索引擎查询请求吞吐量。因此本文采用缓存命中率作为衡量缓存替换策略优劣的指标。

由于缓存空间有限，当缓存中存储的查询结果占满缓存空间后，需要从缓存中替换出一部分数据为新的数据留出空间。为了缓存有较高的命中率，需要替换未来访问次数最低或未来较长时间不会出现的查询结果。缓存替换策略的工作是确定要替换掉的查询结果数据，以最大化缓存命中率。

2　相关工作

2.1当前搜索引擎缓存替换策略分析

缓存管理策略主要分为静态策略和动态策略。静态策略通过统计分析搜索引擎查询日志，将当前一段时间内访问频率最高的查询词对应的返回结果放到缓存中，这是一种离线方法，缓存内容在一定时间内不会发生变化。周期性地对最近历史访问记录进行统计分析，获取最近的高频访问查询更新缓存数据。因为缓存中加载的是流行的查询，热点查询的请求次数占了总查询量的很大一部分，命中率在较小缓存空间下较动态缓存有优势。一段时间内不发生缓存替换，并发访问模式效率高。缓存中是过期的数据，昨天流行的数据在今天不一定流行，不利于捕获大量时效性高的随机查询数据。文献［2］基于用户查询日志比较了动态缓存替换策略LRU，LRU策略的变种：FBR、LRU/2以及SLRU和静态缓存策略的命中率，得出静态缓存对较小容量缓存效率更高，相对动态缓存策略在较小缓存空间下命中率更高，随着缓存容量增大带来的有效性增益不如动态缓存增长快。

动态策略中随着数据项被访问，在缓存数据缺失和缓存空间饱和时会分别导致数据项加载和替换，引起缓存内容不断发生变化。由于缓存具有容量限制，当缓存空间满时要加载新的数据项需要首先采用某种替换算法将部分缓存的内容替换出以留出空间容纳新的缓存数据项。著名的替换算法有LRU，LFU，LRU/2，SLRU等，这些算法分别依据缓存数据项的访问时间信息，频次信息等作为替换依据。

静态和动态混合的缓存策略［5］，充分利用查询的时间局部性和空间局部性。通过历史查询记录分析将访问请求频次最高的流行查询及对应结果放入静态缓存，静态缓存中的数据在一段时间内只读不发生数据替换。其余缓存空间通过指定的替换算法动态管理，用来服务不在静态缓存中的查询。动态和静态相结合的替换策略获得超过单纯动态和静态替换策略的缓存命中率。但也存在动态空间被压缩，捕获随机查询能力下降；数据过时问题，浪费缓存空间；没有统一的数据管理策略，缓存数据查询存在重复请求问题。

文献［8］提出基于查询词历史访问记录特征信息和代表查询词自身特性的指标。证明了缓存命中率随着替换算法涉及特性的增加而提升，充分利用查询的访问特征信息是提高缓存命中率的关键。利用数据统计和机器学习的方法相比直接设计特定的缓存替换算法更为准确，取得较高的缓存命中率。但缓存管理方式复杂，成本高昂，可用性低。

概率驱动的缓存策略［3］，通过统计计算之前提交的每个查询的概率分布，概率模型用来标识特定查询结果页未来访问概率的大小，并基于概率模型来预测用户请求的查询结果页并将对应的查询结果提前放入缓存来提高缓存命中率。文献［6］通过鉴别不常见查询词，在缓存管理策略中引入了缓存进入控制策略阻止用户查询中不活跃的查询词对应的查询结果进入到缓存，避免了不常见查询进入缓存占用常见查询词的空间引起缓存命中率下降。缓存进入控制策略用查询词的过去访问频率预测其未来的访问频率，通过一个初始化训练阶段可以计算得到查询词的过去访问频率。文献［17］给出了确定相关查询和预取的方法。文献［18］提出了预取特定的查询结果页面的方法。文献［7］和［10］研究了不同数据类型的缓存和空间分配比。文献［9］提出在大规模矩阵式搜索结点阵列存在的情况下，通过数据副本和数据聚集，增加位置缓存把搜索请求路由到特定查询结点来优化缓存系统和提升搜索引擎的资源利用率，提升搜索引擎的吞吐量并减少用户延迟。文献［19-20］研究了搜索引擎缓存数据的时效性问题。文献［20-21］研究了搜索引擎缓存对查询计算节省量的问题，引入了查询词索引长度并结合缓存替换算法来量化查询计算节省量。

当前搜索引擎缓存研究启示：要重合运用查询特性信息，从数据中学习，设计符合查询分布规律的替换策略，实现高效的替换算法。

2.2搜索引擎查询分布研究

本文试验所用数据来自搜狗搜索实验室提供的用户查询日志，数据文件为搜狗搜索引擎2008年6月份的用户查询点击日志，日志文件按天划分，每天约170万条记录。每条记录的格式为：访问时间、用户ID、查询请求、该URL在返回结果中的排名、用户点击顺序号和用户点击的URL。缓存策略命中率测试中，采取以第21-27日查询预热，测试第28日命中率的方式，因此在研究查询整体分布时，本文对21-28日查询日志进行整体分析。

大量搜索引擎日志分析显示出搜索引擎访问记录数字统计特性符合一定全局性的规律。用户的查询、点击URL、查看结果页面的频次具有Power-law分布特征［15］；并且不同查询、不同用户和不同点击URL的数量满足Heaps定律［11-12］。Heaps［16］定律折射出：尽管搜索引擎总查询量巨大，但不同查询串的数量不会急剧增长，会保持相对稳定。因此空间适当的搜索引擎缓存不会出现大比例的缓存数据项替换，从理论上保证了搜索引擎的效能。

局部性是缓存能够起作用的理论基础，在计算机领域中指程序在一个段时间内执行期间访问地址在一定范围。本文通过对查询日志统计分析验证了查询请求的局部性，少数高频查询占据了总查询请求次数的大多数。通过搜索日志分析发现：频次最高的20%查询占据了约80%的查询请求量（图2）。占不同查询数较少的搜索频次排名靠前的高频查询占到总查询次数的很大一部分，表明缓存高频查询是提升命中率的关键。

搜索引擎查询时间局部性表现为：对于查询请求序列（Q1，Q2，Q3，…，Qn），Qi（1≤i≤n）表示第i次查询请求，当i＜j时，若Qi=Qj则称Qi在间隔d=|i-j|距离产生重复查询，d被称为查询复用距离。查询复用距离如图1所示，可以看到多数查询的复用距离集中在间隔相对较小的范围内，但是进一步通过统计分析查询词的查询间隔距离可以发现，有相当一部分查询的间隔跨度较大，LRU等动态替换算法管理缓存时会造成后续相同查询缓存缺失，不能复用查询结果产生缓存增益。一部分常见查询间隔较大，捕获这部分查询有利于提升缓存命中率。

以查询热度代表了当前该查询的访问情况，日志分析发现：一段时间内查询访问次数较高、用户数越多，查询结果点击次数较高查询热度越高。捕获热点查询是保证高缓存命中率的关键。查询间隔时间越长、最近未访问时间越久，预示着查询词冷却，未来一定时间内被访问概率变小。

图1　查询复用距离（log-log）

图2　查询频率排名（log-log）

3　基于多查询特性的未来价值函数

传统缓存替换算法如LRU，LFU及其变种以时间和频率作为缓存替换依据，通过多级队列区分单次查询和多次查询等，无法细粒度区分数据项的缓存价值，不能准确的缓存高缓存价值的数据。没有根本解决LRU对大间隔查询捕获不足和LFU的数据污染问题。基于对象大小的替换算法Size和GDSF等主要考虑数据项大小等特性，基于目标函数的替换算法LUV和Mix等复杂替换策略考虑了众多参数但不一定准确符合实际需要。搜索日志分析可以发现：用户查询词分布范围较广，查询词之间没有直接联系和规律，查询请求量有阶段性变化，查询的时效性和频繁性也有较大不同。广泛的查询词范围和不稳定的搜索请求量使得传统缓存替换算法的有效性降低。用在搜索引擎缓存替换策略中，上述缓存替换策略不能充分合理的利用查询请求历史记录中众多统计指标，替换函数不一定符合实际查询分布规律，不能准确确定数据项的缓存价值以提高命中率。

传统替换算法对查询请求的规律参考不足，对查询的时效性，突发性和常见查询等查询分布没有针对性设计，所使用的目标函数不一定符合真实查询请求规律，不能充分利用查询请求历史对未来查询的预测作用。现有缓存替换算法采用一个访问信息指标或几个指标的简单组合作为查询词对应查询结果数据项的替换依据，用在搜索引擎缓存替换策略中，不能充分利用查询请求历史记录中众多统计指标。研究表明基于多特性的缓存替换算法在命中率方面高于现在通用算法，且随着算法涉及特性的增加缓存命中率也提升，这说明充分利用查询中呈现的特性是提高缓存命中率的关键。经典方法没有以最佳的方式利用查询特性，从数据中学习比直接设计替换算法有更好的优势。与直接设计特定的缓存替换算法相比，利用数据统计和机器学习的方法更为准确，特别是在搜索引擎有大量搜索日志可以利用和复杂替换算法的开销与查询处理开销相比较小的现实情况下。

本文致力于充分利用查询词的历史统计信息作为缓存替换的依据以提高缓存命中率，设计新型缓存替换策略，弥补LRU替换策略对常见大间隔查询缓存命中不足的劣势。设计符合查询时效性的模型，基于数据分析中的多元回归方法确定模型参数值，做到模型参数随查询访问记录可调整，利用历史信息预测未来查询请求的可能性作为缓存替换依据，缓存替换算法采用替换掉未来最低访问可能的数据项，保留未来访问可能性高的数据项的方式来提高命中率。

搜索日志相关研究表明：一个查询的热度代表当前该查询访问请求情况，当前的热点查询和常见查询访问次数较高、访问请求的用户数多，查询结果的链接点击次数较高。另一方面：查询词请求出现的间隔时间越长以及该查询词最近未被访问的时间越长预示着该查询词的冷却。当前一段时间查询请求频次越高、请求访问的用户数越多以及查询结果的链接点击次数越多该查询词在未来倾向于被查询的次数越多；当前一段时间内某查询请求间隔时间越长以及该查询最近未被访问的时间越长表示该查询词访问热度较低，预示着未来一段时间内被用户请求查询的可能性越低。

依据以上分析，可以以查询词相关的各种历史统计特征作为参数建模，来标示查询词未来被访问的可能大小，继而作为缓存替换的依据。经过综合分析，提出以下六个查询词特性作为缓存替换的依据：

F1：查询频次，LFU算法的基础，代表了查询词的历史访问热度。

F2：独立用户数，代表了查询的广泛度和流行度。

F3：查询结果平均点击数，代表了用户对查询信息本身的兴趣和了解广度。

F4：最近未访问时长，代表了查询的最近访问时间特性，LRU的基础。

F5：最后两次访问时间间隔，重要的时间局部性特征信息，LIRS算法的基础。

F6：平均访问时间间隔，查询跨度内的平均查询间隔时长是综合的时间局部性度量特征，整体反映了查询的时间局部性强度和缓存效能。

经过全面分析，以：

作为查询热度值函数，其中F1-F6分别为：查询词的查询频次、查询词返回结果的平均点击链接数、该查询对应的独立用户数、查询最近未被访问时长（当前时间减去该查询最近一次的访问时间）、查询平均访问时间间隔以及最后两次查询的访问时间间隔，r1-r6为查询词特征值的指数系数，r0为比例系数，Y代表查询词的热度值。上式中特征值的指数和比例系数的引入使模型更符合实际情况，当前r0-r6的值未知，F1-F6可以通过查询日志统计分析得到，确定未知参数r0-r6的值是问题的关键。

本文所用搜索日志数据为按天划分的搜索日志，某一查询词当日出现次数和间隔时长往往和该查询词上次出现当日的查询词访问记录有联系。基于以上分析，在中，令Y值为某查询词在一天中的出现次数（Y≥1），F1-F6分别为该查询词上一次出现当天搜索日志中该查询词出现的次数、返回结果平均点击次数、独立用户数、平均访问时间间隔、最后两次出现时间间隔以及上次该查询出现时刻距离本日该查询出现时刻的间隔时长。每个查询通过一个月中多日搜索日志构造出多条包含未知参数r0-r6的1.1型等式，两边同时取对数得到：

的形式（其中Y'=lg（Y），β0=lg（r0），β1=r1，X1=lg（F1），……），该等式符合多元线性回归模型，通过多组实际观测数据构造多元线性回归方程组，可以通过最小二乘法计算得到未知参数β0-β6。

多元线性回归定义为：设随机变量y与x1，x2，…，xp满足关系式：

其中β0，β1，…，βp，σ2均为未知参数，p≥2，称式（3）为多元线性回归模型。在实际问题中，通过获得n组观测数据（xi1，xi2，…，xip，yi），i=1，2，…，n，线性回归模型（3）可以表示为：

一般要求观测次数n大于待估计参数的个数，即n＞p+1。本文实验数据中p=6，查询词在一天中的查询请求次数和该查询词上一次出现当日查询词的相关统计信息及时间间隔等组成为一组观测数据，因此可通过以上多元回归模型计算未知参数r0-r6的查询词在一个月的日志文件中需要至少在九天的搜索日志记录中出现（一个查询在前后两日出现的形成一条记录）。

模型（4）的矩阵形式为：

在满足式（3）的多元回归模型中，使用最小二乘估计法根据n组样本观测值（xi1，xi2，…，xip，yi），i=1，2，…，n，参数β0，β1，…，βp的估计值β0'，β1'，…，βp'，使平方和达到最小，对每一个未知数求偏导，并整理得到等式XTXβ= XTY，其中，

可求得β0，β1，…，βp的解为β→=（XTX）-1XTY。然后通过（1.2）式转化就得到了未知参数值r0-r6。

4　基于综合价值的缓存替换策略

缓存替换策略的设计目标是达到较高的缓存命中率以及较低的计算复杂度，这就要求缓存替换策略能够准确评估缓存数据项的价值，找出缓存价值相对低的数据项替换出缓存。缓存数据项的价值依赖于该数据在未来一段时间内被访问的情况：数据项未来被访问的时间距离现在越近、未来一段时间内被请求的次数越多该数据项的缓存价值越高。因此缓存替换时如果能较准确地预测数据项未来被访问的情况，替换出低缓存价值的数据项，保留高缓存价值的数据项，可以达到较高的缓存命中率并充分发挥缓存的效能。

前端实时记录查询特征信息并存储，查询特征记录可以快捷的转化为的访问统计信息F并代入未来价值函数，可以得到该查询词对应的缓存价值。即用查询词当前的访问信息预测评估了未来该查询被请求访问情况。鉴于只有占不同查询中小部分的常见查询才具有未来价值函数值，以及低缓存替换策略计算复杂度的需求，本系统不采用对缓存中所有关键词计算价值函数值并排序然后替换掉价值函数值最低的关键词对应数据项这种缓存替换策略。

本文提出综合了LRU算法和未来价值函数的缓存替换策略，充分发挥LRU策略对查询最近访问时间特性的利用以捕获热点查询且计算复杂度低的优势，以及未来价值函数中利用查询词当前访问统计信息所标识的查询词缓存价值。缓存替换策略为：维护一个以查询词最近一次访问时间为标准的LRU队列，替换时从LRU队列末尾选择N个最久未访问的查询词（N称为替换区大小）做比较。通过以下策略找出要换出的查询词数据项：定义未经过搜索日志分析计算出r0-r6值的查询词的权值为其被请求访问的次数，定义经过搜索日志分析并计算出 r0-r6值的查询词权值为Y=由于经过搜索日志分析并计算出r0-r6的查询词是一个月内至少有九天中被请求访问的常见查询，未经过搜索日志分析计算出r0-r6的查询词往往是生僻查询词或新出现查询词，这种查询词往往只出现一次或少数几次，可重现性差，间隔时间较长，缓存价值低。因此设定经过搜索日志分析计算出r0-r6的查询词的权值大于未经过搜索日志分析计算出r0-r6的查询词的权值，有优先替换掉费常见查询而保留常见查询。遍历替换区中的查询词得到权值最小的查询词作为牺牲者，从缓存中删除该查询和对应的查询结果数据，为未来进入缓存的查询词对应的查询结果数据留出空间。在遍历的过程中，考虑到占查询总量中约20%的查询词只会出现一次没有缓存价值，设定若某个查询词未经过搜索日志分析计算出r0-r6并且其被访问次数为1则直接删除缓存中这条查询词对应数据项，而无需继续遍历比较剩下的查询词。这样大大的提高了缓存替换的效率并且不降低缓存命中率。N作为缓存替换区大小值可以调节，N值越大查询词对应的历史访问统计信息对替换策略的影响越大，同时更倾向于保留常见查询，替换算法的计算复杂度越高；N值越小查询词的动态特性即该查询词的最久未访问时间在替换策略中的影响越高，同时缓存替换计算复杂度越低。

图1　不同替换区大小下的缓存命中率对比

图2　不同缓存大小下本替换策略与LRU替换策略的缓存命中率对比

5　实验结果

曲线开始阶段因为能利用未来价值函数作为替换的依据随着替换区的增大缓存命中率逐渐递增，替换区达到一定大小后命中率趋于平缓稳定，这是因为替换区已经保留了足够多的常见查询，在一定缓存空间下当替换区大小相对缓存空间大小过高时，替换区内常见查询保留过高，不利于对随机查询的再次捕获，导致命中率下降。小缓存空间下（1万）替换区完全覆盖后，缓存保留最常见的查询导致缓存命中率持续提升。

从本图可以看出：本文提出的替换策略相比LRU策略在缓存较小区间随着缓存空间的增加缓存命中率提升的更迅速，可以充分利用缓存空间带来较高的缓存命中率。由图可知，本文提出的缓存替换算法相比LRU算法在最优缓存空间（每日总查询量的20%）下命中率有显著提升，命中率提高7%左右，考虑到查询量巨大，这是非常可观的提升。

6　结语

本文通过对搜索引擎查询分布特性的分析研究，提出了基于多查询特性的未来价值函数，通过周期性日志分析统计计算查询相关特征值并利用多元回归函数计算得到查询词的r参数值，缓存替换时将查询词的未来价值函数值融入到综合替换策略中。首先，通过大规模细粒度的搜索日志分析将每一个查询词过去一个月内的访问历史特征信息按天统计出来，然后基于查询请求分布规律为查询词建立价值函数并利用历史访问统计信息计算出价值函数中的未知参数，最后在缓存替换时充分利用了查询词当下的动态特性和历史访问特征信息预示的缓存价值，本缓存替换策略倾向于保留当下活跃查询词和常见查询词在缓存中，显然这是保证较高缓存命中率的关键。总体上充分利用LRU替换策略的动态特性对时效性查询的捕获，替换时不直接替换掉最久未访问的查询而是从一定量 （替换区大小）最久未访问查询中比较综合价值函数值大小，将综合价值最小的查询替换掉，这样可以保留高缓存价值查询数据以获得较高缓存命中率。本缓存策略弥补了LRU对大查询间隔常见查询缓存缺失的劣势，通过调整替换区大小可以动态改变缓存对常见查询和时效性查询的捕获能力，对查询负载类型的变化具有良好适应性。通过对每日更新的查询日志分析，可以动态调整查询相关特征的参数值，使综合价值函数准确，时效性高，充分利用查询当前的历史访问信息对未来访问情况的预测作用。最后通过对比测试证明了本缓存替换策略相较传统缓存替换策略的优势。

［1］Deitel H M，Deitel P J，Choffnes D R.Operating systems，3rd edition，Prentice Hall，2004

［2］E.Markatos.On caching search engine query results.In 5th International Web Caching and Content Delivery Workshop，May 2000.

［3］R.Lempel and S.Moran.Predictive caching and prefetching of query results in search engines.In Proc of the 12th World Wide Web Conference，19-28，2003

［4］X.Long，T.Suel.Three-level caching for efficient query processing in large web search engines.In Proc of the 14th World Wide Web Conference，May 2005.

［5］T.Fagni，R.Perego，F.Silvestri，S.Orlando.Boosting the performance of web search engines：Caching and prefetching query results by exploiting historical usage data.ACM Trans on Information Systems，24，2006.

［6］R.Baeza-Yates，F.Junqueira，V.Plachouras，H.Witschel.Admission policies for caches of search engine results.InProc.of the 14th String Processing and Information Retrieval Symposium，Sept.2007.

［7］R.Baeze-Yates，A.Gionis，F.Junquerira，et al.Design tradeoffs for search engine caching.ACM Trans on Web，2008，2（4）：1-28.

［8］Q.Gran，T.Suel.Improved techniques for result caching in web search engines.Proceedings of WWW 09，ACM，2009：431-440.

［9］Marin，M.，Gil-Costa，V.，&Gomez-Pantoja，C.，New caching techniques for web search engines.In Proceedings of the 19th ACM international symposium.On high performance distributed computing（pp.215-226），2010.

［10］Rifat Ozcan，I.Sengor Altingovde，B.Barla Cambazoglu，Flavio P.Junqueira，？zgür Ulusoy.A five-level static cache architecture !for web search engines.Information Processing and Management，48（2012）：828-840.

［11］Silverstein C，Henzinger M，Marais H，et al.Analysis of a very large web search log.Proc of SIGIR 98.ACM，1998：6-12.

［12］Y.Li，S.Zhang，B.Wang，et al.Characteristics of Chinese Query Logs.Journal of Computational Information Systems，2008，4（3）：1127-1136.

［13］李亚楠，王斌.一个中文搜索引擎的查询日志分析.数字图书馆论坛.1673-2286.2008.07.002.

［14］马宏远，王斌.基于日志分析的搜索引擎查询结果缓存研究.计算机研究与发展.49：224-228，2012.

［15］M.Faloutsos，P.Faloutsos，C.Faloutsos.On power-law relationships of the Internet topology.SIGCOMM'99：251-262.

［16］Linyuan Lü，Zi-Ke Zhang，Tao Zhou.Deviation of Zipf's and Heaps'Laws in Human Languages with Limited Dictionary Sizes.Scientific Reports 3，Article number：1082.Published 30 January 2013.

［17］Pragya Kaushik.Sreesh Gaur.Mayank Singh.Use of query logs for providing cache support to the search engine.978-93-80544-12-0/14/2014 IEEE.

［18］Hong-yuan Ma，Wei Liu，Bing-jie Wei，Liang Shi，Xiu-guo Bao，Li-hong Wang.PAAP：Prefetch-Aware Admission Policies for Query !Results Cache in Web Search Engines.SIGIR'14 July 06-11 2014.

［19］Edward Bortnikov.Ronny Lempel.and Kolman Vornovitsky.Caching for realtime Search.Springer-Verlag Berlin Heidelberg 2011.

［20］B.Barla Cambazoglu.Flavio P.Junqueira.Vassilis Plachouras.A refreshing perspective of search engine caching.WWW 2010，!April 26-30，2010.

［21］RIFAT OZCAN，ISMAIL SENGOR ALTINGOVDE，OZG¨UR ULUSOY.Cost-aware strategies for query result caching in web Search Engines.ACM 1559-1131/2011/05.

［22］Fethi Burak Sazoglu.B.Barla Cambazoglu.Rifat Ozcan.A financial cost metric for result caching.SIGIR'13，July 28-August.

Search Engine；Cache Replacement Strategy；Integrated Value；Multiple Query Attributes；Regression Analysis

Research on the Search Engine Cache Replacement Strategy Based on Multiple Query Attributes

FANG Yun-yun
（Department of Computer Science，School of Electronics and Information Engineering，Tongji University，Tongji 201804）

1007-1423（2015）23-0003-08

10.3969/j.issn.1007-1423.2015.23.001

房耘耘（1990-），男，山东济宁人，硕士，研究方向为分布式计算、大数据分析

2015-08-01

2015-08-10

缓存是搜索引擎中的重要技术，能显著节省查询处理计算量，缩短查询请求响应时间和提高系统吞吐量，得到学术界的关注和业界的广泛应用。当前搜索引擎缓存替换策略没有充分利用查询的多种访问特征信息，没有充分利用查询分布特性，传统替换策略用在搜索引擎中存在各种不足。针对以上问题研究查询请求的分布特征，分析现有缓存替换策略的不足，然后基于查询词访问特征提出代表查询词未来热度值的综合价值函数模型，然后通过对搜索引擎查询日志进行细粒度的统计分析，得到每个查询词每日各访问特性的详细记录，并基于多元回归分析方法计算得到查询词价值函数模型的未知参数，设计结合查询词当前动态访问特性和未来访问热度值的查询结果缓存管理策略，并通过真实查询记录测试不同替换区大小下本缓存系统的命中率，对比证明所提出的缓存替换策略相对于传统替换策略在命中率方面的显著提升。

Cache is a very important technology in search engine，which can significantly save query computation processing，improve query response and improve system throughput，which are widely applied by the academia and the industry.Current cache replacement policy does not take full advantage of search engine queries of multiple access feature information，does not take advantage of query distribution，also deficiencies exist in the traditional replacement policy when used in search engines.For the above problems，studies query distribution features，analyses the insufficient of existing cache replace strategies，then proposes integrated value function model represent query future heat value based on query access features，analyses search engine query log for fine grain degrees，gets each query's daily access characteristics of detailed records，and based on multiple return analysis in the minimum II multiplication calculation to get the unknown parameter in the function model，designs cache management policy integrate current dynamic access attributes with the heat value of the query in the future，hit ratio test of replace management strategy through real query shows that，in contrast with traditional cache replacement strategy，this replacement strategy significantly exceeds them in hit rate.