map-reduce中的分治思想

01-29

map-reduce 是一種並行的大規模數據計算框架，它的基礎數據結構是<k,v>對，核心思想是分治演算法，只不過在「分」的時候，不僅考慮減小數據規模，更充分了考慮數據之間的耦合關係，將具有強耦合關係的數據劃分到同一組中，低耦合或者不耦合的數據劃分到不同的分組中，然後各個分組並行計算，最後輸出最終的結果過。在map 階段，會將具有強耦合計算關係的數據映射到具有相同key的<k,v>對中，並分發到同一個節點上，在reduce階段，對節點上具有相同key的<k,v>對中的value至執行特定的操作，生成新的v-New, 最終輸出數據<k, v-new>。

map-reduce在"分"的時候，不僅減小了每個子結構的數據規模，更重要的是通過對沒有計算關係的數據解耦，降低了各個子結構的計算複雜性，也就是降低了"治"的成本。

計算的基本流程如下：

input => map=> <k1, v1> => reduce => <k2, v2> => output

以word cnt為例，如下圖所示

實際上，map-reduce作為一種分散式計算框架，定義了一個對數據先通過map進行分割，然後通過reduce進行特定操作的數據處理流程，框架的應用者可以通過實現介面中的map和reduce方法來決定以什麼樣的策略分割數據，以及以什麼樣的策略處理數據。下面是wordcnt的實現示例：

import java.io.IOException;nimport java.util.*;nnimport org.apache.hadoop.fs.Path;nimport org.apache.hadoop.io.*;nimport org.apache.hadoop.mapred.*;nnpublic class WordCount {n public static class Map extends MapReduceBase implements Mapper<LongWritable, Text, Text, IntWritable> {n private final static IntWritable one = new IntWritable(1);n private Text word = new Text();nn public void map(LongWritable key, Text value, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {n String line = value.toString();n StringTokenizer tokenizer = new StringTokenizer(line);n while (tokenizer.hasMoreTokens()) {n word.set(tokenizer.nextToken());n output.collect(word, one);n }n }n }nn public static class Reduce extends MapReduceBase implements Reducer<Text, IntWritable, Text, IntWritable> {n public void reduce(Text key, Iterator<IntWritable> values, OutputCollector<Text, IntWritable> output, Reporter reporter) throws IOException {n int sum = 0;n while (values.hasNext()) {n sum += values.next().get();n }n output.collect(key, new IntWritable(sum));n }n }nn public static void main(String[] args) throws Exception {n JobConf conf = new JobConf(WordCount.class);n conf.setJobName("wordcount");nn conf.setOutputKeyClass(Text.class);n conf.setOutputValueClass(IntWritable.class);nn conf.setMapperClass(Map.class);n conf.setCombinerClass(Reduce.class);n conf.setReducerClass(Reduce.class);nn conf.setInputFormat(TextInputFormat.class);n conf.setOutputFormat(TextOutputFormat.class);nn FileInputFormat.setInputPaths(conf, new Path(args[0]));n FileOutputFormat.setOutputPath(conf, new Path(args[1]));nn JobClient.runJob(conf);n }n}n

map函數將文本中的每行按照word進行切分，每個word映射為<word, one>的k-v對，計算框架對map映射函數輸出的數據進行分發，具有同一個key的k-v對被分發到相同的reduce節點上，然後由reduce函數對每個word進行計數，輸出最終的結果；

main函數顯示了系統如何執行map-reduce程序，JobConf定義了程序運行的相關參數和環境，如job名字，輸入數據的類型，map函數，reduce函數，以及輸入輸出路徑，然後通過jobclient調用任務執行程序，開始執行任務；

map-reudce 任務執行的過程中，hadoop框架會對該任務進行監控，輸出相關的日誌，比如任務執行的階段，完成的比例等。

總之，map-reduce作為一種流行的分散式大規模數據計算框架，充分利用了分治思想，對數據進行切分解耦，分發到系統的各個節點上並行處理，合併處理結果，生成最終需要的輸出數據。分散式系統的每個節點通常既有計算能力，又有存儲能力，所以通常與分散式文件系統共生，如大數據處理中流行的hadoop是包含分散式計算框架和分散式存儲框架的一套大數據處理框架，感興趣的同學可以自行進一步深入了解。