马宏远,王斌

(1.中国科学院计算技术研究所,北京100190;2.中国科学院研究生院,北京100049)

1 引言

据中国互联网络信息中心(China Internet Network Information Center,CNNIC)研究报告显示[1],截至2010年12月,中国网民达到4.57亿,其中搜索引擎使用率达到81.9%,搜索引擎已经成为人们获取信息的主要工具。一方面,互联网网民增多,搜索引擎工作负载变大;另一方面,互联网网页也逐年增多,其规模已经达到600亿,且仍以年增长率超过50%的速度快速膨胀,搜索引擎需要尽可能多地索引这些网页以提供准确和丰富的查询结果。在如此海量信息中,高效获取所需查询对学术界和工业界提出挑战。自21世纪初以来,随着互联网步入高速发展时期,一些搜索引擎检索系统性能优化方法先后被提出,主要有并行处理(Massively Par-allel Processing)、索引压缩(Index Compression)、索引裁剪(Index Prune)、倒排表跳转(List Skipping)、提早结束(Early Termination)等技术。除此之外,缓存技术(Caching)与预取技术(Prefetching)作为重要的系统性能优化手段而被搜索引擎检索系统广泛采用和研究。

缓存是一种通过存放将来可能被请求的数据以提高数据访问速度。被存放的数据可能是计算结果或者数据的副本。如果请求的数据在缓存中被查找到,就直接获取该结果或者副本,否则,请求需要再次计算或者从其位置获得该数据。如果更多的请求能够被缓存所满足,则意味着系统的整体效率会被提高。缓存被广泛应用于计算机系统及应用软件的各个层次,譬如CPU缓存、磁盘缓存、Web缓存。

在本文中,我们提出一种基于查询特性的查询结果缓存与预取的方法,该方法包括用来指导预取的查询结果页码预测模型和基于查询特性的分区缓存。在国内某著名中文商业搜索引擎用户查询日志上验证了我们提出方法的有效性。本文第2节分析搜索引擎查询特性;第3节阐述基于查询特性的查询结果页码预测模型,给出全局和局部预测模型;第4节阐述基于查询特性的查询结果缓存与预取算法框架;第5节是实验结果及分析;第6节是本文结论及未来工作。

2 相关工作

查询结果缓存是通过缓存已被用户检索过的查询结果以避免再次对该结果进行排名计算带来的CPU和磁盘读开销。Markatos[2]首先对搜索引擎环境下,查询结果缓存技术进行研究,通过分析Excite用户查询日志,显示其工作负载具有时间局部性(Temporal Locality),比较动态LRU缓存替换策略以及LRU策略的若干变种和静态缓存策略的命中率,得出静态缓存策略对小容量缓存有效,随着容量增大,有效性降低。Xie[3]讨论缓存位置的影响,分别讨论客户端缓存、代理服务器缓存和搜索引擎服务器缓存技术。Fagni[4]提出静态、动态混合的缓存策略,其将缓存分为静态缓存和动态缓存两个部分。静态缓存用于存放通过预先分析得到的流行查询结果;动态缓存用于存放其余的查询结果。Baeze-Yates[5]从缓存接纳策略角度提出了一种能有效识别不流行的查询的缓存方法,可以阻止不必要的缓存内容进入缓存占用其他有价值的缓存内容。Gan和Suel[6]提出基于查询开销的查询结果缓存方法,考虑查询频率和开销来对查询结果给予不同权重。Ozcan[7]提出基于查询稳定度的查询结果缓存方法,考虑查询在一定时期内的稳定程度来选择查询结果。Skobeltsyn[8]提出一种结合索引裁剪技术的查询结果缓存方法。查询结果预取是通过预测Follow-up查询[9],提前取得查询结果。Lempel[9]根据查询自身特性,建立Follow-up查询页码分布,提出了一种基于该分布的查询结果预取方法。Fagni[4]通过分析查询请求页码对Follow-up查询的影响,提出一种基于当前请求查询页码的自适应查询结果预取方法。对于Web缓存预取[10],主要是通过分析用户访问 URL顺序来预测访问路径,以预取用户数据。

3 搜索引擎查询特性分析

用户行为分析是系统优化的重要基石,文献[3,11-13]对搜索引擎的用户行为进行分析来开展相关工作。与以往分析工作不同,本文着重分析搜索引擎查询特性。本文数据来自于国内某著名中文商业搜索引擎从2006年9月1日到2006年10月31日的用户查询日志,包括近3000多万条用户查询和1亿多条用户点击记录。我们从该日志中提取了所有用户对该搜索引擎发起的查询请求,作为分析搜索引擎查询结果页浏览特性的基础。

图1 搜索引擎查询特性

查询,即查询主题,是用户对信息检索需求的具体表达,用户提交查询给搜索引擎。不同的查询意图对查询结果浏览行为会产生重要影响,譬如用户要搜索“新浪”,通常只浏览第一页查询结果就可以得到自己需要的信息。文献[14]提出了一种查询意图分类方法,将查询分为：(1)导航类;(2)信息类;(3)事务类。图1(a)是在该搜索引擎用户查询日志上,统计用户浏览的查询结果页数,可以看出9%的查询主题只浏览了一页,这些主题大部分属于导航类查询。可见,用户浏览查询结果页数的分布具有显著非均衡性。图1(b)是在该搜索引擎用户查询日志上,统计用户浏览查询结果页码,可以看出页码范围越靠前的访问量递减趋势相比于相对靠后的页码范围内的访问量递减趋势要明显。

4 基于查询特性的查询结果页码预测模型

4.1 相关定义

我们将搜索引擎用户集合定义为U,用户提交查询集合定义为Q,用户提交搜索查询主题集合定义为T,用户提交搜索查询页码集合定义为P,用户查询日志总查询条数定义为N。那么,用户查询日志可以表示为：

即用户查询日志中的第i条查询记录为：在时刻τi,用户ui向搜索引擎提交的查询主题为ti,查询页码为 pi。用户每次提交查询页码集合可以表示为：

给定主题t,该主题下的查询页码集合表示为：

4.2 基于马尔可夫链模型

从我们对该搜索引擎用户查询日志统计表明,约96%的查询请求访问查询结果页码顺序是非逆序的(由于篇幅限制,未贴此结果)。基于此事实,引入如下假设：用户以页码的自然顺序访问查询结果页。我们使用基于马尔可夫链的方法设计预测模型,状态转移概率如图2所示,状态“i”(1≤i≤n)表示用户发起一个查询主题t,请求页码为“i”;状态“0”表示用户发起一个查询主题t后,不再对该主题产生页码请求。在任意时刻τj,当前访问页号 Xj和所有以前访问页号X1,X2,…,Xj-1的信息是已知的,所有将来的访问页号Xj+1仅依赖于现在的信息 Xj,而不依赖以往的信息 X1,X2,…,Xj-1,有：

那么,我们在模型设计过程中,需要获得Pr(Xj+1=i+1|Xj=i)即状态转移图中由状态“i”转移到状态“i+1”的概率pi,i+1。

图2 查询请求页码状态转移图

4.3 查询结果页码预测模型

在第2节中,我们分析了国内某中文商业搜索引擎的查询特性,用户浏览查询结果页数具有显著非均衡性。我们采用4.1节提出的模型设计用户浏览查询结果页码预测模型,模型分为全局预测模型和部分预测模型。

1)全局预测模型

全局预测模型通过记录用户浏览查询主题的统计信息进行预测。根据Pt集合的历史信息,将查询主题t对于查询结果页码i的访问次数记作Countt[i],那么,采用如下定义：

即考虑所有查询主题的查询结果页的分布。我们采用如下方法计算查询结果页码访问概率：

根据上面的定义,给定一个用户对某个查询主题t当前访问的查询结果页码i,预测该用户浏览该查询主题的查询结果页码集合Ωt,预测模型如下,其中用来调节预测效果：

全局预测模型认为所有查询主题都是平等的,每个查询主题都是用该模型进行预测,搜索引擎需要存储所有查询主题的查询结果访问信息。

2)部分预测模型

部分预测模型通过记录用户浏览的部分查询主题的统计信息进行预测。选取高频查询集合作为统计主体。根据Pt集合的历史信息,将查询主题t对于查询结果页码i的访问次数记作Countt[i],那么,采用如下定义：

即只考虑部分查询主题 TSpec的查询结果页的分布。我们采用如下方法计算查询结果页码访问概率：

4.4 模型阀值选取方法

我们采用如下两种方法来确定阀值：(1)设置固定阀值,采用固定值,需要预先设定,阀值与用户浏览当前查询的查询结果页码无关;(2)动态调整阀值,阀值与用户浏览当前查询的查询结果页码有关。

5 算法框架

在本文第4节中,我们给出基于查询特性的查询结果页码预测模型。本节将在此基础上,给出基于查询特性的缓存与预取算法框架,如算法1所示。对于部分预测模型,缓存系统分为两个区间：查询结果缓存区和查询结果缓存区。当搜索引擎收到用户的某一查询主题t时,缓存系统应该首先在t所属的集合所对应的查询结果缓存区中查询,以提高缓存检索相关条目操作的效率。

算法1 基于用户特性的查询结果缓存与预取算法框架

算法1给出了基于查询特性的查询结果缓存与预取算法框架,我们在此给出算法时间复杂度和空间复杂度分析。第6行,在缓存中检索该查询请求的查询结果,该操作依赖于缓存中信息条目的具体组织方式,通常,采用基于哈希的组织方式使该操作开销为Ο(1)。第 11行,缓存条目更新,该操作依赖于所采用的缓存替换策略,如LRU策略的缓存替换时间复杂度为 Ο(1),记作Complexity(Replacement_policy)。第21行,预测查询结果页码集合,由于此过程需要获得该查询相关的统计信息,其依赖于信息的具体组织,可以采用二维表的方式,查询主题ID作为表的行项,因此,该过程时间复杂度为Ο(1)。综上分析,该算法的时间复杂度依赖于所使用缓存替换策略的时间复杂度,Complexity-(Replacement-policy)。算法的空间开销来自于预测模型计算所需要的统计信息,通常,全局预测模型需要存储所有查询主题的统计信息,而部分预测模型只需要存储查询主题的统计信息。

6 实验与分析

6.1 数据集

本文实验数据集来自于国内某著名中文商业搜索引擎从2006年9月1日到2006年10月31日的用户查询日志。选取前500万条用户查询记录预热查询结果缓存,剩下约2500万条用户查询记录作为查询结果缓存的工作负载。

6.2 评价方法

搜索引擎缓存系统是提升系统整体性能的重要手段,缓存系统性能的优劣对整体有着重要影响。通常,缓存是以命中率作为其衡量指标,由于缓存系统实际受到存储容量的限制,需要考虑存储容量因素,即当缓存条目达到一定空间后需要以某种策略替换某些条目。为了分析存储容量对缓存命中率的影响,我们采用工作集模型[15]离线计算该用户查询日志的理论缓存命中率。在该用户查询日志的查询请求负载下,缓存容量和命中率的关系曲线如图3所示。当缓存容量大于0.025(实际缓存查询结果条目占总查询条目的百分比)时,命中率变化趋势趋于平缓。在实验中,我们近似选取5K、10K、20K、50K 、75K 、100K 、150K 、200K 、250K 条查询结 果作为缓存容量来分析缓存性能。从图中可以看出,查询结果缓存命中率理论上界为58.44%(Normalized Size=1时)。

图3 工作集模型下的理论缓存命中率

离线策略通常是用作缓存替换算法的理论分析,需要预先知道当前访问时间以后的全部或者部分工作负载。预先知道工作负载是不现实的,因此,离线策略是不可能在实际系统中实现的。在理论分析中,根据预先知道工作负载的多少可以将离线替换策略分为全局最佳替换策略(Global-OPT)[16]和局部最佳替换策略(Local-OPT)[17]。由于数据集规模大,我们采用Local-OPT(窗口为缓存容量大小)作为本文实验比较目标。

本文提出了基于查询特性的查询结果页码预测模型。在以往的研究工作中,搜索引擎查询结果缓存系统通常采用 Pre-K和Pre-SDC[4]两种预取方法。在我们的实验中,将其作为Baseline。

6.3 结果与分析

本文实验对Pre-SDC、Pre-K和提出的基于查询特性的方法,在缓存容量5K～250K的9个容量配置下,综合多种因素进行实验。Pre-SDC的参数K在取值为1或者2处,能获取最佳命中率(由于篇幅限制,未贴此结果)。因此,实验取K=0、K=1和K=2作为Pre-K和Pre-SDC的参数。

图4 全局预测模型与缓存命中率

图4 是全局预测模型与Pre-SDC、Pre-K、不预取、局部最佳替换策略和理论上限的对比曲线,注意,该实验结果默认使用 LRU替换策略。可以看出图中最下面的W/o prefetching和Local-OPT曲线都是缓存没有采取预取技术所获得的缓存命中率,其结果均偏低,这说明搜索引擎查询结果缓存系统采用预取技术对于系统性能提升是非常必要的。图中最顶部的虚线为不采用预取技术的缓存命中率上界,即认为缓存容量无限大时所获取的命中率。可以看出,在采用预取技术后,缓存容量为250K时,采用预取技术的曲线已经接近该上界。实际上,随着缓存容量的增大(大于250K),采用预取技术的缓存命中率是会超过该理论上界的。我们提出的基于查询特性的缓存与预取方法的缓存命中率均好于未采用预取技术的缓存命中率。由此可见,在缓存预取技术中,考虑查询主题特性可以提高系统性能。

图5 部分预测模型占总查询百分比与缓存命中率关系

图6 部分预测模型与缓存命中率

全局预测模型需要存储全部查询主题统计信息,然而,用户浏览查询结果的页数分布具有显著非均衡性。部分预测模型就是利用这一特性来降低信息存储开销,采用区分服务的思想来提高缓存命中率。图5是部分预测模型的Tspec占总查询百分比的命中率曲线。当 Tspec所占比例为0%时,该方法等同于Pre-SDC方法,当所占比例为100%时,即为基于全局预测模型的缓存与预取方法。可以看出,缓存系统最优命中率在 Ts pec占总查询百分比为40%～80%之间,即基于局部预测模型可以获得比基于全局预测模型好的缓存命中率。从图6可以看出,与Pre-SDC、Pre-K预取策略相比,基于部分预测模型的缓存与预取方法可以获得3.5%～8.45%的命中率提升,其效果也超过了基于全局预测模型的缓存与预取方法的命中率。同时,可以注意到,缓存容量达到150K时,其命中率超过了不采用预取技术的缓存命中率上界。由此可见,基于局部预测模型的缓存与预取方法,一方面,可以提高缓存系统命中率;另一方面,可以降低预测模型存储查询主题统计信息的开销。

接下来,我们分析模型阀值选取方法对预取策略的影响。实验在缓存容量为50K和200K的情况下,对基于查询特性的预测模型,测试固定阀值(以0.1递增,从0到1变化 φ值)和动态调整阀值方法。结果如图7所示,基于查询特性的预测模型在阈值采用动态调整方法时获得最佳缓存命中率,即图中A、B区域显示该结论。

图7 基于查询特性模型阀值对缓存命中率的影响

7 结论和进一步研究

查询结果缓存与预取是有效提升搜索引擎系统性能的关键技术。本文面向搜索引擎查询结果缓存与预取问题,分析国内某著名中文商业搜索引擎的用户查询日志的结果显示,用户对不同查询主题返回的查询结果所浏览的页数具有显著的非均衡性。根据该特性,提出一种基于查询特性的缓存与预取的方法。在该搜索引擎大规模用户查询日志上,验证了我们提出的方法能有效提升搜索引擎缓存系统命中率。

未来的工作主要集中在除了根据查询主题频率属性选择部分查询主题集合Tspec方法外,探寻更多的选择方法融入到本文提出的基于查询特性的缓存与预取算法框架之中。

[1]CNNIC(China Internet Network Information Center).The 27st Report in Development of Internet in China[R].http：//research.cnnic.cn/img/h000/h12/attach201102211453210.pdf

[2]E.P.Markatos.On caching Search Engine Results[J].Computer Communications.Elsevier Science B.V..2001,24(2)：137-143.

[3]Y.Xie,D.R.O'Hallaron.Locality in Search Engine Queries and Its Implications for Caching[C]//INFOCOM'02,2002：1238-1247.

[4]T.Fagni,R.Perego,F.Sivestri,et al.Boosting the Performance of Web Search Engines：Caching and Prefetching Query Results by Exploiting Historical Usage Data[J].ACM Trans.Information Systems,2006,24(1)：51-78.

[5]Q.Gan,T.Suel.Improved Techniques for Result Caching in Web Search Engines[C]//WWW'09,ACM,2009：431-440.

[6]R.Baeze-Yates,F.Junqueira,V.Plachouras,et al.Admission Policies for Caches of Search Engine Results[C]//SPIRE'07,2007：74-85.

[7]R.Ozcan,I.S.Altingovde,et al.Static Query Result CachingRevisited[C]//WWW'08,ACM,2008：1169-1170.

[8]G.Skobeltsyn,F.Junqueira,et al.ResIn：A Combination of Results Caching and Index Pruning for High Performance Web Search Engines[C]//SIGIR'08,ACM,2008：131-138.

[9]R.Lempel,S.Moran.Predictive Caching and Prefetching of Query Results in Search Engines[C]//WWW'03,ACM,2003：19-28.

[10]班志杰,古志民,金瑜.Web预取技术综述[J].计算机研究与发展,2009,46(2)：202-210.

[11]Y.Li,S.Zhang,B.Wang,et al.Characteristics of Chinese Web Searching：A Large-Scale Analysis of Chinese Query Logs[J].Journal of Computational Information Systems.Bethel：Binary Information Press,2008,4(3)：1127-1136.

[12]岑荣伟,刘奕群,张敏,等.基于日志挖掘的搜索引擎用户行文分析[J].中文信息学报,2010,24(3)：49-54.

[13]余慧佳,刘奕群,张敏,等.基于大规模日志分析的网络搜索引擎用户行为研究[J].中文信息学报,2007,21(1)：109-114.

[14]Daniel E.Rose,Danny Levinson.Understanding User Goals in Web Search[C]//WWW'04：Proceedings of the 13th International Conference on World Wide Web.New York,NY,USA：ACM Press,2004：13-19.

[15]D.R.Slutz,I.L.Tratger.A Note on the Calculation of Average Working Set Size[J].ACM Commun.,1974,17(10)：563-565.

[16]R.L.Mattson,J.Gecsie,et al.Evaluation Techniques for Storage Hierarchies[J].IBM Systems Journal,1970,9(2)：78-117.

[17]B.G.Prieve,R.S.Fabry.VMIN-An Optimal Variable Space Page Replacement Algorithm[J].ACM Comm,1976,19(5)：295-297.