+/EE360P

distributed systems

git clone https://git.julia.blue/+/EE360P

vijaygarg1init07ca65d

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