1. A method implemented by data processing apparatus that includes a plurality of computers, the method comprising providing a shuffle service on one or more computers; providing, on each computer of a plurality of computers that are independent of the one or more computers on which the shuffle service is provided, one or more virtual machines on the computer, and a shuffle interface on the computer to the shuffle service, wherein the shuffle service executes external of the virtual machines, and wherein each virtual machine includes a mapping component of a map reduce framework that applies a mapping function to data records, wherein the mapping component: receives a data record having a key and a value; and generates, based on the received data record and using a mapping function, an intermediate data record having an intermediate key and an intermediate value, the intermediate key being different from the key; communicates with the shuffle service through the shuffle interface executing on the computer on which the virtual machine is executing; receiving, by the shuffle service and from the virtual machines, intermediate data records through the shuffle interface; partitioning, by the shuffle service, groups of intermediate data records according to respective intermediate keys; and providing, by the shuffle service to each virtual machine, a part of the intermediate data records through the interface to the virtual machines, wherein the intermediate data records provided to a particular virtual machine have the same intermediate key and are only provided to the particular virtual machine.