+/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 .DataOutputStream ; 22import java .io .EOFException ; 23import java .io .IOException ; 24import java .util .ArrayList ; 25import java .util .List ; 26 27import org .apache .hadoop .conf .Configuration ; 28import org .apache .hadoop .fs .FSDataInputStream ; 29import org .apache .hadoop .fs .FileSystem ; 30import org .apache .hadoop .fs .Path ; 31import org .apache .hadoop .io .Text ; 32import org .apache .hadoop .mapreduce .InputSplit ; 33import org .apache .hadoop .mapreduce .JobContext ; 34import org .apache .hadoop .mapreduce .MRJobConfig ; 35import org .apache .hadoop .mapreduce .RecordReader ; 36import org .apache .hadoop .mapreduce .TaskAttemptContext ; 37import org .apache .hadoop .mapreduce .TaskAttemptID ; 38import org .apache .hadoop .mapreduce .lib .input .FileInputFormat ; 39import org .apache .hadoop .mapreduce .lib .input .FileSplit ; 40import org .apache .hadoop .mapreduce .task .TaskAttemptContextImpl ; 41import org .apache .hadoop .util .IndexedSortable ; 42import org .apache .hadoop .util .QuickSort ; 43import org .apache .hadoop .util .StringUtils ; 44 45/** 46* An input format that reads the first 10 characters of each line as the key 47* and the rest of the line as the value. Both key and value are represented 48* as Text. 49*/ 50public class TeraInputFormat extends FileInputFormat <Text ,Text > { 51 52static final String PARTITION_FILENAME ="_partition.lst" ; 53private static final String NUM_PARTITIONS = 54"mapreduce.terasort.num.partitions" ; 55private static final String SAMPLE_SIZE = 56"mapreduce.terasort.partitions.sample" ; 57static final int KEY_LENGTH =10 ; 58static final int VALUE_LENGTH =90 ; 59static final int RECORD_LENGTH =KEY_LENGTH +VALUE_LENGTH ; 60private static MRJobConfig lastContext =null ; 61private static List <InputSplit >lastResult =null ; 62 63static class TextSampler implements IndexedSortable { 64private ArrayList <Text >records =new ArrayList <Text >(); 65 66public int compare (int i ,int j ) { 67Text left =records .get (i ); 68Text right =records .get (j ); 69return left .compareTo (right ); 70 } 71 72public void swap (int i ,int j ) { 73Text left =records .get (i ); 74Text right =records .get (j ); 75records .set (j ,left ); 76records .set (i ,right ); 77 } 78 79public void addKey (Text key ) { 80synchronized (this ) { 81records .add (new Text (key )); 82 } 83 } 84 85/** 86* Find the split points for a given sample. The sample keys are sorted 87* and down sampled to find even split points for the partitions. The 88* returned keys should be the start of their respective partitions. 89* @param numPartitions the desired number of partitions 90* @return an array of size numPartitions - 1 that holds the split points 91*/ 92Text []createPartitions (int numPartitions ) { 93int numRecords =records .size (); 94System .out .println ("Making " +numPartitions +" from " +numRecords + 95" sampled records" ); 96if (numPartitions >numRecords ) { 97throw new IllegalArgumentException 98 ("Requested more partitions than input keys (" +numPartitions + 99" > " +numRecords +")" ); 100 } 101new QuickSort ().sort (this ,0 ,records .size ()); 102float stepSize =numRecords / (float )numPartitions ; 103Text []result =new Text [numPartitions -1 ]; 104for (int i =1 ;i <numPartitions ; ++i ) { 105result [i -1 ] =records .get (Math .round (stepSize *i )); 106 } 107return result ; 108 } 109 } 110 111/** 112* Use the input splits to take samples of the input and generate sample 113* keys. By default reads 100,000 keys from 10 locations in the input, sorts 114* them and picks N-1 keys to generate N equally sized partitions. 115* @param job the job to sample 116* @param partFile where to write the output file to 117* @throws Throwable if something goes wrong 118*/ 119public static void writePartitionFile (final JobContext job , 120Path partFile )throws Throwable { 121long t1 =System .currentTimeMillis (); 122Configuration conf =job .getConfiguration (); 123final TeraInputFormat inFormat =new TeraInputFormat (); 124final TextSampler sampler =new TextSampler (); 125int partitions =job .getNumReduceTasks (); 126long sampleSize =conf .getLong (SAMPLE_SIZE ,100000 ); 127final List <InputSplit >splits =inFormat .getSplits (job ); 128long t2 =System .currentTimeMillis (); 129System .out .println ("Computing input splits took " + (t2 -t1 ) +"ms" ); 130int samples =Math .min (conf .getInt (NUM_PARTITIONS ,10 ),splits .size ()); 131System .out .println ("Sampling " +samples +" splits of " +splits .size ()); 132final long recordsPerSample =sampleSize /samples ; 133final int sampleStep =splits .size () /samples ; 134Thread []samplerReader =new Thread [samples ]; 135SamplerThreadGroup threadGroup =new SamplerThreadGroup ("Sampler Reader Thread Group" ); 136// take N samples from different parts of the input 137for (int i =0 ;i <samples ; ++i ) { 138final int idx =i ; 139samplerReader [i ] = 140new Thread (threadGroup ,"Sampler Reader " +idx ) { 141 { 142setDaemon (true ); 143 } 144public void run () { 145long records =0 ; 146try { 147TaskAttemptContext context =new TaskAttemptContextImpl ( 148job .getConfiguration (),new TaskAttemptID ()); 149RecordReader <Text ,Text >reader = 150inFormat .createRecordReader (splits .get (sampleStep *idx ), 151context ); 152reader .initialize (splits .get (sampleStep *idx ),context ); 153while (reader .nextKeyValue ()) { 154sampler .addKey (new Text (reader .getCurrentKey ())); 155records +=1 ; 156if (recordsPerSample <=records ) { 157break ; 158 } 159 } 160 }catch (IOException ie ){ 161System .err .println ("Got an exception while reading splits " + 162StringUtils .stringifyException (ie )); 163throw new RuntimeException (ie ); 164 }catch (InterruptedException e ) { 165 166 } 167 } 168 }; 169samplerReader [i ].start (); 170 } 171FileSystem outFs =partFile .getFileSystem (conf ); 172DataOutputStream writer =outFs .create (partFile ,true ,64 *1024 , (short )10 , 173outFs .getDefaultBlockSize (partFile )); 174for (int i =0 ;i <samples ;i ++) { 175try { 176samplerReader [i ].join (); 177if (threadGroup .getThrowable () !=null ){ 178throw threadGroup .getThrowable (); 179 } 180 }catch (InterruptedException e ) { 181 } 182 } 183for (Text split :sampler .createPartitions (partitions )) { 184split .write (writer ); 185 } 186writer .close (); 187long t3 =System .currentTimeMillis (); 188System .out .println ("Computing parititions took " + (t3 -t2 ) +"ms" ); 189 } 190 191static class SamplerThreadGroup extends ThreadGroup { 192 193private Throwable throwable ; 194 195public SamplerThreadGroup (String s ) { 196super (s ); 197 } 198 199@ Override 200public void uncaughtException (Thread thread ,Throwable throwable ) { 201this .throwable =throwable ; 202 } 203 204public Throwable getThrowable () { 205return this .throwable ; 206 } 207 208 } 209 210static class TeraRecordReader extends RecordReader <Text ,Text > { 211private FSDataInputStream in ; 212private long offset ; 213private long length ; 214private static final int RECORD_LENGTH =KEY_LENGTH +VALUE_LENGTH ; 215private byte []buffer =new byte [RECORD_LENGTH ]; 216private Text key ; 217private Text value ; 218 219public TeraRecordReader ()throws IOException { 220 } 221 222public void initialize (InputSplit split ,TaskAttemptContext context ) 223throws IOException ,InterruptedException { 224Path p = ((FileSplit )split ).getPath (); 225FileSystem fs =p .getFileSystem (context .getConfiguration ()); 226in =fs .open (p ); 227long start = ((FileSplit )split ).getStart (); 228// find the offset to start at a record boundary 229offset = (RECORD_LENGTH - (start %RECORD_LENGTH )) %RECORD_LENGTH ; 230in .seek (start +offset ); 231length = ((FileSplit )split ).getLength (); 232 } 233 234public void close ()throws IOException { 235in .close (); 236 } 237 238public Text getCurrentKey () { 239return key ; 240 } 241 242public Text getCurrentValue () { 243return value ; 244 } 245 246public float getProgress ()throws IOException { 247return (float )offset /length ; 248 } 249 250public boolean nextKeyValue ()throws IOException { 251if (offset >=length ) { 252return false ; 253 } 254int read =0 ; 255while (read <RECORD_LENGTH ) { 256long newRead =in .read (buffer ,read ,RECORD_LENGTH -read ); 257if (newRead == -1 ) { 258if (read ==0 ) { 259return false ; 260 }else { 261throw new EOFException ("read past eof" ); 262 } 263 } 264read +=newRead ; 265 } 266if (key ==null ) { 267key =new Text (); 268 } 269if (value ==null ) { 270value =new Text (); 271 } 272key .set (buffer ,0 ,KEY_LENGTH ); 273value .set (buffer ,KEY_LENGTH ,VALUE_LENGTH ); 274offset +=RECORD_LENGTH ; 275return true ; 276 } 277 } 278 279@ Override 280public RecordReader <Text ,Text > 281createRecordReader (InputSplit split ,TaskAttemptContext context ) 282throws IOException { 283return new TeraRecordReader (); 284 } 285 286@ Override 287public List <InputSplit >getSplits (JobContext job )throws IOException { 288if (job ==lastContext ) { 289return lastResult ; 290 } 291long t1 ,t2 ,t3 ; 292t1 =System .currentTimeMillis (); 293lastContext =job ; 294lastResult =super .getSplits (job ); 295t2 =System .currentTimeMillis (); 296System .out .println ("Spent " + (t2 -t1 ) +"ms computing base-splits." ); 297if (job .getConfiguration ().getBoolean (TeraScheduler .USE ,true )) { 298TeraScheduler scheduler =new TeraScheduler ( 299lastResult .toArray (new FileSplit [0 ]),job .getConfiguration ()); 300lastResult =scheduler .getNewFileSplits (); 301t3 =System .currentTimeMillis (); 302System .out .println ("Spent " + (t3 -t2 ) +"ms computing TeraScheduler splits." ); 303 } 304return lastResult ; 305 } 306}