Capturing, indexing, clustering, and retrieving system history

ABSTRACT

We present a method for automatically extracting from a running system an indexable signature that distills the essential characteristic from a system state and that can be subjected to automated clustering and similarity-based retrieval to identify when an observed system state is similar to a previously-observed state. This allows operators to identify and quantify the frequency of recurrent problems, to leverage previous diagnostic efforts, and to establish whether problems seen at different installations of the same site are similar or distinct. We show that the naive approach to constructing these signatures based on simply recording the actual ``raw'' values of collected measurements is ineffective, leading us to a more sophisticated approach based on statistical modeling and inference. Our method requires only that the system's metric of merit (such as average transaction response time) as well as a collection of lower-level operational metrics be collected, as is done by existing commercial monitoring tools. Even if the traces have no annotations of prior diagnoses of observed incidents (as is typical), our technique successfully clusters system states corresponding to similar problems, allowing diagnosticians to identify recurring problems and to characterize the ``syndrome'' of a group of problems. We validate our approach on both synthetic traces and several weeks of production traces from a customer-facing geoplexed 24 x 7 system; in the latter case, our approach identified a recurring problem that had required extensive manual diagnosis, and also aided the operators in correcting a previous misdiagnosis of a different problem.

REFERENCES

• 1: Marcos K. Aguilera , Jeffrey C. Mogul , Janet L. Wiener , Patrick Reynolds , Athicha Muthitacharoen, Performance debugging for distributed systems of black boxes, Proceedings of the nineteenth ACM symposium on Operating systems principles, October 19-22, 2003, Bolton Landing, NY, USA
• 2: P. Barham, A. Donnelly, R. Isaacs, and R. Mortier. Using Magpie for request extraction and workload modelling. In Proc. 6th USENIX OSDI, Dec. 2004.
• 3: G. Candea, S. Kawamoto, Y. Fujiki, G. Friedman, and A. Fox. A microrebootable system -- design, implementation, and evaluation. In Proc. 6th USENIX OSDI, San Francisco, Dec. 2004.
• 4: Mike Y. Chen , Emre Kiciman , Eugene Fratkin , Armando Fox , Eric Brewer, Pinpoint: Problem Determination in Large, Dynamic Internet Services, Proceedings of the 2002 International Conference on Dependable Systems and Networks, p.595-604, June 23-26, 2002
• 5: I. Cohen, M. Goldszmidt, T. Kelly, J. Symons, and J. S. Chase. Correlating instrumentation data to system states: A building block for automated diagnosis and control. In Proc. 6th USENIX OSDI, San Francisco, CA, Dec. 2004.
• 6: R. O. Duda, P. E. Hart, and D. G. Stork. Pattern Classification. Wiley, second edition, 2001.
• 7: D. Jacobs. Distributed computing with BEA WebLogic server. In Proceedings of the Conference on Innovative Data Systems Research, Asilomar, CA, Jan. 2003.
• 8: R. Jain. The Art of Computer Systems Performance Analysis. Wiley-Interscience, New York, NY, 1991.
• 9: J. O. Kephart and W. C. Arnold. Signatures. In Proc. 4th Virus Bulletin International Conference, 1994. http://www.research.ibm.com/antivirus/SciPapers/Kephart/VB94/vb94.html.
• 10: E. Kiciman and A. Fox. Detecting application-level failures in component-based internet services. IEEE Transactions on Neural Networks, Spring 2005.
• 11: D. Mosberger and T. Jin. httperf---a tool for measuring web server performance. http://www.hpl.hp.com/personal/David_Mosberger/httperf.html.
• 12: B. Mukherjee, L. T. Heberlein, and K. N. Levitt. Network intrusion detection. IEEE Network, 8(3):26--41, May 1994.
• 13: Vivek S. Pai , Peter Druschel , Willy Zwaenepoel, IO-Lite: a unified I/O buffering and caching system, ACM Transactions on Computer Systems (TOCS), v.18 n.1, p.37-66, Feb. 2000 [doi>10.1145/332799.332895]
• 14: Judea Pearl, Causality: models, reasoning, and inference, Cambridge University Press, New York, NY, 2000
• 15: J. A. Redstone, M. M. Swift, and B. N. Bershad. Using computers to diagnose computer problems. In Proc. HotOS IX, pages 91--96, May 2003.
• 16: M. Steinder and A. S. Sethi. A survey of fault localization techniques in computer networks. Science of Computer Programming, 53:165--194, 2004.
• 17: System Management Arts (SMARTS) Inc. Automating root cause analysis, 2001. http://www.smarts.com.
• 18: The Open Group. Application Response Measurement (ARM) 2.0 Technical Standard, July 1998. http://www.opengroup.org/onlinepubs/009619299/toc.pdf.
• 19: Matt Welsh , David Culler , Eric Brewer, SEDA: an architecture for well-conditioned, scalable internet services, Proceedings of the eighteenth ACM symposium on Operating systems principles, October 21-24, 2001, Banff, Alberta, Canada
• 20: Ian H. Witten , Eibe Frank, Data mining: practical machine learning tools and techniques with Java implementations, Morgan Kaufmann Publishers Inc., San Francisco, CA, 2000
• 21: S. A. Yemini, S. Kliger, E. Mozes, Y. Yemini, and D. Ohsie. High speed and robust event correlation. IEEE Communications Magazine, pages 82--90, May 1996.
• 22: Steve Zhang , Ira Cohen , Julie Symons , Armando Fox, Ensembles of Models for Automated Diagnosis of System Performance Problems, Proceedings of the 2005 International Conference on Dependable Systems and Networks (DSN'05), p.644-653, June 28-July 01, 2005 [doi>10.1109/DSN.2005.44]

INDEX TERMS

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

General Terms:
Algorithms, Experimentation, Performance

Keywords:
bayesian networks, clustering, information retrieval, performance objectives, signatures