Memory resource allocation for file system prefetching: from a supply chain management perspective

ABSTRACT

As an important technique to hide disk I/O latency, prefetching has been widely studied, and dynamic adaptive prefetching techniques have been deployed in diverse storage environments. However, two issues are not well addressed by previous research: (1) how to handle the prefetching resource allocation between concurrent sequential access streams with different request rates, and (2) how to coordinate prefetching at multiple levels in the data access path.

Interestingly, we found that these problems bear a strong resemblance to situations long studied in the field of supply chain management (SCM), used by retailers such as Wal-Mart. In this paper, we demonstrate how to perform the problem mapping and then apply SCM principles in practice, particularly from the branch of inventory theory, to improve data prefetching performance in storage systems. More specifically, we applied (1) two SCM policies to dynamically configure the sequential prefetching parameters, and (2) an SCM solution to correct the access pattern information distortion in multi-level prefetching. We implemented these SCM-based strategies in the Linux kernel prefetching algorithm and a multi-level storage simulator, and evaluated the performance with three types of workloads. The results indicate that the SCM approaches are able to generate up to a 55.0% of performance improvement for a real-world server workload benchmark, and up to 33.3% for a combination of Linux I/O-intensive applications.

REFERENCES

• 1: Tarek F. Abdelzaher , Kang G. Shin , Nina Bhatti, Performance Guarantees for Web Server End-Systems: A Control-Theoretical Approach, IEEE Transactions on Parallel and Distributed Systems, v.13 n.1, p.80-96, January 2002 [doi>10.1109/71.980028]
• 2: T. Andel. Manage inventory, own information. Transportation and Distribution, 1996.
• 3: Jean-Loup Baer , Tien-Fu Chen, Effective Hardware-Based Data Prefetching for High-Performance Processors, IEEE Transactions on Computers, v.44 n.5, p.609-623, May 1995 [doi>10.1109/12.381947]
• 4: Rakesh Barve , Mahesh Kallahalla , Peter J. Varman , Jeffrey Scott Vitter, Competitive parallel disk prefetching and buffer management, Proceedings of the fifth workshop on I/O in parallel and distributed systems, p.47-56, November 17-17, 1997, San Jose, California, United States [doi>10.1145/266220.266225]
• 5: Ali R. Butt , Chris Gniady , Y. Charlie Hu, The performance impact of kernel prefetching on buffer cache replacement algorithms, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 6: Pei Cao, Application-controlled file caching and prefetching, Princeton University, Princeton, NJ, 1996
• 7: Pei Cao , Edward W. Felten , Anna R. Karlin , Kai Li, A study of integrated prefetching and caching strategies, ACM SIGMETRICS Performance Evaluation Review, v.23 n.1, p.188-197, May 1995
• 8: Zhifeng Chen , Yan Zhang , Yuanyuan Zhou , Heidi Scott , Berni Schiefer, Empirical evaluation of multi-level buffer cache collaboration for storage systems, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 9: Zhifeng Chen, Yuanyuan Zhou, and Kai Li. Evictionbased cache placement for storage caches. In Proceedings of the 2003 USENIX Annual Technical Conference, pages 269--282, Jun 2003. ISBN 1-931971-10-2.
• 10: S. Chopra and P. Meindl. Inventory Management and Production Planning and Scheduling. Prentice-Hall, 2001.
• 11: Brent Chun , David Culler , Timothy Roscoe , Andy Bavier , Larry Peterson , Mike Wawrzoniak , Mic Bowman, PlanetLab: an overlay testbed for broad-coverage services, ACM SIGCOMM Computer Communication Review, v.33 n.3, July 2003 [doi>10.1145/956993.956995]
• 12: Fredrik Dahlgren , Per Stenström, Evaluation of Hardware-Based Stride and Sequential Prefetching in Shared-Memory Multiprocessors, IEEE Transactions on Parallel and Distributed Systems, v.7 n.4, p.385-398, April 1996 [doi>10.1109/71.494633]
• 13: John W. C. Fu , Janak H. Patel, Data prefetching in multiprocessor vector cache memories, Proceedings of the 18th annual international symposium on Computer architecture, p.54-63, May 27-30, 1991, Toronto, Ontario, Canada
• 14: G. Ganger, B.Worthington, and Y. Patt. The disksim simulation environment version 2.0, Dec. 1999.
• 15: Binny S. Gill , Luis Angel D. Bathen, AMP: adaptive multi-stream prefetching in a shared cache, Proceedings of the 5th USENIX conference on File and Storage Technologies, p.26-26, February 13-16, 2007, San Jose, CA
• 16: Binny S. Gill , Dharmendra S. Modha, SARC: sequential prefetching in adaptive replacement cache, Proceedings of the annual conference on USENIX Annual Technical Conference, p.33-33, April 10-15, 2005, Anaheim, CA
• 17: Binny S. Gill, On multi-level exclusive caching: offline optimality and why promotions are better than demotions, Proceedings of the 6th USENIX Conference on File and Storage Technologies, p.1-17, February 26-29, 2008, San Jose, California
• 18: Donald Gross , Carl M. Harris, Fundamentals of queueing theory (2nd ed.)., John Wiley & Sons, Inc., New York, NY, 1985
• 19: Diwaker Gupta, Sangmin Lee, and Michael Vrable. Difference engine: Harnessing memory redundancy in virtual machines. In Proceedings of the 8th USENIX Symposium on Operating System Design and Implementation (OSDI '08), Berkeley, CA, USA, 2008. USENIX Association.
• 20: K. Jeffay , F. D. Smith , A. Moorthy , J. Anderson, Proportional Share Scheduling of Operating System Services for Real-Time Applications, Proceedings of the IEEE Real-Time Systems Symposium, p.480, December 02-04, 1998
• 21: Scott F. Kaplan , Lyle A. McGeoch , Megan F. Cole, Adaptive caching for demand prepaging, Proceedings of the 3rd international symposium on Memory management, June 20-21, 2002, Berlin, Germany
• 22: L. Kleinrock. Queueing Systems: Volume 2: Computer Applications. John Wiley & Sons, 1976.
• 23: B.O. Koopman. On distributions admitting a sufficient statistic. Transaction of American Mathematics Society, 1936.
• 24: R. L. Lee, P.-C. Yew, and D. H. Lawrie. Data prefetching in shared memory multiprocessors. In Proceedings of the International conference on parallel processing, pages 28--31, 1987.
• 25: Chuanpeng Li , Kai Shen, Managing prefetch memory for data-intensive online servers, Proceedings of the 4th conference on USENIX Conference on File and Storage Technologies, p.19-19, December 13-16, 2005, San Francisco, CA
• 26: Chuanpeng Li , Kai Shen , Athanasios E. Papathanasiou, Competitive prefetching for concurrent sequential I/O, ACM SIGOPS Operating Systems Review, v.41 n.3, June 2007
• 27: Zhenmin Li , Zhifeng Chen , Sudarshan M. Srinivasan , Yuanyuan Zhou, C-Miner: Mining Block Correlations in Storage Systems, Proceedings of the 3rd USENIX Conference on File and Storage Technologies, March 31-31, 2004, San Francisco, CA
• 28: Shuang Liang , Song Jiang , Xiaodong Zhang, STEP: Sequentiality and Thrashing Detection Based Prefetching to Improve Performance of Networked Storage Servers, Proceedings of the 27th International Conference on Distributed Computing Systems, p.64, June 25-27, 2007 [doi>10.1109/ICDCS.2007.141]
• 29: mit--beer. The mit beer game. http://beergame.mit.edu.
• 30: David Mosberger , Tai Jin, httperf—a tool for measuring web server performance, ACM SIGMETRICS Performance Evaluation Review, v.26 n.3, p.31-37, Dec. 1998 [doi>10.1145/306225.306235]
• 31: S. Devadas P. Jain and L. Rudolph. Controlling cache pollution in prefetching with software-assisted cache replacement. In Tech. Rep. CSG-462,M.I.T, 2001.
• 32: Athanasios E. Papathanasiou , Michael L. Scott, Energy efficient prefetching and caching, Proceedings of the annual conference on USENIX Annual Technical Conference, p.22-22, June 27-July 02, 2004, Boston, MA
• 33: R. H. Patterson , G. A. Gibson , E. Ginting , D. Stodolsky , J. Zelenka, Informed prefetching and caching, Proceedings of the fifteenth ACM symposium on Operating systems principles, p.79-95, December 03-06, 1995, Copper Mountain, Colorado, United States
• 34: Reducing Cache Pollution of Prefetching in a Small Data Cache, Proceedings of the International Conference on Computer Design: VLSI in Computers & Processors, p.530, September 23-26, 2001
• 35: Edward Silver, David Pyke, and Rein Peterson. Inventory Management and Production Planning and Scheduling. John Wiley & Sons, 1998. ISBN 978-0471119470.
• 36: Alan Jay Smith, Cache Memories, ACM Computing Surveys (CSUR), v.14 n.3, p.473-530, Sept. 1982 [doi>10.1145/356887.356892]
• 37: Gokul Soundararajan , Madalin Mihailescu , Cristiana Amza, Context-aware prefetching at the storage server, USENIX 2008 Annual Technical Conference on Annual Technical Conference, p.377-390, June 22-27, 2008, Boston, Massachusetts
• 38: Andrew Tomkins , R. Hugo Patterson , Garth Gibson, Informed multi-process prefetching and caching, Proceedings of the 1997 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.100-114, June 15-18, 1997, Seattle, Washington, United States
• 39: Theodore M. Wong , John Wilkes, My Cache or Yours? Making Storage More Exclusive, Proceedings of the General Track of the annual conference on USENIX Annual Technical Conference, p.161-175, June 10-15, 2002
• 40: Gala Yadgar , Michael Factor , Kai Li , Assaf Schuster, MC2: Multiple Clients on a Multilevel Cache, Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems, p.722-730, June 17-20, 2008 [doi>10.1109/ICDCS.2008.29]
• 41: Zhe Zhang , Kyuhyung Lee , Xiaosong Ma , Yuanyuan Zhou, PFC: Transparent Optimization of Existing Prefetching Strategies for Multi-Level Storage Systems, Proceedings of the 2008 The 28th International Conference on Distributed Computing Systems, p.740-751, June 17-20, 2008 [doi>10.1109/ICDCS.2008.89]
• 42: Yuanyuan Zhou , James Philbin , Kai Li, The Multi-Queue Replacement Algorithm for Second Level Buffer Caches, Proceedings of the General Track: 2002 USENIX Annual Technical Conference, p.91-104, June 25-30, 2001
• 43: Qingbo Zhu , Zhifeng Chen , Lin Tan , Yuanyuan Zhou , Kimberly Keeton , John Wilkes, Hibernator: helping disk arrays sleep through the winter, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.3 File Systems Management

General Terms:
Design, Performance

Keywords:
memory cache, prefetching, supply chain management