+/EE360P

distributed systems

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

vijaygarg1init07ca65d

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