Provenance for Generalized Map and Reduce Workflows

It is shown how data provenance can be captured for map and reduce functions transparently and used to support backward tracing and forward tracing, and properties that are guaranteed to hold when provenance is applied recursively are identified.

Abstract

We consider a class of workflows, which we call generalized map and reduce workflows (GMRWs), where input data sets are pro-cessed by an acyclic graph of map and reduce functions to pro-duce output results. We show how data provenance (also some-times called lineage) can be captured for map and reduce functions transparently. The captured provenance can then be used to sup-port backward tracing (finding the input subsets that contributed to a given output element) and forward tracing (determining which output elements were derived from a particular input element). We provide formal underpinnings for provenance in GMRWs, and we identify properties that are guaranteed to hold when provenance is applied recursively. We have built a prototype system that supports provenance capture and tracing as an extension to Hadoop. Our system uses a wrapper-based approach, requiring little if any user intervention in most cases, and retaining Hadoop’s parallel execu-tion and fault tolerance. Performance numbers from our system are reported. 1.