+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
1< html > 2 3<!-- 4Licensed to the Apache Software Foundation (ASF) under one or more 5contributor license agreements. See the NOTICE file distributed with 6this work for additional information regarding copyright ownership. 7The ASF licenses this file to You under the Apache License, Version 2.0 8(the "License"); you may not use this file except in compliance with 9the License. You may obtain a copy of the License at 10 11http://www.apache.org/licenses/LICENSE-2.0 12 13Unless required by applicable law or agreed to in writing, software 14distributed under the License is distributed on an "AS IS" BASIS, 15WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 16See the License for the specific language governing permissions and 17limitations under the License. 18--> 19 20< body > 21This package consists of 3 map/reduce applications for Hadoop to 22compete in the annual< a 23href ="http://www.hpl.hp.com/hosted/sortbenchmark "target ="_top "> terabyte sort</ a > 24competition. 25 26< ul > 27< li >< b > TeraGen</ b > is a map/reduce program to generate the data. 28< li >< b > TeraSort</ b > samples the input data and uses map/reduce to 29 sort the data into a total order. 30< li >< b > TeraValidate</ b > is a map/reduce program that validates the 31 output is sorted. 32</ ul > 33 34< p > 35 36< b > TeraGen</ b > generates output data that is byte for byte 37equivalent to the C version including the newlines and specific 38keys. It divides the desired number of rows by the desired number of 39tasks and assigns ranges of rows to each map. The map jumps the random 40number generator to the correct value for the first row and generates 41the following rows. 42 43< p > 44 45< b > TeraSort</ b > is a standard map/reduce sort, except for a custom 46partitioner that uses a sorted list of< i > N-1</ i > sampled keys that define 47the key range for each reduce. In particular, all keys such that 48< i > sample[i-1] <= key < sample[i]</ i > are sent to reduce 49< i > i</ i > . This guarantees that the output of reduce< i > i</ i > are all 50less than the output of reduce< i > i+1</ i > . To speed up the 51partitioning, the partitioner builds a two level trie that quickly 52indexes into the list of sample keys based on the first two bytes of 53the key. TeraSort generates the sample keys by sampling the input 54before the job is submitted and writing the list of keys into HDFS. 55The input and output format, which are used by all 3 applications, 56read and write the text files in the right format. The output of the 57reduce has replication set to 1, instead of the default 3, because the 58contest does not require the output data be replicated on to multiple 59nodes. 60 61< p > 62 63< b > TeraValidate</ b > ensures that the output is globally sorted. It 64creates one map per a file in the output directory and each map ensures that 65each key is less than or equal to the previous one. The map also generates 66records with the first and last keys of the file and the reduce 67ensures that the first key of file< i > i</ i > is greater that the last key of 68file< i > i-1</ i > . Any problems are reported as output of the reduce with the 69keys that are out of order. 70 71< p > 72 73In May 2008, Owen O'Malley ran this code on a 910 node cluster and 74sorted the 10 billion records (1 TB) in 209 seconds (3.48 minutes) to 75win the annual general purpose (daytona) 76< a href ="http://www.hpl.hp.com/hosted/sortbenchmark/ "> terabyte sort 77benchmark</ a > . 78 79< p > 80 81The cluster statistics were: 82< ul > 83< li > 910 nodes 84< li > 4 dual core Xeons @ 2.0ghz per a node 85< li > 4 SATA disks per a node 86< li > 8G RAM per a node 87< li > 1 gigabit ethernet on each node 88< li > 40 nodes per a rack 89< li > 8 gigabit ethernet uplinks from each rack to the core 90< li > Red Hat Enterprise Linux Server Release 5.1 (kernel 2.6.18) 91< li > Sun Java JDK 1.6.0_05-b13 92</ ul > 93 94< p > 95 96The test was on Hadoop trunk (pre-0.18) patched with< a 97href ="http://issues.apache.org/jira/browse/HADOOP-3443 "> HADOOP-3443</ a > 98and< a 99href ="http://issues.apache.org/jira/browse/HADOOP-3446 "> HADOOP-3446</ a > , 100which were required to remove intermediate writes to disk. 101TeraGen used 1021800 tasks to generate a total of 10 billion rows in HDFS, with a 103block size of 1024 MB. 104TeraSort was configured with 1800 maps and 1800 reduces, and 105< i > mapreduce.task.io.sort.mb</ i > , 106< i > mapreduce.task.io.sort.factor</ i > , 107< i > fs.inmemory.size.mb</ i > , and task heap size 108sufficient that transient data was never spilled to disk, other at the 109end of the map. The sampler looked at 100,000 keys to determine the 110reduce boundaries, which lead to imperfect balancing with reduce 111outputs ranging from 337 MB to 872 MB. 112 113</ body > 114</ html >