1. 序章

このチュートリアルでは、 Apache Hadoop オープンソースソフトウェアフレームワークの広く採用されているプログラミングモデルであるMapReduceアルゴリズムを紹介します。これは、元々GoogleがWebページのランクを決定するために開発したものです。 PageRankアルゴリズム。

MapReduceは、多数の処理ノードを使用する並列分散アルゴリズムを使用して、ビッグデータの分散計算を表現できます。 各ジョブは、MapとReduceの2セットのタスクに関連付けられており、主にHadoop分散ファイルシステム（HDFS）のデータのクエリと選択に使用されます。

2. MapReduceはどのように機能しますか？

まず、キーと値のペアがMapReduceの基本的なデータ構造を形成します。 アルゴリズムは、入力キーと値のペアのセットを受け取り、出力としてキーと値のペアのセットを生成します。 MapReduceでは、デザイナーは次の2つのフェーズでマッパーとレデューサーを開発します。

操作の順序：マップ|シャッフル|削減

2.1. マップフェーズ

MapReduceの最初のフェーズ入力ペアを取り、中間のキーと値のペア（key_1、value_1）[（k_2、v_2）]のセットを生成します。 MapReduceライブラリは、同じ中間キーに関連付けられているすべての中間値をグループ化し、それらをreduce関数に渡します。

2.2. フェーズを減らす

MapReduceの第2フェーズは、中間キーとそのキーの値のセットを入力として受け取り、データを簡略化された形式（key_2、[value_2]）[（k_3、v_3）]に縮小します。 これらの値を結合およびマージして、場合によってはより小さな値のセットを形成し、reduce操作を実行します。 中間の値に対応するreduce関数にイテレータが提供されます。

削減フェーズが正常に完了すると、結果がHadoopサーバーに送信されます。

2.3. MapReduce固有のタスク

MapReduceプログラムには、マッパーとリデューサーのコードと、構成パラメーター（入力の場所やストレージ情報など）が含まれています。 開発者はジョブをクラスターのノードに送信し、実行フレームワークが残りを処理します。

MapReduceの特定のジョブは次のとおりです。

  1. スケジューリング：ジョブをより小さな単位に分割し、さまざまなジョブのさまざまなタスクを調整するタスク
  2. データとコードのコロケーション：データの局所性を実現するために、スケジューラーは、タスクに必要なデータの特定のブロックを保持するノードでタスクを開始します
  3. 同期：シャッフルと並べ替えのプロセスは、MapとReduceの間のフェーズを形成します。ここで、Map関数の出力は、そのキーに基づいて並べ替えられ、シャッフルされます。
  4. エラーとフォールトの処理：ノードからの応答がない場合、作業は実行する別のノードに割り当てられます

3. MapReduceを使用する理由

3.1. アルゴリズムの利点

通常のデータベースサーバーは、大量のデータを処理するときにボトルネックが多すぎて苦労します。また、データを大量に消費するいくつかの作業は、コンピューティングノードとストレージノードの分離によって引き起こされるボトルネックに悩まされます。実行することは、プロセッサをそれほど要求しません。 この問題は、タスクを異なるノードに割り当て、すべてのジョブを独立して処理するMapReduceアルゴリズムを使用することで解決されます。

さらに、分散ファイルシステムは、データが異なるノードで順次処理され、ランダムなデータアクセスを回避するように計算を整理する役割を担うため、実行のパフォーマンスが向上します。

3.2. MapReduceはどこで使用されますか？

MapReduceアルゴリズムに関連する典型的な問題/例は次のとおりです。

  • 分散grep：mapタスクは特定のパターンに適合する場合に線を生成しますが、reduceタスクは中間データを出力として単純に再現する恒等関数をフォーマットします
  • URLアクセス頻度のカウント：map関数は、Webページの履歴ファイル要求を処理し、 対応するファイルで検出されるN個のリクエストのペア。 削減機能は、同じURLのすべての結果を要約し、ペアを提供します
  • リバースWebリンクグラフ：マップジョブはペアを返します 「開始点」と呼ばれるページにある1つの「ターゲット」アドレスへのリンクごとに。 削減機能は、すべての「開始点」のリストを特定の1つの「ターゲット」に結合し、ペアを返します。
  • 転置インデックス：map関数は各ドキュメントを読み取り、ペアのリストを返します 、reduce関数は特定の単語のすべてのペアを取得し、ドキュメントを並べ替えて、ペアを返します。 。 逆インデックスは、作成されたすべてのペアのセットによって形成されます

4. MapReduceの例

ドキュメントの大規模なコレクション内の各単語の出現回数をカウントする問題を検討します。 この問題の擬似コード：

最初に、マッパーはKey-Valueを生成しますすべての単語のペア。 すべての単語がキーとして機能し、整数が値の頻度として機能します。 次に、レデューサーはすべての単語に関連付けられているすべてのカウントを合計し、目的のキーペアを作成します。

5. 結論

この記事では、ビッグデータを効果的に処理し、クラスター環境で高レベルの並列処理を実現できるため、広く使用されているアルゴリズムであるMapReduceを紹介しました。テラバイトのデータを同時に処理し、特定のアルゴリズムを高速化する機能により、このアルゴリズムは非常に人気があり、大規模で複雑なデータを処理する企業に広く適用されます。