使用MapReduce/Hadoop對大數據進行排序

我在閱讀有關MapReduce的內容，以下內容令我感到困惑。使用MapReduce/Hadoop對大數據進行排序

假設我們有一個包含100萬個條目（整數）的文件，我們想用MapReduce對它們進行排序。我理解的方式如下：

編寫一個對整數進行排序的映射函數。因此，框架將輸入文件分成多個塊，並將它們分配給不同的映射器。每個映射器將對彼此獨立的數據塊進行排序。一旦完成了所有的映射器，我們將把它們的每個結果傳遞給Reducer，它將結合結果並給出最終結果。

我的疑問是，如果我們有一個reducer，那麼它是如何利用分佈式框架的，如果最終我們必須將結果合併到一個地方？這個問題深入到在一個地方合併100萬個條目。是這樣還是我錯過了什麼？

感謝，錢德爾

來源

2010-09-02 Chander Shivdasani

退房合併排序。

事實證明，排序部分排序列表在操作和內存消耗方面比排序整個列表更有效。

如果reducer獲得4個排序列表，它只需要查找4個列表中的最小元素並選擇一個。如果列表數量不變，則這種減少是O（N）操作。

此外，通常情況下，還原器也是「分佈式」在類似樹的東西中，所以也可以將工作平行化。

來源

2010-09-02 06:51:54

並且reducer可以從每個映射器獲取第一個結果時開始給出結果（在合併排序的情況下）在給出輸出的同時執行進程（合併），它是時間和記憶的巨大改善。 – helios 2010-09-02 07:34:28

如果你總是使用相同數量的映射器，這只是一個常量。一般來說，如果您使用最小堆，並且O（M * N）用於「樸素」方法，則將M個元素合併到N個列表中爲O（M log N）。但是，如你所期望的M >> N，它基本上是線性的。 – SquareCog 2010-09-10 07:35:42

還有一個實際的問題是，在短期內，你的資源，即CPU核心和盒子，是不變的，它需要管理層的同意才能增加M.因此，M看起來像是阿茲特克金字塔，有幾個「常量」步驟。 – 2010-09-10 10:34:16

我認爲，結合多種排序項目比組合多個無序項目高效。所以映射器完成排序塊的任務，並且reducer將它們合併。如果mapper沒有完成排序，reducer將會在排序時遇到困難。

來源

2010-09-02 06:52:20 Gopi

正如其他人所說的，合併比分類簡單得多，所以這裏有一個很大的勝利。

但是，對巨型數據集執行O（N）串行操作也可能會令人望而卻步。正如您正確指出的那樣，最好找到一種並行執行合併的方法。

做到這一點的一種方法是從隨機分區器（這是通常使用的）替換分區功能到更聰明一點。例如，Pig爲此做了什麼，即對您的數據集進行採樣，以粗略估計值的分佈，然後將值的範圍分配給不同的reducers。減速器0獲取所有元素< 1000，減速器1獲取所有元素> = 1000和< 5000，依此類推。然後你可以並行地進行合併，並且按照你所知道的每個reducer任務的編號排序最終結果。

來源

2010-09-10 07:41:30 SquareCog

因此，使用的map-reduce（雖然不是最有效的一個）排序的最簡單的方法就是做以下

地圖相（Input_Key，將input_value）發出了在（將input_value，輸入鍵）

減速機是一種身份Reduceer

因此，舉例來說，如果我們的數據是學生，年齡數據庫那麼你的映射器的輸入是（ 'A'，1）（ 'B'，2）（ 'C' ，10）...並且輸出將是（1，A）（2，B）（10，C）

還沒有嘗試過這個邏輯，但它是我正在努力的一個作業問題的一步。將更新源代碼/邏輯鏈接。

來源

2011-04-11 19:26:59 rOrlig

已將源代碼和解釋放在這裏http://rorlig.wordpress.com/2011/04/17/sorting-data-with-mapreduce/ – rOrlig 2011-04-17 02:37:20

你如何驗證它？以及如何確保發射的密鑰被分類？ – lenhhoxung 2016-01-14 15:26:15

對不起，我來晚了，但對於未來的讀者，是錢德勒，你得到它錯了

邏輯是，減速機可處理洗牌，然後進行排序僅在其運行的節點的數據。我的意思是在一個節點上運行的reducer不能查看其他節點的數據，它僅適用於其數據的reduce算法。合併分類的SO合併程序不適用。

因此對於我們使用Tera排序的大數據，這只是標識映射器和定製分區器的縮減器。從這裏閱讀更多關於它的信息您應該從這裏閱讀更多關於它的信息Hadoop's implementation for Terasort。它指出：

「TeraSort是一種標準映射/縮減排序，除了定製分區程序使用排序的N-1個抽樣鍵列表來定義每個縮減程序的鍵範圍外，特別是所有鍵樣例[i - 1] < = key < sample [i]被髮送以減少i，這保證了reduce i的輸出都小於reduce i + 1的輸出。

來源

2013-06-27 17:26:06

使用MapReduce可以高效地執行排序。但是你似乎在考慮使用mapreduce來實現合併排序來實現這一目的。它可能不是理想的候選人。

喜歡你提到，歸併（與地圖，減少）將包括以下步驟：

分區的元素分成小組並指定每組映射器中以循環方式
每個映射器將對子集進行排序並返回{K，{subset}}，其中K對所有映射器都是相同的
由於在所有映射器中使用相同的K，所以只有一個減少，因此只有一個減速器。減速器可以合併數據並返回排序結果

這裏的問題是，就像您提到的那樣，在還原階段可能只有一個減速器排除了並行。就像在其他回覆中提到的那樣，可以考慮使用像terasort這樣的mapreduce特定實現。

在http://www.chinacloud.cn/upload/2014-01/14010410467139.pdf

再回到合併排序實測值的說明中，這將是可行的，如果所述的hadoop（或等同物）工具提供減速器的層級結構，其中減速器的一個電平的輸出變爲減速器的下一級或者將其循環回同一組reducer

來源

2016-08-29 18:07:03

使用MapReduce/Hadoop對大數據進行排序

回答

相關問題