173

私のCouchDBの質問に関連しています。

誰でも麻痺者が理解できる言葉で MapReduce を説明できますか?

4

8 に答える 8

203

Map と Reduce の基本に至るまで。

Mapは、ある種のリスト内のアイテムを別の種類のアイテムに「変換」し、それらを同じ種類のリストに戻す機能です。

数字のリスト [1,2,3] があり、すべての数字を 2 倍にしたいとします。この場合、「すべての数字を 2 倍にする」関数は関数 x = x * 2 です。マッピングがなければ、次のように記述できます。単純なループ、たとえば

A = [1, 2, 3]
foreach (item in A) A[item] = A[item] * 2

私は A = [2, 4, 6] を持っていますが、ループを書く代わりに、マップ関数があれば書くことができます

A = [1, 2, 3].Map(x => x * 2)

x => x * 2 は、[1,2,3] の要素に対して実行される関数です。何が起こるかというと、プログラムは各項目を取得し、x を各項目に等しくすることによってそれに対して (x => x * 2) を実行し、結果のリストを生成します。

1 : 1 => 1 * 2 : 2  
2 : 2 => 2 * 2 : 4  
3 : 3 => 3 * 2 : 6

したがって、(x => x * 2) で map 関数を実行すると、[2, 4, 6] になります。

Reduceは、リスト内の項目を「収集」し、それらすべてに対して何らかの計算を実行して、それらを単一の値に削減する関数です。

合計または平均の検索はすべて reduce 関数のインスタンスです。[7, 8, 9] などの数字のリストがあり、それらを合計したい場合、次のようなループを記述します。

A = [7, 8, 9]
sum = 0
foreach (item in A) sum = sum + A[item]

しかし、reduce 関数にアクセスできる場合は、次のように記述できます。

A = [7, 8, 9]
sum = A.reduce( 0, (x, y) => x + y )

なぜ 2 つの引数 (0 と x と y を持つ関数) が渡されるのか、少し混乱しています。reduce 関数が有用であるためには、2 つの項目を取り、何かを計算し、その 2 つの項目を 1 つの値に "還元" できる必要があります。したがって、プログラムは、単一の値になるまで各ペアを削減できます。

実行は次のようになります。

result = 0
7 : result = result + 7 = 0 + 7 = 7
8 : result = result + 8 = 7 + 8 = 15
9 : result = result + 9 = 15 + 9 = 24

しかし、常にゼロから始めたいとは思わないので、最初の引数はシード値、特に最初のresult =行の値を指定できるようにするためにあります。

2 つのリストを合計したい場合、次のようになります。

A = [7, 8, 9]
B = [1, 2, 3]
sum = 0
sum = A.reduce( sum, (x, y) => x + y )
sum = B.reduce( sum, (x, y) => x + y )

または、現実の世界で見つける可能性が高いバージョン:

A = [7, 8, 9]
B = [1, 2, 3]

sum_func = (x, y) => x + y
sum = A.reduce( B.reduce( 0, sum_func ), sum_func )

Map\Reduce のサポートにより、データベースを使用するためにデータが DB にどのように格納されているかを知らなくてもデータベースを操作できるため、DB ソフトウェアの良い点です。それが DB エンジンの目的です。

Map または Reduce 関数のいずれかをエンジンに提供することで、必要なものをエンジンに「伝える」ことができれば、DB エンジンはデータを回避し、関数を適用して、必要な結果を得ることができます。すべてのレコードをループする方法を知らなくても、すべてが必要です。

インデックスとキー、結合とビュー、および単一のデータベースが保持できる多くのデータがあるため、データが実際にどのように格納されているかを隠すことで、コードの記述と保守が容易になります。

並列プログラミングについても同じことが言えます。ループ コードを実際に実装するのではなく、データで何をしたいのかを指定するだけであれば、基盤となるインフラストラクチャが同時並列ループで関数を「並列化」して実行できます。

于 2008-08-27T17:09:09.497 に答える
63

MapReduce は、開発者が mapper 関数と reduce 関数以外のコードを記述する必要なく、膨大な量のデータを並列に処理する方法です。

map関数はデータを取り込み、結果を生成します。結果はバリアに保持されます。この関数は、多数の同じマップタスクと並行して実行できます。次に、データセットをスカラー値に減らすことができます。

したがって、SQL ステートメントのように考えると、

SELECT SUM(salary)
FROM employees
WHERE salary > 1000
GROUP by deptname

mapを使用して、給与が 1000 を超える従業員のサブセットを取得できます。このマップは、バリアにグループ サイズのバケットを出力します。

Reduceは、これらの各グループを合計します。結果セットを提供します。

グーグルペーパーの私の大学の研究ノートからこれを拾っただけです

于 2008-08-26T22:21:28.910 に答える
35
  1. 大量のデータを取る
  2. すべてのデータムを別の種類のデータムに変換する何らかの変換を実行します
  3. それらの新しいデータをさらに単純なデータに結合する

ステップ 2 はマップです。ステップ3はReduceです。

例えば、

  1. 道路上の一対の圧力計で 2 つのインパルス間の時間を取得する
  2. それらの時間をメートルの距離に基づいて速度にマッピングします
  3. それらの速度を平均速度まで下げる

MapReduce が Map と Reduce に分かれている理由は、異なる部分を簡単に並行して実行できるためです。(特に、Reduce に特定の数学的特性がある場合)。

MapReduce の複雑で適切な説明については、Google の MapReduce Programming Model -- Revisited (PDF)を参照してください。

于 2008-08-26T20:04:46.477 に答える
22

MAP と REDUCE は、人間が最後の恐竜を殺した時代からの古い Lisp 関数です。

名前、そこに住んでいる人の数、都市の規模に関する情報を含む都市のリストがあるとします。

(defparameter *cities*
  '((a :people 100000 :size 200)
    (b :people 200000 :size 300)
    (c :people 150000 :size 210)))

ここで、人口密度が最も高い都市を見つけたいと思うかもしれません。

まず、MAP を使用して都市名と人口密度のリストを作成します。

(map 'list
     (lambda (city)
         (list (first city)
               (/ (getf (rest city) :people)
                  (getf (rest city) :size))))
     *cities*)

=>   ((A 500) (B 2000/3) (C 5000/7))

REDUCE を使用して、人口密度が最大の都市を見つけることができます。

(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        '((A 500) (B 2000/3) (C 5000/7)))

 =>   (C 5000/7)

両方の部分を組み合わせると、次のコードが得られます。

(reduce (lambda (a b)
          (if (> (second a) (second b))
             a
             b))
        (map 'list
             (lambda (city)
                (list (first city)
                   (/ (getf (rest city) :people)
                      (getf (rest city) :size))))
             *cities*))

関数を紹介しましょう:

(defun density (city)
   (list (first city)
         (/ (getf (rest city) :people)
            (getf (rest city) :size))))

(defun max-density (a b)
   (if (> (second a) (second b))
          a
          b))

次に、MAP REDUCE コードを次のように記述できます。

(reduce 'max-density
        (map 'list 'density *cities*))

 =>   (C 5000/7)

MAPand REDUCE(評価は裏返し) を呼び出すので、 map reduceと呼ばれます。

于 2009-04-17T22:29:41.200 に答える
20

Googleの論文から例を見てみましょう。MapReduce の目標は、ある種のアルゴリズムで並行して動作する処理ユニットの負荷を効率的に使用できるようにすることです。例は次のとおりです。一連のドキュメント内のすべての単語とその数を抽出したいとします。

典型的な実装:

for each document
    for each word in the document
        get the counter associated to the word for the document
        increment that counter 
    end for
end for

MapReduce の実装:

Map phase (input: document key, document)
for each word in the document
    emit an event with the word as the key and the value "1"
end for

Reduce phase (input: key (a word), an iterator going through the emitted values)
for each value in the iterator
    sum up the value in a counter
end for

そのあたりで、マップ フェーズで並行して処理される "分割" で一連のドキュメントを分割するマスター プログラムが作成されます。発行された値は、ワーカーによってワーカー固有のバッファーに書き込まれます。マスター プログラムは、バッファーの処理準備が整ったことを通知されるとすぐに、他のワーカーに Reduce フェーズを実行するよう委任します。

すべてのワーカー出力 (Map または Reduce ワーカー) は、実際には分散ファイル システム (Google の場合は GFS) または CouchDB の場合は分散データベースに格納されたファイルです。

于 2008-08-26T21:47:21.037 に答える
11

MapReduceの非常に簡単で迅速な「初心者向け」の紹介は、http: //www.marcolotz.com/? p=67 で入手できます。

その内容の一部を投稿する:

まず、MapReduce はなぜ最初に作成されたのでしょうか。

基本的に、Google は大規模な計算ジョブを簡単に並列化して、ネットワーク経由で接続された多数のマシンにデータを分散できるようにするソリューションを必要としていました。それとは別に、透過的な方法でマシンの障害を処理し、負荷分散の問題を管理する必要がありました。

MapReduce の真の強みとは?

MapReduce マジックは、Map 関数と Reduce 関数のアプリケーションに基づいていると言えます。私は強く反対していることを告白しなければなりません。MapReduce の人気を高めた主な機能は、自動並列化と分散の機能とシンプルなインターフェースです。これらの要因と、ほとんどのエラーに対する透過的な障害処理が組み合わされているため、このフレームワークは非常に人気がありました。

論文のもう少しの深さ：

MapReduce は、Google の論文 (Dean & Ghemawat、2004 年 – リンクはこちら) で、並列アプローチとコモディティ コンピューター クラスターを使用してビッグ データで計算を行うためのソリューションとして最初に言及されました。Java で記述された Hadoop とは対照的に、Google のフレームワークは C++ で記述されています。このドキュメントでは、大規模なデータ セットに対する関数型プログラミングの Map および Reduce 関数を使用して、並列フレームワークがどのように動作するかについて説明します。

このソリューションには、Map と Reduce と呼ばれる 2 つの主要なステップがあり、最初と 2 番目のステップの間に、Combine と呼ばれるオプションのステップがあります。Map ステップが最初に実行され、入力キーと値のペアで計算が行われ、新しい出力キーと値が生成されます。入力キーと値のペアの形式は、必ずしも出力形式のペアと一致する必要はないことに注意してください。Reduce ステップは、同じキーのすべての値を組み立て、それに対して他の計算を実行します。その結果、この最後のステップでキーと値のペアが出力されます。MapReduce の最も簡単なアプリケーションの 1 つは、ワード カウントの実装です。

このアプリケーションの疑似コードを以下に示します。

map(String key, String value):

// key: document name
// value: document contents
for each word w in value:
EmitIntermediate(w, “1”);

reduce(String key, Iterator values):

// key: a word
// values: a list of counts
int result = 0;
for each v in values:
    result += ParseInt(v);
Emit(AsString(result));

お気づきのように、マップはレコード (この場合、レコードは行) 内のすべての単語を読み取り、その単語をキーとして、数値 1 を値として出力します。後で、reduce は同じキーのすべての値をグループ化します。例を挙げましょう。「house」という単語がレコードに 3 回出現するとします。レデューサーの入力は [house,[1,1,1]] になります。レデューサーでは、キー house のすべての値を合計し、次のキー値を出力として提供します: [house,[3]]。

これが MapReduce フレームワークでどのように見えるかのイメージを次に示します。

元の MapReduce Google ペーパーからの画像

MapReduce アプリケーションの他のいくつかの古典的な例として、次のように言うことができます。

•URLアクセス頻度のカウント

•リバース Web リンク グラフ

•分散grep

•ホストごとの項ベクトル

過剰なネットワーク トラフィックを回避するために、このホワイト ペーパーでは、フレームワークがデータの局所性を維持する方法について説明しています。これは、マップ ジョブを実行しているマシンのメモリ/ローカル ストレージにデータがあることを常に確認し、ネットワークからデータをフェッチしないようにする必要があることを意味します。マッパーのネットワーク スループットを削減することを目的として、前述のオプションのコンバイナー ステップが使用されます。コンバイナーは、特定のマシンのマッパーの出力に対して計算を実行してから、別のマシンにある可能性があるリデューサーに送信します。

このドキュメントでは、障害が発生した場合にフレームワークの要素がどのように動作するかについても説明しています。これらの要素は、論文ではワーカーおよびマスターと呼ばれます。オープンソースの実装では、より具体的な要素に分割されます。Google は論文でアプローチを説明しただけで、独自のソフトウェアをリリースしていないため、モデルを実装するために多くのオープンソース フレームワークが作成されました。例として、Hadoop や MongoDB の限定的な MapReduce 機能を挙げることができます。

ランタイムは、入力データの分割、マシンの大規模なセット全体でのプログラム実行のスケジューリング、マシン障害の処理 (もちろん透過的な方法で)、マシン間通信の管理など、専門家ではないプログラマーの詳細を処理する必要があります。 . 経験豊富なユーザーは、入力データがワーカー間で分割される方法として、これらのパラメーターを調整できます。

重要な概念:

•<strong>フォールト トレランス: マシンの障害を適切に許容する必要があります。これを実行するために、マスターは定期的にワーカーに ping を送信します。マスターが特定のワーカーから一定時間内に応答を受信しない場合、マスターはそのワーカーでの作業が失敗したと定義します。この場合、障害のあるワーカーによって完了されたすべてのマップ タスクは破棄され、別の使用可能なワーカーに渡されます。ワーカーがまだ map または reduce タスクを処理している場合も、同様のことが起こります。ワーカーがそのリデュース部分をすでに完了している場合、すべての計算は失敗した時点ですでに終了しており、リセットする必要がないことに注意してください。主な障害点として、マスターに障害が発生すると、すべてのジョブが失敗します。このため、データ構造を保存するために、マスターの定期的なチェックポイントを定義できます。

•<strong>ローカリティ: ネットワーク トラフィックを回避するために、フレームワークは、すべての入力データが計算を実行するマシンでローカルに利用できるようにします。元の説明では、レプリケーション ファクターが 3 に設定され、ブロック サイズが 64 MB の Google ファイル システム (GFS) を使用しています。これは、64 MB の同じブロック (ファイル システム内のファイルを構成するブロック) が、3 つの異なるマシンに同一のコピーを持つことを意味します。マスターはブロックがどこにあるかを知っており、そのマシンでマップ ジョブをスケジュールしようとします。それが失敗した場合、マスターはタスク入力データのレプリカの近くにマシンを割り当てようとします (つまり、データ マシンの同じラック内のワーカー マシン)。

•<strong>タスクの粒度: 各マップ フェーズが M 個のピース​​に分割され、各リデュース フェーズが R 個のピース​​に分割されると仮定すると、M と R がワーカー マシンの数よりもはるかに大きいことが理想的です。これは、多くの異なるタスクを実行するワーカーが動的負荷分散を改善するという事実によるものです。それとは別に、ワーカーが失敗した場合の回復速度が向上します (完了した多くのマップ タスクを他のすべてのマシンに分散できるため)。

•<strong>バックアップ タスク: Map または Reducer ワーカーの動作が、クラスター内の他のワーカーよりもはるかに遅い場合があります。これにより、合計処理時間が保持され、その単一の低速マシンの処理時間と等しくなる場合があります。元の論文では、MapReduce 操作が完了に近づいたときにマスターによってスケジュールされる、バックアップ タスクと呼ばれる代替方法について説明しています。これらは、進行中のタスクのマスターによってスケジュールされたタスクです。したがって、MapReduce 操作は、プライマリまたはバックアップが完了すると完了します。

•<strong>カウンター: イベントの発生をカウントしたい場合があります。このため、作成された場所をカウントします。各ワーカーのカウンター値は定期的にマスターに伝達されます。次に、マスターは、成功した map および reduce タスクのカウンター値を集約し (そうです。Pregel アグリゲーターはこの場所から来たようです)、MapReduce 操作が完了すると、それらをユーザー コードに返します。マスター ステータスでは現在のカウンター値も利用できるため、プロセスを監視している人間はプロセスの動作を追跡できます。

上記のすべての概念があれば、Hadoop は簡単に理解できると思います。元の MapReduce 記事または関連することについて質問がある場合は、お知らせください。

于 2014-11-18T11:47:08.910 に答える
4

陳腐に聞こえたくありませんが、これは非常に役に立ちました。非常に簡単です。

cat input | map | reduce > output
于 2011-07-05T14:52:54.747 に答える