Execution clusters aid in the inspection and comparison of multiple executions by providing an overview of all executions at once. Developers can quickly scan through cluster results to see how executions are alike or different based on the groups into which they are sorted. Clustering also helps developers pinpoint executions of interest by allowing them to inspect a subset of executions matching a desired measure. This subset can be further narrowed down by performing one of the previously mentioned searches (keyword and structured search) on top of the clustering results. Execution names among clusters are highlighted if their corresponding graphs contain instances matching the developer query.

Section 6.2.2 discusses two case studies in which the multi-execution comparison and clustering were useful to developers working on complex distributed systems.

IMPLEMENTATION

ShiViz reads events and their happens-before relation from a log, then visualizes one or more executions as time-space diagrams. Sections 5.1 and 5.2 describe creation and parsing of logs, and Section 5.3 gives details about the ShiViz implementation.

Logging the Happens-before Relation

Typical distributed systems already contain logging calls to record events and values of interest; for example, by printing them to a file. Therefore, most of the work to create a log is already done. However, the partial happens-before order of the events may be lost due to the concur- rent execution. One way to preserve this order is to associate a vector clock timestamp with each

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

 TX Manager MMSystem Log® print ("tx abort") (Dm Host =X Manager| _vent : abot  send(“tx aborted”)      "ex aborted” SYReplicat Mil( = \System Log   Host: Replicat3 msg = eev()peinte(nsa)——(4)-m Event : tx aborted         (a) Uninstrumented systemLog‘Analysis     TX Manager ( Xvector  payload = “tx aborted”buf = prepareSend(“tx abort”payload)|   Host: TX Manager|\VTime :[1,4,1]   send(buf)            Replicat( Xvector =buf = reev()payload = unpackReceive(buf)LoghocalEvent (payload)   Host: ReplicatVTime : [2,4,1]Event : tx aborted         (b) System instrumented with XVector     

Fig. 8. A log-based view of the bottom-most edge from TX Manager to Replica 1 in Figure 1. (a) Uninstru- mented version of the system that produces a log that can be manually analyzed. (b) A system instrumented with XVector to capture the partial ordering relation; the resulting log can be analyzed using ShiViz.

event [36, 80]. We have developed XVector, a suite of libraries to instrument distributed systems to log happens-before partial order via vector time. For exposition, our XVector explanation assumes the distributed system uses message passing, but the XVector approach is equally applicable to systems that use other inter-host communication, such as shared memory.

The XVector library relieves developers from needing to implement the vector clock algo- rithm [36, 80] (recall Section 3.2). To use the library, developers (1) initialize the library, and (2) make calls to the library to pack and unpack existing messages sent by the system with a header that consists of the vector clock timestamp. XVector maintains a vector clock for each host in the system and updates it whenever the client application makes calls to pack or unpack. These packing calls also take a string that will be logged to a log file along with the current vector clock timestamp. XVector also includes a call that can be used to just log a message with a vector timestamp. Figure 8 details the XVector instrumentation for a small part of the two-phase commit

We have built XVector implementations for several languages: C, C++, Java, and Go. These li- braries inter-operate, allowing multi-lingual systems to be instrumented. XVector integrates with popular logging libraries in these languages, such as Log4J. For two languages, Java and Go, we have versions of XVector that automatically instrument the source code using static analysis and a whitelist of known networking library calls. This procedure is described in more detail in our previous work on inferring distributed system invariants [46]. For the other languages, the devel- oper must manually log information with XVector. We are working on automating this process

Given a log, ShiViz needs to know the following:

—For each event, the host that executed the event, the vector timestamp of the event (recall Section

), and a text string describing the event. —Optionally, additional data associated with each event, which developers can search for within Sh

iz (see Section

). • Optionally, how to divide the log into multiple system execution traces.

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

The developer specifies this information with a regular expression that matches events and an optional regular expression to delimit system traces. The event regular expression must contain three named capture groups to extract the triples of [host,clock,event] information from the log and may contain other named capture groups.

This method of processing logs is flexible and can accommodate many format types (including text, JSON, etc.) without making any assumptions about the system that produced the log. We have used ShiViz to visualize not just distributed systems but also multi-threaded applications.

5.3 ShiViz Implementation