MapReduceの能力を実証するために使用される主な例の1つは、Terasortベンチマークです。MapReduce環境で使用される並べ替えアルゴリズムの基本を理解するのに問題があります。
私にとって、並べ替えには、他のすべての要素との関係における要素の相対的な位置を決定することが含まれます。したがって、並べ替えには、「すべて」と「すべて」を比較することが含まれます。平均的な並べ替えアルゴリズム（クイック、バブルなど）は、これをスマートな方法で実行します。
私の考えでは、データセットを多くの部分に分割するということは、1つの部分を並べ替えることができ、それでもこれらの部分を「完全な」完全に並べ替えられたデータセットに統合する必要があることを意味します。数千のシステムに分散されたテラバイトのデータセットを考えると、これは大きな作業になると思います。
では、これは実際にどのように行われるのでしょうか。このMapReduceソートアルゴリズムはどのように機能しますか？
私が理解するのを手伝ってくれてありがとう。
Terasort に対する Hadoop の実装の詳細を次に示します。
TeraSort は標準の map/reduce ソートですが、reduce ごとにキー範囲を定義する N − 1 個のサンプル キーのソート済みリストを使用するカスタム パーティショナーを除きます。特に、sample[i − 1] <= key < sample[i] のようなすべてのキーは、i を減らすために送信されます。これにより、reduce i の出力がすべて reduce i+1 の出力よりも小さいことが保証されます。」
したがって、彼らの秘訣は、マップ段階でキーを決定する方法にあります。基本的に、単一のレデューサーのすべての値が、他のすべてのレデューサーに対して「事前にソート」されることが保証されます。
James Hamilton の Blog Postから参考文献を見つけました。
Google リファレンス: MapReduce: 大規模クラスターでの単純化されたデータ処理
出演:
OSDI'04: オペレーティング システムの設計と実装に関する第 6 回シンポジウム
、カリフォルニア州サンフランシスコ、2004 年 12 月。
そのリンクには、PDF と HTML スライドの参照があります。
実装リファレンスを含む説明が記載されたウィキペディアのページもあります。
批判も、
並列データベースとシェアード ナッシング アーキテクチャの先駆的な専門家である David DeWitt と Michael Stonebraker は、MapReduce を使用できる幅広い問題について物議を醸す主張をいくつか行っています。彼らは、そのインターフェイスが低レベルすぎると呼び、その支持者が主張しているパラダイムシフトを本当に表しているかどうかを疑問視しました. 彼らは、20 年以上にわたって存在してきた先行技術の例として Teradata を挙げて、MapReduce 支持者の新規性の主張に異議を唱えています。彼らは MapReduce プログラマーと Codasyl プログラマーを比較し、どちらも「低レベルのレコード操作を実行する低レベル言語で書いている」ことに注目しました。MapReduce の入力ファイルの使用とスキーマ サポートの欠如により、B ツリーやハッシュ パーティショニングなどの一般的なデータベース システム機能によって実現されるパフォーマンスの向上が妨げられます。
推測するだけで...
膨大なデータ セットが与えられた場合、データをいくつかのチャンクに分割して並列処理します (おそらくレコード番号、つまりレコード 1 - 1000 = パーティション 1 など)。
各パーティションをクラスター内の特定のノードに割り当て/スケジュールします。
各クラスタ ノードは、おそらくキーのアルファベット順で、パーティションを独自のミニ パーティションにさらに分割 (マップ) します。したがって、パーティション 1 で、A で始まるすべてのものを取得し、x のミニ パーティション A に出力します。現在 A(x) が既に存在する場合は、新しい A(x) を作成します。x を連番に置き換えます (おそらく、これはスケジューラーのジョブです)。つまり、次の A(x) の一意の ID を教えてください。
マッパー (前のステップ) によって完了したジョブを「削減」クラスター ノードに引き渡し (スケジュール) ます。リデュース ノード クラスターは、すべてのマッパー タスクが完了したときにのみ発生する各 A(x) パーツの並べ替えをさらに洗練します (まだ存在する可能性がある場合、A で始まるすべての単語の並べ替えを実際に開始することはできません)。別のものになる予定です 作成中のミニパーティション）。結果を最終的なソート済みパーティションに出力します (つまり、Sorted-A、Sorted-B など)。
完了したら、並べ替えられたパーティションを再び 1 つのデータセットに結合します。この時点では、n 個のファイルを単純に連結しただけです (A - Z のみを実行している場合、n は 26 になる可能性があります)。
間に中間ステップがあるかもしれません...よくわかりません:)。つまり、最初の削減ステップの後に、さらにマップして削減します。