Cloud⁹

The order inversion design pattern is covered in Chapter 3, where the example is computing bigram relative frequencies. A reference implementation can be found in the solutions to the bigram counting exercise.

Here's how it works, very briefly: in addition to each bigram count, the mapper emits an special key (word, *) which contributes to the marginal count of the word. We define the sort order so that this special key always comes before the bigram counts, so that by preserving state across multiple reduce method calls,we can compute the relative frequency directly by simple division. We also need to define a custom partitioner to send all keys with the same left element to the same reducer.