我在閱讀有關MapReduce的內容,以下內容令我感到困惑。使用MapReduce/Hadoop對大數據進行排序
假設我們有一個包含100萬個條目(整數)的文件,我們想用MapReduce對它們進行排序。我理解的方式如下:
編寫一個對整數進行排序的映射函數。因此,框架將輸入文件分成多個塊,並將它們分配給不同的映射器。每個映射器將對彼此獨立的數據塊進行排序。一旦完成了所有的映射器,我們將把它們的每個結果傳遞給Reducer,它將結合結果並給出最終結果。
我的疑問是,如果我們有一個reducer,那麼它是如何利用分佈式框架的,如果最終我們必須將結果合併到一個地方?這個問題深入到在一個地方合併100萬個條目。是這樣還是我錯過了什麼?
感謝, 錢德爾
並且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