May 11, 2009

Hadoop Sorts a Petabyte in 16.25 Hours and a Terabyte in 62 Seconds

We used Apache Hadoop to compete in Jim Gray's Sort benchmark. Jim's Gray's sort benchmark consists of a set of many related benchmarks, each with their own rules. All of the sort benchmarks measure the time to sort different numbers of 100 byte records. The first 10 bytes of each record is the key and the rest is the value. The minute sort must finish end to end in less than a minute. The Gray sort must sort more than 100 terabytes and must run for at least an hour. The best times we observed were:

Within the rules for the 2009 Gray sort, our 500 GB sort set a new record for the minute sort and the 100 TB sort set a new record of 0.578 TB/minute. The 1 PB sort ran after the 2009 deadline, but improves the speed to 1.03 TB/minute. The 62 second terabyte sort would have set a new record, but the terabyte benchmark that we won last year has been retired. (Clearly the minute sort and terabyte sort are rapidly converging, and thus it is not a loss.) One piece of trivia is that only the petabyte dataset had any duplicate keys (40 of them).

We ran our benchmarks on Yahoo's Hammer cluster. Hammer's hardware is very similar to the hardware that we used in last year's terabyte sort. The hardware and operating system details are:

• approximately 3800 nodes (in such a large cluster, nodes are always down)
• 2 quad core Xeons @ 2.5ghz per node
• 4 SATA disks per node
• 8G RAM per node (upgraded to 16GB before the petabyte sort)
• 1 gigabit ethernet on each node
• 40 nodes per rack
• 8 gigabit ethernet uplinks from each rack to the core
• Red Hat Enterprise Linux Server Release 5.1 (kernel 2.6.18)
• Sun Java JDK (1.6.0_05-b13 and 1.6.0_13-b03) (32 and 64 bit)

We hit a JVM bug that caused a core dump in 1.6.0_05-b13 on the larger sorts (100TB and 1PB) and switched over to the later JVM, which resolved the issue. For the larger sorts, we used 64 bit JVMs for the Name Node and Job Tracker.

Because the smaller sorts needed lower latency and faster network, we only used part of the cluster for those runs. In particular, instead of our normal 5:1 over subscription between racks, we limited it to 16 nodes in each rack for a 2:1 over subscription. The smaller runs can also use output replication of 1, because they only take minutes to run and run on smaller clusters, the likelihood of a node failing is fairly low. On the larger runs, failure is expected and thus replication of 2 is required. HDFS protects against data loss during rack failure by writing the second replica on a different rack and thus writing the second replica is relatively slow.

Below are the timelines for the jobs counting from the job submission at the Job Tracker. The diagrams show the number of tasks running at each point in time. While maps only have a single phase, the reduces have three: shuffle, merge, and reduce. The shuffle is the transfer of the data from the maps. Merge doesn't happen in these benchmarks, because none of the reduces need multiple levels of merges. Finally, the reduce phase is where the final merge and writing to HDFS happens. I've also included a category named waste that represents task attempts that were running, but ended up either failing, or being killed (often as speculatively executed task attempts).

If you compare this years charts to last year's, you'll notice that tasks are launching much faster now. Last year we only launched one task per heartbeat, so it took 40 seconds to get all of the tasks launched. Now, Hadoop will fill up a Task Tracker in a single heartbeat. Reducing that job launch overhead is very important for getting runs under a minute.

As with last year, we ran with significantly larger tasks than the defaults for Hadoop. Even with the new more aggressive shuffle, minimizing the number of transfers (maps * reduces) is very important to the performance of the job. Notice that in the petabyte sort, each map is processing 15 GB instead of the default 128 MB and each reduce is handling 50 GB. When we ran the petabyte with more typical values 1.5 GB / map, it took 40 hours to finish. Therefore, to increase throughput, it makes sense to consider increasing the default block size, which translates into the default map size, to at least up to 1 GB.

We used a branch of trunk with some modifications that will be pushed back into trunk. The primary ones are that we reimplemented shuffle to re-use connections, and we reduced latencies and made timeouts configurable. More details including the changes we made to Hadoop are available in our report on the results.

-- Owen O'Malley and Arun Murthy

Posted at May 11, 2009 3:00 PM

Bookmark this on Delicious

Comments

Posted by: Ben at May 11, 2009 9:44 PM | Permalink

Posted by: Owen O'Malley at May 12, 2009 8:26 AM | Permalink

Posted by: Ben at May 12, 2009 4:04 PM | Permalink

Posted by: Owen O'Malley at May 15, 2009 9:49 AM | Permalink

Posted by: walter at May 16, 2009 10:25 AM | Permalink

Posted by: Owen O'Malley at May 16, 2009 8:27 PM | Permalink

Posted by: Bradley at May 17, 2009 6:16 AM | Permalink

Posted by: Francisco at May 17, 2009 9:08 AM | Permalink

Posted by: Yavuz at May 17, 2009 10:54 AM | Permalink

Posted by: tim hawkins at June 9, 2009 12:57 AM | Permalink

Posted by: Pablo Navarro Castillo at July 1, 2009 4:57 AM | Permalink

Posted by: Rares Vernica at July 16, 2009 6:46 PM | Permalink

Posted by: Nasser at August 15, 2009 1:42 PM | Permalink

Posted by: Nasser at August 15, 2009 11:41 PM | Permalink

Posted by: ak at October 30, 2009 2:54 PM | Permalink