互联网上进行信息获取的关键词搜索引擎缓存响应时间

　　互联网上进行信息获取的关键词搜索引擎缓存响应时间

　　分布式中文搜索引擎FlyingSender的缓存优化策略及实现 闵高照，（华东理工大学，上海200237)Abstract 随着搜索引擎的日益普及，如何减少用户查询响应时间和减少网络问题负载成为一个重要的研究课题，本文提出了一种建立用户查询结果缓存的策略，并讨论了其相关结构、更新方法、替换策略关键词搜索引擎缓存响应时间负载缓存策略分布式中文搜索Engine Flyingsender闵高照，邵志清（华东理工大学计算机系，上海200237) [摘要]随着搜索引擎用户的增长，反馈时间用户的请求如何降低网络负载服务器负载一直是一个非常重要的研究课题。论文提出缓存搜索引擎结果同时也讨论信息更新替换 [关键词] 搜索引擎缓存反馈时间工作量一、 引言随着互联网和Web技术的发展，互联网上的信息越来越多。

　　搜索引擎已经成为互联网上获取信息最重要的手段之一，越来越多的用户通过搜索引擎找到自己需要的信息。人们对搜索引擎的要求越来越高。搜索引擎的响应时间、召回率和准确率已成为评价搜索引擎质量的重要指标。针对搜索引擎数据更新慢、网页排名质量低、运行不分布式等问题，我们设计并实现了大型中文搜索引擎FlyingSender。随着用户请求数量的增加，如何降低服务器负载和用户响应时间成为我们重要的研究课题。在本文中，我们提出了一种基于缓存的优化策略和实现技术。可以有效减少对用户的响应时间，减轻服务器和网络的负担。 二、分布式搜索引擎查询服务器架构在一般分布式中文搜索引擎系统架构中，查询服务器处理用户查询请求的整体架构图如下： 用户查询查询服务系统图 当用户发送查询请求时，我们首先在汉语词典中查找词条的ID号，然后在索引库中查找词条的索引信息，得到收录该词条ID号的所有网页。然后，我们在数据库中搜索该词的所有网页的排名值，结合词在每个网页中的权重，对这些网页进行排序，然后将结果返回给用户。当用户的查询量变得非常大时，网络流量和查询效率的限制将成为整个系统的瓶颈。

　　我们可以根据对用户搜索行为和结果的分析来考虑优化整个系统。很多人对用户的搜索行为进行了跟踪研究[1,2]，得出了一些重要的结论：大约%的用户会浏览下一页的查询结果；可以看出它们是用户查询的结果。建立缓存是减少网络负载和减少响应时间的一种非常有效的方法。大多数浏览器都在客户端的内存或磁盘中建立了查询文档的缓存记录。我们考虑在服务端构建用户查询结果缓存，用于存储用户查询后的一些结果。当用户发出查询请求时，系统首先在缓存中搜索相应的信息。如果存在，则将结果直接返回给用户。如果缓存中没有相应的信息，则将其发送到搜索引擎的搜索程序进行查询。建立一个合适大小的缓存，可以让用户查询在缓存中达到6%的命中率，而无需到各个节点去检索相应的信息，大大降低了网络负载。考虑存在于缓存中的大小为 Si 的文档，检索时间为 Si，其中 Bi 是缓存和客户端之间的实际带宽。如果要从原创存储节点检索文档，则检索时间是从客户端到提供文档的服务器的实际带宽。在这里，我们忽略了从网络节点检索相关网页信息所需的时间。大多数情况下，用户客户端与缓存之间的带宽较高，而与其他网络节点的连接相对较慢。

　　因此，我们可以认为b并建立缓存可以大大减少用户的查询响应时间。缓存区建立后的检索时间可以用t表示为文件i在缓存中被找到的概率。在建立用户查询结果缓存的过程中，我们必须考虑以下问题： 何时以及如何替换缓存中的内容（替换策略作者简介：闵高照（，男，硕士，研究方向：互联网）搜索引擎、网络协议与安全；邵志清教授，博士生导师Web服务器中文词三、缓存结构与更新策略文献【提出建立两级缓存结构：静态缓存区和动态缓存区，其中用户查询次数存储在静态缓存中 大部分查询结果，动态缓存区存储用户查询次数和频繁查询结果，它们对静态缓存区中的内容采用周期性批量更新，以保证缓存数据和系统数据的一致性，根据用户查询条目的数量和频率决定是否将结果存储在静态缓存中。但是，我们认为用户的行为有与网页本身内容的更新频率无关。用户查询较多的条目，因此网页更新速度可能会更快（例如“伊拉克局势”）或较慢（例如某些更改周期相对较长的内容）。即使是同一个item的查询结果，也有部分网页更新缓慢。更新比较快。我们只会设置一个缓存区。查询结果网页采用统一的更新策略，不同的网页会有不同的更新频率。

　　我们建立了一个动态模型来获取网页的抓取和更新频率），可以估计网页变化的频率。如下图： 网页的最后更新时间和访问时间。图中虚线表示网页发生变化的时刻，即最后一次读取到网页头部信息中的更新时间。实线代表我们访问网页的时刻。 T 表示两次访问网页之间的时间间隔。从图中可以看出，如果某个网页在第一次访问之间发生了变化，则该网页在时间T发生了变化；相反，网页没有变化，X保持不变。下面的算法用于估计网页的更新频率： 当使用最近更新时间来估计网页变化的频率时，每次获取一个网页，都需要记录该网页的最近更新时间和访问次数网页的时间。对于那些没有最新更新时间元信息的网页，需要使用其他元信息检查网页的变化，比如网页的长度和Et。这样，所有网页都可以使用上述算法来估计网页变化的频率。当然，在估计没有最新更新时间值的网页时，误差可能会比较大。随着访问次数的增加，概率会越来越接近真实值。这样，我们就得到了每个网页的更新频率，并将其存储在相应的网页信息数据库中。在我们建立的缓存区中，我们会为访问用户建立一个哈希表，为经常访问和经常访问的条目建立哈希表。表项内容包括关键字Key，相关的Ur号）链表指针，指向Key对应的网页内容缓存块链表，网页内容缓存块链表按顺序，存储关键字查询结果对应的前1个网页信息的返回结果。

　　当用户查询时，首先搜索表。如果表中存在该条目，则搜索条目对应于Ur链表，将网页内容返回给用户，直到链表的链接指针为空。否则，将其提交到原创搜索系统以开始新的搜索。我们的用户查询结果缓存采用下图所示的存储结构： 用户查询结果缓存结构，最近更新时间是我们创建或更新网页的时间，我们根据网页的更新频率（存储在网页信息数据库中）和最近的更新时间，可以计算出下次更新的时间。缓存管理器会在一定时间（例如一天）内检索缓存区域，更新需要更新的网页内容，删除不再存在的网页的链接点。 Key1 *Link1 Key2 *Link2 UrlId 网页内容最后更新时间 下次更新时间 nextUrlId 网页内容最后更新时间 下次更新时间 nextUrlId 网页内容最后更新时间 下次更新时间 nextUrlId 网页最近更新时间content Next update time Next 根据我们设计的缓存结构，缓存管理器以更小的周期更新网页，可以更好的保证网页内容的“新鲜度”。同时，缓存管理器按照一定的周期批量更新缓存区中的网页内容。确保它适应互联网上不断增加的网页信息和网页相关性变化。 四、Replacement 策略由于我们的缓存区存储在有限的内存中，所以我们必须限制缓存区的大小。同时，建立缓存区的主要目的是提高用户缓存命中率。用户的搜索行为会影响我们的缓存。存储在我们缓存中的内容只会存储用户查询频率较高和查询频率较高的内容。

　　所以我们必须有一个替换策略。当新的内容需要转移到缓存区时，必须按照这个策略替换一些缓存块。在操作系统、数据库管理系统（DBMS）和一些分布式文件系统等领域，对替换策略有深入的研究。由于用户在搜索引擎中的搜索行为表现出明显的时空分布特征，替换策略也是一致的。上面的系统是不同的。我们采用相对简单的策略来维护用户通过缓存管理器检索到的条目信息的日志表。内容包括：条目信息K，总检索次数C1，在第一次检索时使用该信息。可以分别计算一段时间内每个词条的用户查询频率和权重计算周期。对于每次搜索，将相应术语的总搜索次数和该时间段内的搜索次数加 1。缓存管理器定期（例如每隔一天）计算权重的大小。权重大小与 1 之间的常数用于平衡词条的总查询频率和周期内的查询频率。根据权重的大小，我们决定条目是否进入缓存区。设置一个权重阈值 p 将这个条目交换到缓存区中，并将缓存区中权重最小的一项换出。算法如下： 替换函数，传入参数为关键词五、Cache Manager 整个缓存区由缓存管理器维护。缓存管理器包括几个模块：查询管理模块、更新管理模块、替换管理模块。结构如图： 用户查询缓存管理器结构 各模块功能简介如下： 查询管理模块：接收用户查询，先查询缓存区对应的内容，如果存在，则返回查询结果；如果不存在，则转发到原搜索部更新管理模块：定期（较短）查询缓存中的内容，根据网页的更新频率更新相应的网页内容。

　　定期（更长时间）批量更新缓冲区的内容。更换管理模块：维修日志表。创建初始缓冲区。根据替换策略替换缓冲区中的内容。由于用户查询行为有一定的时间段分布，在一段实验中，用户查询行为有如下分布： 查询管理更新管理替换管理原搜索系统用户查询时间分布图我们可以考虑用户查询次数运行更新并在较短的时间内进行更换操作，使服务器的负载得到更好的平衡。 六、实验结果和结论我们记忆。我们之前抓取了一些教育网站作为*敏*感*词*网站，并返回了大约 1 页的网络文件。我们在查询结果缓存建立前后进行了多组查询对比实验。每个查询返回 2 个相关网页。本实验基于单线程，文件系统位于本地。如果考虑分布在不同节点上的文件和数据库基于此，缓存策略的访问效率会更加明显。实验结果如下： 缓存建立前每个检索条件的平均检索时间（ms 缓存建立后每个检索条件的平均检索时间（ms） 从中可以看出缓存命中的命中率，建立缓存后的查询效率非常可观，随着我们随着检索次数的增加、时间的延长和缓存容量的增加，系统可以达到理想的查询效果，从而大大优化了查询的整体性能搜索引擎。为查询结果建立缓存区，对于减少用户查询响应时间，减少网络负载都有非常重要的意义。

　　如何更好地优化和提高缓存的性能将是我们进一步研究的重要课题。参考文献 [1]Evangelos,P.Markatos CachingSearch Engine Query Results。 5th International Web Caching ContentDelivery Workshop。 2000 年 5 月 谢英连，大卫·奥哈拉伦。 Locality SearchEngine Queries ItsImplications Caching.IEEE INFOCOM 2002 [3]王剑.FlyingSender中文搜索引擎架构与实现技术。华东理工大学硕*敏*感*词*论文。 2002.1 [4]M.Abrams、CRStandridge、G.Abdulla、S.Williams 和 EAFox。 Caching Proxies:Limitations第四国际WWW大会，1995.[5]沉文琴。搜索引擎中网络爬行更新策略的设计与实现。华东理工大学硕*敏*感*词*论文. 2004.2