Exploiting nonstationarity for performance prediction

ABSTRACT

Real production applications ranging from enterprise applications to large e-commerce sites share a crucial but seldom-noted characteristic: The relative frequencies of transaction types in their workloads are nonstationary, i.e., the transaction mix changes over time. Accurately predicting application-level performance in business-critical production applications is an increasingly important problem. However, transaction mix nonstationarity casts doubt on the practical usefulness of prediction methods that ignore this phenomenon.

This paper demonstrates that transaction mix nonstationarity enables a new approach to predicting application-level performance as a function of transaction mix. We exploit nonstationarity to circumvent the need for invasive instrumentation and controlled benchmarking during model calibration; our approach relies solely on lightweight passive measurements that are routinely collected in today's production environments. We evaluate predictive accuracy on two real business-critical production applications. The accuracy of our response time predictions ranges from 10% to 16% on these applications, and our models generalize well to workloads very different from those used for calibration.

We apply our technique to the challenging problem of predicting the impact of application consolidation on transaction response times. We calibrate models of two testbed applications running on dedicated machines, then use the models to predict their performance when they run together on a shared machine and serve very different workloads. Our predictions are accurate to within 4% to 14%. Existing approaches to consolidation decision support predict post-consolidation resource utilizations. Our method allows application-level performance to guide consolidation decisions.

REFERENCES

• 1: A. Andrzejak, M. Arlitt, and J. A. Rolia. Bounding the resource savings of utility computing models. Technical Report HPL-2002-339, HP Labs, Dec. 2002.
• 2: Martin Arlitt, Characterizing Web user sessions, ACM SIGMETRICS Performance Evaluation Review, v.28 n.2, p.50-63, Sept. 2000 [doi>10.1145/362883.362920]
• 3: Characterizing the scalability of a large web-based shopping system, ACM Transactions on Internet Technology (TOIT), v.1 n.1, p.44-69, Aug. 2001 [doi>10.1145/383034.383036]
• 4: Martin F. Arlitt , Carey L. Williamson, Web server workload characterization: the search for invariants, Proceedings of the 1996 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.126-137, May 23-26, 1996, Philadelphia, Pennsylvania, United States
• 5: Martin F. Arlitt , Carey L. Williamson, Internet Web servers: workload characterization and performance implications, IEEE/ACM Transactions on Networking (TON), v.5 n.5, p.631-645, Oct. 1997 [doi>10.1109/90.649565]
• 6: H. Pat Artis, Capacity planning for MVS computer systems, ACM SIGMETRICS Performance Evaluation Review, v.8 n.4, p.45-62, Winter 1979-1980 [doi>10.1145/1041864.1041869]
• 7: Paul Barham , Austin Donnelly , Rebecca Isaacs , Richard Mortier, Using magpie for request extraction and workload modelling, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.18-18, December 06-08, 2004, San Francisco, CA
• 8: I. Barrodale and F. Roberts. An improved algorithm for discrete LI linear approximations. SIAM Journal of Numerical Analysis, 10:839--848, 1973.
• 9: Forest Baskett , K. Mani Chandy , Richard R. Muntz , Fernando G. Palacios, Open, Closed, and Mixed Networks of Queues with Different Classes of Customers, Journal of the ACM (JACM), v.22 n.2, p.248-260, April 1975 [doi>10.1145/321879.321887]
• 10: Gunter Bolch , Stefan Greiner , Hermann de Meer , Kishor Shridharbhai Trivedi, Queueing Networks and Markov Chains, Wiley-Interscience, 2005
• 11: L. Breslau, P. Cao, L. Fan, G. Phillips, and S. Shenker. Web caching and Zipf-like distributions: Evidence and implications. In INFOCOM, Mar. 1999.
• 12: Jin Cao , William S. Cleveland , Dong Lin , Don X. Sun, On the nonstationarity of Internet traffic, Proceedings of the 2001 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, p.102-112, June 2001, Cambridge, Massachusetts, United States
• 13: Giuliano Casale, An efficient algorithm for the exact analysis of multiclass queueing networks with large population sizes, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 14: Adrian Cockcroft , Walker, Capacity Planning for Internet Services, Prentice Hall Professional Technical Reference, 2001
• 15: Ira Cohen , Moises Goldszmidt , Terence Kelly , Julie Symons , Jeffrey S. Chase, Correlating instrumentation data to system states: a building block for automated diagnosis and control, Proceedings of the 6th conference on Symposium on Opearting Systems Design & Implementation, p.16-16, December 06-08, 2004, San Francisco, CA
• 16: Ira Cohen , Steve Zhang , Moises Goldszmidt , Julie Symons , Terence Kelly , Armando Fox, Capturing, indexing, clustering, and retrieving system history, Proceedings of the twentieth ACM symposium on Operating systems principles, October 23-26, 2005, Brighton, United Kingdom
• 17: Peter J. Denning , Jeffrey P. Buzen, The Operational Analysis of Queueing Network Models, ACM Computing Surveys (CSUR), v.10 n.3, p.225-261, Sept. 1978 [doi>10.1145/356733.356735]
• 18: A. Esposito , A. Mazzeo , P. Costa, Workload characterization for trend analysis, ACM SIGMETRICS Performance Evaluation Review, v.10 n.2, p.5-15, Summer 1981 [doi>10.1145/1041799.1041800]
• 19: Hewlett-Packard. OpenView Transaction Analyzer, Sept. 2006. http://h20229.www2.hp.com/products/tran/.
• 20: R. Jain. The Art of Computer Systems Performance Analysis. John Wiley & Sons, 1991.
• 21: The JBoss J2EE Application Server. http://www.jboss.com.
• 22: Jaeyeon Jung , Balachander Krishnamurthy , Michael Rabinovich, Flash crowds and denial of service attacks: characterization and implications for CDNs and web sites, Proceedings of the 11th international conference on World Wide Web, May 07-11, 2002, Honolulu, Hawaii, USA [doi>10.1145/511446.511485]
• 23: Terence Kelly, Detecting performance anomalies in global applications, Proceedings of the 2nd conference on Real, Large Distributed Systems, p.8-8, December 13, 2005, San Francisco, CA
• 24: T. Kelly and A. Zhang. Predicting performance in distributed enterprise applications. Technical Report HPL-2006-76, HP Labs, May 2006. http://www.hpl.hp.com/techreports/2006/HPL-2006-76.html.
• 25: D. Krishnamurthy, J. A. Rolia, and S. Majumdar. SWAT: A tool for stress testing session-based Web applications. In Computer Measurement Group Conf., Dec. 2003.
• 26: Diwakar Krishnamurthy , Jerome A. Rolia , Shikharesh Majumdar, A Synthetic Workload Generation Technique for Stress Testing Session-Based Systems, IEEE Transactions on Software Engineering, v.32 n.11, p.868-882, November 2006 [doi>10.1109/TSE.2006.106]
• 27: James R. Larus, Whole program paths, Proceedings of the ACM SIGPLAN 1999 conference on Programming language design and implementation, p.259-269, May 01-04, 1999, Atlanta, Georgia, United States
• 28: Xue Liu , Jin Heo , Lui Sha, Modeling 3-Tiered Web Applications, Proceedings of the 13th IEEE International Symposium on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.307-310, September 27-29, 2005 [doi>10.1109/MASCOT.2005.41]
• 29: Daniel Menascé , Virgílio Almeida , Rudolf Riedi , Flávia Ribeiro , Rodrigo Fonseca , Wagner Meira, Jr., In search of invariants for e-business workloads, Proceedings of the 2nd ACM conference on Electronic commerce, p.56-65, October 17-20, 2000, Minneapolis, Minnesota, United States [doi>10.1145/352871.352878]
• 30: Daniel A. Menascé , Virgilio A. F. Almeida , Rodrigo Fonseca , Marco A. Mendes, A methodology for workload characterization of E-commerce sites, Proceedings of the 1st ACM conference on Electronic commerce, p.119-128, November 03-05, 1999, Denver, Colorado, United States [doi>10.1145/336992.337024]
• 31: Mercury Interactive. Loadrunner load tester, Sept. 2006. http://www.mercury.com/us/products/performance-center/loadrunner/.
• 32: MySQL database. http://www.mysql.com.
• 33: J. Neter, M. H. Kutner, C. J. Nachtsheim, and W. Wasserman. Applied Linear Statistical Models. Irwin, fourth edition, 1996.
• 34: C. R. Rao and H. Toutenburg. Linear Models: Least Squares and Alternatives. Springer, 1999.
• 35: M. Reiser , S. S. Lavenberg, Mean-Value Analysis of Closed Multichain Queuing Networks, Journal of the ACM (JACM), v.27 n.2, p.313-322, April 1980 [doi>10.1145/322186.322195]
• 36: J. A. Rolia , K. C. Sevcik, The Method of Layers, IEEE Transactions on Software Engineering, v.21 n.8, p.689-700, August 1995 [doi>10.1109/32.403785]
• 37: J. A. Rolia, X. Zhu, and M. Arlitt. Resource access management for a resource utility for commercial applications. In Int'l Sympos. on Integrated Network Mgmt. (IM), Mar. 2003.
• 38: Rice University Bidding System (RUBiS), Mar. 2004. http://rubis.objectweb.org/.
• 39: Robert F. Sauers , Chris P. Ruemmler , Peter S. Weygant, HP-UX 11i Tuning and Performance (2nd Edition), Prentice Hall PTR, Upper Saddle River, NJ, 2004
• 40: Bianca Schroeder , Adam Wierman , Mor Harchol-Balter, Open versus closed: a cautionary tale, Proceedings of the 3rd conference on 3rd Symposium on Networked Systems Design & Implementation, p.18-18, May 08-10, 2006, San Jose, CA
• 41: Christopher Stewart , Kai Shen, Performance modeling and system management for multi-component online services, Proceedings of the 2nd conference on Symposium on Networked Systems Design & Implementation, p.71-84, May 02-04, 2005
• 42: The Stock Online Benchmark. http://forge.objectweb.org/projects/stock-online.
• 43: D. W. Stroock. An Introduction to Markov Processes. Springer, May 2005.
• 44: R. Talaber. Server consolidation assessments with VMware CapacityPlanner, Oct. 2005. http://downloads.vmware.com/vmworld/2005/pac196.pdf.
• 45: The Open Group. Application response measurement (ARM), Sept. 2006. http://www.opengroup.org/management/arm.
• 46: Eno Thereska , Brandon Salmon , John Strunk , Matthew Wachs , Michael Abd-El-Malek , Julio Lopez , Gregory R. Ganger, Stardust: tracking activity in a distributed storage system, Proceedings of the joint international conference on Measurement and modeling of computer systems, June 26-30, 2006, Saint Malo, France
• 47: Transaction Processing Performance Council. TPC-W benchmark, Apr. 2005. http://www.tpc.org/tpcw/.
• 48: Bhuvan Urgaonkar , Giovanni Pacifici , Prashant Shenoy , Mike Spreitzer , Asser Tantawi, An analytical model for multi-tier internet services and its applications, Proceedings of the 2005 ACM SIGMETRICS international conference on Measurement and modeling of computer systems, June 06-10, 2005, Banff, Alberta, Canada
• 49: Bhuvan Urgaonkar , Prashant Shenoy , Timothy Roscoe, Resource overbooking and application profiling in shared hosting platforms, Proceedings of the 5th symposium on Operating systems design and implementation

  Due to copyright restrictions we are not able to make the PDFs for this conference available for downloading

  , December 09-11, 2002, Boston, Massachusetts [doi>10.1145/1060289.1060312]
• 50: VMWare. Server capacity planning and consolidation, Oct. 2005. http://www.vmware.com/news/releases/vac_services.html.
• 51: Qing Wang , Dwight J. Makaroff , H. Keith Edwards, Characterizing customer groups for an e-commerce website, Proceedings of the 5th ACM conference on Electronic commerce, May 17-20, 2004, New York, NY, USA [doi>10.1145/988772.988805]
• 52: R. R. Wilcox. Introduction to Robust Estimation and Hypothesis Testing. Elsevier, second edition, 2005.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS

General Terms:
Experimentation, Management, Measurement, Performance

Keywords:
LAR regression, enterprise, internet services, mutli-tier, noninvasive, nonstationarity, performance prediction, realistic workloads