# S2p: Provenance Research for Stream Processing System
## 7 Experimental Evaluation
### Evaluation Metrics  
Our experiments take the end-to-end cost (we will simply call it cost for short in the following) and throughput [47] as metrics to evaluate the efficiency of s2p in the online provenance phase. We also evaluate space overhead to measure how much additional space is needed to store provenance-related data.  
In our study, we evaluate the cost for various workloads (i.e., data set in different sizes), i.e., the cost is calculated as the time difference between the moment one stream  
\begin{table}
\begin{tabular}{c} Map, \\ Filter, \\ KeyBy, \\ Window, \\ Reduce \\ \end{tabular} & 500G \\ \hline \hline \end{tabular}
\end{table}
Table 2: Subject Applications.  
application starts and the moment that all results are generated. Throughput, in this study, is the number of source data that is ingested and processed per time unit.  
The space cost mainly consists of two parts, i.e., references to source data (i.e., parents' ID list in every stream data) and persisted checkpoints. Since references to source data are piggybacking on stream data and propagate from upstream operators to downstream operators, there is no additional space necessary to store references-related data for intermediate operators until after the sink operators because the intermediate data are temporary and dropped soon as they are transferred to downstream operators. Therefore, we will focus on the data passing through sink operators only, for these are to be stored for future analysis.  
The first experiment compares how cost changes when normal Flink is enabled with online provenance capability. This is achieved by executing the same application under each workload on both s2p-flink and normal Flink, then recording and analyzing their corresponding computing time.  
We measure the increased degree of cost under the workload \(w\) as the increased ratio \(\sigma^{w}\) as in Equation (4).  
\[\sigma^{w}=\frac{\tilde{\phi}^{w}-\bar{\varphi}^{w}}{\bar{\varphi}^{w}} \tag{4}\]  
where \(\tilde{\phi}^{w}\) represents the trimmed mean of s2p-flink's cost and \(\tilde{\varphi}^{w}\) refers to native Flink's.  
The second experiment focuses on the decline of throughput for s2p-flink. We carry out each workload of various sizes. For each workload, we compare the throughput of the same application with and without provenance (i.e., s2p-flink vs. normal Flink).  
Similarly, we measure the degree of throughput reduction under the workload \(w\) as the decreased ratio \(\eta^{w}\) as in Equation (5).  
\[\eta^{w}=\frac{\tilde{\rho}^{w}-\bar{v}^{w}}{\bar{\rho}^{w}} \tag{5}\]  
where \(\bar{\rho}\) represents the trimmed mean of normal Flink's throughput and \(\bar{v}^{w}\) refers to s2p-flink's.  
The third experiment is to measure the space overhead. We define the space overhead ratio \(\tau^{w}\) to present the additional space required quantitively. It is calculated as follows in Equation (6).  
\[\tau^{w}=\frac{\sum\beta_{i}}{\psi^{w}},i\in\{0,1,...,|OP_{i}|\} \tag{6}\]  
where \(\beta_{i}\) is the space overhead for additional space required in \(i\)th sink operator instance, \(\psi^{w}\) is the size of source data under workload \(w\), and \(|OP_{i}|\) is the number of terminus operators' instance. In our experiment, we can obtain \(\sum\beta_{i}\) by calculating the data size difference between stream data processed by s2p's terminus operators and the ones processed by native Flink's terminus operators under each workload \(w\).  
In all experiments, we executed the applications under each workload seven times and computed the trimmed mean value by removing the maximum and minimum results and averaging the remaining five among the seven runs. We also configured s2p-flink to retain 20 versions of checkpoints and persisted these checkpoints in HDFS.