2009-09-30 48 views
2

我在考慮在hadoop中構建一個小測試應用程序以獲取系統的掛起。在將值發送給reducer之前對值進行排序

我想到的應用程序將在統計領域。 我想從我的reducer函數(其中我必須假設可能有大量值用於某些鍵)中得到「每個鍵的10個最差值」。

我的計劃是,進入我的減速機的價值基本上是「實際價值」和「實際價值的質量/相關性」的組合。 基於相關性,我「簡單地」想要採用10個最差/最佳值並從減速器輸出它們。

我該如何去做(假設特定鍵的數量巨大)? 有沒有一種方法可以在將它們發送到reducer之前對所有值進行排序(並且在讀完第一個10時停止讀取輸入)或者必須以不同的方式完成這些操作?

有人可以在這裏指出我可以看一看示例代碼嗎?


更新:我發現了兩個有趣的問題吉拉和HADOOP-485HADOOP-686

任何人都有關於如何在Hadoop 0.20 API中使用它的代碼片段?

回答

1

聽起來好像你想要使用一個組合器,它定義瞭如何處理在Map端創建的值,然後再將它們發送到Reducer,但是在按鍵分組後。 組合器通常被設置爲reducer類(所以你減少了地圖側,然後再減少)。

看一看的例子的wordCount如何使用組合預先計算部分計數:

http://wiki.apache.org/hadoop/WordCount


更新 這就是我心目中的您的問題;不過,我可能誤解了你正在嘗試做的事情。

每個映射器都會發出<key, {score, data}>對。

組合器獲取這些對的部分集合:<key, [set of {score, data}>並執行本地排序(仍位於映射器節點上),並輸出<key, [sorted set of top 10 local {score, data}]>對。

的減速將得到<key, [set of top-10-sets]> - 所有它做的是執行排序合併的合併步驟(不排序需要)爲每個數值組成員,並停止在合併時,前10個值被上拉。


更新2

所以,現在我們知道了等級作爲cumilative,因此,你不能將數據早期採用組合過濾,唯一的事情是做什麼的你建議 - 進行二次排序。你找到了合適的門票;有一個如何在src/examples/org/apache/hadoop/examples/SecondarySort中的Hadoop 20中執行此操作的示例。java(或者,如果你不想下載整個源代碼樹,你可以看看https://issues.apache.org/jira/browse/HADOOP-4545中的示例補丁)

+0

嗯,據我瞭解合併的目的是爲「這是一個特定節點上運行的部分減速」。在那個時候我不能截斷結果,因爲我不知道當時的價值的總體「質量」。 – 2009-10-01 10:13:03

+0

更新:有趣的建議。這樣做(組合已經截斷的子集)通常會導致與「確切」的做法不同的輸出。這對我的情況可能會足夠好。我會考慮的。謝謝。 – 2009-10-01 20:05:54

+0

你能解釋爲什麼這會導致不同的輸出?我認爲,全球排名前10位的項目肯定包含在每個分區的前10項(可能是前3名,後2名,前5名 - 但他們都在那裏)。 – SquareCog 2009-10-01 21:02:55

4

聽起來像SecondarySortProblem一樣。如果您願意,可以查看「Hadoop:權威指南」。它來自O'Reilly。您也可以在線訪問它。在那裏他們描述了一個很好的實現。

我也是自己實現的。基本上,它的工作原理如下: 分區器將關注所有鍵值對,並將同一個鍵用於單個reducer。沒什麼特別的。 但也有GroupingComparator,這將形成分組。實際上,一個組作爲迭代器傳遞給一個reduce() - 調用。所以分區可以包含多個分組。但分區的數量應該與減速器的數量相等。但是分組還允許在執行compareTo方法時進行一些排序。

使用此方法,您可以控制,但是最好/最差/最高/最低的按鍵首先會到達減速器。所以讀完這10個鍵之後,可以不做任何進一步的迭代就離開reduce方法。

希望那是有幫助:-)