1. A method implemented by data processing apparatus that includes a plurality of computers, the method comprising: providing, on each computer of a plurality of computers, one or more virtual machines on the computer, and a shuffle interface on the computer to a shuffle service, wherein the shuffle service executes on one or more computers that are independent of the plurality of computers on which the one or more virtual machines are provided, and wherein each virtual machine includes a mapping component of a map reduce framework that applies a mapping function to data records; for each virtual machine: receiving, by the mapping component, a data record having a key and a value; generating, by the mapping component, 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; sending to the shuffle service, through the shuffle interface executing on the computer on which the virtual machine is executing, the intermediate data record; and receiving, from the shuffle service, intermediate data records through the shuffle interface; wherein: the shuffle service partitions groups of intermediate data records according to respective intermediate keys; and the intermediate data records received by a particular virtual machine have the same intermediate key and are only provided to the particular virtual machine, and there are a plurality of different intermediate keys and a corresponding plurality of different virtual machines.