Partitioning

你的名字 2022-03-11 08:28 196阅读 0赞

In the [ Issue \#1][Issue _1] of [ this series][this series], we set up the “learning playground” (based on the [ Cloudera Virtual Machine][Cloudera Virtual Machine]) in order to enjoy hands-on learning experiences around Hadoop. In this issue, we’ll use our playground to investigate the partitioning features offered by Hadoop.

**What is it all about?**

As you may know, a map/reduce job will contains most of the time more than  1 reducer.  So basically, when a mapper emits a key value pair, it has to be sent to one of the reducers. Which one? The mechanism sending specific key-value pairs to specific reducers is called **partitioning** (the key-value pairs space is partitioned among the reducers). A [ Partitioner ][Partitioner]is responsible to perform the partitioning.

In Hadoop, the default partitioner is [ HashPartitioner][HashPartitioner], which hashes a record’s key to determine which partition (and thus which reducer) the record belongs in.The number of partition is then equal to the number of reduce tasks for the job.

**Why is it important?**

First, it has a direct impact on the overall performance of your job: a poorly designed partitioning function will not evenly distributes the charge over the reducers, potentially loosing all the interest of the map/reduce distributed infrastructure.

Second, it maybe sometimes necessary to control the key/value pairs partitioning over the reducers. Let’s illustrate it on a simple example. Suppose that your job’s input is a (huge) set of tokens and their number of occurrences (for instance the output of the canonical [ word count hadoop example][word count hadoop example]) and that you want to sort them by number of occurrences. Let’s also suppose that your job will be handled by 2 reducers. If you run your job without using any customized partitioner, you’ll get something like this:

[![partialSortOn2Reducers][]][partialSortOn2Reducers 1]

(Click to enlarge)

As you can see, the tokens are correctly ordered by number of occurrences on each reducer (which is what hadoop guarantees by default) but this is not what you need! You’d rather expect something like:

[![TotalSortOn2Reducers][]][TotalSortOn2Reducers 1]

(Click to enlarge)

where tokens are totally ordered over the reducers, from 1 to 30 occurrences on the first reducer and from 31 to 14620 on the second. This would happen as a result of a correct partitioning function: all the tokens having a number of occurrences inferior to N (here 30) are sent  to reducer 1 and the others are sent to reducer 2, resulting in two partitions. Since the tokens are sorted on each partition, you get the expected total order on the number of occurrences.

Below, we’ll use our playground to observe the issue happening  on real data and see how we solve it using customized partitioners.

Also, as a second example of use of customized partitioning functions, let’s cite the [original map/reduce google paper][original map_reduce google paper]: “sometimes the output keys are URLs, and we want all entries for a single host to end up in the same output. To support situations like this, the user of the MapReduce library can provide a special partitioning function. For example, using “hash(Hostname(urlkey)) mod R” as the partitioning function causes all URLs from the same host to end up in the same output”.

**Feeling the partitions in our playground**

If your playground is not yet set up, check the [ Issue \#1 of this series][Issue _1]. As an input for our job, we’ll use a tsv file containing the list of tokens and their number of occurrences extracted from ([once again][]) the full moby dick text. [ Click here][Click here] to download this input. You’ll notice that the pairs (tokens, \#occurrences) are alphanumerically sorted on tokens value.

First, we’ll use a very simple pre-processing job to transform the input data into a more convenient format to use within hadoop: the Sequence File Output Format. Sequence files are a basic file based data structure persisting the key/value pairs in a binary format and allowing you to interact more easily with basic hadoop data types (e.g [ IntWritable][IntWritable], [ LongWritable][LongWritable], etc…). Here is the simple pre-processing job:

package com.philippeadjiman.hadooptraining;
     
    import java.io.IOException;
     
    import org.apache.hadoop.fs.Path;
    import org.apache.hadoop.io.IntWritable;
    import org.apache.hadoop.io.LongWritable;
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.mapred.FileInputFormat;
    import org.apache.hadoop.mapred.FileOutputFormat;
    import org.apache.hadoop.mapred.JobClient;
    import org.apache.hadoop.mapred.JobConf;
    import org.apache.hadoop.mapred.MapReduceBase;
    import org.apache.hadoop.mapred.Mapper;
    import org.apache.hadoop.mapred.OutputCollector;
    import org.apache.hadoop.mapred.Reporter;
    import org.apache.hadoop.mapred.SequenceFileOutputFormat;
     
    public class SortDataPreprocessor { 
     
    	static class PreprocessorMapper extends MapReduceBase implements Mapper { 
     
    		private Text word = new Text();
     
    		public void map(LongWritable key, Text value,
    				OutputCollector output, Reporter reporter) throws IOException { 
    			String line = value.toString();
    			String[] tokens = line.split("t");
    			if( tokens == null || tokens.length != 2 ){ 
    				System.err.print("Problem with input line: "+line+"n");
    				return;
    			}
    			int nbOccurences = Integer.parseInt(tokens[1]);
    			word.set(tokens[0]);
    			output.collect(new IntWritable(nbOccurences),word );
    		}
    	}
     
    	public static void main(String[] args) throws IOException { 
    		JobConf conf = new JobConf(SortDataPreprocessor.class);
     
    		FileInputFormat.setInputPaths(conf, new Path(args[0]));
    		FileOutputFormat.setOutputPath(conf, new Path(args[1]));
     
    		conf.setMapperClass(PreprocessorMapper.class);
    		conf.setOutputKeyClass(IntWritable.class);
    		conf.setOutputValueClass(Text.class);
    		conf.setNumReduceTasks(0);
    		conf.setOutputFormat(SequenceFileOutputFormat.class);
    		JobClient.runJob(conf);
    	}
    }

You’ll notice that:

*  it contains only a mapper (no reducer),
 *  a basic error management is performed for potential malformed lines,
 *  the output key is the number of occurrences (as an IntWritable) and the output value is the associated token,
 *  The sequence file output format is specified using setOutputFormat(SequenceFileOutputFormat.class);

To run it, package the job using maven (see [ Issue \#1][Issue _1]), put the input file on hdfs in an input directory (let’s call it input) and execute:

hadoop jar playing-with-partitions.jar com.philippeadjiman.hadooptraining.SortDataPreprocessor /user/training/input /user/training/pre_process

This will create a directory called “pre\_process” on hdfs containing a set of pairs (\#occurrences,token), respectively of format [ IntWritable][IntWritable] and [ Text][Text], in a [ SequenceFileOutputFormat][SequenceFileOutputFormat].

Now we can, perform the sort based on this new input. Writing a job for such a task is actually trivial since this is primarily what hadoop is doing by default, so here it is:

You’ll notice that:

*  There is neither map nor reduce methods! This is because sorting is a default behavior so we don’t have to do anything (we’re just interested here to see how it’ll be partitioned),
 *  The input/output formats are specified based on the output of our pre-processing job,
 *  We explicitly set the number of reducer to 2, which is the important part here since we want to observe how the output will be partitioned (without specifying it, the output will be generated using only one reducer).

Just run it using:

hadoop jar playing-with-partitions.jar com.philippeadjiman.hadooptraining.SortExample /user/training/pre_process /user/training/output

Once completed, an output directory will be created on hdfs with two files, one for each reducer that were used. You can observe the content of the output using commands like:

hadoop fs -cat output/part-00000 | less
    hadoop fs -cat output/part-00001 | less

As you’ll see, the two outputs are sorted but do not represent a total order, as explained above. Let’s fix it.

**How to implement your own partitioning function**

So how do we create a total order out of those two reducers?

A first solution is to create our own partitionner which is as simple as implementing the [ Partitioner<K,V>][Partitioner_K_V] interface:

package com.philippeadjiman.hadooptraining;
     
    package com.philippeadjiman.hadooptraining;
     
    import org.apache.hadoop.io.IntWritable;
    import org.apache.hadoop.io.Text;
    import org.apache.hadoop.mapred.JobConf;
    import org.apache.hadoop.mapred.Partitioner;
     
    public class MyPartitioner implements Partitioner<IntWritable,Text> { 
    	@Override
    	public int getPartition(IntWritable key, Text value, int numPartitions) { 
    		/* Pretty ugly hard coded partitioning function. Don't do that in practice, it is just for the sake of understanding. */
    		int nbOccurences = key.get();
     
    		if( nbOccurences < 3 )
    			return 0;
    		else
    			return 1;
    	}
     
    	@Override
    	public void configure(JobConf arg0) { 
     
    	}
     
    }

This implementation of getPartition specifies to put all the pairs having a key (which is here the number of occurrences) being less than 3 into the first partition and the other into the second one. This is of course a pretty bad practice to hard code like that a partitioning function but this is simply for the sake of understanding.

To use this created partition just add the following line to the main method of the previous SortExample class:

conf.setPartitionerClass(MyPartitioner.class);

Why did I choose 3? Because as a side effect of the Zipf law, the number of tokens having a number of occurrences of 1 and 2 will be as much as big that all the others together! (to see a Zipf Law in action, [ check this post][once again]). So 3 was chosen just for balancing a little bit the partitions.

Re-package the code with the customized partition, remove the old output, run it again and check that our problem is solved: there is a total order over the partitions.

**How to automatically find “good” partitioning function using sampling**

Now, as I mentioned above, it is a pretty bad practice to hard code how to partition the keys. But on the other hand, how would I know automatically and in advance how to divide the partition in the general case?

Hadoop provide a nice way to approximate *a priori* a good partitioning function using an [ InputSampler][InputSampler]. For instance, a [ RandomSampler][RandomSampler], will sample the input at random to estimate what is the best way to partition. The sampler will wrote into a file called, by default, \_patition.lst describing the partition that the job will automatically use to decide which key/value pairs to send to which reducers. This mechanism has to be used in combination with a [ TotalOrderPartitioner][TotalOrderPartitioner].

Here is a code sample using such a sampler with a total order partitioner:

InputSampler.Sampler<IntWritable, Text> sampler =
    	new InputSampler.RandomSampler<IntWritable, Text>(0.1, 100);
    InputSampler.writePartitionFile(conf, sampler);
    conf.setPartitionerClass(TotalOrderPartitioner.class);

Sometimes, there are some issues with the file \_partition.lst that is not found. It always worked for me when I specified explicitly where to find the file using the [ TotalOrderPartitioner.setPartitionFile();][TotalOrderPartitioner.setPartitionFile] method. Also pay attention to invoke this method before the call to writePartitionFile. Also, note that the sampling mechanism is necessary since considering all the input to compute the partition would be inefficient for large files.

**Some remarks**

*  A customized partitioning would not have been necessary if we had only one reducer since all the key/value pairs would have ended into the same output file. It is easy to understand that such a constraint is a nonsense and that using more than one reducer is most of the time necessary, else the map/reduce concept would not be very useful…
 *  Even if we used a small dataset on the semi-distributed infrastructure of the [ cloudera virtual machine][Cloudera Virtual Machine] to observe partitioning in action and to learn how to customize it, the same concepts can be applied to a larger infrastructure. To see a very interesting use case of customized partitioning strategy for sorting purpose on a big infrastructure, check the famous [TeraByte sort on hadoop][].

**Conclusion**

Partitioning in map/reduce is a fairly simple concept but that is important to get correctly. Most of the time, the default partitioning based on an hash function can be sufficient. But as we illustrated in this Issue, you’ll need sometime to modify the default behavior and to customize your own partitioning suited for your needs.

If you have some questions, or if you have experimented other use cases of customized partitioning in your application, please comment/share. See you soon for another Issue.

[Issue _1]: http://philippeadjiman.com/blog/2009/12/07/hadoop-tutorial-part-1-setting-up-your-mapreduce-learning-playground/
[this series]: http://philippeadjiman.com/blog/the-hadoop-tutorial-series/
[Cloudera Virtual Machine]: http://www.cloudera.com/hadoop-training-virtual-machine
[Partitioner]: http://hadoop.apache.org/common/docs/current/api/org/apache/hadoop/mapreduce/Partitioner.html
[HashPartitioner]: http://hadoop.apache.org/common/docs/current/api/org/apache/hadoop/mapreduce/lib/partition/HashPartitioner.html
[word count hadoop example]: http://hadoop.apache.org/common/docs/current/mapred_tutorial.html#Example%3A+WordCount+v1.0
[partialSortOn2Reducers]: /images/20220311/96c2e1d317b746a3b1012d09cbb18819.png
[partialSortOn2Reducers 1]: http://www.philippeadjiman.com/blog/wp-content/uploads/2009/12/partialSortOn2Reducers11.jpg
[TotalSortOn2Reducers]: /images/20220311/c7824f6fb0df4199ab7f3b888c6f041b.png
[TotalSortOn2Reducers 1]: http://www.philippeadjiman.com/blog/wp-content/uploads/2009/12/TotalSortOn2Reducers1.jpg
[original map_reduce google paper]: http://labs.google.com/papers/mapreduce.html
[once again]: http://philippeadjiman.com/blog/2009/10/26/drawing-the-long-tail-of-a-zipf-law-using-gnuplot-java-and-moby-dick/
[Click here]: http://www.philippeadjiman.com/blog/wp-content/uploads/2009/12/wordcount_moby-dick1.tsv
[IntWritable]: http://hadoop.apache.org/common/docs/r0.17.0/api/org/apache/hadoop/io/IntWritable.html
[LongWritable]: http://hadoop.apache.org/common/docs/r0.17.0/api/org/apache/hadoop/io/LongWritable.html
[Text]: http://hadoop.apache.org/common/docs/r0.17.0/api/org/apache/hadoop/io/Text.html
[SequenceFileOutputFormat]: http://hadoop.apache.org/common/docs/current/api/org/apache/hadoop/mapred/SequenceFileOutputFormat.html
[Partitioner_K_V]: http://hadoop.apache.org/common/docs/r0.18.3/api/org/apache/hadoop/mapred/Partitioner.html
[InputSampler]: http://hadoop.apache.org/common/docs/current/api/org/apache/hadoop/mapred/lib/InputSampler.html
[RandomSampler]: http://hadoop.apache.org/common/docs/current/api/org/apache/hadoop/mapred/lib/InputSampler.RandomSampler.html
[TotalOrderPartitioner]: http://hadoop.apache.org/common/docs/r0.19.0/api/org/apache/hadoop/mapred/lib/TotalOrderPartitioner.html
[TotalOrderPartitioner.setPartitionFile]: http://hadoop.apache.org/common/docs/r0.19.0/api/org/apache/hadoop/mapred/lib/TotalOrderPartitioner.html#setPartitionFile%28org.apache.hadoop.mapred.JobConf,%20org.apache.hadoop.fs.Path%29
[TeraByte sort on hadoop]: http://sortbenchmark.org/YahooHadoop.pdf