# S2p: Provenance Research for Stream Processing System
## 1 Introduction
There exist two categories of provenance work that target different data processing paradigms separately (batch processing vs. stream processing); they are shown in Table 1.  
For those targeting batch processing systems [15; 16], the state-of-the-art solutions include RAMP [17] (for Hadoop), HadoopProv [18] (for Hadoop), and Titian [19] (for Spark). Batch processing systems periodically consume blocks of static data (usually long in hours or even days). They adopt the BSP model [20; 21], which processes in a series of supersteps, i.e., iterating a large batch of data followed by a global barrier with synchronization among workers. These two features bring convenience in designing a provenance solution for batch processing systems, as they can conveniently revisit any source data and intermediate data from disks (e.g., for Hadoop) or memory (e.g., for Spark). The BSP model also makes replay from some stages (e.g., Titian [19]) possible, as it naturally divides the job into stages. On the contrary, solutions targeting stream processing systems include Ariadne [22; 23] and GeneLog [4; 24], among other solutions. DSP adopts the dataflow model [25], in which incoming data are processed as soon as they arrive and produce results within a short period (usually in milliseconds or seconds). As a new big data processing pattern, DSP systems present some new features that challenge the provenance design described as follows. 1. Stream data, a.k.a. real-time data, are ephemeral in many applications, which means that their intermediate data will not be persisted during transformation within jobs. Storing these intermediate data and their provenance metadata naively is impossible because the total data may be multiple times larger than the source data. If we store all dependencies and intermediate data objects, the amount of information recorded can potentially cause a storage burden problem. 2. Stream processing systems usually generate results within milliseconds to seconds processed by jobs. A heavy provenance capturing mechanism will bring in perceived delay substantially. 3. Current DSP systems usually closely integrate state with computation [26]. Unlike the batch processing system, in which data is batched and computed as a whole group, stream processing systems lack a similar global view for the whole data set. State in stream processing systems is then used to memorize the historical data ever seen or some intermediate results, which may indirectly affect the results. Due to this new feature, a consummated provenance for stream processing systems should also consider how states evolve together with the data transformation. We usually have no previously known information about which kinds of data are biased or more likely to be tracked by users, whether in crash-culprit scenarios or accountability purposes. This elicits another requirement, i.e., the ability to track every piece of stream data in a provenance solution. It is extremely inefficient to process the entire data set on every tuple, especially when the data is large. However, provenance for intermediate data is not directly used most of the time [14], which means that retaining full provenance for every piece of data would be a waste for most cases. In some scenarios, users want to \"replay\" intermediate data in detail [1]. In other scenarios [4; 24], they may only need to know which specific source data contribute to the results to be analyzed. We present s2p, a novel provenance solution for DSP systems to tackle the challenges above. The s2p solution consists of online provenance and offline provenance, through which the previous one builds the mapping relation between source data and result data, and the latter provides detailed information about transformation processes, intermediate results, and more. This design is inspired by the philosophy of lambda architecture [27] in which different results with different precision are handled by different process. Our s2p solution traces stream data across varieties of operators.