ShiViz groups and merges these local events into a single node to simplify the visualization and emphasize global ordering information, as illustrated in Figure 3(a). This transformation is enabled by default: All series of events that can be collapsed are collapsed when the execution graph is first shown to the developer. They can expand or collapse each set of nodes independently by clicking on the node and selecting “expand” or “collapse.”

a subset of the hosts in the system. Using the hide host transformations, a developer can remove a host (including the corresponding host timeline and log lines) from view, or bring these back into view. To hide a host, a developer double-clicks on the host box at the top of the time-space ➈ diagram. Hidden hosts are collected in the right panel ( in Figure 2). To unhide the host, devel- opers double click on the host box in this panel. A dashed edge connects two events at not-hidden hosts that are connected transitively through one or more hidden hosts. Figure 3(b) illustrates this

Transformation 3: filter by host. The filter by host transformation refines the graph to show just the set of events and hosts that are relevant to communication with a particular host. A white square inside the host box denotes a filtered host. It is possible to filter by more than one host and to unfilter hosts in any order. Figure 3(c) illustrates the filter by host transformation. Figure 4 shows an example of this transformation on the log and view from Figure 2.

Throughout these transformations, the log in the left panel continues to reflect the visible events on the right. For example, when a host is hidden from the graph, the log lines for that host are hidden as well. Therefore, these three graph transformations are log transformations as well.

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



Fig. 4. An illustration of the filter by host transformation, applied to the log and view in Figure 2. (Top) The user can select to hide a host or to filter by a host transformation by clicking on the host’s box. (Bottom) Shows the result of choosing to filter by a host (nio-server1) in the top view. Notice that the filtered orange host box is highlighted and the result of the transformation is to retain just those host timelines with which this host has directly communicated. The boxes for hosts with which the filtered host did not communicate are added to the hidden processes list on the right and their timelines are removed from view.

A key feature of ShiViz transformations is that they are composable; that is, ShiViz has built-in semantics to resolve the layering of transformations. So, it is possible to hide a host, then un- collapse a set of events, filter by two hosts, and finally hide one more host. A developer can also remove transformations from this layering in any order, not just in the reverse of the order in which the transformations were added.

Supporting Execution Graph Queries

Few developers read or browse a complex system’s log manually. Instead, developers often focus on specific parts of the log and write regular expressions to parse information they need out of the log [109]. Presenting a visual partial ordering that describes an execution cannot help with this. To be useful for complex logs, ShiViz must be able to support developer queries about the partial ordering. A key challenge for ShiViz is in supporting graph-based queries. Using graph- based queries, developers can express the topologies of interesting event orderings, rather than the text contents of the events themselves.

ShiViz implements two kinds of searches: structured search and keyword search. When a devel- ➆ oper clicks in the search area at the top of the screen ( in Figure 2), a drop-down appears, using which the developer can either perform a structured search or a keyword search query.

4.2.1 Structured Search. In a structured search, a developer queries the execution graph for a set of events that are related through a particular ordering pattern. We call this pattern a sub- graph. The sub-graph can be either user-defined or predefined, and search results are presented as highlighted sub-graphs overlaid on top of the execution graph.

A user-defined sub-graph (left side of Figure 5) is generated by the developer with a mouse by adding a number of hosts, host events, and connections between pairs of events to define a partial order. During a query, ShiViz searches every possible permutation of hosts and events to

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



Fig. 5. Structured search with a query corresponding to use case 2 from Section 2. The regular expressions (in bold font below each host box) are host constraints that restrict the search to those scenarios in which the host names in the execution graph match the three host constraints. The right side shows the results of the search with two highlighted matches.

find matching sub-graphs. Most interesting user-defined sub-graphs are small in size (fewer than 5 hosts and 10 events) and our algorithm is fast enough to find a match, if one exists, in under a second.

In Figure 5, the sub-graph represents a forwarding pattern where the leftmost host sends a message to the middle host, which then communicates with the right-most host. This communi- cation chain is then reversed. The drawn sub-graph is also represented as a textual query in the search bar in Figure 5, specifying hosts and their corresponding vector clocks. Modifying either the user-defined sub-graph or its textual representation will update the other to match. This sim- plifies custom structure reuse and sharing, as sub-graphs can be generated by pasting text strings starting with #structure into the search bar.