Workload Characterization for Web Search

Myeongjae Jeon (전명재); 이영규

Workload Characterization for Web Search

Journal of Knowledge Information Technology and Systems
Abbr : JKITS
2016, 11(4), pp.425-433
Publisher : Korea Knowledge Information Technology Society
Research Area : Interdisciplinary Studies > Interdisciplinary Research
Published : August 31, 2016

Myeongjae Jeon ¹, 이영규 ²

¹마이크로소프트 연구소
²대전과학기술대학교

Accredited

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.

KEYWORDS

Web search, Workload characterization, Memory management, I/O, Locality

Citation status

* References for papers published after 2023 are currently being built.

[journal] L. A. Barroso. / 2003 / Web search for a planet: The google cluster architecture / IEEE Micro 23(2) : 22~28

[confproc] J. Dean / 2009 / Challenges in building large-scale information retrieval systems: invited talk / WSDM 2009

[confproc] M. Jeon. / 2013 / Adaptive parallelism for web search / EuroSys ’13

[confproc] M. Jeon. / 2014 / Predictive parallelization: Taming tail latencies in web search / SIGIR

[confproc] R. Baeza-Yates. / 2007 / The impact of caching on search engines / SIGIR

[journal] F. Blagojevic. / 2007 / Runtime scheduling of dynamic parallelism on accelerator-based multi-core systems / Parallel Comput 33 : 10~719

[confproc] B. B. Cambazoglu. / 2010 / A refreshing perspective of search engine caching / WWW

[confproc] E. Frachtenberg / 2009 / Reducing query latencies in web search using fine-grained parallelism / WWW

[confproc] S. Jonassen. / 2012 / Prefetching query results and its impact on search engines / SIGIR

[confproc] Q. Gan. / 2009 / Improved techniques for result caching in web search engines / WWW

[confproc] C. Macdonald. / 2012 / Learning to predict response times for online query scheduling / SIGIR

[confproc] S. Ren. / 2013 / Exploiting processor heterogeneity in interactive services / ICAC

[confproc] M. E. Haque. / 2015 / Few-to-many: Incremental parallelism for reducing tail latency in interactive services / ASPLOS

[journal] 전명제 / 2011 / Empirical Analysis of a Large-Scale Blog Workload / 한국지식정보기술학회 논문지 / 한국지식정보기술학회 6(1) : 17~26

[confproc] Z. Li. / 2004 / C-Miner: Mining block correlations in storage systems / FAST : 173~186

KJCKorea
Journal Central

Journal of Knowledge Information Technology and Systems 2023 KCI Impact Factor : 0.89