Workload Characterization for Web Search

다국어 초록 (Multilingual Abstract)

Web search distributes query processing across many servers, and each web search server processes multiple queries concurrently to achieve high throughput. A fundamental requirement of web search is responsiveness, which is typically guided by a response time SLA. As this is applied to each and every search query, understanding how system resources are utilized during query execution is important. In this paper, we present workload characterization for web search, with a focus on temporal and spatial locality of index data access. A key finding includes high temporal locality, suggesting that data caching plays an important role in achieving good performance. Moreover, this paper analyzes how effective the preferching of index data is in web search. The prefetching is a very common optimization in web search in order to amortize delay related to data reads from external storage. From the analysis, we observe that the prefetching is not only frequent, but also aggressive, with large size of data to be issued for prefetching. Surprisingly, this optimization is effective in web search. However, some portion of the prefetched data is not accessed by the query due to early termination, and this paper shows that this accounts for 8.3% of total prefetched data. As a future work, we will study how to reconcile many prefetching requests issued by concurrent queries under heavy loads. Lastly, we believe that this work will fuel future endeavors on improving memory management for web search workloads.

참고문헌 (Reference)

1 전명제, "대용량 블로그 워크로드 분석" 한국지식정보기술학회 6 (6): 17-26, 2011

2 L. A. Barroso., "Web search for a planet: The google cluster architecture" 23 (23): 22-28, 2003

3 R. Baeza-Yates., "The impact of caching on search engines" 2007

4 F. Blagojevic., "Runtime scheduling of dynamic parallelism on accelerator-based multi-core systems" 33 : 10-719, 2007

5 E. Frachtenberg, "Reducing query latencies in web search using fine-grained parallelism" 2009

6 S. Jonassen., "Prefetching query results and its impact on search engines" 2012

7 M. Jeon., "Predictive parallelization: Taming tail latencies in web search" 2014

8 C. Macdonald., "Learning to predict response times for online query scheduling" 2012

9 Q. Gan., "Improved techniques for result caching in web search engines" 2009

10 M. E. Haque., "Few-to-many: Incremental parallelism for reducing tail latency in interactive services" 2015

11 S. Ren., "Exploiting processor heterogeneity in interactive services" 2013

12 J. Dean, "Challenges in building large-scale information retrieval systems: invited talk" 2009

13 Z. Li., "C-Miner: Mining block correlations in storage systems" 173-186, 2004

14 M. Jeon., "Adaptive parallelism for web search" 2013

15 B. B. Cambazoglu., "A refreshing perspective of search engine caching" 2010