More Web Proxy on the site http://driver.im/

research-article

On the design of a new Linux readahead framework

Authors:

XU ChenfengAuthors Info & Claims

ACM SIGOPS Operating Systems Review, Volume 42, Issue 5

Pages 75 - 84

https://doi.org/10.1145/1400097.1400106

Published: 01 July 2008 Publication History

Abstract

As Linux runs an increasing variety of workloads, its in-kernel readahead algorithm has been challenged by many unexpected and subtle problems. To name a few: readahead thrashings arise when readahead pages are evicted prematurely under memory pressure; readahead attempts on already cached pages are undesirable; interrupted-then-retried reads and locally disordered NFS reads that can easily fool the sequential detection logic. In this paper, we present a new Linux readahead framework with flexible and robust heuristics that can cover varied sequential I/O patterns. It also enjoys great simplicity by handling most abnormal cases in an implicit way. We demonstrate its advantages by a host of case studies. Network throughput is 3 times better in the case of thrashing and 1.8 times better for large NFS files. On serving large files with lighttpd, the disk utilization is decreased by 26% while providing 17% more network throughput.

References

[1]

S. Bhattacharya, J. Tran, M. Sullivan, and C. Mason. Linux aio performance and robustness for enterprise workloads. In Proceedings of the Linux Symposium, 2004.

[2]

A. D. Brown, T. C. Mowry, and O. Krieger. Compiler-based i/o prefetching for out-of-core applications. ACM Trans. Comput. Syst., 19:111--170, 2001.

Digital Library

[3]

A. R. Butt, C. Gniady, and Y. C. Hu. The performance impact of kernel prefetching on buffer cache replacement algorithms. SIGMETRICS Perform. Eval. Rev., 33:157--168, 2005.

Digital Library

[4]

P. Cao, E. W. Felten, A. R. Karlin, and K. Li. A study of integrated prefetching and caching strategies. In Proceedings of the 1995 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, pages 188--197, Ottawa, Ontario, Canada, 1995. ACM.

Digital Library

[5]

P. Cao, E. W. Felten, A. R. Karlin, and K. Li. Implementation and performance of integrated application-controlled file caching, prefetching, and disk scheduling. ACM Trans. Comput. Syst., 14:311--343, 1996.

Digital Library

[6]

G. Dini, G. Lettieri, and L. Lopriore. Caching and prefetching algorithms for programs with looping reference patterns. The Computer Journal, 49:42--61, 2006.

Digital Library

[7]

D. Ellard, J. Ledlie, P. Malkani, and M. Seltzer. Passive NFS tracing of email and research workloads. In Proceedings of the Second USENIX Conference on File and Storage Technologies (FAST'03), pages 203--216, San Francisco, CA, March 2003.

Digital Library

[8]

D. Ellard and M. Seltzer. Nfs tricks and benchmarking traps. In Proceedings of the FREENIX 2003 Technical Conference, pages 101--114, San Antonio, TX, June 2003.

Digital Library

[9]

B. Esfahbod. Preload - an adaptive prefetching daemon. Master's thesis, Graduate Department of Computer Science, University of Toronto, 2006.

[10]

R. J. Feiertag and E. I. Organick. The multics input/output system. In Proceedings of the third ACM symposium on Operating systems principles, pages 35--41, Palo Alto, California, United States, 1971. ACM.

Digital Library

[11]

B. S. Gill and L. A. D. Bathen. Optimal multistream sequential prefetching in a shared cache. Trans. Storage, 3(3):10, 2007.

Digital Library

[12]

B. S. Gill and D. S. Modha. Sarc: sequential prefetching in adaptive replacement cache. In ATEC'05: Proceedings of the USENIX Annual Technical Conference 2005 on USENIX Annual Technical Conference, pages 33--33, Berkeley, CA, USA, 2005. USENIX Association.

Digital Library

[13]

T. M. Kroeger and D. D. E. Long. Design and implementation of a predictive file prefetching algorithm. In Proceedings of the General Track: 2002 USENIX Annual Technical Conference, pages 105--118, Berkeley, CA, USA, 2001. USENIX Association.

Digital Library

[14]

C. Li and K. Shen. Managing prefetch memory for data-intensive online servers. In FAST'05: Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, pages 19--19, Berkeley, CA, USA, 2005. USENIX Association.

Digital Library

[15]

C. Li, K. Shen, and A. E. Papathanasiou. Competitive prefetching for concurrent sequential i/o. In Proceedings of the ACM SIGOPS/EuroSys European Conference on Computer Systems 2007, pages 189--202, Lisbon, Portugal, 2007. ACM.

Digital Library

[16]

Z. Li, Z. Chen, and Y. Zhou. Mining block correlations to improve storage performance. Trans. Storage, 1:213--245, 2005.

Digital Library

[17]

S. Liang, S. Jiang, and X. Zhang. Step: Sequentiality and thrashing detection based prefetching to improve performance of networked storage servers. In ICDCS, page 64, 2007.

Digital Library

[18]

M. K. McKusick, W. N. Joy, S. J. Leffler, and R. S. Fabry. A fast file system for unix. ACM Trans. Comput. Syst., 2(3):181--197, 1984.

Digital Library

[19]

R. Pai, B. Pulavarty, and M. Cao. Linux 2.6 performance improvement through readahead optimization. In Proceedings of the Linux Symposium, 2004.

[20]

A. E. Papathanasiou and M. L. Scott. Aggressive prefetching: An idea whose time has come. In Proceedings of the 10th Workshop on Hot Topics in Operating Systems (HotOS), 2005.

Digital Library

[21]

R. H. Patterson, G. A. Gibson, E. Ginting, D. Stodolsky, and J. Zelenka. Informed prefetching and caching. In Proceedings of the fifteenth ACM symposium on Operating systems principles, pages 79--95, Copper Mountain, Colorado, United States, 1995. ACM.

Digital Library

[22]

R. H. Patterson, G. A. Gibson, and M. Satyanarayanan. A status report on research in transparent informed prefetching. SIGOPS Oper. Syst. Rev., 27(2):21--34, 1993.

Digital Library

[23]

J.-F. Paris, A. Amer, and D. D. E. Long. A stochastic approach to file access prediction. In Proceedings of the international workshop on Storage network architecture and parallel I/Os, pages 36--40, New Orleans, Louisiana, 2003. ACM.

Digital Library

[24]

D. Revel, D. McNamee, D. Steere, and J. Walpole. Adaptive prefetching for device independent file I/O. Technical Report CSE-97-005, 18, 1997.

Digital Library

[25]

E. Shriver, C. Small, and K. A. Smith. Why does file system prefetching work? In ATEC'99: Proceedings of the Annual Technical Conference on 1999 USENIX Annual Technical Conference, pages 71--84, Berkeley, CA, USA, 1999. USENIX Association.

Digital Library

[26]

G. A. S. Whittle, J.-F. Pâris, A. Amer, D. D. E. Long, and R. Burns. Using multiple predictors to improve the accuracy of file access predictions. In MSS '03: Proceedings of the 20 th IEEE/11th NASA Goddard Conference on Mass Storage Systems and Technologies (MSS'03), page 230, Washington, DC, USA, 2003. IEEE Computer Society.

Digital Library

[27]

F. Wu, H. Xi, J. Li, and N. Zou. Linux readahead: less tricks for more. In Proceedings of the Linux Symposium, 2007.

Cited By

Seo DJoo YDutt N(2024)Improving Virtualized I/O Performance by Expanding the Polled I/O Path of LinuxProceedings of the 16th ACM Workshop on Hot Topics in Storage and File Systems10.1145/3655038.3665944(31-37)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3655038.3665944
Ryu JAn JKang KGanesan DLane NShi W(2024)EximCache: Block I/O Caching Based on Latency Sensitivity from the Readahead FrameworkProceedings of the 30th Annual International Conference on Mobile Computing and Networking10.1145/3636534.3697435(1611-1613)Online publication date: 4-Dec-2024
https://dl.acm.org/doi/10.1145/3636534.3697435
Ryu JLee DShin KKang KNaor DGoel A(2023)Fast application launch on personal computing/communication devicesProceedings of the 21st USENIX Conference on File and Storage Technologies10.5555/3585938.3585965(425-439)Online publication date: 21-Feb-2023
https://dl.acm.org/doi/10.5555/3585938.3585965
Show More Cited By

Index Terms

On the design of a new Linux readahead framework

Recommendations

Criticality aware tiered cache hierarchy: a fundamental relook at multi-level cache hierarchies
ISCA '18: Proceedings of the 45th Annual International Symposium on Computer Architecture

On-die caches are a popular method to help hide the main memory latency. However, it is difficult to build large caches without substantially increasing their access latency, which in turn hurts performance. To overcome this difficulty, on-die caches ...
Near-Optimal Parallel Prefetching and Caching

Recently there has been a great deal of interest in the operating systems research community in prefetching and caching data from parallel disks, as a technique for enabling serial applications to improve input--output (I/O) performance. In this paper, ...
Using Libception to Understand and Improve HTTP Streaming Video Server Throughput
ICPE '17: Proceedings of the 8th ACM/SPEC on International Conference on Performance Engineering

Video streaming applications generate a large fraction of Internet traffic. Much of this content is delivered over HTTP using standard web servers. Unlike other types of web workloads, HTTP video streaming workloads are typically disk bound, and ...

Comments

Please enable JavaScript to view thecomments powered by Disqus.

Information & Contributors

Information

Published In

cover image ACM SIGOPS Operating Systems Review

ACM SIGOPS Operating Systems Review Volume 42, Issue 5

Research and developments in the Linux kernel

July 2008

113 pages

ISSN:0163-5980

DOI:10.1145/1400097

Issue’s Table of Contents

Copyright © 2008 Authors.

Publisher

Association for Computing Machinery

New York, NY, United States

Publication History

Published: 01 July 2008

Published in SIGOPS Volume 42, Issue 5

Check for updates

Author Tags

Qualifiers

Research-article

Funding Sources

Contributors

Other Metrics

View Article Metrics

Bibliometrics & Citations

Bibliometrics

Article Metrics

46
Total Citations
View Citations
2,577
Total Downloads

Downloads (Last 12 months)41
Downloads (Last 6 weeks)6

Reflects downloads up to 01 Jan 2025

Other Metrics

View Author Metrics

Citations

Cited By

Seo DJoo YDutt N(2024)Improving Virtualized I/O Performance by Expanding the Polled I/O Path of LinuxProceedings of the 16th ACM Workshop on Hot Topics in Storage and File Systems10.1145/3655038.3665944(31-37)Online publication date: 8-Jul-2024
https://dl.acm.org/doi/10.1145/3655038.3665944
Ryu JAn JKang KGanesan DLane NShi W(2024)EximCache: Block I/O Caching Based on Latency Sensitivity from the Readahead FrameworkProceedings of the 30th Annual International Conference on Mobile Computing and Networking10.1145/3636534.3697435(1611-1613)Online publication date: 4-Dec-2024
https://dl.acm.org/doi/10.1145/3636534.3697435
Ryu JLee DShin KKang KNaor DGoel A(2023)Fast application launch on personal computing/communication devicesProceedings of the 21st USENIX Conference on File and Storage Technologies10.5555/3585938.3585965(425-439)Online publication date: 21-Feb-2023
https://dl.acm.org/doi/10.5555/3585938.3585965
Qian YCheng WZeng LLi XVef MDilger ALai SIhara SFan YBrinkmann AMohror KArnold DBadia R(2023)Xfast: Extreme File Attribute Stat Acceleration for LustreProceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis10.1145/3581784.3607080(1-12)Online publication date: 12-Nov-2023
https://dl.acm.org/doi/10.1145/3581784.3607080
Akgun IAydin ABurford AMcNeill MArkhangelskiy MZadok E(2023)Improving Storage Systems Using Machine LearningACM Transactions on Storage10.1145/356842919:1(1-30)Online publication date: 19-Jan-2023
https://dl.acm.org/doi/10.1145/3568429
Li ASudvarg MLiu HYu ZGill CZhang N(2022)PolyRhythm: Adaptive Tuning of a Multi-Channel Attack Template for Timing Interference2022 IEEE Real-Time Systems Symposium (RTSS)10.1109/RTSS55097.2022.00028(225-239)Online publication date: Dec-2022
https://doi.org/10.1109/RTSS55097.2022.00028
Xu YLi HWang HGu BLv YLuo LLi CShi L(2022)Practical optimizations for lightweight distributed file system on consumer devicesCCF Transactions on High Performance Computing10.1007/s42514-022-00132-w4:4(474-491)Online publication date: 2-Dec-2022
https://doi.org/10.1007/s42514-022-00132-w
Akgun IAydin AShaikh AVelikov LZadok EShilane PWon Y(2021)A Machine Learning Framework to Improve Storage System PerformanceProceedings of the 13th ACM Workshop on Hot Topics in Storage and File Systems10.1145/3465332.3470875(94-102)Online publication date: 27-Jul-2021
https://dl.acm.org/doi/10.1145/3465332.3470875
Liu CLee YJung MKandemir MChoi WSherwood TBerger EKozyrakis C(2021)Prolonging 3D NAND SSD lifetime via read latency relaxationProceedings of the 26th ACM International Conference on Architectural Support for Programming Languages and Operating Systems10.1145/3445814.3446733(730-742)Online publication date: 19-Apr-2021
https://dl.acm.org/doi/10.1145/3445814.3446733
Li DOta KZhong YDong MTang YQiu J(2021)Towards High-Efficient Transaction Commitment in a Virtualized and Sustainable RDBMSIEEE Transactions on Sustainable Computing10.1109/TSUSC.2019.28908416:3(507-521)Online publication date: 1-Jul-2021
https://doi.org/10.1109/TSUSC.2019.2890841
Show More Cited By

View Options

Login options

Check if you have access through your login credentials or your institution to get full access on this article.

Full Access

Get this Publication

View options

PDF

View or Download as a PDF file.

eReader

View online with eReader.

Media

Figures

Other

Tables

View Issue’s Table of Contents