+/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*/ 18package org .apache .hadoop .examples .pi ; 19 20import java .io .DataInput ; 21import java .io .DataOutput ; 22import java .io .File ; 23import java .io .IOException ; 24import java .io .PrintWriter ; 25import java .util .ArrayList ; 26import java .util .Arrays ; 27import java .util .List ; 28import java .util .Map ; 29import java .util .concurrent .Callable ; 30 31import org .apache .commons .logging .Log ; 32import org .apache .commons .logging .LogFactory ; 33import org .apache .hadoop .conf .Configuration ; 34import org .apache .hadoop .conf .Configured ; 35import org .apache .hadoop .examples .pi .math .Summation ; 36import org .apache .hadoop .fs .FileSystem ; 37import org .apache .hadoop .fs .Path ; 38import org .apache .hadoop .io .IntWritable ; 39import org .apache .hadoop .io .NullWritable ; 40import org .apache .hadoop .io .Writable ; 41import org .apache .hadoop .mapreduce .Cluster ; 42import org .apache .hadoop .mapreduce .ClusterMetrics ; 43import org .apache .hadoop .mapreduce .InputFormat ; 44import org .apache .hadoop .mapreduce .InputSplit ; 45import org .apache .hadoop .mapreduce .Job ; 46import org .apache .hadoop .mapreduce .JobContext ; 47import org .apache .hadoop .mapreduce .MRJobConfig ; 48import org .apache .hadoop .mapreduce .Mapper ; 49import org .apache .hadoop .mapreduce .Partitioner ; 50import org .apache .hadoop .mapreduce .RecordReader ; 51import org .apache .hadoop .mapreduce .Reducer ; 52import org .apache .hadoop .mapreduce .TaskAttemptContext ; 53import org .apache .hadoop .mapreduce .TaskInputOutputContext ; 54import org .apache .hadoop .mapreduce .lib .output .FileOutputFormat ; 55import org .apache .hadoop .net .NetUtils ; 56import org .apache .hadoop .util .Tool ; 57import org .apache .hadoop .util .ToolRunner ; 58 59/** 60* The main class for computing sums using map/reduce jobs. 61* A sum is partitioned into jobs. 62* A job may be executed on the map-side or on the reduce-side. 63* A map-side job has multiple maps and zero reducer. 64* A reduce-side job has one map and multiple reducers. 65* Depending on the clusters status in runtime, 66* a mix-type job may be executed on either side. 67*/ 68public final class DistSum extends Configured implements Tool { 69private static final Log LOG =LogFactory .getLog (DistSum .class ); 70 71private static final String NAME =DistSum .class .getSimpleName (); 72private static final String N_PARTS ="mapreduce.pi." +NAME +".nParts" ; 73///////////////////////////////////////////////////////////////////////////// 74/** DistSum job parameters */ 75static class Parameters { 76static final int COUNT =6 ; 77static final String LIST ="<nThreads> <nJobs> <type> <nPart> <remoteDir> <localDir>" ; 78static final String DESCRIPTION = 79"\n <nThreads> The number of working threads." 80 +"\n <nJobs> The number of jobs per sum." 81 +"\n <type> 'm' for map side job, 'r' for reduce side job, 'x' for mix type." 82 +"\n <nPart> The number of parts per job." 83 +"\n <remoteDir> Remote directory for submitting jobs." 84 +"\n <localDir> Local directory for storing output files." ; 85 86/** Number of worker threads */ 87final int nThreads ; 88/** Number of jobs */ 89final int nJobs ; 90/** Number of parts per job */ 91final int nParts ; 92/** The machine used in the computation */ 93final Machine machine ; 94/** The remote job directory */ 95final String remoteDir ; 96/** The local output directory */ 97final File localDir ; 98 99private Parameters (Machine machine ,int nThreads ,int nJobs ,int nParts , 100String remoteDir ,File localDir ) { 101this .machine =machine ; 102this .nThreads =nThreads ; 103this .nJobs =nJobs ; 104this .nParts =nParts ; 105this .remoteDir =remoteDir ; 106this .localDir =localDir ; 107 } 108 109/** {@inheritDoc} */ 110public String toString () { 111return "\nnThreads = " +nThreads 112 +"\nnJobs = " +nJobs 113 +"\nnParts = " +nParts +" (" +machine +")" 114 +"\nremoteDir = " +remoteDir 115 +"\nlocalDir = " +localDir ; 116 } 117 118/** Parse parameters */ 119static Parameters parse (String []args ,int i ) { 120if (args .length -i <COUNT ) 121throw new IllegalArgumentException ("args.length - i < COUNT = " 122 +COUNT +", args.length=" 123 +args .length +", i=" +i +", args=" +Arrays .asList (args )); 124 125final int nThreads =Integer .parseInt (args [i ++]); 126final int nJobs =Integer .parseInt (args [i ++]); 127final String type =args [i ++]; 128final int nParts =Integer .parseInt (args [i ++]); 129final String remoteDir =args [i ++]; 130final File localDir =new File (args [i ++]); 131 132if (!"m" .equals (type ) && !"r" .equals (type ) && !"x" .equals (type )) { 133throw new IllegalArgumentException ("type=" +type +" is not equal to m, r or x" ); 134 }else if (nParts <=0 ) { 135throw new IllegalArgumentException ("nParts = " +nParts +" <= 0" ); 136 }else if (nJobs <=0 ) { 137throw new IllegalArgumentException ("nJobs = " +nJobs +" <= 0" ); 138 }else if (nThreads <=0 ) { 139throw new IllegalArgumentException ("nThreads = " +nThreads +" <= 0" ); 140 } 141Util .checkDirectory (localDir ); 142 143return new Parameters ("m" .equals (type )?MapSide .INSTANCE 144 :"r" .equals (type )?ReduceSide .INSTANCE :MixMachine .INSTANCE , 145nThreads ,nJobs ,nParts ,remoteDir ,localDir ); 146 } 147 } 148///////////////////////////////////////////////////////////////////////////// 149/** Abstract machine for job execution. */ 150public static abstract class Machine { 151/** Initialize a job */ 152abstract void init (Job job )throws IOException ; 153 154/** {@inheritDoc} */ 155public String toString () {return getClass ().getSimpleName ();} 156 157/** Compute sigma */ 158static void compute (Summation sigma , 159TaskInputOutputContext <?, ?,NullWritable ,TaskResult >context 160 )throws IOException ,InterruptedException { 161String s ; 162LOG .info (s ="sigma=" +sigma ); 163context .setStatus (s ); 164 165final long start =System .currentTimeMillis (); 166sigma .compute (); 167final long duration =System .currentTimeMillis () -start ; 168final TaskResult result =new TaskResult (sigma ,duration ); 169 170LOG .info (s ="result=" +result ); 171context .setStatus (s ); 172context .write (NullWritable .get (),result ); 173 } 174 175/** Split for the summations */ 176public static final class SummationSplit extends InputSplit implements Writable ,Container <Summation > { 177private final static String []EMPTY = {}; 178 179private Summation sigma ; 180 181public SummationSplit () {} 182private SummationSplit (Summation sigma ) {this .sigma =sigma ;} 183/** {@inheritDoc} */ 184@ Override 185public Summation getElement () {return sigma ;} 186/** {@inheritDoc} */ 187@ Override 188public long getLength () {return 1 ;} 189/** {@inheritDoc} */ 190@ Override 191public String []getLocations () {return EMPTY ;} 192 193/** {@inheritDoc} */ 194@ Override 195public void readFields (DataInput in )throws IOException { 196sigma =SummationWritable .read (in ); 197 } 198/** {@inheritDoc} */ 199@ Override 200public void write (DataOutput out )throws IOException { 201new SummationWritable (sigma ).write (out ); 202 } 203 } 204 205/** An abstract InputFormat for the jobs */ 206public static abstract class AbstractInputFormat extends InputFormat <NullWritable ,SummationWritable > { 207/** Specify how to read the records */ 208@ Override 209public final RecordReader <NullWritable ,SummationWritable >createRecordReader ( 210InputSplit generic ,TaskAttemptContext context ) { 211final SummationSplit split = (SummationSplit )generic ; 212 213//return a record reader 214return new RecordReader <NullWritable ,SummationWritable >() { 215boolean done =false ; 216 217/** {@inheritDoc} */ 218@ Override 219public void initialize (InputSplit split ,TaskAttemptContext context ) {} 220/** {@inheritDoc} */ 221@ Override 222public boolean nextKeyValue () {return !done ?done =true :false ;} 223/** {@inheritDoc} */ 224@ Override 225public NullWritable getCurrentKey () {return NullWritable .get ();} 226/** {@inheritDoc} */ 227@ Override 228public SummationWritable getCurrentValue () {return new SummationWritable (split .getElement ());} 229/** {@inheritDoc} */ 230@ Override 231public float getProgress () {return done ?1f :0f ;} 232/** {@inheritDoc} */ 233@ Override 234public void close () {} 235 }; 236 } 237 } 238 } 239///////////////////////////////////////////////////////////////////////////// 240/** 241* A machine which does computation on the map side. 242*/ 243public static class MapSide extends Machine { 244private static final MapSide INSTANCE =new MapSide (); 245 246/** {@inheritDoc} */ 247@ Override 248public void init (Job job ) { 249// setup mapper 250job .setMapperClass (SummingMapper .class ); 251job .setMapOutputKeyClass (NullWritable .class ); 252job .setMapOutputValueClass (TaskResult .class ); 253 254// zero reducer 255job .setNumReduceTasks (0 ); 256 257// setup input 258job .setInputFormatClass (PartitionInputFormat .class ); 259 } 260 261/** An InputFormat which partitions a summation */ 262public static class PartitionInputFormat extends AbstractInputFormat { 263/** Partitions the summation into parts and then return them as splits */ 264@ Override 265public List <InputSplit >getSplits (JobContext context ) { 266//read sigma from conf 267final Configuration conf =context .getConfiguration (); 268final Summation sigma =SummationWritable .read (DistSum .class ,conf ); 269final int nParts =conf .getInt (N_PARTS ,0 ); 270 271//create splits 272final List <InputSplit >splits =new ArrayList <InputSplit >(nParts ); 273final Summation []parts =sigma .partition (nParts ); 274for (int i =0 ;i <parts .length ; ++i ) { 275splits .add (new SummationSplit (parts [i ])); 276//LOG.info("parts[" + i + "] = " + parts[i]); 277 } 278return splits ; 279 } 280 } 281 282/** A mapper which computes sums */ 283public static class SummingMapper extends 284Mapper <NullWritable ,SummationWritable ,NullWritable ,TaskResult > { 285@ Override 286protected void map (NullWritable nw ,SummationWritable sigma ,final Context context 287 )throws IOException ,InterruptedException { 288compute (sigma .getElement (),context ); 289 } 290 } 291 } 292///////////////////////////////////////////////////////////////////////////// 293/** 294* A machine which does computation on the reduce side. 295*/ 296public static class ReduceSide extends Machine { 297private static final ReduceSide INSTANCE =new ReduceSide (); 298 299/** {@inheritDoc} */ 300@ Override 301public void init (Job job ) { 302// setup mapper 303job .setMapperClass (PartitionMapper .class ); 304job .setMapOutputKeyClass (IntWritable .class ); 305job .setMapOutputValueClass (SummationWritable .class ); 306 307// setup partitioner 308job .setPartitionerClass (IndexPartitioner .class ); 309 310// setup reducer 311job .setReducerClass (SummingReducer .class ); 312job .setOutputKeyClass (NullWritable .class ); 313job .setOutputValueClass (TaskResult .class ); 314final Configuration conf =job .getConfiguration (); 315final int nParts =conf .getInt (N_PARTS ,1 ); 316job .setNumReduceTasks (nParts ); 317 318// setup input 319job .setInputFormatClass (SummationInputFormat .class ); 320 } 321 322/** An InputFormat which returns a single summation. */ 323public static class SummationInputFormat extends AbstractInputFormat { 324/** @return a list containing a single split of summation */ 325@ Override 326public List <InputSplit >getSplits (JobContext context ) { 327//read sigma from conf 328final Configuration conf =context .getConfiguration (); 329final Summation sigma =SummationWritable .read (DistSum .class ,conf ); 330 331//create splits 332final List <InputSplit >splits =new ArrayList <InputSplit >(1 ); 333splits .add (new SummationSplit (sigma )); 334return splits ; 335 } 336 } 337 338/** A Mapper which partitions a summation */ 339public static class PartitionMapper extends 340Mapper <NullWritable ,SummationWritable ,IntWritable ,SummationWritable > { 341/** Partitions sigma into parts */ 342@ Override 343protected void map (NullWritable nw ,SummationWritable sigma ,final Context context 344 )throws IOException ,InterruptedException { 345final Configuration conf =context .getConfiguration (); 346final int nParts =conf .getInt (N_PARTS ,0 ); 347final Summation []parts =sigma .getElement ().partition (nParts ); 348for (int i =0 ;i <parts .length ; ++i ) { 349context .write (new IntWritable (i ),new SummationWritable (parts [i ])); 350LOG .info ("parts[" +i +"] = " +parts [i ]); 351 } 352 } 353 } 354 355/** Use the index for partitioning. */ 356public static class IndexPartitioner extends Partitioner <IntWritable ,SummationWritable > { 357/** Return the index as the partition. */ 358@ Override 359public int getPartition (IntWritable index ,SummationWritable value ,int numPartitions ) { 360return index .get (); 361 } 362 } 363 364/** A Reducer which computes sums */ 365public static class SummingReducer extends 366Reducer <IntWritable ,SummationWritable ,NullWritable ,TaskResult > { 367@ Override 368protected void reduce (IntWritable index ,Iterable <SummationWritable >sums , 369Context context )throws IOException ,InterruptedException { 370LOG .info ("index=" +index ); 371for (SummationWritable sigma :sums ) 372compute (sigma .getElement (),context ); 373 } 374 } 375 } 376///////////////////////////////////////////////////////////////////////////// 377/** 378* A machine which chooses Machine in runtime according to the cluster status 379*/ 380public static class MixMachine extends Machine { 381private static final MixMachine INSTANCE =new MixMachine (); 382 383private Cluster cluster ; 384 385/** {@inheritDoc} */ 386@ Override 387public synchronized void init (Job job )throws IOException { 388final Configuration conf =job .getConfiguration (); 389if (cluster ==null ) { 390String jobTrackerStr =conf .get ("mapreduce.jobtracker.address" ,"localhost:8012" ); 391cluster =new Cluster (NetUtils .createSocketAddr (jobTrackerStr ),conf ); 392 393 } 394chooseMachine (conf ).init (job ); 395 } 396 397/** 398* Choose a Machine in runtime according to the cluster status. 399*/ 400private Machine chooseMachine (Configuration conf )throws IOException { 401final int parts =conf .getInt (N_PARTS ,Integer .MAX_VALUE ); 402try { 403for (;;Thread .sleep (2000 )) { 404//get cluster status 405final ClusterMetrics status =cluster .getClusterStatus (); 406final int m = 407status .getMapSlotCapacity () -status .getOccupiedMapSlots (); 408final int r = 409status .getReduceSlotCapacity () -status .getOccupiedReduceSlots (); 410if (m >=parts ||r >=parts ) { 411//favor ReduceSide machine 412final Machine value =r >=parts ? 413ReduceSide .INSTANCE :MapSide .INSTANCE ; 414Util .out .println (" " +this +" is " +value +" (m=" +m +", r=" +r +")" ); 415return value ; 416 } 417 } 418 }catch (InterruptedException e ) { 419throw new IOException (e ); 420 } 421 } 422 423 } 424///////////////////////////////////////////////////////////////////////////// 425private final Util .Timer timer =new Util .Timer (true ); 426private Parameters parameters ; 427 428/** Get Parameters */ 429Parameters getParameters () {return parameters ;} 430/** Set Parameters */ 431void setParameters (Parameters p ) {parameters =p ;} 432 433/** Create a job */ 434private Job createJob (String name ,Summation sigma )throws IOException { 435final Job job =Job .getInstance (getConf (),parameters .remoteDir +"/" + 436name ); 437final Configuration jobconf =job .getConfiguration (); 438job .setJarByClass (DistSum .class ); 439jobconf .setInt (N_PARTS ,parameters .nParts ); 440SummationWritable .write (sigma ,DistSum .class ,jobconf ); 441 442// disable task timeout 443jobconf .setLong (MRJobConfig .TASK_TIMEOUT ,0 ); 444// do not use speculative execution 445jobconf .setBoolean (MRJobConfig .MAP_SPECULATIVE ,false ); 446jobconf .setBoolean (MRJobConfig .REDUCE_SPECULATIVE ,false ); 447 448return job ; 449 } 450 451/** Start a job to compute sigma */ 452private void compute (final String name ,Summation sigma )throws IOException { 453if (sigma .getValue () !=null ) 454throw new IOException ("sigma.getValue() != null, sigma=" +sigma ); 455 456//setup remote directory 457final FileSystem fs =FileSystem .get (getConf ()); 458final Path dir =fs .makeQualified (new Path (parameters .remoteDir ,name )); 459if (!Util .createNonexistingDirectory (fs ,dir )) 460return ; 461 462//setup a job 463final Job job =createJob (name ,sigma ); 464final Path outdir =new Path (dir ,"out" ); 465FileOutputFormat .setOutputPath (job ,outdir ); 466 467//start a map/reduce job 468final String startmessage ="steps/parts = " 469 +sigma .E .getSteps () +"/" +parameters .nParts 470 +" = " +Util .long2string (sigma .E .getSteps ()/parameters .nParts ); 471Util .runJob (name ,job ,parameters .machine ,startmessage ,timer ); 472final List <TaskResult >results =Util .readJobOutputs (fs ,outdir ); 473Util .writeResults (name ,results ,fs ,parameters .remoteDir ); 474fs .delete (dir ,true ); 475 476//combine results 477final List <TaskResult >combined =Util .combine (results ); 478final PrintWriter out =Util .createWriter (parameters .localDir ,name ); 479try { 480for (TaskResult r :combined ) { 481final String s =taskResult2string (name ,r ); 482out .println (s ); 483out .flush (); 484Util .out .println (s ); 485 } 486 }finally { 487out .close (); 488 } 489if (combined .size () ==1 ) { 490final Summation s =combined .get (0 ).getElement (); 491if (sigma .contains (s ) &&s .contains (sigma )) 492sigma .setValue (s .getValue ()); 493 } 494 } 495 496/** Convert a TaskResult to a String */ 497public static String taskResult2string (String name ,TaskResult result ) { 498return NAME +" " +name +"> " +result ; 499 } 500 501/** Convert a String to a (String, TaskResult) pair */ 502public static Map .Entry <String ,TaskResult >string2TaskResult (final String s ) { 503// LOG.info("line = " + line); 504int j =s .indexOf (NAME ); 505if (j ==0 ) { 506int i =j +NAME .length () +1 ; 507j =s .indexOf ("> " ,i ); 508final String key =s .substring (i ,j ); 509final TaskResult value =TaskResult .valueOf (s .substring (j +2 )); 510return new Map .Entry <String ,TaskResult >(){ 511@ Override 512public String getKey () {return key ;} 513@ Override 514public TaskResult getValue () {return value ;} 515@ Override 516public TaskResult setValue (TaskResult value ) { 517throw new UnsupportedOperationException (); 518 } 519 }; 520 } 521return null ; 522 } 523 524/** Callable computation */ 525class Computation implements Callable <Computation > { 526private final int index ; 527private final String name ; 528private final Summation sigma ; 529 530Computation (int index ,String name ,Summation sigma ) { 531this .index =index ; 532this .name =name ; 533this .sigma =sigma ; 534 } 535 536/** @return The job name */ 537String getJobName () {return String .format ("%s.job%03d" ,name ,index );} 538 539/** {@inheritDoc} */ 540@ Override 541public String toString () {return getJobName () +sigma ;} 542 543/** Start the computation */ 544@ Override 545public Computation call () { 546if (sigma .getValue () ==null ) 547try { 548compute (getJobName (),sigma ); 549 }catch (Exception e ) { 550Util .out .println ("ERROR: Got an exception from " +getJobName ()); 551e .printStackTrace (Util .out ); 552 } 553return this ; 554 } 555 } 556 557/** Partition sigma and execute the computations. */ 558private Summation execute (String name ,Summation sigma ) { 559final Summation []summations =sigma .partition (parameters .nJobs ); 560final List <Computation >computations =new ArrayList <Computation >(); 561for (int i =0 ;i <summations .length ;i ++) 562computations .add (new Computation (i ,name ,summations [i ])); 563try { 564Util .execute (parameters .nThreads ,computations ); 565 }catch (Exception e ) { 566throw new RuntimeException (e ); 567 } 568 569final List <Summation >combined =Util .combine (Arrays .asList (summations )); 570return combined .size () ==1 ?combined .get (0 ):null ; 571 } 572 573/** {@inheritDoc} */ 574@ Override 575public int run (String []args )throws Exception { 576//parse arguments 577if (args .length !=Parameters .COUNT +2 ) 578return Util .printUsage (args ,getClass ().getName () 579 +" <name> <sigma> " +Parameters .LIST 580 +"\n <name> The name." 581 +"\n <sigma> The summation." 582 +Parameters .DESCRIPTION ); 583 584int i =0 ; 585final String name =args [i ++]; 586final Summation sigma =Summation .valueOf (args [i ++]); 587setParameters (DistSum .Parameters .parse (args ,i )); 588 589Util .out .println (); 590Util .out .println ("name = " +name ); 591Util .out .println ("sigma = " +sigma ); 592Util .out .println (parameters ); 593Util .out .println (); 594 595//run jobs 596final Summation result =execute (name ,sigma ); 597if (result .equals (sigma )) { 598sigma .setValue (result .getValue ()); 599timer .tick ("\n\nDONE\n\nsigma=" +sigma ); 600return 0 ; 601 }else { 602timer .tick ("\n\nDONE WITH ERROR\n\nresult=" +result ); 603return 1 ; 604 } 605 } 606 607/** main */ 608public static void main (String []args )throws Exception { 609System .exit (ToolRunner .run (null ,new DistSum (),args )); 610 } 611}