Storage performance virtualization via throughput and latency control

ABSTRACT

I/O consolidation is a growing trend in production environments due to increasing complexity in tuning and managing storage systems. A consequence of this trend is the need to serve multiple users and/or workloads simultaneously. It is imperative to ensure that these users are insulated from each other by virtualization in order to meet any service-level objective (SLO). Previous proposals for performance virtualization suffer from one or more of the following drawbacks: (1) They rely on a fairly detailed performance model of the underlying storage system; (2) couple rate and latency allocation in a single scheduler, making them less flexible; or (3) may not always exploit the full bandwidth offered by the storage system.This article presents a two-level scheduling framework that can be built on top of an existing storage utility. This framework uses a low-level feedback-driven request scheduler, called AVATAR, that is intended to meet the latency bounds determined by the SLO. The load imposed on AVATAR is regulated by a high-level rate controller, called SARC, to insulate the users from each other. In addition, SARC is work-conserving and tries to fairly distribute any spare bandwidth in the storage system to the different users. This framework naturally decouples rate and latency allocation. Using extensive I/O traces and a detailed storage simulator, we demonstrate that this two-level framework can simultaneously meet the latency and throughput requirements imposed by an SLO, without requiring extensive knowledge of the underlying storage system.

REFERENCES

• 1: Guillermo A. Alvarez , Elizabeth Borowsky , Susie Go , Theodore H. Romer , Ralph Becker-Szendy , Richard Golding , Arif Merchant , Mirjana Spasojevic , Alistair Veitch , John Wilkes, Minerva: An automated resource provisioning tool for large-scale storage systems, ACM Transactions on Computer Systems (TOCS), v.19 n.4, p.483-518, November 2001 [doi>10.1145/502912.502915]
• 2: Eric Anderson , Michael Hobbs , Kimberly Keeton , Susan Spence , Mustafa Uysal , Alistair C. Veitch, Hippodrome: Running Circles Around Storage Administration, Proceedings of the Conference on File and Storage Technologies, p.175-188, January 28-30, 2002
• 3: John Bruno , Jose Brustoloni , Eran Gabber , Banu Ozden , Abraham Silberschatz, Disk Scheduling with Quality of Service Guarantees, Proceedings of the IEEE International Conference on Multimedia Computing and Systems Volume II-Volume 2, p.400, June 07-11, 1999
• 4: Chambliss, D., Alvarez, G., Pandey, P., Jadav, D., Xu, J., Menon, R., and Lee, T. 2003. Performance virtulization for large-scale storage systems. In Proceedings of the Symposium on Reliable Distributed Systems (SRDS).
• 5: Ganger, G., Worthington, B., and Patt, Y. 2006. The DiskSim Simulation Environment Version 2.0 Reference Manual. http://www.pdl.cmu.edu/DiskSim/.
• 6: Goyal, P., Jadav, D., Modha, D. S., and Tewari, R. 2003. CacheCOW: QoS for storage system caches. In Proceedings of the 8th International Workshop on Quality of Service (IWQoS), Monterey, CA.
• 7: Lan Huang , Gang Peng , Tzi-cker Chiueh, Multi-dimensional storage virtualization, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 8: Wei Jin , Jeffrey S. Chase , Jasleen Kaur, Interposed proportional sharing for a storage service utility, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 9: Karlsson, M., Karamanolis, C., and Zhu, X. 2004. Triage: Performance isolation and differentiation for storage systems. In Proceedings of the 9th International Workshop on Quality of Service (IWQoS).
• 10: Bong-Jun Ko , Kang-Won Lee , Khalil Amiri , Seraphin Calo, Scalable Service Differentiation in a Shared Storage Cache, Proceedings of the 23rd International Conference on Distributed Computing Systems, p.184, May 19-22, 2003
• 11: Christopher R. Lumb , Arif Merchant , Guillermo A. Alvarez, Façade: Virtual Storage Devices with Performance Guarantees, Proceedings of the 2nd USENIX Conference on File and Storage Technologies, March 31-31, 2003, San Francisco, CA
• 12: Abhay K. Parekh , Robert G. Gallager, A generalized processor sharing approach to flow control in integrated services networks: the single-node case, IEEE/ACM Transactions on Networking (TON), v.1 n.3, p.344-357, June 1993 [doi>10.1109/90.234856]
• 13: Prashant Shenoy , Harrick M. Vin, Cello: A Disk Scheduling Framework for Next Generation Operating Systems*, Real-Time Systems, v.22 n.1-2, p.9-48, Jan.-March 2002 [doi>10.1023/A:1013437003242]
• 14: Elizabeth Shriver , Arif Merchant , John Wilkes, An analytic behavior model for disk drives with readahead caches and request reordering, Proceedings of the 1998 ACM SIGMETRICS joint international conference on Measurement and modeling of computer systems, p.182-191, June 22-26, 1998, Madison, Wisconsin, United States
• 15: The Openmail Trace. 2006. http://tesla.hpl.hp.com/private_software/.
• 16: Mustafa Uysal , Guillermo A. Alvarez , Arif Merchant, A Modular, Analytical Throughput Model for Modern Disk Arrays, Proceedings of the Ninth International Symposium in Modeling, Analysis and Simulation of Computer and Telecommunication Systems (MASCOTS'01), p.183, August 15-18, 2001
• 17: Mengzhi Wang , Kinman Au , Anastassia Ailamaki , Anthony Brockwell , Christos Faloutsos , Gregory R. Ganger, Storage device performance prediction with CART models, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 10-14, 2004, New York, NY, USA
• 18: WebSearch trace. 2006. http://traces.cs.umass.edu/storage/.
• 19: Bruce L. Worthington , Gregory R. Ganger , Yale N. Patt, Scheduling algorithms for modern disk drives, Proceedings of the 1994 ACM SIGMETRICS conference on Measurement and modeling of computer systems, p.241-251, May 16-20, 1994, Nashville, Tennessee, United States
• 20: Zhang, H. 1995. Service disciplines for guaranteed performance service in packet-switching networks. In Proceedings of the IEEE 83 Conference.
• 21: 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

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.2 Storage Management

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Operational analysis; Monitors; Measurements

General Terms:
Algorithms, Design, Management, Performance

Keywords:
I/O scheduling, Storage systems, fairness, performance isolation, quality of service, virtualization