[解決済み] MapReduceのソートアルゴリズムはどのように動作するのですか？

質問

MapReduceの威力を示す主な例のひとつが Terasortベンチマーク . MapReduce環境で使用されるソートアルゴリズムの基本が分からなくて困っています。

私にとってのソートは、単に他のすべての要素との関係で要素の相対的な位置を決定することを含んでいます。つまり、ソートには、"すべて"と"すべて"を比較することが含まれるのです。平均的なソートアルゴリズム (クイック、バブル、...) は、単にこれをスマートに行うだけです。

私の考えでは、データセットを多くの部分に分割することは、1 つの部分をソートすることができ、その後、これらの部分を「完全な」完全にソートされたデータセットに統合する必要があります。何千ものシステムに分散されたテラバイト級のデータセットを考えると、これは膨大な作業になることが予想されます。

では、実際にどのように行われているのでしょうか？このMapReduceのソートアルゴリズムはどのように動作するのでしょうか？

理解の手助けをしてくれてありがとうございます。

どのように解決するのですか？

以下は HadoopのTerasortの実装です。 :

TeraSortは標準的なmap/reduceソートであるが、各リデュースのキー範囲を定義するN - 1個のサンプルキーのソートリストを使用するカスタムパーティショナーを除いては、リデュースである。特に、sample[i - 1] <= key < sample[i]のようなすべてのキーは、reduce iに送られます。これは、reduce iの出力がすべてreduce i+1の出力より小さいことを保証しています。

つまり、彼らのトリックは、mapフェーズでキーを決定する方法にあるのです。基本的に、彼らは単一のリデューサ内のすべての値が他のすべてのリデューサに対して「事前にソート」されていることが保証されていることを確認します。

私はこの論文のリファレンスを James Hamilton のブログ記事 .