Minerva: An automated resource provisioning tool for large-scale storage systems

ABSTRACT

Enterprise-scale storage systems, which can contain hundreds of host computers and storage devices and up to tens of thousands of disks and logical volumes, are difficult to design. The volume of choices that need to be made is massive, and many choices have unforeseen interactions. Storage system design is tedious and complicated to do by hand, usually leading to solutions that are grossly over-provisioned, substantially under-performing or, in the worst case, both.To solve the configuration nightmare, we present minerva: a suite of tools for designing storage systems automatically. Minerva uses declarative specifications of application requirements and device capabilities; constraint-based formulations of the various sub-problems; and optimization techniques to explore the search space of possible solutions.This paper also explores and evaluates the design decisions that went into Minerva, using specialized micro- and macro-benchmarks. We show that Minerva can successfully handle a workload with substantial complexity (a decision-support database benchmark). Minerva created a 16-disk design in only a few minutes that achieved the same performance as a 30-disk system manually designed by human experts. Of equal importance, Minerva was able to predict the resulting system's performance before it was built.

REFERENCES

• 1: 3COM CORP. 1996. Gigabit Ethernet comes of age. 3Com Corporation. Technology white paper.
• 2: ANSI. 1996. Fibre Channel Arbitrated Loop. ANSI. Standard X3.272-1996.
• 3: Baruch Awerbuch , Yair Bartal , Amos Fiat, Competitive distributed file allocation, Proceedings of the twenty-fifth annual ACM symposium on Theory of computing, p.164-173, May 16-18, 1993, San Diego, California, United States [doi>10.1145/167088.167142]
• 4: BOROWSKY, E., GOLDING, R., MERCHANT, A., SCHREIER, L., SHRIVER, E., SPASOJEVIC, M., AND WILKES,J. 1997. Using attribute-managed storage to achieve QoS. In Proceedings of the 5th Intl. Workshop on Quality of Service (June 1997).
• 5: P. C. Chu , J. E. Beasley, A genetic algorithm for the generalised assignment problem, Computers and Operations Research, v.24 n.1, p.17-23, Jan. 1997 [doi>10.1016/S0305-0548(96)00032-9]
• 6: COFFMAN, E., GAREY, M., AND JOHNSON, D. 1984. Approximation algorithms for bin-packing: An updated survey. In G. AUSIELLO,M.LUCERTINI, AND P. SERAFINI Eds., Algorithm Design for Computer System Design, pp. 49-106. Springer-Verlag.
• 7: Lawrence W. Dowdy , Derrell V. Foster, Comparative Models of the File Assignment Problem, ACM Computing Surveys (CSUR), v.14 n.2, p.287-313, June 1982 [doi>10.1145/356876.356883]
• 8: A. Drexl, A simulated annealing approach to the multiconstraint zero-one knapsack problem, Computing, v.40 n.1, p.1-8, January 1988 [doi>10.1007/BF02242185]
• 9: Michael R. Garey , David S. Johnson, Computers and Intractability: A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1979
• 10: J. P. Gelb, System-managed storage, IBM Systems Journal, v.28 n.1, p.77-103, 1989
• 11: HEWLETT-PACKARD COMPANY. 1998. Model 30/FC High Availability Disk Array-User's Guide. Hewlett-Packard Company. Pub. No. A3661-90001.
• 12: Geoffrey H. Kuenning, Kitrace: precise interactive measurement of operating systems kernels, Software—Practice & Experience, v.25 n.1, p.1-21, Jan. 1995 [doi>10.1002/spe.4380250102]
• 13: MENON,J.AND MATTSON, D. 1992. Performance of disk arrays in transaction processing environments. In Proceedings of the 12th ICDCS (June 1992), pp. 302-309.
• 14: MERCHANT,A.AND ALVAREZ, G. A. 2001. Disk array models in Minerva. Technical Report HPL-2001- 118 (April), Hewlett-Packard Laboratories. http://www.hpl.hp.com/techreports.
• 15: Arif Merchant , Philip S. Yu, Analytic Modeling of Clustered RAID with Mapping Based on Nearly Random Permutation, IEEE Transactions on Computers, v.45 n.3, p.367-373, March 1996 [doi>10.1109/12.485575]
• 16: David A. Patterson , Garth Gibson , Randy H. Katz, A case for redundant arrays of inexpensive disks (RAID), Proceedings of the 1988 ACM SIGMOD international conference on Management of data, p.109-116, June 01-03, 1988, Chicago, Illinois, United States
• 17: PATTIPATI,K.R.AND WOLF, J. L. 1990. A file assignment problem model for extended local area network environments. In Proceedings of the 10th ICDCS (May 1990), pp. 554-61.
• 18: RUEMMLER,C.AND WILKES, J. 1993. Unix disk access patterns. In Proceedings of the Winter USENIX (Jan. 1993), pp. 405-420.
• 19: Alexander Thomasian , Jai Menon, Performance Analysis of RAID5 Disk Arrays with a Vacationing Server Model for Rebuild Mode Operation, Proceedings of the Tenth International Conference on Data Engineering, p.111-119, February 14-18, 1994
• 20: TOYODA, Y. 1975. A simplified algorithm for obtaining approximate solutions to zero-one programming problems. Management Science 21, 12 (Aug.), 1417-27.
• 21: TRANSACTION PROCESSING PERFORMANCE COUNCIL. 1992. TPC benchmark C, standard specification, revision 1.0. Transaction Processing Performance Council.
• 22: TRANSACTION PROCESSING PERFORMANCE COUNCIL. 1996. TPC benchmark D, standard specification, revision 1.2. Transaction Processing Performance Council.
• 23: TRICK, M. 1992. A linear relaxation heuristic for the generalized assignment problem. Naval Research Logistics 39, 137-51.
• 24: J. Wolf, The placement optimization program: a practical solution to the disk file assignment problem, Proceedings of the 1989 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.1-10, May 23-26, 1989, Oakland, California, United States

INDEX TERMS

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

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Modeling and prediction

  G. Mathematics of Computing
  G.1 NUMERICAL ANALYSIS
      G.1.6 Optimization
          Subjects: Constrained optimization

General Terms:
Algorithms, Management, Performance

Keywords:
Disk array, RAID, automatic design