CIRCUMFLEX: A Scheduling Optimizer for MapReduce Workloads Involving Shared Scans

We consider MapReduce clusters designed to support multiple concurrent jobs, concentrating on environments in which the number of distinct datasets is modest relative to the number of jobs. Many datasets in such scenarios will wind up being scanned by multiple concurrent Map phase jobs. As has been noticed previously, this scenario provides an opportunity for Map phase jobs to cooperate, sharing the scans of these datasets, and thus reducing the costs of such scans. Our paper has two main contributions. First, we present a new, novel and highly general method for sharing scans and thus amortizing their costs. This concept, which we will call cyclic piggybacking, is an alternative to the more traditional batching scheme described in the literature, and seems to have a number of advantages over that scheme. Second, we describe a method for optimizing schedules within the context of this cyclic piggybacking paradigm. This scheme, a significant but natural generalization of the recently introduced flex scheduler for MapReduce, can optimize a wide variety of metrics. Such cost functions include average response time, average stretch, and any minimax-type metric. The overall approach, including both cyclic piggybacking and the flex generalization, is called circumflex. We demonstrate the excellent performance of circumflex via a variety of simulation experiments, and we describe a practical implementation strategy.

By: Joel Wolf, Andrey Balmin, Deepak Rajan, Kirsten Hildrum, Rohit Khandekar, Sujay Parekh, Kun-Lung Wu, Rares Vernica

Published in: RC25118 in 2011


This Research Report is available. This report has been submitted for publication outside of IBM and will probably be copyrighted if accepted for publication. It has been issued as a Research Report for early dissemination of its contents. In view of the transfer of copyright to the outside publisher, its distribution outside of IBM prior to publication should be limited to peer communications and specific requests. After outside publication, requests should be filled only by reprints or legally obtained copies of the article (e.g., payment of royalties). I have read and understand this notice and am a member of the scientific community outside or inside of IBM seeking a single copy only.


Questions about this service can be mailed to .