MapReduceまたはメモリとプロセッサの能力を超える計算（zaumiなしで試します）

MapReduceについて長い間お話ししたかったのですが、どのように見ても、それは単純に恐怖を感じるほどの考えですが、実際には多くの目的にとって非常にシンプルで便利なアプローチです。 そして、それを自分で実現することはそれほど難しくありません。

MapReduceが何であるかを理解していない人のために、私はすぐに言わなければなりません。 考え出した人のために-ここでは有用なものは何もありません。

MapReduceのアイデアが個人的にどのように生まれたのかから始めましょう（そのように呼ばれていることは知りませんでしたが、もちろん、Googleよりもずっと後で私に伝わりました）。

まず、彼女がどのように生まれたのか（アプローチが間違っていた）、次にそれを正しく行う方法について説明します。

ウィキペディア上のすべての単語を数える方法（間違ったアプローチ）

そして彼女は、おそらくどこにでも生まれました-通常の記憶が十分でないときに単語の頻度を数えるために（ウィキペディア上のすべての単語の頻度を数えるため）。 「頻度」という言葉の代わりに「出現回数」があるはずですが、簡単にするために「頻度」のままにします。

最も単純なケースでは、ハッシュ（dict、map、hash、連想配列、PHPのarray（））を作成し、その中の単語を読み取ることができます。

$dict['word1'] += 1

しかし、ハッシュの下のメモリが終了し、すべての単語の100分の1だけをカウントした場合はどうすればよいでしょうか？

メモリがなくなるまで単語の一部をカウントし、ハッシュをディスクに保存して、この問題を解決しました。 つまり、ファイルに対して1行ずつ直接：

aardvark | 5
aachen | 2

問題がありました-これらのファイルをマージする方法は？ 結局のところ、それぞれがRAM 全体を占有します。

最初は、各ファイルから最も人気のある1,000,000語のみを取り出して結合するというアイデアがありました。これはRAMに収まり、少なくともリストの一番上（最も人気のある語）をカウントします。 これはもちろん機能しましたが、数百万の下位の単語が失われ、さらに多くの単語があったことが判明しました。

ファイルをソートするというアイデアが生まれました。

次に、20個のソートされたファイルを取得し、それらのそれぞれから最初の1000行を読み取ります。それらはほぼ同じ単語（ソートされたファイル）になります。 要約して新しいハッシュを作成します。「aaa ...」などで始まる単語のみが含まれ、新しいファイルに保存されます。 次の1000行をすべて読み取ります。 そこには、ほとんどすべてのファイルに「aab ...」という言葉があります。

したがって、新しいファイルははるかに小さく形成されます。 しかし、それでも言葉は繰り返されます。 もう一度並べ替え、1000行で読み、合計します。 ほぼ正しいファイルであることがわかります（一部の単語はまだ1000行を超えている可能性があります）。数回繰り返します...最終的に、エラーが非常に少ないファイルを取得します（ただし、エラーはあります）。

退屈な、長いが、より良いオプションは発生しませんでした。

間違ったアプローチの弱点

このアプローチには1つの弱点がありました。つまり、元の20個のファイルを結合することです。 改善する方法は？

問題は、一部の単語が一部のファイルに存在しないか、1000行の異なるブロックに存在するという事実から発生します。 つまり、最初の1000行ではなく、1行だけで、同じ単語で20ファイルすべてから取得できれば、20ファイルすべてを1つのパスに結合できます。



どうやってやるの？ 一般的に、これはMergeSortアルゴリズムの最後のステップです↑ソートされたリストを結合します。 わかっている場合は、スキップしてください。

20個すべてのファイルの最初の行を取得し、最小の最初の要素（単語）を探します。ファイルを並べ替えたので、一般的にすべての要素で最小になります。 これが「aardvark」という単語だとしましょう。この20の行すべてから、この単語「aardvark」に関連するものだけを読み取ります。 そしてそこから、それを削除する場所から-それらのファイルでのみ、2行目を読みます。 繰り返しになりますが、これら20個の最小値を探しています。類推すると、さらに、すべてのファイルの最後に到達するまでです。

最も単純な形式のMapReduce

実際、10年前にGoogleが私たちの前で発明したものをMapReduceと呼んでいます。

自転車の発明は今日まで続いています。

そのため、 "foo bar baz bar"という行があり"foo bar baz bar" 。

出力で受け取る必要があります： { foo: 1, bar: 2, baz: 1 } 。

最初のステップでは、 行を取得してそれを単語に分割し、そのような配列を作成します（または、「タプル」-「タプル」）。

[ 'foo', 1 ]
[ 'bar', 1 ]
[ 'baz', 1 ]
[ 'bar', 1 ]

（次に、明確になる場合は括弧と引用符を省略します）
それらを受け取り、ソートします。

bar, 1
bar, 1
baz, 1
foo, 1

barは2回連続して表示されるため、次の形式で結合します。

bar, (1,1)
baz, (1)
foo, (1)

(1,1)は一種のネストされた配列です。つまり、技術的には- ["bar", [1,1]]です。

次に、配列の2番目の要素を追加します 。 取得するもの：

bar, 2
baz, 1
foo, 1

まさに彼らが望んだもの。

主な質問は、ヤギのボタンのアコーディオンのために何ですか...または私たちはここで何をしたのですか？

過去に戻る

2行のみが収まり、1分あたり1行に1つの操作しか実行できないコンピューターがあると想像してください。 （笑いを止めるには、少なくとも1回ウィキペディアのすべての単語を数えた後、設定されたメモリ制限で笑う権利があります。ギグがいくつあるとしても、それはまだ適合しません。

（ "foo bar baz bar" ）この方法で2つのファイルを作成できます。

file1.txt
[ 'bar', 1 ]
[ 'foo', 1 ]

file2.txt
[ 'bar', 1 ]
[ 'baz', 1 ]


メモリには2行あります。すべてが正常であり、メモリの制限に適合しています。

MergeSortの手順を使用して、これらのファイルを行ごとに結合できます。

bar, (1,1)
baz, (1)
foo, (1)

同時に、メモリには2つのファイルの2行のみが保存されます-必要以上ではありません。

実際、私たちが行ったことはすでにMapReduceです。

単語（ , 1 ） , 1配列を生成するステップ - このステップは「マップ」と呼ばれます。
(1,1)を要約するステップは、 「縮小」ステップです。

残りのステップは、アルゴリズム自体によって実行されます（MergeSortを介した並べ替えと結合）。

マップ、削減？ これは何ですか

これらのステップ自体は、「マップ」の場合はユニットの発行、「リデュース」の場合は折り畳みで構成されるとは限りません。 これらは、単に何かを受け入れたり、提供したりできる機能です。 目的に応じて。

この場合、「Map」は、1つの単語を取り、 (, 1)を生成する、作成した関数です。

また、「Reduce」は、配列(, (1,1))を取り、 (, 2)を生成する、作成した関数です。

単純にPythonに入れる：

  words = ["foo"、 "bar"、 "baz"]
 def map1（単語）：
   return [word、1]

 arr = ["foo"、[1,1]]
 def reduce1（arr）：
   return [arr [0]、sum（arr [1]）] 

またはPHP：

  $単語=配列（ "foo"、 "bar"、 "baz"）
関数map1（$ word）{
   return array（$ word、1）;
 }

 arr =配列（ "foo"、配列（1,1））
関数reduce1（arr）{
   return array（$ arr [0]、array_sum（$ arr [1]））;
 } 

したがって、メモリ制限をバイパスしましたが、速度制限をバイパスする方法はありますか？

このようなコンピューターが2台あると想像してください。 それらのそれぞれに最初の行を与え、最初に言います（より正確には、MapReduceは言います）：奇数の場所で単語だけを数え、そして2番目の-偶数の場所でのみ単語を数えます。

最初の生成物：
"foo bar baz bar":
foo, 1
baz, 1

2番目は以下を生成します。
"foo bar baz bar":
bar, 1
bar, 1

上記のように（より正確にはMapReduce）両方から結果を取得し、ソートしてからMergeSortを実行します。

bar, (1,1)
baz, (1)
foo, (1)

1台のコンピューターを数えたときとまったく同じ結果です！

（MapReduce）は2台のコンピューターに再度配布しています。1行目は奇数行のみを提供し、2行目は偶数行を提供し、各コンピューターにReduceステップ（2桁目を追加）を依頼します。

実際、これらの行が互いに独立していることは明らかなので、結果は再び必要なものになります。

主なことは、2台のコンピューターが並行して動作し、そのため、 1台のコンピューターの2倍の速度で動作することです（ただし、1台のコンピューターから別のコンピューターへのデータ転送にかかる時間のロスは除く）

早退

ふふ！ したがって、MapReduce-より高速に実行する必要があるか、十分なメモリがない（またはそのいずれか）ものを読み取るために必要です。

より興味深い例は、人気による並べ替え（カスケード）です。

ウィキペディア上の単語の数を数えながら、同時に人気の高いものから最も人気のないものまで、その人気の逆順でリストを作成したいとします。

ウィキペディアのすべての単語がメモリに収まらないことは明らかです。そして、戻り値のソートのために、この巨大な配列はメモリに収まりません。 MapReduceのカスケードが必要です。最初のMapReduceの結果は、2番目のMapReduceの入力に送られます。

正直に言うと、「カスケード」という言葉が正しいかどうかはわかりません。具体的にはMapReduceに当てはまります。 私はこの言葉を他の人にはできないように説明しているので、この言葉を自分で使っています（言葉の滝の結果はMapReduceに落ち、すぐに2番目のMapReduceに流れます）。

さて、単語を数える方法-私たちはすでに知っています：

「フーバーバズフー」

私たちが書いたMapステップは以下を生成します。
foo, 1
bar, 1
baz, 1
foo, 1

さらにMapReduceは（プログラマとしてのあなたではなく、それ自体）それらを以下に結合します：
bar, (1)
baz, (1)
foo, (1,1)

そして、私たちが書いたReduceステップは以下を生成します
bar, 1
baz, 1
foo, 2

ここで、ウィキペディア全体を検討し、この配列には何十億もの単語が含まれていると想像してください。 メモリ内で並べ替えることはできません。 別のMapReduceを見てみましょう。今回はMapがこのトリックを実行します。

[, 15] -> map（）戻り値-> [-15, ]
[2, 15] -> map（）戻り値-> [-15, 2]
[3, 120] -> map（）戻り値-> [-120, 3]
[4, 1] -> map（）戻り値-> [-1, 4]

これは何のためですか？

MapReduceは、Reduceに進む前に、これらのすべての配列を配列の最初の要素（負の数に等しい）で並べ替えます。 MapReduceは、データの全量がメモリに収まらない場合でもソートすることができます。これが素晴らしい点です。 ウィキペディアのすべての単語について、 arsort($words)実行することはできませんが、MapReduceは実行できます。

数字の前にマイナスがあるのはなぜですか？

MapReduceは常に昇順でソートされますが、降順でソートする必要があるためです。 それでは、昇順で並べ替えを使用して、数値を降順に並べ替える方法はありますか？ ソートの前にマイナス1を掛け、再度マイナス1を掛けます。

昇順の正の数：1、15、120
昇順の負の数： -120, -15, -1 （必要なのはマイナス記号のみで、-1を掛けて単純に削除します）

次のことがReduceの入力になります：

-120, (3)
-15, (, 2) <-- - MergeSort !
-1, (4)

素敵ですが、2つの単語の「頻度」は15で、MergeSortによってグループ化されました。 修正します。

ここで、Reduceでは、最初の数値に-1を掛けるだけで、最初の行に1つの配列、2番目に2つの配列、3番目に1つの配列を生成するだけです。

実際、MapReduceを使用する実施形態によっては、必要な出力配列が1つだけであるため、Reduceステップで2つの配列を出力できない場合があります。その後、プログラムのReduceステップの後に実行してください。

取得するもの：

120, 3
15, ,
15, 2
1, 4

美人！ 必要なもの。

繰り返しますが、ここで回避した主なものは、例が4行であり、Wikipediaには記憶に収まらない数十億の単語があることを思い出してください。

簡単なMapReduceを作成して遊ぶ方法は？

PHPの場合 ： 最も単純な例 。
Pythonは 最も単純な例です （Pythonバージョンについては以下を参照）。

コードでは、ファイルとMergeSortの意味で、黒で多かれ少なかれ完全なMapReduceを作成するために何をどこに置くべきかを示しました。 ただし、これはいわば、MapReduceがどのように動作するかを理解するための参照実装です。 これはまだMapReduceです。具体的には、メモリの観点から見たこの実装は、通常のハッシュよりも有益ではありません。

PHPを選択しましたが、ほとんどのプログラマーがPHPを読み、目的の言語に翻訳するのが簡単になるため、これらの目的には最も妥当ではありません。

ヒントとチート

はい、配列（json_encode）のJSON表現を1行ずつ保存することをお勧めします-単語のスペース、Unicode、数字、データ型の問題は、次のようになります。
["foo", 1]
["bar", 1]
["foo", 1]

ヒント-Python では、 MergeSortがすでに実装している最後のステップはheapq.merge(*iterables)です。

つまり、10個のファイルをJSON表現で接続するだけで十分です。

  items = list（ファイル内のファイル名のitertools.imap（json.loads、open（filename）））
 heapq.merge内のアイテム（*アイテム）：
   ＃.... reduce（item）.... 

MergeSortを実装したPHPでは、50行にわずらわなければならないと思います。 もちろん、コメントの中でより良い選択肢を教えてくれる人がいない限り。

Pythonでは、MapReduceのyieldと__iter__非常に興味深いことを行うことができます！ たとえば、次のとおりです。

  x = MapReduce（）
 「foo bar bar」の単語の場合.split（）：
    x.send（（word、1））

単語の場合、xにあるもの：
   印刷語、合計（1） 

class MapReduce -あなたは自分でそれを書かなければなりません（最も単純な作業フォームで24行以内に保たれたかもしれません-多分少ないです-iter_groupを単純化することはPHPの例のgroup_tuples_by_first_element関数に類似しています）。

注意-この方法はMapReduceにとって古典的ではなく、多くのマシンで並列化することは困難です（ただし、この方法では、使用可能なメモリ以上のデータボリュームで作業することは非常に簡単です）。 map1とreduce1が関数であるmap_reduce(source_data, map1, reduce1)メソッドmap_reduce(source_data, map1, reduce1) 、より正確です。

HadoopでのMapReduceの実装は、最も一般的なソリューションです。 （私はそれを試していないが、最も人気があるものを知っているだけだ）。

あとがき

だから、ここで、ZaumiのないMapReduceについての私の話が役に立つことを願っています。

MapReduceは、大規模な計算に非常に役立ちます。 SQLクエリのほとんどは、いくつかのテーブルにさえ、MapReduce + join_iteratorに分解するのはそれほど難しくありません（詳細は後ほど説明します）。

強みがある場合-次のトピックでは、MapReduceを使用して一般的な単語よりも興味深いタスクを検討する方法について説明します-たとえば、インターネット上のリンクの読み方、他の単語の文脈での単語の頻度、都市の人々、数百の企業の価格表による製品など。

はい、みんなここにいます！ MapReduceはGoogleが特許を取得していますが、保護の目的で使用されています。この方法を公式に許可したHadoopと同じです。 だから-注意して扱ってください。

パート2：より高度な例

ヨイハジ
いつものように、Habrから
2010

（いつか簡単に説明することを学びます....）