Competitive Prefetching for Data-Intensive Online Servers

In a disk I/O-intensive online server, sequential data ac- cesses of one application instance can be frequently in- terrupted by other concurrent processes. Although ag- gressive I/O prefetching can improve the granularity of sequential data access, it must control the I/O bandwidth wasted on prefetching unneeded data. In this paper, we propose a competitive prefetching strategy that balances the overhead of disk I/O switching and that of unnec- essary prefetching. Based on a simple model, we show that the performance of our strategy (in terms of I/O throughput) is at least half that of the optimal offline pol- icy. We have implemented competitive prefetching in the Linux 2.6.3 kernel and conducted experiments based on microbenchmarks and two real applications (an index searching server and the Apache Web server). Our eval- uation results demonstrate that competitive prefetching can improve the throughput of real applications by 15%- 47%. The improvement is achieved without any applica- tion assistance or changes.