+/EE360P
distributed systems
git clone https://git.julia.blue/+/EE360P
07ca65d
master
1/** 2* Licensed to the Apache Software Foundation (ASF) under one 3* or more contributor license agreements. See the NOTICE file 4* distributed with this work for additional information 5* regarding copyright ownership. The ASF licenses this file 6* to you under the Apache License, Version 2.0 (the 7* "License"); you may not use this file except in compliance 8* with the License. You may obtain a copy of the License at 9* 10* http://www.apache.org/licenses/LICENSE-2.0 11* 12* Unless required by applicable law or agreed to in writing, software 13* distributed under the License is distributed on an "AS IS" BASIS, 14* WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. 15* See the License for the specific language governing permissions and 16* limitations under the License. 17*/ 18 19package org .apache .hadoop .examples .terasort ; 20 21import java .io .DataInputStream ; 22import java .io .IOException ; 23import java .io .PrintStream ; 24import java .net .URI ; 25 26import org .apache .commons .logging .Log ; 27import org .apache .commons .logging .LogFactory ; 28import org .apache .hadoop .conf .Configurable ; 29import org .apache .hadoop .conf .Configuration ; 30import org .apache .hadoop .conf .Configured ; 31import org .apache .hadoop .fs .FileSystem ; 32import org .apache .hadoop .fs .Path ; 33import org .apache .hadoop .io .Text ; 34import org .apache .hadoop .mapreduce .Job ; 35import org .apache .hadoop .mapreduce .JobContext ; 36import org .apache .hadoop .mapreduce .MRJobConfig ; 37import org .apache .hadoop .mapreduce .Partitioner ; 38import org .apache .hadoop .mapreduce .lib .output .FileOutputFormat ; 39import org .apache .hadoop .util .Tool ; 40import org .apache .hadoop .util .ToolRunner ; 41 42/** 43* Generates the sampled split points, launches the job, and waits for it to 44* finish. 45* <p> 46* To run the program: 47* <b>bin/hadoop jar hadoop-*-examples.jar terasort in-dir out-dir</b> 48*/ 49public class TeraSort extends Configured implements Tool { 50private static final Log LOG =LogFactory .getLog (TeraSort .class ); 51static String SIMPLE_PARTITIONER ="mapreduce.terasort.simplepartitioner" ; 52static String OUTPUT_REPLICATION ="mapreduce.terasort.output.replication" ; 53 54/** 55* A partitioner that splits text keys into roughly equal partitions 56* in a global sorted order. 57*/ 58static class TotalOrderPartitioner extends Partitioner <Text ,Text > 59implements Configurable { 60private TrieNode trie ; 61private Text []splitPoints ; 62private Configuration conf ; 63 64/** 65* A generic trie node 66*/ 67static abstract class TrieNode { 68private int level ; 69TrieNode (int level ) { 70this .level =level ; 71 } 72abstract int findPartition (Text key ); 73abstract void PrintStream strm )throws IOException ; 74int getLevel () { 75return level ; 76 } 77 } 78 79/** 80* An inner trie node that contains 256 children based on the next 81* character. 82*/ 83static class InnerTrieNode extends TrieNode { 84private TrieNode []child =new TrieNode [256 ]; 85 86InnerTrieNode (int level ) { 87super (level ); 88 } 89int findPartition (Text key ) { 90int level =getLevel (); 91if (key .getLength () <=level ) { 92return child [0 ].findPartition (key ); 93 } 94return child [key .getBytes ()[level ] &0xff ].findPartition (key ); 95 } 96void setChild (int idx ,TrieNode child ) { 97this .child [idx ] =child ; 98 } 99void PrintStream strm )throws IOException { 100for (int ch =0 ;ch <256 ; ++ch ) { 101for (int i =0 ;i <2 *getLevel (); ++i ) { 102strm .' ' ); 103 } 104strm .ch ); 105strm .println (" ->" ); 106if (child [ch ] !=null ) { 107child [ch ].strm ); 108 } 109 } 110 } 111 } 112 113/** 114* A leaf trie node that does string compares to figure out where the given 115* key belongs between lower..upper. 116*/ 117static class LeafTrieNode extends TrieNode { 118int lower ; 119int upper ; 120Text []splitPoints ; 121LeafTrieNode (int level ,Text []splitPoints ,int lower ,int upper ) { 122super (level ); 123this .splitPoints =splitPoints ; 124this .lower =lower ; 125this .upper =upper ; 126 } 127int findPartition (Text key ) { 128for (int i =lower ;i <upper ; ++i ) { 129if (splitPoints [i ].compareTo (key ) >0 ) { 130return i ; 131 } 132 } 133return upper ; 134 } 135void PrintStream strm )throws IOException { 136for (int i =0 ;i <2 *getLevel (); ++i ) { 137strm .' ' ); 138 } 139strm .lower ); 140strm .", " ); 141strm .println (upper ); 142 } 143 } 144 145 146/** 147* Read the cut points from the given sequence file. 148* @param fs the file system 149* @param p the path to read 150* @param job the job config 151* @return the strings to split the partitions on 152* @throws IOException 153*/ 154private static Text []readPartitions (FileSystem fs ,Path p , 155Configuration conf )throws IOException { 156int reduces =conf .getInt (MRJobConfig .NUM_REDUCES ,1 ); 157Text []result =new Text [reduces -1 ]; 158DataInputStream reader =fs .open (p ); 159for (int i =0 ;i <reduces -1 ; ++i ) { 160result [i ] =new Text (); 161result [i ].readFields (reader ); 162 } 163reader .close (); 164return result ; 165 } 166 167/** 168* Given a sorted set of cut points, build a trie that will find the correct 169* partition quickly. 170* @param splits the list of cut points 171* @param lower the lower bound of partitions 0..numPartitions-1 172* @param upper the upper bound of partitions 0..numPartitions-1 173* @param prefix the prefix that we have already checked against 174* @param maxDepth the maximum depth we will build a trie for 175* @return the trie node that will divide the splits correctly 176*/ 177private static TrieNode buildTrie (Text []splits ,int lower ,int upper , 178Text prefix ,int maxDepth ) { 179int depth =prefix .getLength (); 180if (depth >=maxDepth ||lower ==upper ) { 181return new LeafTrieNode (depth ,splits ,lower ,upper ); 182 } 183InnerTrieNode result =new InnerTrieNode (depth ); 184Text trial =new Text (prefix ); 185// append an extra byte on to the prefix 186trial .append (new byte [1 ],0 ,1 ); 187int currentBound =lower ; 188for (int ch =0 ;ch <255 ; ++ch ) { 189trial .getBytes ()[depth ] = (byte ) (ch +1 ); 190lower =currentBound ; 191while (currentBound <upper ) { 192if (splits [currentBound ].compareTo (trial ) >=0 ) { 193break ; 194 } 195currentBound +=1 ; 196 } 197trial .getBytes ()[depth ] = (byte )ch ; 198result .child [ch ] =buildTrie (splits ,lower ,currentBound ,trial , 199maxDepth ); 200 } 201// pick up the rest 202trial .getBytes ()[depth ] = (byte )255 ; 203result .child [255 ] =buildTrie (splits ,currentBound ,upper ,trial , 204maxDepth ); 205return result ; 206 } 207 208public void setConf (Configuration conf ) { 209try { 210FileSystem fs =FileSystem .getLocal (conf ); 211this .conf =conf ; 212Path partFile =new Path (TeraInputFormat .PARTITION_FILENAME ); 213splitPoints =readPartitions (fs ,partFile ,conf ); 214trie =buildTrie (splitPoints ,0 ,splitPoints .length ,new Text (),2 ); 215 }catch (IOException ie ) { 216throw new IllegalArgumentException ("can't read partitions file" ,ie ); 217 } 218 } 219 220public Configuration getConf () { 221return conf ; 222 } 223 224public TotalOrderPartitioner () { 225 } 226 227public int getPartition (Text key ,Text value ,int numPartitions ) { 228return trie .findPartition (key ); 229 } 230 231 } 232 233/** 234* A total order partitioner that assigns keys based on their first 235* PREFIX_LENGTH bytes, assuming a flat distribution. 236*/ 237public static class SimplePartitioner extends Partitioner <Text ,Text > 238implements Configurable { 239int prefixesPerReduce ; 240private static final int PREFIX_LENGTH =3 ; 241private Configuration conf =null ; 242public void setConf (Configuration conf ) { 243this .conf =conf ; 244prefixesPerReduce = (int )Math .ceil ((1 << (8 *PREFIX_LENGTH )) / 245 (float )conf .getInt (MRJobConfig .NUM_REDUCES ,1 )); 246 } 247 248public Configuration getConf () { 249return conf ; 250 } 251 252@ Override 253public int getPartition (Text key ,Text value ,int numPartitions ) { 254byte []bytes =key .getBytes (); 255int len =Math .min (PREFIX_LENGTH ,key .getLength ()); 256int prefix =0 ; 257for (int i =0 ;i <len ; ++i ) { 258prefix = (prefix <<8 ) | (0xff &bytes [i ]); 259 } 260return prefix /prefixesPerReduce ; 261 } 262 } 263 264public static boolean getUseSimplePartitioner (JobContext job ) { 265return job .getConfiguration ().getBoolean (SIMPLE_PARTITIONER ,false ); 266 } 267 268public static void setUseSimplePartitioner (Job job ,boolean value ) { 269job .getConfiguration ().setBoolean (SIMPLE_PARTITIONER ,value ); 270 } 271 272public static int getOutputReplication (JobContext job ) { 273return job .getConfiguration ().getInt (OUTPUT_REPLICATION ,1 ); 274 } 275 276public static void setOutputReplication (Job job ,int value ) { 277job .getConfiguration ().setInt (OUTPUT_REPLICATION ,value ); 278 } 279 280public int run (String []args )throws Exception { 281LOG .info ("starting" ); 282Job job =Job .getInstance (getConf ()); 283Path inputDir =new Path (args [0 ]); 284Path outputDir =new Path (args [1 ]); 285boolean useSimplePartitioner =getUseSimplePartitioner (job ); 286TeraInputFormat .setInputPaths (job ,inputDir ); 287FileOutputFormat .setOutputPath (job ,outputDir ); 288job .setJobName ("TeraSort" ); 289job .setJarByClass (TeraSort .class ); 290job .setOutputKeyClass (Text .class ); 291job .setOutputValueClass (Text .class ); 292job .setInputFormatClass (TeraInputFormat .class ); 293job .setOutputFormatClass (TeraOutputFormat .class ); 294if (useSimplePartitioner ) { 295job .setPartitionerClass (SimplePartitioner .class ); 296 }else { 297long start =System .currentTimeMillis (); 298Path partitionFile =new Path (outputDir , 299TeraInputFormat .PARTITION_FILENAME ); 300URI partitionUri =new URI (partitionFile .toString () + 301"#" +TeraInputFormat .PARTITION_FILENAME ); 302try { 303TeraInputFormat .writePartitionFile (job ,partitionFile ); 304 }catch (Throwable e ) { 305LOG .error (e .getMessage ()); 306return -1 ; 307 } 308job .addCacheFile (partitionUri ); 309long end =System .currentTimeMillis (); 310System .out .println ("Spent " + (end -start ) +"ms computing partitions." ); 311job .setPartitionerClass (TotalOrderPartitioner .class ); 312 } 313 314job .getConfiguration ().setInt ("dfs.replication" ,getOutputReplication (job )); 315TeraOutputFormat .setFinalSync (job ,true ); 316int ret =job .waitForCompletion (true ) ?0 :1 ; 317LOG .info ("done" ); 318return ret ; 319 } 320 321/** 322* @param args 323*/ 324public static void main (String []args )throws Exception { 325int res =ToolRunner .run (new Configuration (),new TeraSort (),args ); 326System .exit (res ); 327 } 328 329}