# S2p: Provenance Research for Stream Processing System
## 2 Preliminaries
### Stream Provenance Problem Definition  
The purpose of DSP provenance is to track how each stream data has changed over time. The provenance schema involves provenance capturing, storage, and querying. Here, we will classify some related expressions for future convenience. The set \(X=\{x_{t},x_{t+1,}x_{t+2},...\}\) represents the input stream data into one operator with timestamps \(t,t+1,t+2\), etc. The set \(Y=\{y_{u},y_{u+1},y_{u+2},...\}\) represents the computing results out of this operator with timestamps \(u,u+1,u+2\), etc. \(P(. )\) is operator transformation, which encapsulates user-defined data processing logic. Then, we conduct the provenance definition in this paper. Result data \(y_{u}\)'s provenance consists of the minimal source data set and a series of transformations that derivate it from the source data set. In other words, the provenance for stream result data is constituted by subinstance of source data \(I\subseteq X\) where the set \(I\) is the minimum set among all subsets that contribute to \(y_{u}\), and transformations \(P^{n}(...(P^{2}(P^{1}(P^{0}(I)))))\) such that \(y_{u}=P^{n}(...(P^{2}(P^{1}(P^{0}(I)))))\). Figure 2: An overview of the DSP computing model. Though user-defined data processing logic varies, the semantics of DSP APIs constrain the input and output data relationship at a high level. For instance, _map_ is a standard operator in DSP systems that ingests one stream data each time and produces one output. In this case, \(P(. )\) corresponds to _map_. For any output data \(y_{u}\), we can find at least one input \(x_{i}\). Hence, we can express the provenance for the result data \(y_{u}\) as \((map,\{x_{i}\}_{\min},y_{u})\), where \(\{x_{i}\}_{\min}\) is the minimal subset of the input data that leads to \(y_{u}\). However, the way to find the minimal set \(I\) for one DSP system differs for stateless operators and stateful operators. For stateless operators, their output results purely depend on the latest input and operators' semantics. Nevertheless, for stateful operators, the historical stream data will also potentially contribute to the current result indirectly through the internal states \(S\), which are persisted by stateful operators. Consider one DSP job (shown in Figure 3) as an example. It consists of three stateless operators (i.e., \(OP_{1}\), \(OP_{2}\), \(OP_{4}\)) and one stateful operator (i.e., \(OP_{3}\)). We can see that \(OP_{3}\)'s output is determined by its input values and its \"side effects\" (i.e., state) affected by historical data. To include complete provenance information for stateful operators, we express it as a list of nested tuples \((P_{i},(\{x_{i}\}_{\min},s_{j}),y_{u})\), where \(\{x_{i}\}_{\min}\) is the minimal subset of input data. The state \(s_{j}\) is a snapshot when \(\{x_{i}\}_{\min}\) is being processed and potentially decided by the historical input data recursively. For the example in Figure 3, we express the provenance of one result data as a graph, shown in Figure 4.  
Because of the long-running (e.g., months, or even years) nature of one nontrivial DSP job, recording all state transition for further provenance purposes is expensive or even impossible. In this paper, our solution will only pinpoint every state transition in a certain period in the offline provenance phase when quite a few state data are to be stored. State tracking is not the only obstacle for DSP provenance. DSP data's ephemeral nature brings another problem: that we have to cache the intermediate stream data for further provenance query. Since we have no previously known information about the potential analysis bias in the future, we have to assume that every stream data might be selected as object data. Therefore, our solution should have the capability to retrospect every piece of data. Our first attempt to achieve this requirement is to cache all the  
Figure 4: Provenance graph for our DSP instance. Figure 3: One DSP dataflow instance, which consists of four operators.