Data Algorithms

Chapter 5. Order Inversion

The main focus of this chapter is the Order Inversion (OI) design pattern, which can be used to control the order of reducer values in the MapReduce framework (which is useful because some computations require ordered data). Typically, the OI pattern is applied during the data analysis phase. In Hadoop and Spark, the order of values arriving at a reducer is undefined (there is no order unless we exploit the sorting phase of MapReduce to push the data needed for calculations to the reducer). The OI pattern works for pair patterns, which use simpler data structures and require less reducer memory, due to the fact that there is no additional sorting and ordering of reducer values in the reducer phase.

To help you understand the OI pattern, we’ll start with a simple example. Consider a reducer with a composite key of (K₁, K₂) and assume that K₁ is the natural key component of the composite key. Say this reducer receives the following values (there is no ordering between these values):

• V₁, V₂, ..., V_n

By implementing the OI pattern, we can sort and classify the values arriving at the reducer with a key of (K₁, K₂). The sole purpose of using the OI pattern is to properly sequence data presented to the reducer. To demonstrate the OI design pattern, we’ll assume that K₁ is a fixed part of the composite key and that K₂ has only three (this can be any number) distinct values, {K_2a, K_2b, K_2c}, which generate the values shown in Table 5-1. (Note that we have to ...