mapreduce排序算法

我們將繼續(xù)執(zhí)行有關(guān)實(shí)現(xiàn)MapReduce算法的系列文章，該系列可在使用MapReduce進(jìn)行數(shù)據(jù)密集型文本處理中找到。 本系列的其他文章：

使用MapReduce進(jìn)行數(shù)據(jù)密集型文本處理

使用MapReduce進(jìn)行數(shù)據(jù)密集型文本處理-本地聚合第二部分

使用Hadoop計(jì)算共現(xiàn)矩陣

MapReduce算法–順序反轉(zhuǎn)

這篇文章介紹了在使用MapReduce進(jìn)行數(shù)據(jù)密集型文本處理的第3章中找到的二級(jí)排序模式。 Hadoop在將映射器發(fā)出的數(shù)據(jù)自動(dòng)排序后再發(fā)送給reduce，但是如果您還想按值排序怎么辦？ 您當(dāng)然會(huì)使用二級(jí)排序。 通過稍加操作鍵對(duì)象的格式，二級(jí)排序使我們能夠在排序階段將值考慮在內(nèi)。 這里有兩種可能的方法。

第一種方法涉及讓減速器緩沖給定鍵的所有值，并對(duì)這些值進(jìn)行歸約器排序。 由于reducer將接收給定鍵的所有值，因此此方法可能會(huì)導(dǎo)致reducer的內(nèi)存不足。

第二種方法涉及通過向自然鍵添加部分或整個(gè)值來創(chuàng)建組合鍵，以實(shí)現(xiàn)您的排序目標(biāo)。 這兩種方法之間的權(quán)衡是對(duì)reducer中的值進(jìn)行顯式排序，這很有可能會(huì)更快（存在內(nèi)存不足的風(fēng)險(xiǎn)），但實(shí)現(xiàn)“值到鍵”轉(zhuǎn)換方法會(huì)減輕MapReduce框架的排序工作，這是Hadoop / MapReduce設(shè)計(jì)要做的核心。 出于本文的目的，我們將考慮“關(guān)鍵價(jià)值”方法。 我們將需要編寫一個(gè)自定義分區(qū)程序，以確保所有具有相同鍵（自然鍵不包括帶有值的復(fù)合鍵的自然鍵）的數(shù)據(jù)都發(fā)送到同一reduce和自定義比較器，因此一旦數(shù)據(jù)被自然鍵分組到達(dá)減速機(jī)。

值到密鑰轉(zhuǎn)換

直接創(chuàng)建復(fù)合鍵。 我們需要做的是分析在排序過程中我們要考慮值的哪一部分并將適當(dāng)?shù)牟糠痔砑拥阶匀绘I中。 然后，我們需要在鍵類或比較器類中的compareTo方法上進(jìn)行工作，以確保對(duì)組合鍵進(jìn)行了說明。 我們將重新訪問天氣數(shù)據(jù)集，并將溫度作為自然鍵的一部分（自然鍵是年和月連接在一起）。 結(jié)果將列出給定月份和年份中最冷的一天。 該示例的靈感來自Hadoop，《權(quán)威指南》一書中的二級(jí)排序示例。 盡管可能有更好的方法可以實(shí)現(xiàn)此目標(biāo)，但它足以說明次級(jí)排序的工作原理。

映射器代碼

我們的映射器代碼已經(jīng)將年和月連接在一起，但是我們還將把溫度作為鍵的一部分。 由于我們將值包含在鍵本身中，因此映射器將發(fā)出NullWritable，在其他情況下，我們將發(fā)出溫度。

public class SecondarySortingTemperatureMapper extends Mapper<LongWritable, Text, TemperaturePair, NullWritable> {private TemperaturePair temperaturePair = new TemperaturePair();private NullWritable nullValue = NullWritable.get();private static final int MISSING = 9999; @Overrideprotected void map(LongWritable key, Text value, Context context) throws IOException, InterruptedException {String line = value.toString();String yearMonth = line.substring(15, 21);int tempStartPosition = 87;if (line.charAt(tempStartPosition) == '+') {tempStartPosition += 1;}int temp = Integer.parseInt(line.substring(tempStartPosition, 92));if (temp != MISSING) {temperaturePair.setYearMonth(yearMonth);temperaturePair.setTemperature(temp);context.write(temperaturePair, nullValue);}} }

現(xiàn)在，我們已將溫度添加到密鑰中，我們?yōu)閱⒂幂o助排序設(shè)置了條件。 剩下要做的就是在必要時(shí)編寫考慮溫度的代碼。 在這里，我們有兩種選擇，編寫一個(gè)Comparator或在TemperaturePair類上調(diào)整compareTo方法（TemperaturePair實(shí)現(xiàn)WritableComparable）。 在大多數(shù)情況下，我建議寫一個(gè)單獨(dú)的Comparator，但是TemperaturePair類是專門為演示二次排序而編寫的，因此我們將修改TemperaturePair類的compareTo方法。

@Overridepublic int compareTo(TemperaturePair temperaturePair) {int compareValue = this.yearMonth.compareTo(temperaturePair.getYearMonth());if (compareValue == 0) {compareValue = temperature.compareTo(temperaturePair.getTemperature());}return compareValue;}

如果我們想按降序排序，我們可以簡(jiǎn)單地將溫度比較的結(jié)果乘以-1。
現(xiàn)在，我們已經(jīng)完成了排序所需的部分，我們需要編寫一個(gè)自定義分區(qū)程序。

合伙人代碼

為了確保在確定將哪個(gè)縮減程序發(fā)送數(shù)據(jù)時(shí)僅考慮自然鍵，我們需要編寫一個(gè)自定義分區(qū)程序。 該代碼很簡(jiǎn)單，在計(jì)算將數(shù)據(jù)發(fā)送到的減速器時(shí)，僅考慮TemperaturePair類的yearMonth值。

public class TemperaturePartitioner extends Partitioner<TemperaturePair, NullWritable>{@Overridepublic int getPartition(TemperaturePair temperaturePair, NullWritable nullWritable, int numPartitions) {return temperaturePair.getYearMonth().hashCode() % numPartitions;} }

盡管自定義分區(qū)程序保證了年和月的所有數(shù)據(jù)都到達(dá)同一還原器，但我們?nèi)匀恍枰紤]該還原器將按鍵對(duì)記錄進(jìn)行分組的事實(shí)。

分組比較器

數(shù)據(jù)到達(dá)精簡(jiǎn)器后，所有數(shù)據(jù)均按鍵分組。 由于我們有一個(gè)復(fù)合鍵，因此我們需要確保記錄僅按自然鍵分組。 這是通過編寫自定義GroupPartitioner完成的。 為了將記錄分組在一起，我們只考慮了TemperaturePair類的yearMonth字段的Comparator對(duì)象。

public class YearMonthGroupingComparator extends WritableComparator {public YearMonthGroupingComparator() {super(TemperaturePair.class, true);}@Overridepublic int compare(WritableComparable tp1, WritableComparable tp2) {TemperaturePair temperaturePair = (TemperaturePair) tp1;TemperaturePair temperaturePair2 = (TemperaturePair) tp2;return temperaturePair.getYearMonth().compareTo(temperaturePair2.getYearMonth());} }

結(jié)果

這是運(yùn)行我們的二級(jí)排序作業(yè)的結(jié)果：

new-host-2:sbin bbejeck$ hdfs dfs -cat secondary-sort/part-r-00000 190101 -206 190102 -333 190103 -272 190104 -61 190105 -33 190106 44 190107 72 190108 44 190109 17 190110 -33 190111 -217 190112 -300

結(jié)論

雖然按值對(duì)數(shù)據(jù)進(jìn)行排序可能不是普遍的需求，但是在需要時(shí)，這是個(gè)不錯(cuò)的工具。 此外，通過使用自定義分區(qū)程序和組分區(qū)程序，我們能夠更深入地了解Hadoop的內(nèi)部工作原理。 感謝您的時(shí)間。

資源資源

• Jimmy Lin和Chris Dyer 使用MapReduce進(jìn)行的數(shù)據(jù)密集型處理
• Hadoop： Tom White 的權(quán)威指南
• 來自博客的源代碼和測(cè)試
• Hadoop API
• MRUnit用于單元測(cè)試Apache Hadoop映射減少工作

參考： MapReduce算法–來自我們的JCG合作伙伴 Bill Bejeck的“ 二級(jí)排序”，來自“ 隨機(jī)編碼思考”博客。

翻譯自: https://www.javacodegeeks.com/2013/01/mapreduce-algorithms-secondary-sorting.html

mapreduce排序算法

總結(jié)

以上是生活随笔為你收集整理的mapreduce排序算法_MapReduce算法–二级排序的全部?jī)?nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯(cuò)，歡迎將生活随笔推薦給好友。