# S2p: Provenance Research for Stream Processing System
## 9 Related Work
### Batch-Processing Oriented Provenance  
Titian [19] is an interactive data provenance library integrating with Apache Spark. It enhances RDD [52] in Spark with fine-grained data provenance capabilities. We chose Titian as our first attempt to implement data provenance for Flink. However, as it is so tightly coupled with Spark, it is challenging to migrate directly into the DSP systems. Their approaches rely on stage replay capability, which means that Titian can trace RDD transformation within a stage by tracing back to the stage input and rerunning the stage transformation. This benefits from the RDD model, i.e., an RDD has enough information about how it was derived from other data sets, contributing to Titian's low overhead since it needs only to capture data lineage at the stage boundaries and adopt stage replay to trace RDD transformation within a stage.  
However, this is not feasible for DSP systems. Take Apache Flink as an instance. DataSet and DataStream [28] are two fundamental data types at Flink's core, which target bounded data sets and unbounded data streams, respectively. In contrast with RDD, they preserve no lineage data as RDDs such that it requires tracing each record to maintain their lineage relation when fine-grained provenance is required. Stage replay does not work for DSP systems either. DSP systems do not adopt the BSP model [20; 21], as Spark does. Instead, they adopt the dataflow computation model [53] with long-running or continuous operators. As computation progresses, operators update their local state, and messages are directly transferred between operators [54]. Data passing in DSP systems are more complicated because there exists asynchronous redistribution for interoperator data passing, which means that data will be buffered for a short time, such as milliseconds, and then sent to the downstream operator immediately to continue the process. All these together imply unfeasible to realize the same Titian stage boundary rerunning policy in DSP systems.  
RAMP [17] extends Hadoop to support provenance capturing and tracing for MapReduce jobs. It wraps Map and Reduce functions and propagates input identifiers of functions through the computations. RAMP requires user intervention in many cases, but it does not modify the core of Hadoop. RAMP does not store any intermediate data, which prevents a complete provenance and lacks the ability to view any intermediate data.  
[PERSON] [31] enables debugging map-reduce systems with minimal overhead by selectively replaying partial data computation. It can re-execute any task in the job in a single-process debugger. It achieves low overhead by taking advantage of task determinism, which is assumed in frameworks such as MapReduce [55], Dryad [56], etc. It runs a daemon with the framework's master only to collect information, while s2p runs several daemons with both masters and slaves so that the number of data transmitted can be efficiently reduced.  
Others, including [PERSON] [29], BigDebug [1] (a Titian follow-up research) argument big data frameworks with provenance ability, but are restricted to computing over static data and cannot easily be applied into DSP systems.