# S2p: Provenance Research for Stream Processing System
## 5 Offline Provenance  
The purpose of offline provenance is to obtain detailed execution information for some specific data of interest. To avoid affecting the original DSP system, we replay the DSP job in a simulation environment. We restart the job from a certain point and track the transformation of data of interest. Figure 8 outlines how to replay the process in a simulation environment based on the online data collected in the online provenance phase.  
Offline (Offline, in our paper, means the process of capturing and querying fine-grained provenance is independent with the original DSP execution environment) provenance refers to replaying the DSP job partially. It relies on the checkpoint mechanism in DSP systems and the ability to reaccess their source data. The periodic checkpoints slice the continuous processes and put marks in the stream. We can then replay the application from some specific points as required.  
The process to obtain fine-grained provenance information for some object output result data is as follows. First, initialize the simulation environment with the extended s2p-DSP platforms (i.e., DSP systems extended with provenance capability) predeployed. Second, extract the source ID lists of the object result data. Third, query their corresponding source data according to the source ID list and obtain the earliest checkpoint among them. Fourth, set the job state from the earliest checkpoints and tune stateful operators with the checkpoint data from remote backup repositories (e.g., state persisted in distributed file  
Figure 8: Replaying DSP jobs from one specific checkpoint n-k. First, stateful operators fetch corresponding state values from distributed filesystems and set as their current state. Then source operators ingest the old stream data starting from where checkpoint n-k marks.  
systems). Finally, rerun this stream process job and track the detailed data transformation information passing operators.  
**Restart from the earliest checkpoint bounded in object source data**: The nearest state snapshot may happen some time ago before the object source data arrive. In the online provenance phase, we bound IDs of each data item with the nearest checkpoint information. Checkpoints may vary for different object source data. To determine where our replay process should occur, we process the object source data in Algorithm 1.  
```
Input: Object source data set \(\{(ID_{n},Chk_{m})\}\) Output: The checkpoint \(Chk_{r}\) where we restart the job from during offline provenance init\(Chk_{r}\longleftarrow MAX\_ChkVersion\); \(length\longleftarrow\) length of \(\{(ID_{n},Chk_{m})\}\); for\(i\gets 0\)to\(length-1\)do if\(Chk_{r}\)small than\(Chk_{m}^{i}\)in\((ID_{n},Chk_{m})_{i}\)then \(Chk_{r}\longleftarrow Chk_{m}^{i}\);  end if  end for
```  
**Algorithm 1**Checkpoint Determination Among Object Source Data  
**Runtime monitoring**: Detailed runtime information, including object data that arrives at or leaves operators, state transformation, etc. We also generate a unique ID for every data, including the intermediate data derivated from our object data. Similar to what we have done in online provenance, we wrap operators to store the data of interest, including data fed into operators, the temporary result after operators, etc. Furthermore, it is also necessary to record stateful operators' state values because they may contribute to output results.  
For reducing the network burden caused by moving these monitoring data, they are all stored in their local machines and managed by our system transparently in distributed mode.