Presented at: 19th International World Wide Web Conference (WWW2010)
by Flavio Junqueira, B. Barla Cambazoglu, Vassilis Plachouras, Swee Lim, Baoqiu Cui, Scott Banachowski
Web search engines are required to process very large amounts of data with a very low latency to return the best answers to user queries. To achieve low latency, designers of search engines take advantage of the query frequency distribution and employ caching at various levels of the system, e.g., caching of query results. The search engine also needs to update its index frequently to incorporate changes to the Web. After every index update, however, the query results for some entries in the cache might be stale. One solution to this problem is to flush the content of the cache. As the frequency of index updates increases, this solution imposes a significant performance penalty. In this work, we first argue that eviction policies are not as important as policies for invalidating queries and updating the cache content upon new versions of the index. We then introduce a novel caching algorithm that uses a time-to-live value to expire queries and refreshes queries using idle cycles of the engine. The cache selects the queries to refresh according to their frequency or temperature and to their age. More frequent and older queries are selected for refreshing because they are more likely to result in more hits in the future. In addition, we present mechanisms for setting the rate of refreshes issued by the cache. Our evaluation results on real workloads show that our cache outperforms an extension of LRU with refreshes, while the refresh rate is set so that the latency of queries is within a specified range. An implementation of this algorithm is currently in production use.
Keywords: Indexing, caching, distribution, index compression
Resource URI on the dog food server: http://data.semanticweb.org/conference/www/2010/paper/main/829
Explore this resource elsewhere: