Parallelization contract: Difference between revisions

Revision as of 11:04, 5 January 2014

Latest revision as of 16:26, 9 September 2023

(9 intermediate revisions by 9 users not shown)

Line 1:

{{Orphanoriginal research|date=DecemberMay 20132023}}

The '''parallelization contract''' or '''PACT''' programming model is a generalization of the [[MapReduce]] [[programming model]] and uses [[Higher-order function|second order functions]] to perform concurrent computations on large ([[Petabyte]]s) data sets in parallel.

Line 9:

* Program structure: PACT allows the composition of arbitrary acyclic data flow graphs. In contract, MapReduce programs have a static structure (Map -> Reduce).

* Data Model: PACT's data model are records of arbitrary many fields of arbitrary types. MapReduce's KeyValue-Pairs can be considered as records with two fields.

[[Apache Flink]], an open-source parallel data processing platform has implemented '''PACT'''s. Flink allows users to specify user functions with annotations.

== Logical view ==

Line 20 ⟶ 22:

Optionally, the user code can be annotated with additional information. These annotations disclose some information on the behavior of the black-box user function. The [[PactCompiler|PACT Compiler]] can utilize the information to obtain more efficient execution plans. However, while a missing annotation will not change the result of the execution, an incorrect Output Contract produces wrong results.

{{:wiki:pact.png?nolink&600|}}

The currently supported Input Contracts and annotation are presented and discussed in the following.

Line 36:

== MAP ==

The Map Input Contract works in the same way as in MapReduce. It has a single input and assigns each input record to its own subset. Hence, all records are processed independently from each other (see figure below). \\

{{:wiki:map.png?nolink&100|}}

== REDUCE ==

The Reduce Input Contract has the same semantics as the reduce function in MapReduce. It has a single input and groups together all records that have identical key fields. Each of these groups is handed as a whole to the user code and processed by it (see figure below). The PACT Programming Model does also support optional Combiners, e.g. for partial aggregations. \\

{{:wiki:reduce.png?nolink&100|}}

== CROSS ==

The Cross Input Contract works on two inputs. It builds the Cartesian product of the records of both inputs. Each element of the Cartesian product (pair of records) is handed to the user code. \\

{{:wiki:cross.png?nolink&160|}}

== MATCH ==

The Match Input Contract works on two inputs. From both inputs it matches those records that are identical on their key fields come from different inputs. Hence, it resembles an equality join where the keys of both inputs are the attributes to join on. Each matched pair of records is handed to the user code. \\

{{:wiki:match.png?nolink&160|}}

== COGROUP ==

The CoGroup Input Contract works on two inputs as well. It can be seen as a Reduce on two inputs. On each input, the records are grouped by key (such as Reduce does) and handed to the user code. In contrast to Match, the user code is also called for a key if only one input has a pair with it (see blue key in example below).

{{:wiki:cogroup.png?nolink&200|}}

=== Pact Record Data Model ===

Line 68 ⟶ 59:

In contrast to MapReduce, PACT uses a more generic data model of records ([[PactRecord|Pact Record]]) to pass data between functions. The Pact Record can be thought of as a tuple with a free schema. The interpretation of the fields of a record is up to the user function. A Key/Value pair (as in MapReduce) is a special case of that record with only two fields (the key and the value).

For input contracts that operate on keys (like //Reduce//, //Match//, or //CoGroup//, one specifies which combination of the record's fields make up the key. An arbitrary combination of fields may used. See the [https://github.com/stratosphere-eu/stratosphere/blob/master/pact/pact-examples/src/main/java/eu/stratosphere/pact/example/relational/TPCHQuery3.java|TPCH Query ExampeExample] on how programs defining //Reduce// and //Match// contracts on one or more fields and can be written to minimally move data between fields.

The record may be sparsely filled, i.e. it may have fields that have //null// values. It is legal to produce a record where for example only fields 2 and 5 are set. Fields 1, 3, 4 are interpreted to be //null//. Fields that are used by a contract as key fields may however not be null, or an exception is raised.

Line 78 ⟶ 69:

== Constant Fields ==

The **'''Constant Fields**''' annotation marks fields that are not modified by the user code function. Note that for every input record a constant field may not change its content and position in any output record! In case of binary second-order functions such as Cross, Match, and CoGroup, the user can specify one annotation per input.

== Constant Fields Except ==

The **'''Constant Fields Except**''' annotation is inverse to the **Constant Fields** annotation. It annotates all fields which might be modified by the annotated user-function, hence the optimizer considers **any not annotated field as constant**. This annotation should be used very carefully! Again, for binary second-order functions (Cross, Match, CoGroup), one annotation per input can be defined. Note that either the Constant Fields or the Constant Fields Except annotation may be used for an input.

=== PACT Programs ===

PACT programs are constructed as data flow graphs that consist of data sources, PACTs, and data sinks. One or more data sources read files that contain the input data and generate records from those files. Those records are processed by one or more PACTs, each consisting of an Input Contract, user code, and optional code annotations. Finally, the results are written back to output files by one or more data sinks. In contrast to the MapReduce programming model, a PACT program can be arbitrary complex and has no fixed structure. \\

The figure below shows a PACT program with two data sources, four PACTs, and one data sink. Each data source reads data from a specified ___location in the file system. Both sources forward the data to respective PACTs with Map Input Contracts. The user code is not shown in the figure. The output of both Map PACTs streams into a PACT with a Match Input Contract. The last PACT has a Reduce Input Contract and forwards its result to the data sink.

Line 95 ⟶ 86:

* The PACT programming model encourages a more modular programming style. Although the number of user functions is usually higher, they are more fine-grain and focus on specific problems. Hence, interweaving of functionality which is common for MapReduce jobs can be avoided.

* Data analysis tasks can be expressed as straight-forwardstraightforward data flows, especially when multiple inputs are required.

* PACT has a record-based data model, which reduces the need to specify custom data types as not all data items need to be packed into a single value type.

* PACT frequently eradicates the need for auxiliary structures, such as the distributed cache, which "break" the parallel programming model.

Line 102 ⟶ 93:

For a more detailed comparison of the MapReduce and PACT programming models you can read our paper //"MapReduce and PACT - Comparing Data Parallel Programming Models"// (see our [https://www.stratosphere.eu/index.php?q=publications|publications page]).

== See also ==

{{Empty section|date=December 2013}}

== References ==

{{reflist}}

* [https://web.archive.org/web/20120424184436/http://www.stratosphere.eu/files/NephelePACTs_10.pdf "Nephele/PACTs: A Programming Model and Execution Framework for Web-Scale Analytical Processing"]—paper by D. Battré, S. Ewen, F. Hueske, O. Kao, [[Volker Markl|V. Markl]], and D. Warneke from [http://www.tu-berlin.de/menue/home/parameter/en/ TU Berlin] published in Proc. of ACM SoCC 2010. The paper introduces the PACT programming model, a generalization of MapReduce, developed in the [http://www.stratosphere.eu Stratosphere] research project.

* [https://web.archive.org/web/20120424184448/http://www.stratosphere.eu/files/ComparingMapReduceAndPACTs_11.pdf "MapReduce and PACT - Comparing Data Parallel Programming Models"]—paper by A. Alexandrov, S. Ewen, M. Heimel, F. Hueske, O. Kao, V. Markl, E. Nijkamp, and D. Warneke from [http://www.tu-berlin.de/menue/home/parameter/en/ TU Berlin] published in Proc. of BTW 2011.

== Further reading ==

Line 117 ⟶ 104:

== External links ==

* [http://stratosphere.eu Stratosphere project home page]

* [http://www.hpts.ws/papers/2011/posters/Poster2011_06_Bodner.pdf Stratosphere slide presentation]