Combiners in Hadoop MapReduce

A combiner function in MapReduce has the same form as the reduce function (and is an implementation of the Reducer interface), except its output types are the intermediate key and value types (K₂ and V₂), so they can feed the reduce function:

combiner: (K₂, list(V₂)) → list(K₂, V₂)

Often the combiner and reduce functions are the same, in which case K₃ is the same as K₂, and V₃ is the same as V₂. On the other hand, Hadoop reserves the right to use combiners at its discretion. This means that a combiner may be invoked zero, one, or multiple times. Hence, the correctness of a MapReduce algorithm shouldn't depend on computations performed by the combiner or depend on them even being run at all.