Multi-dimensional storage virtualization

ABSTRACT

Most state-of-the-art commercial storage virtualization systems focus only on one particular storage attribute, capacity. This paper describes the design, implementation and evaluation of a multi-dimensional storage virtualization system called Stonehenge, which is able to virtualize a cluster-based physical storage system along multiple dimensions, including bandwidth, capacity, and latency. As a result, Stonehenge is able to multiplex multiple virtual disks, each with a distinct bandwidth, capacity, and latency attribute, on a single physical storage system as if they are separate physical disks. A key enabling technology for Stonehenge is an efficiency-aware real-time disk scheduling algorithm called dual-queue disk scheduling, which maximizes disk utilization efficiency while providing Quality of Service (QoS) guarantees. To optimize disk utilization efficiency, Stonehenge exploits run-time measurements extensively, for admission control, computing latency-derived bandwidth requirement, and predicting disk service time.

References

1. G. Alvarez, E. Borowsky, S. Go, T. Romer, R. BeckerSzendy, R. Golding, A. Merchant, M. Spasojevic, A. Veitch, and J. Wilkes. Minerva: an automated resource provisioning tool for large-scale storage systems. ACM Transactions on Computer Systems, 2001.
2. D. Anderson, J. Dykes, and E. Riedel. More than an interface: Scsi vs. ata. In Proceeding of File System and Storage Technology Conference (FAST 03), Jan 2003.
3. E. Anderson, M. Hobbs, K. Keeton, S. Spence, M. Uysal, and A. Veitch. Hippodrome: running circles around storage administration. In Conference on File and Storage Technology (FAST'02), pages 175--188, Monterey, CA, January 2002.
4. E. Anderson, M. Kallahalla, S. Spence, R. Swaminathan, and Q. Wang. Ergastulum: an approach to solving the workload and device configuration problem. Technical Report HPL-SSP-2001-05, HP Laboratories, 2001.
5. L. Breslau, S. Jamin, and S. Shenker. Comments on the performance of measurement-based admission control. In Proceedings of IEEE Infocomm 2000, Tel Aviv, Israel, March 2000.
6. J. L. Bruno, J. C. Brustoloni, E. Gabber, B. Ozden, and A. Silberschatz. Disk scheduling with quality of service guarantees. In Proc. of IEEE Int. Conf. on Multimedia Computing and Systems (ICMCS'99), pages 400--405, 1999.
7. S. Chen, J. A. Stankovic, J. F. Kurose, and D. Towsley. Performance evaluation of two new disk scheduling algorithms for real-time systems. Technical Report UM-CS-1990-077, 1990.
8. D. Ferrari and D. C. Verma. A scheme for real-time channel establishment in wide-area networks. IEEE Journal on Selected Areas in Communications, 8(3):368--379, 1990.
9. K. Gopalan and T. Chiueh. Real-time disk scheduling using deadline sensitive scan. Technical Report ECSL-TR-92, SUNY Stony Brook, January 2001.
10. W. Hsu. Dynamic locality improvement techniques for increasing effective storage performance. Technical Report UCB/CSD-03-1223, Computer Science Division, University of California at Berkeley, Jan, 2003.
11. L. Huang. Stonehenge: A high performance virtualized storage cluster with qos guarantee. Technical Report TR-138, ECSL, Computer Science Department, SUNY Stony Brook, 2003.
12. S. Jamin, P. Danzig, S. Shenker, and L. Zhang. A measurement-based admission control algorithm for integrated services packet networks. In SIGCOMM Symposium on Communications Architectures and Protocols, pages 2--13, 1995.
13. C. R. Lumb, A. Merchant, and G. A. Alvarez. Façade: Virtual storage devices with performance guarantees. In Proceedings of the 2nd USENIX conference on File and Storage technolgies, pages 131--144, San Francisco, CA, April 2003.
14. A. K. Parekh and R. G. Gallagher. A generalized processor sharing approach to ow control in integrated services networks: the multiple node case. IEEE/ACM Transactions on Networking, 2(2):137--150, 1994.
15. P. Shenoy and H. M. Vin. Cello: A disk scheduling framework for next generation operating systems. In Proceedings of ACM SIGMETRICS Conference, Madison, WI, pages 44--55, June 1998.
16. Y. Toyoda. A simplified algorithm for obtaining approximate solutions to zero-one integer programming. Management Science, 21:1417--1427, 1975.
17. B. Urgaonkar, P. Shenoy, and T. Roscoe. Resource overbooking and application profiling in shared hosting platforms. In Proceedings of the Fifth Symposium on Operating Systems Design and Implementation (OSDI), pages 239254, Boston, MA, December 2002.
18. H. M. Vin, P. Goyal, and A. Goyal. A statistical admission control algorithm for multimedia servers. In ACM Multimedia, pages 33--40, 1994.
19. R. Wijayaratne and A. Reddy. Integrated qos management for disk I/O. In Proc. of IEEE Int. Conf. on Multimedia Computing and Systems (ICMCS'99), Florence, Italy, June 1999.
20. B. Worthington, G. R. Ganger, Y. N. Patt, and J. Wilkes. On-line extraction of SCSI disk drive parameters. In Performance Evaluation Review, volume 23, pages 146--56, May 1995.
21. H. Zhang. Service disciplines for guaranteed performance service in packet-switching networks. In Proc. of the IEEE, Vol. 83, no. 10, pages 1374--1396, Oct 1995.
22. L. Zhang. VirtualClock: A new traffic control algorithm for packet-switched networks. ACM Transactions on Computer Systems, 9(2):101--124, 1991.

Index Terms

• General and reference

  • Cross-computing tools and techniques

    • Measurement

• Information systems

  • Information storage systems

    • Storage management

• Software and its engineering

  • Software organization and properties

    • Contextual software domains

      • Operating systems

        • File systems management

        • Memory management

        • Process management