Basic MapReduce Definitions

A map-reduce job is a computing problem where you need to apply a transformation function to a data set, and then calculate some aggregated values from subsets of this data. Not every distributed processing problem comes down to a map-reduce job, but many of them do, and it is just a very useful tool and a nice way to look at some data processing problems in general.

Map-reduce is not a distributed processing thing per se, these are just a couple of completely regular programming operations that just happen to play nicely with distributed processing. This is why problems that can be solved with a simple map are usually referred to as embarrassingly parallelizable problems.

For the sake of completeness, let's remember some definitions using Scala lingo. The map operator takes an Iterable[A] and applies a function A => B to each of its elements, generating an Iterable[B].

    x: Seq[A] = (...)
    y: Seq[B] = x map { r => ... }

The reduce operator takes an Iterable[B] and a function (B, B) => B, and "reduces" the whole set to a single value.

    z: Seq[B] = y reduce { (r, s) => ... }

Many problems can be solved by using these two operations. For instance, the sum of the first ten even numbers equals

    scala> 0 to 9 map (_ * 2) reduce (_ + _)
    res6: Int = 90

These are just the basic definitions, but apart from map you should also be interested in the flatMap operator, where each element from the input set generates many outputs, or even none. This previous reduce definition is also restricted to idempotent operations, but it is possible to work with more generic functions with a (C, B) => C signature, as happens with the foldRight Scala operation. Also, a map-reduce job usually have only these two steps, the "map" and the "reduce", but it is possible to create more complicated jobs with more steps. We will not be concerned with that at this moment.