MapReduce排序算法如何工作？

Question

用於演示MapReduce功能的主要示例之一是Terasort benchmark。我無法理解MapReduce環境中使用的排序算法的基礎知識。

對我來說，排序只需要確定一個元素與所有其他元素的相對位置。所以排序包括比較「一切」和「一切」。您的平均排序算法（快速，氣泡，...）只是以一種明智的方式做到這一點。

在我看來，將數據集分成多個部分意味着您可以對單個部分進行排序，然後您仍然必須將這些部分整合到'完整'完全排序的數據集中。鑑於分佈在數千個系統上的terabyte數據集，我預計這將是一項艱鉅的任務。

那麼這是如何做到的？這個MapReduce排序算法是如何工作的？

謝謝你幫助我理解。

Answer 1

這裏有一些細節上Hadoop's implementation for Terasort：

TeraSort是一個標準的地圖/排序減少，除了使用N的排序列表的自定義分區 - 定義鍵的範圍爲每減少1個採樣鍵。特別是，樣本[i - 1] < =樣本[i]的密鑰<被髮送以減少i。這保證了減少i的輸出都小於減少i + 1的輸出。「

所以他們的訣竅是他們在映射階段確定鍵的方式，基本上他們確保每個值一個減速是保證「預排序」對所有其他減速。

我發現通過James Hamilton's Blog Post本文參考。

Answer 2

谷歌參考：MapReduce: Simplified Data Processing on Large Clusters

出演：
OSDI'04：第六屆學術研討會操作系統的設計與實現，
舊金山，CA，十二月，2004

該鏈接具有PDF和HTML-Slide參考。

還有一個Wikipedia page with description與實施參考。

而且批評，

大衛德威特和邁克爾·斯通布雷克，並行數據庫和無共享架構創業專家，作出了關於那MapReduce的可用於問題的廣度一些有爭議的斷言。他們稱其界面太低級，並質疑它是否真正代表其支持者所聲稱的範例轉變。他們質疑MapReduce支持者的新穎性主張，並將Teradata列爲已有二十多年的現有技術的一個例子;他們將MapReduce程序員與Codasyl程序員進行了比較，指出他們都是「用低級別語言編寫低級別的記錄操作」。 MapReduce使用輸入文件和缺少模式支持可以防止通用數據庫系統功能（如B樹和散列分區）啓用性能改進，但PigLatin和Sawzall等項目正在開始解決這些問題。

Answer 3

只是猜測......

鑑於龐大的數據集，則可以將數據分割成一些塊並行，即記錄1進行處理（也許通過記錄號 - 1000 =分區1，和等等）。

將每個分區分配/調度到集羣中的特定節點。

每個羣集節點都會將分區進一步分割（映射）到它自己的迷你分區中，可能是按鍵字母順序。因此，在分區1中，將所有以A開頭的內容輸出到x的迷你分區A中。如果當前有A（x），則創建一個新的A（x）。將x替換爲順序號（也許這是調度程序的工作）。即給我下一個A（X）唯一的ID。

將映射器（前一步驟）完成的作業移交（調度）到「減少」羣集節點。然後減少節點集羣將進一步改進每個A（x）部分的排序，當映射器任務完成時，這些部分將很快發生（當仍然存在仍然存在的可能性時，實際上無法開始排序所有以w/A開始的單詞將成爲另一個迷你分區）。將結果輸出到最終的排序分區（即Sorted-A，Sorted-B等）

完成後，再次將已排序的分區組合到單個數據集中。在這一點上，它只是n個文件（其中n可能是26，如果你只是在做A - Z）等簡單串聯等。

可能有中間步驟之間......我不確定： ）。即在最初的縮小步驟之後進一步映射並減少。

Answer 4

我有同樣的問題，而讀谷歌的MapReduce紙。@Yuval˚F的answer幾乎解決了我的難題。

我在閱讀報紙時注意到的一件事是，魔術發生在分區中（在地圖之後，減少之前）。

本文使用hash(key) mod R作爲分區示例，但這不是將中間數據分區到不同reduce任務的唯一方法。

只需添加邊界條件來@Yuval˚F的answer使它完成：假設分鐘（S）和max（S）是被採樣的鍵中的最小密鑰和最大密鑰;所有密鑰<分鐘（S）被分區爲一個reduce任務;反之亦然，所有密鑰> = max（S）被分區爲一個reduce任務。

對採樣鍵沒有硬性限制，如最小或最大。只是，更均勻地將這些R密鑰分佈在所有密鑰中，這個分佈式系統更「平行」，減少操作員存在內存溢出問題的可能性更小。