CHEX: Multiversion Replay with
Ordered Checkpoints

Suppose that Alice is researching different image classification pipelines. She has a large labeled set of images and progressively tries different combinations of preprocessing steps and neural network architectures. For example, she may replace an entire step with one that is more sophisticated but slower, or vice-versa. As she makes changes, she keeps a copy of the previous versions in separate Jupyter notebooks. We call these her different program versions; they are similar to different experiments in scientific computing. Once done, Alice would like to share her different program versions with Bob so that he can independently repeat and regenerate the results and verify Alice’s work. We say Bob faces the multiversion replay problem: executing all the versions given to him by Alice as efficiently as possible where (i) many versions repeat some of the same preprocessing steps, but (ii) without reusing any of Alice’s own computation. In this paper, we address this problem.

Collaborative scenarios such as the one above arise routinely in scientific computing and data science, where sharing, repeating and verifying results is common. Several tools have been recently proposed for it (Janin et al., 2014; Chirigati et al., 2016; O’Callahan et al., 2017; Pham et al., 2013, 2015a, 2015b; Malik and et. al., 2017; Yuan et al., 2018). These tools audit the execution of a program, and create a container-like package consisting of all files referenced by the program during its execution. This package can then be used to repeat results in different environments. These tools have much to offer; they do not, however, exploit the efficiency possible by solving the multiversion replay problem. As the reproduction of results becomes increasingly time consuming, addressing such problems is critical.

One of the above tools is the Sciunit system, developed by some of the co-authors. It allows multiple versions of a program to be included in the same package and shared for repetition (Ton That et al., 2017; Yuta Nakamura and Malik, 2020). We noted that having two or more versions in the same package sets up a natural opportunity for reusing computations that are often common across versions—i.e., a number of versions may perform the same computations for quite some time before the y branch out as the researcher tries out different options. But, in order to accurately identify computations that can be reused across versions, we need to be able to determine the point to which the execution of two versions can be treated as equivalent and from which they branch. We develop a methodology to identify common computations in program code fragments or cells of the versions. This methodology depends on lineage audited during program execution (Pham et al., 2013, 2015a; Nakamura et al., 2020). For repetition, at Bob’s end, we share computational state across versions in the form of checkpoints . Let us now see with an example how sharing computational state across versions via checkpoints creates an opportunity to optimize computational time when repeating multiple versions.

Suppose that Alice has shared with Bob a package with three versions. Assume Alice has developed her code in the REPL style and her first version is divided into two cells that take time 1 minute and 10 minutes, respectively (Figure 1 left). Her second version has the same first two cells but she adds a third cell. Her last version, which processes the dataset, has the same first cell, but diverges after that, and cells 2 and 3 now takes 11 and 2 minutes, respectively. Now, during repetition, if Bob checkpoints cell $b$ while computing $v1$ and then restores that checkpoint for $v2$, he can complete $v2$ in just 1 unit of time (saving 11 units in $v2$). This checkpoint is , however, not useful for $v3$ since cell $b$ has been changed to $d$ in this version. Observe, that although $a$ is common across all three versions, checkpointing $a$ , instead of $b$, is not optimal. In the example on the right, on the other hand, checkpointing $a$ is the better option since the bulk of the computation takes place in $a$.

The example above leads to the question: Why doesn’t Bob just checkpoint both $a$ and $b$? Storage is cheap after all! Indiscriminate caching, however, is not a practical solution: In machine learning examples, e.g., checkpointing all cells across versions (as our experiments indicate) can lead to a memory requirement in the range of 50-550GB, for even moderately-sized multiversion programs. Thus, we consider a limited in-memory space as this avoids additional I/O costs from checkpointing. Limited space leads to a n optimization problem: As we will show, given limited space and multiple versions with different cost and size estimates of cells, deciding checkpoint locations for efficient replay of all versions is an NP-hard problem. We present efficient heuristics to solve this problem.

We briefly describe the REPL environment under which CHEX operates. CHEX is not limited to the REPL environment but this is easy to illustrate visually so we adopt this for ease of exposition. We discuss generalization to other environments in Section 9.

REPL or Read-Evaluate-Print-Loop is a programming environment. A popular example is the Jupyter notebook. As shown in Figure 2, it contains code partitioned into cells. Developers typically use a separate cell for each “step” of the program: preprocessing the dataset, training the model, etc. This allows them to interactively test each step before writing the next. One restriction is that control flow constructs, such as if-blocks, loops, cannot be split across cells. We denote a REPL program by an ordered list of cells, e.g., the left program in Figure 2 is denoted $L_{1}=[x_{1},x_{2},\ldots,x_{5}]$, and the right program as $L_{2}=[y_{1},y_{2},\ldots,y_{6}]$.

In a typical REPL execution, cells are executed in sequence from the first to last. While the Jupyter notebook allows out-of-order cell execution, we do not consider such execution. (We elaborate on this constraint further in Section 9.) The state of the program at the end or beginning of each cell is termed the program state. The program state at any point of execution consists of the values of all variables and objects used by the program at that point — intuitively, it is all the contents of the memory associated with the program. So, e.g., for the program $L=[x_{1},x_{2},\ldots,x_{5}]$, the corresponding program states are $[ps_{0},ps_{1},\ldots,ps_{5}]$, in which $ps_{i-1}$ denotes the program state just before cell $x_{i}$ is executed. The state $ps_{0}$, which is just before the first cell is executed, includes the value of the environment and any initial input.

CHEX works in combination with an auditing system which monitors executions and provides the following details about each program state, $ps_{i}$:

• •

  computation time, $\delta_{i}$, the time to reach the program state $ps_{i}$ from its predecessor $ps_{{i-1}}$,

• •

  size, $sz_{i}$, size of the program state $ps_{i}$,

• •

  code hash, $h_{i}$, computed by hashing code in cell $i$, and

• •

  lineage, $g_{i}$, which is determined by combining the predecessor cell’s lineage with the sequence of system events that are triggered by program instructions in the cell $i$ and the hashes of the associated external data dependencies. Thus, $g_{i}=(g_{i-1},h_{i},E_{i})$, where $E_{i}$ is the ordered set of system events in cell along with the hash of the content accessed by the event. Initially, $g_{0}=\{\}.$

To see why $g_{i}$ is so defined, we note that the execution of the program code in cell $i$ (and the code in previous cells) resulted in $ps_{i}$. Therefore, $ps_{i}$ at the end of a cell’s execution depends on its (i) initial environment, (ii) code that is run, and (iii) external input data. The environment is determined by the execution state at the start of the cell. Thus, (i) and (ii) are captured via $g_{i-1}$ and $h_{i}$. Further, every external input data file $f$ is accessed via a system call event. For each such event, we record a hash of its contents of $f$ in $E_{i}$.

Figure 3 shows the audited information for the two programs, $L_{1}$ and $L_{2}$. The ordered set of system events for the third cells of the two programs are shown in the shaded box below.

As we see in Figure 2, the two programs behave the same till the end of the third cell ($x_{3}$ in $L_{1}$, $y_{3}$ in $L_{2}$) and then diverge. If the audited lineage, as shown in Figure 3, is established to be same, then the program state at the end of $x_{3}$ can be used before $y_{4}$. i.e, we can skip executing cells $y_{1}$ to $y_{3}$. CHEX uses recorded lineage to determine when the program state is identical across versions, and decides which common computations to save. We now present a high-level block diagram of CHEX in Figure 4.

CHEX has two modes audit and replay. It is used in audit mode to audit details of executions on Alice’s side. Details of multiple executions, i.e. the $\delta$, $sz$, $h$ and $g$ of each cell across versions are represented in the form of a data structure called the Execution Tree. We discuss the execution tree and how it is created in detail in Section 6. CHEX creates a package of all Alice’s versions and their data, binary, and code dependencies, along with the execution tree. This package can now be shared with Bob.

CHEX is used in replay mode on Bob’s side. It first determines an efficient replay sequence or replay order, i.e., a plan for execution that includes checkpoint caching decisions. To do so CHEX inputs a cache size bound, $B$, and then executes a heuristic algorithm on the execution tree received from Alice to determine the most cost efficient replay sequence for that cache size. Computing a cost-optimal replay sequence for multiple versions of a program with a cache bound is an NP-hard problem as we show in Section 4 and so we describe some efficient heuristics for this purpose (Section 5). Finally, once the replay sequence is computed, CHEX uses this replay sequence to compute, checkpoint, restore-switch REPL program cells or evict stored checkpoints from cache.

We now describe the multiversion replay problem. Figure 5 summarizes the symbols used in Section 2. In the replay mode, CHEX inputs an execution tree, $T$, and a fixed cache size, $B$, to solve the multiversion replay problem. We define the execution tree as:

The multiversion replay problem is an optimization problem that arises when multiple versions of a program, each previously executed, are replayed as a collection. Once the multiversion program is represented as an execution tree it is clear that there is some advantage in not replaying the common prefixes of this tree.

Under these operations, and given an execution tree and a fixed amount of space for storing checkpoints, the multiversion replay problem aims to determine a replay sequence that has the minimum replay costs. We define a general replay sequence as follows:

At the initial step $S_{0}$ is empty and the root of the tree is computed. At any given step $t$, $O_{t}$ is of one of the following four types. Here, $u_{j}$ and $u_{k}$ are nodes in $V$, the vertices of $T$.

• •

  Compute $CT(u_{j})$: computes $u_{j}$;

• •

  Checkpoint $CP(u_{j})$: checkpoints $u_{j}$ into the cache;

• •

  Restore $RS(u_{j},u_{k})$: restores a previous checkpointed $u_{j}$ in cache and switches to $u_{k}$ where $u_{j}=parent(u_{k})$; and

• •

  Evict $EV(u_{j})$: evicts a previous checkpoint $u_{j}$ from cache;

The cache size can never exceed $B$, i.e. $|S_{t}|\leq B$ for $0\leq t\leq m$. Further, an operation $O_{t}$ at step $t$ can only be performed on $u_{j},u_{k}$ under the following constraints:

• •

  Checkpoint from working memory: A node in the execution tree is checkpointed only if it was computed in some previous step, after which there are only some evictions (to make space), if at all, i.e., if $O_{t}=CP(u_{j})$ $\implies$ $S_{t}=S_{t-1}\cup\{u_{j}\}$ and $O_{t-i}=CT(u_{j})$, for some $1\leq i\leq t$, and $O_{t^{\prime}}=EV(u_{t^{\prime}})$ for $t-i<t^{\prime}<t$.

• •

  Restore from cache and switch to child: A node is restored only if it was in cache in a previous step, and without altering cache state, switches to one of its children in the execution tree, which is computed next i.e., if $O_{t}=RS(u_{j},u_{k})$ $\implies$ $u_{j}\in S_{t-1}$, $S_{t}=S_{t-1}$, $O_{t+1}=CT(u_{k})$.

• •

  Evict from cache: A node is evicted from cache and alters its state, i.e., if $O_{t}=EV(u_{j})$ $\implies$ $u_{j}\in S_{t-1}$, $S_{t}=S_{t-1}-\{u_{j}\}$.

• •

  Continue computation: Continue computing a node if its parent was being computed or if its parent was restored, i.e., if $O_{t}=CT(u_{j})$ $\implies$ $O_{t-1}=CT(parent(u_{j}))$ or $O_{t-1}=RS(parent(u_{j}),u_{j})$ and $S_{t}=S_{t-1}$ or t= 1 and $u_{j}$=root of the tree $T$.

We assume the operations generate complete and minimal sequences. A replay sequence is complete if all leaf nodes of the tree $T$ appear in $R$, and is minimal if no $u_{j}$ that is in cache is recomputed.

In MVR-P, we assume the cost of checkpoint, restore-switch, and evict operations to be negligible. Thus, the only cost considered is the cost of computing the cells. Determining the minimum cost replay order leads to a natural trade-off between computational cost of cells and fixed-size cache storage occupied by the checkpointed state of the cells. Thus, to optimally utilize a given amount of storage we must determine for each cell whether its next cell be recomputed, or some other cell be recomputed by checkpointing the state of the current cell. We state that determining the replay order is computationally hard.

To prove this first define the decision version of MVR-P. Given an execution tree $T$, a cache size parameter $B>0$ and a total cost parameter $\Delta>0$, define $RP(T,B,\Delta)$ to be the decision problem with answer YES if there is a replay sequence of $T$ with cost at most $\Delta$ and size of cache at most $B$, and with answer NO otherwise.

From Theorem 3 we know that it is unlikely we will find polynomial time solution to MVR-P. Accordingly, we present two efficient heuristics for this problem. Both heuristics restrict our exploration of the search space to solutions in which the execution order of the nodes of the execution tree corresponds to a DFS traversal of the tree—a natural, simple order in which to approach the replay of the tree. In order to formalize this notion we present some definitions. In the following, for sake of brevity, we specify only the compute $CT(u_{j})$ type operations in replay sequences. The other operations (checkpoint, restore, evict) are separately specified. In this briefer format, each step of a replay sequence is of the form $(u_{t},S_{t})$ specifying that at step $t$, $u_{t}$ is computed, and the resulting cache is $S_{t}$.

We observe that in an ex-ancestor replay sequence if the helper sequence of $v_{j}$ is non-empty then it either begins with the root of $T$ or with a node whose parent is in $S_{i_{j-1}}$.

We illustrate this definition with an example. Consider the tree in Figure 6. Assume for now that cache size $B=0$ and consider the following replay sequence:

where bold font indicates repeat appearance nodes. Here the indices 1, 2, 3, 4, 5, 6, 8, 9, 10, 11, 14, 15, 16, 21, 22, and 26 are first appearances and all others are repeat appearances. Let’s take the example of node $n$. It’s first appearance index is $21$. Its helper sequence extends from indices 17 to 20 and contains $\mathbf{a},\mathbf{c},\mathbf{f},\mathbf{i}$. This is a simple path in the tree beginning from the node containing $a$ which is an ancestor of $n$. In fact it is easy to verify that this sequence is an ex-ancestor replay sequence.

The question arises: Are there meaningful replay sequences that are not ex-ancestor replay sequences? For example, would it make sense to modify $n$’s helper sequence and make it $\mathbf{a},\mathbf{c},e,\mathbf{f},\mathbf{i}.$ It appears that the extra computation of $e$ is superfluous and so a priori it is not obvious that such replay sequences are meaningful from the point of view of efficient replay. Therefore we focus on ex-ancestor replay sequences. We conjecture that an optimal solution to MVR-P will be such a sequence.

Note that first appearance sequence of the example discussed below Definition 1 gives us a DFS-traversal of $T$. Hence this is a DFS-based replay sequence for the tree of Figure 6.

Now assume a cache size $B=25$ and the caching decisions made according to the first replay sequence in Figure 7.¹¹1All three replay sequences in Figure 7 are DFS-based. The corresponding replay sequence is similarly: $a,b,d,g,k,o,c,e,h,l,f,i,m,\mathbf{i},n,p,j$. Since $a,c,$ and $f$ are cached at appropriate junctures, the only node with a non-empty helper sequence is $n$ and the length of this sequence is just one, i.e., there is only one cell that has to be recomputed apart from its first appearance computation. For the second and third sequence in Figure 7 the number of recomputations are similarly three ($\mathbf{a},\mathbf{c},\mathbf{f}$) and zero respectively.

We are able to explicitly bound the number of DFS-based replay sequences.

Since $h$ is $\Omega(\log n)$ from Proposition 3 it appears that the space of possible solution is superexponential. In order to control the complexity of our solutions we restrict the solution space in two different ways and define two heuristics.

We now discuss how CHEX constructs the execution tree at Alice’s end. As per Definition 1, an execution tree merges reusable program states of different versions into a single node in the tree. Thus given $n$ audited versions, possibly of different length, to construct an execution tree, we need to identify which states are reusable. Given the per cell values of state computation time $\delta_{i}$ and size $sz_{i}$, state lineage $g_{i}$, and state code hash $h_{i}$, we use the following conditions to to identify a reusable state:

In other words we say that two states are reusable if they are equal i.e., they are (i) equal at code syntactic level, (ii) after cell execution, result in the same state lineage (note state lineage of $i^{th}$ cell depends on state lineage of previous cell), and (iii) have roughly similar execution costs. Program state does not remain equal when cell code is edited, which changes the hash value of that cell and any subsequent cell. Similar states across versions also do not remain equal if costs change drastically, i.e., computed on different hardwares (viz. GPU vs CPU). Equating state lineage depends on the granularity at which the system events are audited. Since in CHEX, lineage is audited at the level of system calls, there are some pre-processing steps that are necessary to establish equality, such as accounting for partial orders, abstracting real process identifiers, and accounting for hardware interrupts. We describe these issues below.

Lineage equality implies that at end of cell $i$ of version $L_{1}$, $g_{i}$ is the same as that at end of cell $i$ of version $L_{2}$. This is true if and only if the sequence of system call events (and their parameters)—till $i$ in $L_{1}$ and $i$ in $L_{2}$—exactly match. But if a cell, e.g., forks a child process, which itself issues system calls, then each version’s sequence will contain the parent calls and the child process calls interleaved in possibly different orders.

In Figure 3 the parent process forks a child and then issues a ‘mem’ memory call, and the child process itself issues ‘exec’, ‘open’, and ‘read’ calls. As the figure shows, it is possible that in the sequence for version $L_{1}$ the ‘mem’ access is before the ‘read’, while for $L_{2}$ it is after. If we want to correctly determine that the state in $L_{1}$ is identical to that in $L_{2}$ at this point, we need to recognize that the sequence of system calls is an arbitrary total order imposed on an underlying partial order. The partial order for $L_{1}$ and $L_{2}$ is identical, while the total order can differ.

In our implementation, we essentially reconstruct the underlying partial order when we detect asynchronous computation, and match it to identify equality of program states in different versions. This is achieved by separating the events into PID-specific sequences and then comparing corresponding sequences. The above comparison can only be established when process identifiers are abstracted to their logical values. Memory accesses cannot be abstracted and we just count the number of accesses in a cell. Comparison must also account for external inputs in addition to system events. As Figure 3 shows the hash of external dataset file ‘new_fashion’ is changed from ‘b2e1772’ to ‘6789b34. Thus, the two cells cannot be equated even though the order of system call sequence in $E$ is the same.

A related nuance is due to hardware interrupts. If $P_{1}$ experiences a hardware interrupt and $P_{2}$ does not, we make the safe choice: assume the program states are not equal. (It is easy to make the opposite choice, by simply ignoring hardware interrupts, if so desired.)

We now describe CHEX’s implementation and present an extensive evaluation of CHEX for multiversion replay.

We use CRIU as a checkpointing mechanism. This is precisely to enable checkpoint of a process independent of its programming language²²2 Native serializations, viz. Pickle, provide only a slight performance benefit (1-2%).. CRIU does not freeze the state of the container but just the application process. Currently, CHEX is integrated with the IPython kernel. In future, we plan to integrate CHEX with Xeus (Community, 2016), which will help us extend CHEX to C programs as well. For the purposes of reproducibility we have made available the code for the audit and replay mode of CHEX at  (Nithin Naga Manne, 2021). We have also provided data sets comprising a set of notebooks with pre-computed execution trees.

We used a combination of real-world applications and synthetic datasets for evaluation. We ran all our experiments on a 2.2GHz Intel Xeon CPU E5-2430 server with 64GB of memory, running 64-bit Red Hat Enterprise Linux 6.5. The heuristics were developed in Python 3.4.

We used four neural network machine learning applications (ML) and two scientific computing (SC) applications. Table 2 describes the characteristics of these notebooks. For the majority of the applications, the number of versions was determined in consultation with the notebook authors, by identifying meaningful changes to parameter values. Other notebooks were changed similarly. Total replay cost is the time to run all the versions with no cache. Total checkpoint size is the space required if each cell of the corresponding execution tree is checkpointed. Cell compute range and Cell checkpoint size represents the range of cell compute time and checkpoint size ranges , respectively. The changed parameter row mentions application parameters that were changed to create versions. The only way we created versions was by changing parameters. We did not modify any part of the programs in any other way.

The case of the parameter epochs in ML notebooks is special. In our case, the ML notebooks embed deep neural networks, in which typically the compute-intensive part is the back propagation during the training phase. Back propagation is usually implemented as an iterative for-loop, whose upper bound is defined by the epochs parameter. Changing epochs will change the training length and the number of iterations in the for-loop. Such a change to create a new version, however, will also re-run the entire training phase again, which will include the training iterations performed in the previous version. Therefore to create a version when the change is to epochs, we do not modify the value in-place. Instead we add a new cell. This cell consists of the author-provided training loop but with a incremental range of epochs starting from the last epoch value of the previous cell. This way of modifying the epoch parameter introduces no change to the code and corresponds to incremental training, which is often used in ML to take advantage of previous computations.

Closer in spirit to our work is the DataHubs (Bhattacherjee et al., 2015) system that seeks to maintain multiple versions of large data sets without fully replicating them. In this system some versions are stored fully materialized and others are stored only as deltas linked to other versions. The problem is to trade off total storage required versus time taken to recreate a version. At a glance, it is possible to think that the program states of the cells of our multiversion program can be aligned with the data sets considered in DataHubs. However, the fundamental difference is that DataHubs assumes each version of a data set has already been created the first time. Thus, they assume that at least one version of the data set is stored in its entirety. In CHEX, the equivalent thing would be for Alice to share some of the program states generated in her execution with Bob. This defeats the entire purpose of independent repetition by Bob.

We now discuss any assumptions that CHEX makes and our results. We assumed that CHEX works with REPL cells, but, in general, we do not constrain users like Alice to program with REPL interfaces. If the code is not developed via a REPL interface, CHEX preprocesses it into cells, akin to a program developed via a REPL interface, before monitoring. This preprocessing takes care to not split functions or control flows into separate cells. Thus every input program is automatically transformed into an equivalent REPL program and then entered into the CHEX.

We have assumed multiple versions for a given program. We make no assumptions on the types of edits that constitutes a version on Alice’s side. Thus, Alice can change values of parameters, specifications of datasets, models, or learning algorithms. She can also add or delete entire cells. In practice we have found such versions to not correspond to development versions but as separate branches in version-control repositories. In workflow systems they also correspond to independent, but related, experiments.

We have only demonstrated a scenario in which Alice shares notebooks with Bob for multiversion replay. A more evolved back-and-forth sharing of packages that accounts for any previous multiversion replay decisions to be persisted, will require further changes both to the system and the algorithm. In such a scenario, if the caches persist, some intermediate results are available for free and the algorithm needs to accommodate for that accordingly. This scenario is part of our future work.

Finally, our experiments show that CHEX significantly decreases the replay time for compute and data-intensive notebooks and allows a user to execute far higher number of versions in a given amount of time. The benefit arises particularly for notebooks where pre-processing or training steps are compute and data-intensive. In particular, if all computation is conducted in the last cell, then opportunities for optimization on intermediate results reduce drastically. In this case, one option is to further divide the last cell to look for opportunities of optimization. However, a better approach may be to look for opportunities within referenced function or libraries, if any.

In this work we have highlighted the need for improving the efficiency of multiversion replay. Our work shows that execution lineage can be used to establish cell equality and reuse shared program state to optimize replaying of multiversions. We show that optimizing is not trivial and, given a fixed cache size, MVR-P  is NP-hard and present two efficient heuristics for reducing the total computation time. We develop novel checkpoint-based caching support for replaying versions and show that CHEX is able to reduce the compute time of several machine learning and scientific computing notebooks using a cache size that is smaller than the checkpoint size of a notebook.

In the future, we wish to extend CHEX for queries and the standard database provenance model. This problem seems akin to how we previously extended provenance-based application virtualization (Pham et al., 2013) to database virtualization (Pham et al., 2015a). We also wish to explore how CHEX can incorporate program restructuring, which happens during interactive notebook development leveraging recent provenance models developed in this area (Macke et al., 2020; Koop and Patel, 2017; Brachmann et al., 2020) and developing corresponding online algorithms.