Anti-combining for MapReduce
Alper Okcan, Mirek Riedewald · 2014
We propose Anti-Combining, a novel optimization for MapReduce programs to decrease the amount of data transferred from mappers to reducers. In contrast to Combiners, which decrease data transfer by performing reduce work on the mappers, Anti-Combining shifts mapper work to the reducers. It is also conceptually different from traditional compression techniques. While the latter are applied outside the MapReduce framework by compressing map output and then decompressing it before the data is fed into the reducer, Anti-Combining is integrated into mapping and reducing functionality itself. This enables lightweight algorithms and data reduction even for cases where the Map output data shows no redundancy that could be exploited by traditional compression techniques. Anti-Combining can be enabled automatically for any given MapReduce program through purely syntactic transformations. In some cases, in particular for certain non-deterministic Map and Partition functions, only a weaker version can be applied. At runtime the Anti-Combining enabled MapReduce program will dynamically and adaptively decrease data transfer by making fine-grained local decisions. Our experiments show that Anti-Combining can achieve data transfer reduction similar to or better than traditional compression techniques, while also reducing CPU and local I/O cost. It can even be applied in combination with them to greater effect.