|
1：shuffle階段的排序（部分排序） shuffle階段的排序可以理解成兩部分，一個是對spill進(jìn)行分區(qū)時，由于一個分區(qū)包含多個key值，所以要對分區(qū)內(nèi)的<key,value>按照key進(jìn)行排序，即key值相同的一串<key,value>存放在一起，這樣一個partition內(nèi)按照key值整體有序了。 第二部分并不是排序，而是進(jìn)行merge，merge有兩次，一次是map端將多個spill 按照分區(qū)和分區(qū)內(nèi)的key進(jìn)行merge，形成一個大的文件。第二次merge是在reduce端，進(jìn)入同一個reduce的多個map的輸出 merge在一起，該merge理解起來有點復(fù)雜，最終不是形成一個大文件，而且期間數(shù)據(jù)在內(nèi)存和磁盤上都有，關(guān)于這點金子準(zhǔn)備日后單獨(dú)整理一下。 所以shuffle階段的merge并不是嚴(yán)格的排序意義，只是將多個整體有序的文件merge成一個大的文件，由于同的task執(zhí)行，map的輸出會有所不同，所以merge后的結(jié)果不是每次都相同，不過還是嚴(yán)格要求按照分區(qū)劃分，同時每個分區(qū)內(nèi)的具有相同key的<key,value>對挨在一起。
shuffle排序綜述：如果只定義了map函數(shù)，沒有定義reduce函數(shù)，那么輸入數(shù)據(jù)經(jīng)過shuffle的排序后，結(jié)果為key值相同的輸出挨在一起，且key值小的一定在前面，這樣整體來看key值有序（宏觀意義的，不一定是按從大到小，因為如果采用默認(rèn)的HashPartitioner，則key 的hash值相等的在一個分區(qū)，如果key為IntWritable的話，每個分區(qū)內(nèi)的key會排序好的），而每個key對應(yīng)的value不是有序的。 應(yīng)用一：金子理解：shuffle的排序隨不能滿足全局排序，但是實際中還是幫助我們做了很多工作，比如我們只希望把<key,value>對按照key值，將相同key的<key,value>對輸出到一起，這樣shuffle排序就可以滿足了，也就不需要reduce函數(shù)，只單獨(dú)指定map函數(shù)就OK啦！ 應(yīng)用二：基于分區(qū)的MapFile查找技術(shù)。（我沒仔細(xì)看）
2：全排序 對于全排序，金子深有體會，借助于hadoop的Terasort，我曾經(jīng)寫了整數(shù)和字符串的全排序，其中代碼重疊率很高，只注意改改輸入格式什么的就OK了。要進(jìn)行全局排序，首先要理解分區(qū)的概念，并且要使用TotalOrderpartition（因為默認(rèn)的partition是hashpartition，不適用于全局排序）。主要思路就是將數(shù)據(jù)按照區(qū)間進(jìn)行分割，比如對整數(shù)排序，［0，10000］的在partiiton 0中，（10000，20000］在partition 1中。。。這樣排序后面的partition中的數(shù)據(jù)肯定比排在前面的partition中的數(shù)要大，宏觀上看是有序的，然后在對每個分區(qū)中的數(shù)據(jù)進(jìn)行排序，由于這時分區(qū)中數(shù)據(jù)量已經(jīng)比較小了，在進(jìn)行排序就容易的多了。在數(shù)據(jù)分布均勻的情況下，每個分區(qū)內(nèi)的數(shù)據(jù)量基本相同，這種就是比較理想的情況了，但是實際中數(shù)據(jù)往往分布不均勻，出現(xiàn)了數(shù)據(jù)傾斜的情況，這時按照之前的分區(qū)劃分?jǐn)?shù)據(jù)就不合適了，此時就需要一個東西的幫助——采樣器。采樣的核心思想是只查看一小部分鍵，獲得鍵的近似分布，并由此鍵分區(qū)。關(guān)于采樣器的一些使用細(xì)節(jié)，可以查看我的另一篇博客：Hadoop 中的采樣器－不一樣的視角 Hadoop中的采樣器——不一樣的視角 典型應(yīng)用：TeraSort
3：二次排序 也稱作輔助排序，MapReduce框架在把記錄到達(dá)reducers之前會將記錄按照鍵排序。對于任意一個特殊的鍵，然而，值是不排序的。甚至是，值在兩次執(zhí)行中的順序是不一樣的，原因是它們是從不同的map中來的，這些不同的map可能在不同的執(zhí)行過程中結(jié)束的先后順序不確定。通常情況下，大多數(shù)的MapReduce程序的reduce函數(shù)不會依賴于值的順序。然而，我們也可通過以一種特殊的方式排序和分組鍵，來指定值的順序。 二次排序金子并沒有使用過，不過在join連接操作中，輸入到一個reduce中的value<list>是來自兩個表的，如果進(jìn)行排序，將第一個表的放在前面，第二個表的放在后面，這樣就只需要將表1存放到ArrayList中，表二不需要，然后進(jìn)行全連接就搞定啦，這樣是很多關(guān)于并行數(shù)據(jù)庫的論文中對join操作的一個明顯優(yōu)化。 看到一篇寫的很好的分析二次排序的博客：http://blog.sina.com.cn/s/blog_70324d8d0100wa63.html，講的是日志分析中二次排序是怎么應(yīng)用的。要寫二次排序，則需要非常熟悉Jobconf的幾個函數(shù)，以及各自相關(guān)的類：
A：setOutputKeyComparatorClass ：參數(shù)為繼承RawComparator的子類public void setOutputKeyComparatorClass(Class<? extends RawComparator> theClass)
RawComparator接口：繼承自Comparator ，就是一個比較器，直接在代表對象特征的字節(jié)上進(jìn)行操作。經(jīng)常使用的其實現(xiàn)的類有：DoubleWritable.Comparator, FloatWritable.Comparator, IntWritable.Comparator, LongWritable.Comparator, NullWritable.Comparator, SecondarySort.FirstGroupingComparator, SecondarySort.IntPair.Comparator,Text.Comparator,WritableComparator
自定義的類要實現(xiàn)compare函數(shù)。以上這部分的代碼就是對組合鍵中的key進(jìn)行排序的意思。 很多的二次排序例子中就利用繼承WritableComparator來實現(xiàn)根據(jù)組合鍵進(jìn)行排序。即將compare中的兩個參數(shù)轉(zhuǎn)換為組合鍵，組合鍵中的自然鍵不同時按照自然鍵排序，自然鍵相同時按照自然值排序。可參見《權(quán)威指南》中p243的代碼。
B：setPartitionerClass:用于指定用于分區(qū)的類，參數(shù)我繼承Partitioner的類
public void setPartitionerClass(Class<? extends Partitioner> theClass)
二次排序中由于map的輸出key為組合鍵IntPair，所以自定義的分區(qū)類要繼承Partitioner，同時函數(shù)getPartition 的返回值要根據(jù)組合鍵中的自然鍵，即key.first進(jìn)行判斷，例如return Math.abs(key.getFirst()*127)% numpartitions; 返回值相同的就被分配到一個分區(qū)中了。這樣一個分區(qū)中有多個不同的自然鍵，但是reduce的輸入要滿足對于非組合鍵，就是單純的一個自然鍵時，輸入是 <key, value<list>>的形式，而現(xiàn)在全部都是<IntPair ,value><IntPair,value>....的形式，我們要將自然鍵相同的value放到一起，形成一個list，要怎么辦呢，就要進(jìn)行分組啦?。?！分組也同樣要用comparator，見下面C哦～
C：setOutputValueGroupingComparator：指定用戶自定義的comparator，用于將reduce的輸入進(jìn)行分組，二次排序中可以理解為將自然鍵key相同的放到一起，相同key的value放到一個value迭代器里。
public void setOutputValueGroupingComparator(Class<? extends RawComparator> theClass)
二次排序工作原理綜述：（轉(zhuǎn)自：http://p-x1984./blog/800269）
在map階段，使用job.setInputFormatClass定義的InputFormat將輸入的數(shù)據(jù)集分割成小數(shù)據(jù)塊splites，同時InputFormat提供一個RecordReder的實現(xiàn)。Hadoop自帶的例子SecondrySort使用TextInputFormat，他提供的RecordReder會將文本的一行的行號作為key，這一行的文本作為value。這就是自定義Map的輸入是<LongWritable,
Text>的原因。然后調(diào)用自定義Map的map方法，將一個個<LongWritable, Text>對輸入給Map的map方法。注意輸出應(yīng)該符合自定義Map中定義的輸出<IntPair, IntWritable>。最終是生成一個List<IntPair, IntWritable>。在map階段的最后，會先調(diào)用job.setPartitionerClass對這個List進(jìn)行分區(qū)，每個分區(qū)映射到一個reducer。每個分區(qū)內(nèi)又調(diào)用job.setSortComparatorClass設(shè)置的key比較函數(shù)類排序。可以看到，這本身就是一個二次排序。如果沒有通過job.setSortComparatorClass設(shè)置key比較函數(shù)類，則使用key的實現(xiàn)的compareTo方法。在第一個例子中，使用了IntPair實現(xiàn)的compareTo方法，而在下一個例子中，專門定義了key比較函數(shù)類。
二次排序應(yīng)用： 日志分析（轉(zhuǎn)自：）
1：shuffle階段的排序（部分排序） shuffle階段的排序可以理解成兩部分，一個是對spill進(jìn)行分區(qū)時，由于一個分區(qū)包含多個key值，所以要對分區(qū)內(nèi)的<key,value>按照key進(jìn)行排序，即key值相同的一串<key,value>存放在一起，這樣一個partition內(nèi)按照key值整體有序了。 第二部分并不是排序，而是進(jìn)行merge，merge有兩次，一次是map端將多個spill 按照分區(qū)和分區(qū)內(nèi)的key進(jìn)行merge，形成一個大的文件。第二次merge是在reduce端，進(jìn)入同一個reduce的多個map的輸出 merge在一起，該merge理解起來有點復(fù)雜，最終不是形成一個大文件，而且期間數(shù)據(jù)在內(nèi)存和磁盤上都有，關(guān)于這點金子準(zhǔn)備日后單獨(dú)整理一下。 所以shuffle階段的merge并不是嚴(yán)格的排序意義，只是將多個整體有序的文件merge成一個大的文件，由于同的task執(zhí)行，map的輸出會有所不同，所以merge后的結(jié)果不是每次都相同，不過還是嚴(yán)格要求按照分區(qū)劃分，同時每個分區(qū)內(nèi)的具有相同key的<key,value>對挨在一起。
shuffle排序綜述：如果只定義了map函數(shù)，沒有定義reduce函數(shù)，那么輸入數(shù)據(jù)經(jīng)過shuffle的排序后，結(jié)果為key值相同的輸出挨在一起，且key值小的一定在前面，這樣整體來看key值有序（宏觀意義的，不一定是按從大到小，因為如果采用默認(rèn)的HashPartitioner，則key 的hash值相等的在一個分區(qū)，如果key為IntWritable的話，每個分區(qū)內(nèi)的key會排序好的），而每個key對應(yīng)的value不是有序的。 應(yīng)用一：金子理解：shuffle的排序隨不能滿足全局排序，但是實際中還是幫助我們做了很多工作，比如我們只希望把<key,value>對按照key值，將相同key的<key,value>對輸出到一起，這樣shuffle排序就可以滿足了，也就不需要reduce函數(shù)，只單獨(dú)指定map函數(shù)就OK啦！ 應(yīng)用二：基于分區(qū)的MapFile查找技術(shù)。（我沒仔細(xì)看）
2：全排序 對于全排序，金子深有體會，借助于hadoop的Terasort，我曾經(jīng)寫了整數(shù)和字符串的全排序，其中代碼重疊率很高，只注意改改輸入格式什么的就OK了。要進(jìn)行全局排序，首先要理解分區(qū)的概念，并且要使用TotalOrderpartition（因為默認(rèn)的partition是hashpartition，不適用于全局排序）。主要思路就是將數(shù)據(jù)按照區(qū)間進(jìn)行分割，比如對整數(shù)排序，［0，10000］的在partiiton 0中，（10000，20000］在partition 1中。。。這樣排序后面的partition中的數(shù)據(jù)肯定比排在前面的partition中的數(shù)要大，宏觀上看是有序的，然后在對每個分區(qū)中的數(shù)據(jù)進(jìn)行排序，由于這時分區(qū)中數(shù)據(jù)量已經(jīng)比較小了，在進(jìn)行排序就容易的多了。在數(shù)據(jù)分布均勻的情況下，每個分區(qū)內(nèi)的數(shù)據(jù)量基本相同，這種就是比較理想的情況了，但是實際中數(shù)據(jù)往往分布不均勻，出現(xiàn)了數(shù)據(jù)傾斜的情況，這時按照之前的分區(qū)劃分?jǐn)?shù)據(jù)就不合適了，此時就需要一個東西的幫助——采樣器。采樣的核心思想是只查看一小部分鍵，獲得鍵的近似分布，并由此鍵分區(qū)。關(guān)于采樣器的一些使用細(xì)節(jié)，可以查看我的另一篇博客：Hadoop 中的采樣器－不一樣的視角 Hadoop中的采樣器——不一樣的視角 典型應(yīng)用：TeraSort
3：二次排序 也稱作輔助排序，MapReduce框架在把記錄到達(dá)reducers之前會將記錄按照鍵排序。對于任意一個特殊的鍵，然而，值是不排序的。甚至是，值在兩次執(zhí)行中的順序是不一樣的，原因是它們是從不同的map中來的，這些不同的map可能在不同的執(zhí)行過程中結(jié)束的先后順序不確定。通常情況下，大多數(shù)的MapReduce程序的reduce函數(shù)不會依賴于值的順序。然而，我們也可通過以一種特殊的方式排序和分組鍵，來指定值的順序。 二次排序金子并沒有使用過，不過在join連接操作中，輸入到一個reduce中的value<list>是來自兩個表的，如果進(jìn)行排序，將第一個表的放在前面，第二個表的放在后面，這樣就只需要將表1存放到ArrayList中，表二不需要，然后進(jìn)行全連接就搞定啦，這樣是很多關(guān)于并行數(shù)據(jù)庫的論文中對join操作的一個明顯優(yōu)化。 看到一篇寫的很好的分析二次排序的博客：http://blog.sina.com.cn/s/blog_70324d8d0100wa63.html，講的是日志分析中二次排序是怎么應(yīng)用的。要寫二次排序，則需要非常熟悉Jobconf的幾個函數(shù)，以及各自相關(guān)的類：
A：setOutputKeyComparatorClass ：參數(shù)為繼承RawComparator的子類public void setOutputKeyComparatorClass(Class<? extends RawComparator> theClass)
RawComparator接口：繼承自Comparator ，就是一個比較器，直接在代表對象特征的字節(jié)上進(jìn)行操作。經(jīng)常使用的其實現(xiàn)的類有：DoubleWritable.Comparator, FloatWritable.Comparator, IntWritable.Comparator, LongWritable.Comparator, NullWritable.Comparator, SecondarySort.FirstGroupingComparator, SecondarySort.IntPair.Comparator,Text.Comparator,WritableComparator
自定義的類要實現(xiàn)compare函數(shù)。以上這部分的代碼就是對組合鍵中的key進(jìn)行排序的意思。 很多的二次排序例子中就利用繼承WritableComparator來實現(xiàn)根據(jù)組合鍵進(jìn)行排序。即將compare中的兩個參數(shù)轉(zhuǎn)換為組合鍵，組合鍵中的自然鍵不同時按照自然鍵排序，自然鍵相同時按照自然值排序?？蓞⒁姟稒?quán)威指南》中p243的代碼。
B：setPartitionerClass:用于指定用于分區(qū)的類，參數(shù)我繼承Partitioner的類
public void setPartitionerClass(Class<? extends Partitioner> theClass)
二次排序中由于map的輸出key為組合鍵IntPair，所以自定義的分區(qū)類要繼承Partitioner，同時函數(shù)getPartition 的返回值要根據(jù)組合鍵中的自然鍵，即key.first進(jìn)行判斷，例如return Math.abs(key.getFirst()*127)% numpartitions; 返回值相同的就被分配到一個分區(qū)中了。這樣一個分區(qū)中有多個不同的自然鍵，但是reduce的輸入要滿足對于非組合鍵，就是單純的一個自然鍵時，輸入是 <key, value<list>>的形式，而現(xiàn)在全部都是<IntPair ,value><IntPair,value>....的形式，我們要將自然鍵相同的value放到一起，形成一個list，要怎么辦呢，就要進(jìn)行分組啦?。。》纸M也同樣要用comparator，見下面C哦～
C：setOutputValueGroupingComparator：指定用戶自定義的comparator，用于將reduce的輸入進(jìn)行分組，二次排序中可以理解為將自然鍵key相同的放到一起，相同key的value放到一個value迭代器里。
public void setOutputValueGroupingComparator(Class<? extends RawComparator> theClass)
二次排序工作原理綜述：（轉(zhuǎn)自：http://p-x1984./blog/800269）
在map階段，使用job.setInputFormatClass定義的InputFormat將輸入的數(shù)據(jù)集分割成小數(shù)據(jù)塊splites，同時InputFormat提供一個RecordReder的實現(xiàn)。Hadoop自帶的例子SecondrySort使用TextInputFormat，他提供的RecordReder會將文本的一行的行號作為key，這一行的文本作為value。這就是自定義Map的輸入是<LongWritable,
Text>的原因。然后調(diào)用自定義Map的map方法，將一個個<LongWritable, Text>對輸入給Map的map方法。注意輸出應(yīng)該符合自定義Map中定義的輸出<IntPair, IntWritable>。最終是生成一個List<IntPair, IntWritable>。在map階段的最后，會先調(diào)用job.setPartitionerClass對這個List進(jìn)行分區(qū)，每個分區(qū)映射到一個reducer。每個分區(qū)內(nèi)又調(diào)用job.setSortComparatorClass設(shè)置的key比較函數(shù)類排序?？梢钥吹?，這本身就是一個二次排序。如果沒有通過job.setSortComparatorClass設(shè)置key比較函數(shù)類，則使用key的實現(xiàn)的compareTo方法。在第一個例子中，使用了IntPair實現(xiàn)的compareTo方法，而在下一個例子中，專門定義了key比較函數(shù)類。
二次排序應(yīng)用： 日志分析（轉(zhuǎn)自：） |
|
|
