+/EE360P

distributed systems

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

vijaygarg1init07ca65d

master
10.8 KiB329 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 */
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 {
50  private static final Log LOG = LogFactory.getLog(TeraSort.class);
51  static String SIMPLE_PARTITIONER = "mapreduce.terasort.simplepartitioner";
52  static 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   */
58  static class TotalOrderPartitioner extends Partitioner<Text,Text>
59      implements Configurable {
60    private TrieNode trie;
61    private Text[] splitPoints;
62    private Configuration conf;
63
64    /**
65     * A generic trie node
66     */
67    static abstract class TrieNode {
68      private int level;
69      TrieNode(int level) {
70        this.level = level;
71      }
72      abstract int findPartition(Text key);
73      abstract void print(PrintStream strm) throws IOException;
74      int getLevel() {
75        return level;
76      }
77    }
78
79    /**
80     * An inner trie node that contains 256 children based on the next
81     * character.
82     */
83    static class InnerTrieNode extends TrieNode {
84      private TrieNode[] child = new TrieNode[256];
85      
86      InnerTrieNode(int level) {
87        super(level);
88      }
89      int findPartition(Text key) {
90        int level = getLevel();
91        if (key.getLength() <= level) {
92          return child[0].findPartition(key);
93        }
94        return child[key.getBytes()[level] & 0xff].findPartition(key);
95      }
96      void setChild(int idx, TrieNode child) {
97        this.child[idx] = child;
98      }
99      void print(PrintStream strm) throws IOException {
100        for(int ch=0; ch < 256; ++ch) {
101          for(int i = 0; i < 2*getLevel(); ++i) {
102            strm.print(' ');
103          }
104          strm.print(ch);
105          strm.println(" ->");
106          if (child[ch] != null) {
107            child[ch].print(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     */
117    static class LeafTrieNode extends TrieNode {
118      int lower;
119      int upper;
120      Text[] splitPoints;
121      LeafTrieNode(int level, Text[] splitPoints, int lower, int upper) {
122        super(level);
123        this.splitPoints = splitPoints;
124        this.lower = lower;
125        this.upper = upper;
126      }
127      int findPartition(Text key) {
128        for(int i=lower; i<upper; ++i) {
129          if (splitPoints[i].compareTo(key) > 0) {
130            return i;
131          }
132        }
133        return upper;
134      }
135      void print(PrintStream strm) throws IOException {
136        for(int i = 0; i < 2*getLevel(); ++i) {
137          strm.print(' ');
138        }
139        strm.print(lower);
140        strm.print(", ");
141        strm.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     */
154    private static Text[] readPartitions(FileSystem fs, Path p,
155        Configuration conf) throws IOException {
156      int reduces = conf.getInt(MRJobConfig.NUM_REDUCES, 1);
157      Text[] result = new Text[reduces - 1];
158      DataInputStream reader = fs.open(p);
159      for(int i=0; i < reduces - 1; ++i) {
160        result[i] = new Text();
161        result[i].readFields(reader);
162      }
163      reader.close();
164      return 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     */
177    private static TrieNode buildTrie(Text[] splits, int lower, int upper, 
178                                      Text prefix, int maxDepth) {
179      int depth = prefix.getLength();
180      if (depth >= maxDepth || lower == upper) {
181        return new LeafTrieNode(depth, splits, lower, upper);
182      }
183      InnerTrieNode result = new InnerTrieNode(depth);
184      Text trial = new Text(prefix);
185      // append an extra byte on to the prefix
186      trial.append(new byte[1], 0, 1);
187      int currentBound = lower;
188      for(int ch = 0; ch < 255; ++ch) {
189        trial.getBytes()[depth] = (byte) (ch + 1);
190        lower = currentBound;
191        while (currentBound < upper) {
192          if (splits[currentBound].compareTo(trial) >= 0) {
193            break;
194          }
195          currentBound += 1;
196        }
197        trial.getBytes()[depth] = (byte) ch;
198        result.child[ch] = buildTrie(splits, lower, currentBound, trial, 
199                                     maxDepth);
200      }
201      // pick up the rest
202      trial.getBytes()[depth] = (byte) 255;
203      result.child[255] = buildTrie(splits, currentBound, upper, trial,
204                                    maxDepth);
205      return result;
206    }
207
208    public void setConf(Configuration conf) {
209      try {
210        FileSystem fs = FileSystem.getLocal(conf);
211        this.conf = conf;
212        Path partFile = new Path(TeraInputFormat.PARTITION_FILENAME);
213        splitPoints = readPartitions(fs, partFile, conf);
214        trie = buildTrie(splitPoints, 0, splitPoints.length, new Text(), 2);
215      } catch (IOException ie) {
216        throw new IllegalArgumentException("can't read partitions file", ie);
217      }
218    }
219
220    public Configuration getConf() {
221      return conf;
222    }
223    
224    public TotalOrderPartitioner() {
225    }
226
227    public int getPartition(Text key, Text value, int numPartitions) {
228      return 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   */
237  public static class SimplePartitioner extends Partitioner<Text, Text>
238      implements Configurable {
239    int prefixesPerReduce;
240    private static final int PREFIX_LENGTH = 3;
241    private Configuration conf = null;
242    public void setConf(Configuration conf) {
243      this.conf = conf;
244      prefixesPerReduce = (int) Math.ceil((1 << (8 * PREFIX_LENGTH)) / 
245        (float) conf.getInt(MRJobConfig.NUM_REDUCES, 1));
246    }
247    
248    public Configuration getConf() {
249      return conf;
250    }
251    
252    @Override
253    public int getPartition(Text key, Text value, int numPartitions) {
254      byte[] bytes = key.getBytes();
255      int len = Math.min(PREFIX_LENGTH, key.getLength());
256      int prefix = 0;
257      for(int i=0; i < len; ++i) {
258        prefix = (prefix << 8) | (0xff & bytes[i]);
259      }
260      return prefix / prefixesPerReduce;
261    }
262  }
263
264  public static boolean getUseSimplePartitioner(JobContext job) {
265    return job.getConfiguration().getBoolean(SIMPLE_PARTITIONER, false);
266  }
267
268  public static void setUseSimplePartitioner(Job job, boolean value) {
269    job.getConfiguration().setBoolean(SIMPLE_PARTITIONER, value);
270  }
271
272  public static int getOutputReplication(JobContext job) {
273    return job.getConfiguration().getInt(OUTPUT_REPLICATION, 1);
274  }
275
276  public static void setOutputReplication(Job job, int value) {
277    job.getConfiguration().setInt(OUTPUT_REPLICATION, value);
278  }
279
280  public int run(String[] args) throws Exception {
281    LOG.info("starting");
282    Job job = Job.getInstance(getConf());
283    Path inputDir = new Path(args[0]);
284    Path outputDir = new Path(args[1]);
285    boolean useSimplePartitioner = getUseSimplePartitioner(job);
286    TeraInputFormat.setInputPaths(job, inputDir);
287    FileOutputFormat.setOutputPath(job, outputDir);
288    job.setJobName("TeraSort");
289    job.setJarByClass(TeraSort.class);
290    job.setOutputKeyClass(Text.class);
291    job.setOutputValueClass(Text.class);
292    job.setInputFormatClass(TeraInputFormat.class);
293    job.setOutputFormatClass(TeraOutputFormat.class);
294    if (useSimplePartitioner) {
295      job.setPartitionerClass(SimplePartitioner.class);
296    } else {
297      long start = System.currentTimeMillis();
298      Path partitionFile = new Path(outputDir, 
299                                    TeraInputFormat.PARTITION_FILENAME);
300      URI partitionUri = new URI(partitionFile.toString() +
301                                 "#" + TeraInputFormat.PARTITION_FILENAME);
302      try {
303        TeraInputFormat.writePartitionFile(job, partitionFile);
304      } catch (Throwable e) {
305        LOG.error(e.getMessage());
306        return -1;
307      }
308      job.addCacheFile(partitionUri);  
309      long end = System.currentTimeMillis();
310      System.out.println("Spent " + (end - start) + "ms computing partitions.");
311      job.setPartitionerClass(TotalOrderPartitioner.class);
312    }
313    
314    job.getConfiguration().setInt("dfs.replication", getOutputReplication(job));
315    TeraOutputFormat.setFinalSync(job, true);
316    int ret = job.waitForCompletion(true) ? 0 : 1;
317    LOG.info("done");
318    return ret;
319  }
320
321  /**
322   * @param args
323   */
324  public static void main(String[] args) throws Exception {
325    int res = ToolRunner.run(new Configuration(), new TeraSort(), args);
326    System.exit(res);
327  }
328
329}