Figure 1 is a time-space diagram, which is the standard visualization of the happens-before re- lation in a distributed system [66]. (ShiViz displays distributed system executions as time-space diagrams; see Figure 2.) The time-space diagram expresses happens-before relations as directed edges between events. (This ordering is transitive, but for clarity, the diagram omits transitive edges.) For example, in the diagram, the tx prepare event at TX Manager occurs before the abort event at Replica 1 (there is an edge from tx prepare to abort). In a time-space diagram, two events are concurrent if the time-space diagram lacks a directed path between them. For example, in Fig- ure 1 there is no directed path between the concurrent events abort at Replica 1 and commit at Replica 2.

One way to represent partial order in a system trace is to associate a vector clock timestamp with each event. These timestamps make explicit the partial order of events in the system trace. The remainder of this section briefly explains vector time and an algorithm to record vector timestamps in a distributed system [36, 80]. Though more efficient vector clock mechanisms exist [4, 6], we believe that vector timestamps [36, 80] are practical for debugging: short time periods on large systems, or during development and testing.

For concreteness, our explanation below assumes that the distributed system uses message pass- ing, but vector timestamps are equally applicable to a system that uses other mechanisms for inter- host communication, such as shared memory.

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



Fig. 1. Time-space diagram illustrating an execution of the two-phase commit protocol [8] with one transac- tion manager and two replicas. The vertical lines represent the host ordering, and the diagonal lines represent the interaction ordering. Each event has an associated vector timestamp. For conciseness, this time-space diagram does not explicitly include message send and receive events.

Ordering Events with Vector Time

In a distributed system of h hosts, each host maintains a local logical time. In addition, each host maintains a vector clock, which is an underestimate of the logical time at all hosts. A vector clock = is an array of monotonically increasing clocks C [c 0, c 1, . . . ,c h−1], where c j represents the lo- cal logical time at host j. C denotes the vector clock at host i and C [j] represents i’s current i i knowledge about the local logical time at j.

The hosts update their clocks to reflect the execution of events in the system by following

(

) Each host starts with an initial vector clock [

, . . . ,

]. (

) After a host i generates an event, it increments its own clock value (at index i) by

, i.e., ++ C [i] . Sending and receiving a message are each considered an event. i (

) Every message sent by a host i includes the value of its vector clock C . Upon receiving i ALN

) ∀ <

AI = the message, host j updates its vector clock to C such that k, C [k] max(C [k],C [k]). i j

The above description assumes that every host knows the complete set of participating hosts in the system and that this set does not change over time.

Using the above procedure, each event in the system is associated with a vector timestamp—the value of C immediately after the event occurred. Vector timestamps are partially ordered by the ≺ ≺ a relation , where C C if and only if each entry of C is less than or equal to the corresponding 9a’ ≺ 47 ∀ ≤ pra entry of C and at least one entry is strictly less. More formally: C C iff i,C[i] C [i] and ∃ avy j,C[j] < C [j]. This ordering is partial, because some timestamp pairs cannot be ordered (e.g., [1, 2] and [2, 1]). In this case, we say that the two corresponding events occurred concurrently.

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



Fig. 2. ShiViz screen visualizing an execution of the Voldemort distributed data store. Key features and areas ➀ of the UI are numbered. Log lines corresponding to the currently visible time-space diagram to the right. ➁ Boxes at the top represent hosts in the system; the box colors provide a consistent coloring for events and ➂ ➃ log lines associated with a host. An event on a host timeline is represented as a circle. A sequence of local events with no intermediate communication is collapsed into a larger circle whose label indicates the ➄ ➅ number of collapsed events. When an event is clicked, details for the event are shown in a pane, and the relevant log line is highlighted and its log line number is shown to its left. The log line may also be clicked ➆ ➇ directly. The graph may be searched by keywords or by structure (Section 4.2). When the developer ➈ hovers over an event or host, details are shown in this top-right pane. The developer can click on a host to omit it and its log lines from the visualization (Section 4.1.3). Hidden hosts are kept in a list to the right and can be restored with a double-click.

Note that it is possible for one event to precede another event in wall clock time, yet the two events are concurrent according to their vector timestamps.

SUPPORT FOR LOG UNDERSTANDING

ShiViz visualizes a logged distributed execution as a time-space diagram—a common mental model used by programmers for distributed systems. Two key differences from prior tools are ShiViz’s emphasis on time-space visualizations that it can generate for all concurrent systems and a pow- erful set of operations to help developers navigate, search, and explore the logged execution as a graph rather than a text-based log.