Associativity lets a reduction combine intermediate results in different groupings without changing the final result. This property makes grouped data suitable for parallel reduction, because reducers need not receive mapper outputs in one fixed arrangement. section 13.2.2
Use associativity as a design check before parallelizing a computation:
- Group data by the attributes needed for independent reductions. section 13.2.2
- Verify that each reducer can combine intermediate results regardless of their grouping or output arrangement. section 13.2.2
- Avoid assuming associativity solves dependencies between adjacent or sequential data entries; time series generally still require ordered processing. section 13.2.2
Reducing coin data
Parallel processes can count coins or compute their total value independently, then combine those partial results centrally. When coin records are grouped by type, reducers can combine each group’s intermediate lists only if their operation is associative. section 13.2.2
$100: 1 50¢: 1 $100: 1 $1: 1 25¢: 1 ...
Inspect the coin records used to motivate splitting input into mapper chunks before reduction. section 13.2.2
