Distributed System Executions

Distributed systems pose unique challenges for software developers. Understanding the system’s commu- nication topology and reasoning about concurrent activities of system hosts can be difficult. The standard approach, analyzing system logs, can be a tedious and complex process that involves reconstructing a system log from multiple hosts’ logs, reconciling timestamps among hosts with non-synchronized clocks, and un- derstanding what took place during the execution encoded by the log. This article presents a novel approach for tackling three tasks frequently performed during analysis of distributed system executions: (1) under- standing the relative ordering of events, (2) searching for specific patterns of interaction between hosts, and (3) identifying structural similarities and differences between pairs of executions. Our approach consists of XVector, which instruments distributed systems to capture partial ordering information that encodes the happens-before relation between events, and ShiViz, which processes the resulting logs and presents dis- tributed system executions as interactive time-space diagrams. Two user studies with a total of 109 students and a case study with 2 developers showed that our method was effective, helping participants answer sta- tistically significantly more system-comprehension questions correctly, with a very large effect size.

Additional Key Words and Phrases: Distributed systems, program comprehension, log

Ivan Beschastnikh, Perry Liu, Albert Xing, Patty Wang, Yuriy Brun, and Michael D. Ernst. 2020. Visualizing Distributed System Executions. ACM Trans. Softw. Eng. Methodol. 29, 2, Article 9 (March 2020), 38 pages. https://doi.org/10.1145/3375633

We acknowledge the support of the Natural Sciences and Engineering Research Council of Canada (NSERC) through the Discovery grant, funding reference numbers 2014-04870 and 2019-05090. Authors Perry Liu, Albert Xing, and Patty Wang contributed to the project while sponsored by the NSERC USRA program. This material is based upon work supported by the United States Air Force under contract nos. FA8750-12-2-0107 and FA8750-15-C-0010, and by the National Science

contributed to the project while sponsored by the NSERC USRA program. This material is based upon work supported by the United States Air Force under contract nos. FA8750-12-2-0107 and FA8750-15-C-0010, and by the National Science Foundation under grant nos. CCF-1453474 and CCF-1763423. Authors’ addresses: I. Beschastnikh, P. Liu, A. Xing, and P. Wang, University of British Columbia, 201-2366 Main Mall, Vancouver, BC, V6T 1Z4, Canada; emails: bestchai@cs.ubc.ca, {perry, albert.xing}@alumni.ubc.ca, patty.pcw@gmail.com; Y. Brun,University ofMassachusetts Amherst, 140Governors Drive, Amherst, MA, 01003-9264;email:brun@cs.umass.edu; M. D. Ernst, University of Washington, 185 Stevens Way, Seattle, WA, 98195-2350; email: mernst@cs.washington.edu. Permission to make digital or hard copies of all or part of this work for personal or classroom use is granted without fee provided that copies are not made or distributed for profit or commercial advantage and that copies bear this notice and the full citation on the first page. Copyrights for components of this work owned by others than the author(s) must be honored. Abstracting with credit is permitted. To copy otherwise, or republish, to post on servers or to redistribute to lists, requires prior specific permission and/or a fee. Request permissions from permissions@acm.org. © 2020 Copyright held by the owner/author(s). Publication rights licensed to ACM. 1049-331X/2020/03-ART9 $15.00

Authors’ addresses: I. Beschastnikh, P. Liu, A. Xing, and P. Wang, University of British Columbia, 201-2366 Main Mall, Vancouver, BC, V6T 1Z4, Canada; emails: bestchai@cs.ubc.ca, {perry, albert.xing}@alumni.ubc.ca, patty.pcw@gmail.com; Y. Brun,University ofMassachusetts Amherst, 140Governors Drive, Amherst, MA, 01003-9264;email:brun@cs.umass.edu;

https://doi.org/10.1145/3375633

ACM Transactions on Software Engineering and Methodology, Vol. 29, No. 2, Article 9. Pub. date: March 2020.

INTRODUCTION

Understanding and debugging distributed systems is challenging. Given two events at different hosts, it is not obvious whether one of them is causally dependent on the other, even if each of the events has a timestamp. Distributed systems are prone to failure and are designed to be resilient to it: messages may be dropped, new hosts may join, and existing hosts may leave or fail without notice. Pausing or stepping through a distributed execution is generally impossible. Today, one standard strategy that developers use to diagnose software bugs and reason about program exe- cution is logging [20, 40, 88, 123, 124]. Prior work has observed that logs play an important role in resolving cloud-based system outages [50, 51, 122], access-denied issues [120], and configuration issues [121], among other tasks [85]. A typical way that logging is used in distributed systems is by logging system behavior to generate a log for each host (e.g., using printf statements or logging libraries such as Log4J). The developers then analyze the global sequence of events across different hosts by serializing the logs from multiple hosts using timestamps in the logs. However, serializing a distributed system to a total order is misleading—even if the clocks are perfectly synchronized, a total order hides the fact that events may have occurred concurrently, independently of one another.

Three important tasks that developers perform while testing or diagnosing distributed systems

Understanding the relative ordering of events. Given two events at different hosts, is one potentially causally dependent on the other? (If not, then their relative order is an ac

cident of timing—such as scheduling or speed of message delivery—that could be reversed without any effect on the rest of the execution.) When do hosts communicate with one an