Performance debugging for distributed systems of black boxes

ABSTRACT

Many interesting large-scale systems are distributed systems of multiple communicating components. Such systems can be very hard to debug, especially when they exhibit poor performance. The problem becomes much harder when systems are composed of "black-box" components: software from many different (perhaps competing) vendors, usually without source code available. Typical solutions-provider employees are not always skilled or experienced enough to debug these systems efficiently. Our goal is to design tools that enable modestly-skilled programmers (and experts, too) to isolate performance bottlenecks in distributed systems composed of black-box nodes.We approach this problem by obtaining message-level traces of system activity, as passively as possible and without any knowledge of node internals or message semantics. We have developed two very different algorithms for inferring the dominant causal paths through a distributed system from these traces. One uses timing information from RPC messages to infer inter-call causality; the other uses signal-processing techniques. Our algorithms can ascribe delay to specific nodes on specific causal paths. Unlike previous approaches to similar problems, our approach requires no modifications to applications, middleware, or messages.

REFERENCES

• 1: Alignment Software, Inc. Appassure. http://www.alignmentsoftware.com, 2003.
• 2: S. Bagchi, G. Kar, and J. L. Hellerstein. Dependency analysis in distributed systems using fault injection: Application to problem determination in an e-commerce environment. In Proc. 12th Intl. Workshop on Distributed Systems: Operations & Management, Nancy, France, Oct. 2001.
• 3: A. Brown, G. Kar, and A. Keller. An active approach to characterizing dynamic dependencies for problem determination in a distributed environment. In Proc. 7th IFIP/IEEE Intl. Symp. on Integrated Network Management, Seattle, WA, May 2001.
• 4: Rafael C. Carrasco , José Oncina, Learning Stochastic Regular Grammars by Means of a State Merging Method, Proceedings of the Second International Colloquium on Grammatical Inference and Applications, p.139-152, September 21-23, 1994
• 5: M. Chen, E. Kiciman, A. Accardi, A. Fox, and E. Brewer. Using runtime paths for macro analysis. In Proc. HotOS-IX, Kauai, HI, May 2003.
• 6: 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
• 7: Anja Feldmann, BLT: Bi-layer tracing of HTTP and TCP&slash;IP, Proceedings of the 9th international World Wide Web conference on Computer networks : the international journal of computer and telecommunications netowrking, p.321-335, June 2000, Amsterdam, The Netherlands
• 8: Emden R. Gansner , Stephen C. North, An open graph visualization system and its applications to software engineering, Software—Practice & Experience, v.30 n.11, p.1203-1233, Sept. 2000 [doi>10.1002/1097-024X(200009)30:11<1203::AID-SPE338>3.3.CO;2-E]
• 9: Susan L. Graham , Peter B. Kessler , Marshall K. Mckusick, Gprof: A call graph execution profiler, Proceedings of the 1982 SIGPLAN symposium on Compiler construction, p.120-126, June 23-25, 1982, Boston, Massachusetts, United States
• 10: ETE: A Customizable Approach to Measuring End-to-End Response Times and Their Components in Distributed Systems, Proceedings of the 19th IEEE International Conference on Distributed Computing Systems, p.152, May 31-June 04, 1999
• 11: Curtis E. Hrischuk , Jerome A. Rolia , C. Murray Woodside, Automatic Generation of a Software Performance Model Using an Object-Oriented Prototype, Proceedings of the 3rd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, p.399-409, January 10-18, 1995
• 12: Polly Huang , Anja Feldmann , Walter Willinger, A non-instrusive, wavelet-based approach to detecting network performance problems, Proceedings of the 1st ACM SIGCOMM Workshop on Internet Measurement, November 01-02, 2001, San Francisco, California, USA [doi>10.1145/505202.505229]
• 13: R. Isaacs and P. Barham. Performance analysis in loosely-coupled distributed systems. In 7th CaberNet Radicals Workshop, Bertinoro, Italy, Oct. 2002.
• 14: V. Jacobson, C. Leres, and S. McCanne. tcpdump. www.tcpdump.org, 1989.
• 15: JBoss Group. http://www.jboss.org/.
• 16: E. Kiciman. JBoss request-tracing in Pinpoint, 2003.
• 17: J. B. Micheel. Personal communication, 2003.
• 18: B. P. Miller, DPM: A Measurement System for Distributed Programs, IEEE Transactions on Computers, v.37 n.2, p.243-248, February 1988 [doi>10.1109/12.2157]
• 19: B. P. Miller and C.-Q. Yang. Critical path analysis for the execution of parallel and distributed programs. In Proc. 8th Intl. Conf. on Distributed Computing Systems, pages 366--373, San Jose, CA, June 1988.
• 20: D. L. Mills. The network computer as precision timekeeper. In Proc. Precision Time and Time Interval (PTTI) Applications and Planning Meeting, pages 96--108, Reston, VA, Dec. 1996.
• 21: Vern Paxson, Automated packet trace analysis of TCP implementations, Proceedings of the ACM SIGCOMM '97 conference on Applications, technologies, architectures, and protocols for computer communication, p.167-179, September 14-18, 1997, Cannes, France
• 22: Performant, Inc. Optibench. http://www.performant.com/.
• 23: Quest Software Inc. Performasure. http://java.quest.com/performasure, 2003.
• 24: Sun Microsystems, Inc. Java Pet Store Demo. http://developer.java.sun.com/developer/releases/petstore/.
• 25: Sun Microsystems, Inc. J2EE platform specification. http://java.sun.com/j2ee/, 2003.
• 26: Brian Tierney , William Johnston , Brian Crowley , Gary Hoo , Chris Brooks , Dan Gunter, The NetLogger Methodology for High Performance Distributed Systems Performance Analysis, Proceedings of the The Seventh IEEE International Symposium on High Performance Distributed Computing, p.260, July 28-31, 1998
• 27: Y. Zhang and V. Paxson. Detecting stepping stones. In Proc. 9th USENIX Security Symp., Denver, CO, Aug. 2000.

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Distributed debugging

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.5 Testing and Debugging
          Subjects: Testing tools (e.g., data generators, coverage testing)

General Terms:
Algorithms, Measurement, Performance

Keywords:
black box systems, distributed systems, performance analysis, performance debugging