DMR: A Deterministic MapReduce for Multicore Systems

摘要

MapReduce has been shown promising to harness the multicore platform. Existing MapReduce libraries on multicore are written with shared-memory Pthreads, which introduce pervasive nondeterminism and might produce nondeter-ministic results if user-provided map or reduce functions are sensitive to the input order. We propose DMR, a deterministic MapReduce library, to ensure deterministic program behaviors no matter whether map/reduce function is sensitive to the input order. DMR adopts a round-robin scheduling of map tasks and a partitioned scheduling of reduce tasks to ensure deterministic scheduling. DMR is written with a deterministic message passing multithreaded model (DetMP) to provide Phoenix-like API, thus Phoenix workloads can be built and run on DMR with no or little change. Evaluation results by testing seven Phoenix workloads show that DMR only runs worse than Phoenix on an iterative MapReduce application kmeans, outperforms Phoenix between 1.42X and 3.33X faster on pea and word_count, and scales better than Phoenix on 3 of the rest 4 workloads.