A Highly Scalable Parallel Caching System for Web Search Engine Results

Abstract. This paper discusses the design and implementation of SDC, a new caching strategy aimed to efficiently exploit the locality present in the stream of queries submitted to a Web Search Engine. SDC stores the results of the most frequently submitted queries in a fixed-size read-only portion of the cache, while the queries that cannot be satisfied by the static portion compete for the remaining entries of the cache according to a given cache replacement policy. We experimentally demonstrated the superiority of SDC over purely static and dynamic policies by measuring the hit-ratio achieved on two large query logs by varying cache parame-ters and the replacement policy used. Finally, we propose an implemen-tation optimized for concurrent accesses, and we accurately evaluate its scalability.