Competitive Prefetching for Data-Intensive Online Servers Chuanpeng Li, Athanasios E. Papathanasiou, and Kai Shen Department of Computer Science, University of Rochester In a disk I/O-intensive online server, sequential data accesses of one application instance can be frequently interrupted by other concurrent processes. Although aggressive 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 unnecessary 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 policy. 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 evaluation results demonstrate that competitive prefetching can improve the throughput of real applications by 15%--47%. The improvement is achieved without any application assistance or changes.