An On-the-fly Provenance Tracking Mechanism for Stream Processing Systems

Applications that operate over streaming data withhigh-volume and real-time processing requirements are becomingincreasingly important. These applications process streamingdata in real-time and deliver instantaneous responses to supportprecise and on-time decisions. In such systems, traceability -the ability to verify and investigate the source of a particularoutput - in real-time is extremely important. This ability allowsraw streaming data to be checked and processing steps to beverified and validated in timely manner. Therefore, it is crucialthat stream systems have a mechanism for dynamically trackingprovenance - the process that produced result data - at executiontime, which we refer to as on-the-fly stream provenance tracking.In this paper, we propose a novel on-the-fly provenance trackingmechanism that enables provenance queries to be performeddynamically without requiring provenance assertions to be storedpersistently. We demonstrate how our provenance mechanismworks by means of an on-the-fly provenance tracking algorithm.The experimental evaluation shows that our provenance solutiondoes not have a significant effect on the normal processing ofstream systems given a 7% overhead. Moreover, our provenancesolution offers low-latency processing (0.3 ms per additionalcomponent) with reasonable memory consumption.