Web搜索引擎的多层次缓存数据布局方法及实时检索缓存失效内容更新策略研究

Cache is a vital component for efficiency of large-scale Web search engines, and hierarchical cache and maintaining the freshness of cached query results for real-time search are the current research challenges.. In the program, we will study data layout approach for the hierarchical cache in Web search engine, and the limitations of the current approaches for single cache layer can be broken through. The impact on the relationship among query results, inverted lists and intersection lists will be explored to convert the issue to a state-of-the-art multi-knapsack problem. Stale query results refreshing policy for real-time search cache is another research problem in the program, and refreshing policy is a key issue in production search engine system. The self-similarity analysis of some large-scale search engine workloads will be conducted, and some effective workload-aware refreshing policies based on query frequency, query processing cost and cached query results life-cycle will be presented.. Finally, a high-performance hierarchical search engine cache for real-time search will be implemented in the program. The effectiveness of those approaches in the program will be verified on some large-scale commercial Web search engine query logs..

缓存是有效提升大规模Web搜索引擎性能的重要组件，搜索引擎多层次缓存与面向实时检索的缓存查询结果实时性问题是当前领域面临的重要挑战。. 本项目研究在多层次缓存场景下的搜索引擎缓存数据布局方法，突破现有研究仅适用单一层次缓存技术局限，通过分析查询结果、倒排表、倒排表交集因素间的影响关系，将该难题转化为多背包问题进行求解；研究工作负载感知的缓存失效内容更新策略，填补面向实时检索缓存失效内容更新策略研究的空白，对搜索引擎工作负载进行自相似性特征分析，提出搜索引擎工作负载感知的缓存失效内容更新策略，包括基于查询频率、查询时间开销、缓存内容生命周期的更新策略。. 最后，实现一套面向实时检索的高性能搜索引擎多层次缓存系统，采用大规模真实商业搜索引擎查询日志作为工作负载，在该系统上开展实验，验证研究成果的有效性。

缓存查询结果是网络搜索引擎提高效率的关键技术。网络搜索引擎利用庞大的倒排索引在紧张的时延约束下处理用户查询。在这种条件下，搜索引擎系统需要庞大的基础设施，这包括上千台计算机和持续地投资维护这些设备。优化搜索引擎效率对网络搜索系统来说非常重要，即使微小的改进也可能为搜索引擎节省下巨额的设备费用。查询结果缓存技术被广泛地被搜索引擎采用来提高搜索引擎效率，减少查询响应时间和降低搜索引擎后台负载。针对以上问题，本项目研究索引更新缓慢而容量受限的查询结果缓存算法，缓存容量足够大时面向实时检索的缓存更新策略和查询开销感知的缓存替换算法。. .本项目的主要工作如下：. .(1) 研究查询结果、倒排表、倒排表交集因素间的影响关系。为一个先进的查询结果缓存框架SDC选择动态缓存算法来达到更高的缓存命中率。将九种动态缓存算法分别作为SDC的动态缓存逐出策略，在真实的搜索引擎日志下，比较它们应用于SDC的缓存命中率，时间、空间复杂度为选择合适的动态缓存策略提供依据。实验结果表明，采用ARC替换策略能够使SDC缓存达到最高的缓存命中率。. (2) 研究工作负载感知的缓存失效内容更新策略。随着存储技术的进步，存储硬件设备的容量不断增大、访问速度不断提高、价格越来越便宜，廉价的存储设备容量大到足够存储所有过去用户查询的结果, 而一个无穷大的缓存面临着缓存结果陈旧的问题。本文研究面向实时检索的缓存更新策略，包括基于查询频率、查询时间开销、缓存内容生命周期的更新策略，以达到节约搜索引擎后台处理资源的目的。. .(3) 提出一种查询开销感知的查询结果缓存替换算法。比LRU缓存替换算法减少了约1.5%的总查询计算开销，且在缓存命中率方面仅比LRU缓存替换算法少了不到千分之一。. .最后，实现了一套面向实时检索的高性能搜索引擎多层次缓存系统，在大规模真实商业搜索引擎查询日志作为工作负载，验证研究成果的有效性。