MapReduceアルゴリズムをわかりやすく説明する方法

Hackbright でメンターをしているときに、技術的な背景が限られている学生に MapReduce アルゴリズムを説明するように求められたので、その仕組みを示す楽しい例を思いつきました。

MapReduce アルゴリズムの例

トランプのデッキにスペードが何枚あるかを数えたいとします。直感的な方法は、各カードを 1 枚ずつ確認し、スペードのカードがいくつあるかを数えることです。

MapReduce メソッドは次のとおりです。

1.このカードの山をすべてのプレイヤーに配布します

2. 各プレイヤーに手札にあるスペードの枚数を数えてもらい、その数を報告してもらいます。

3. プレイヤー全員から言われた数字を合計し、最良の結論を導き出します。

MapReduce アルゴリズムの背景

2004年、Googleは大量のデータを分析できるMapReduceアルゴリズムを公開しました。 「ビッグデータ」という言葉を聞くと、それは単一のマシンでは効率的に保存または分析するには大きすぎる問題を指します。 MapReduce は、コンピューティング ワークロードをさまざまなコンピュータ クラスターに分散することで、ビッグ データに関連するほとんどの分析問題を解決できます。 Hadoop は、MapReduce アルゴリズムを使用してビッグデータを管理するための最もオープン ソースな方法を提供します。 MapReduce は現在主流です。

したがって、一般的に言えば、「ビッグ データ」と聞くと、おそらく Hadoop を使用してデータを保存することを意味し、通常は MapReduce を使用してデータが抽出および取得されることを意味します。

MapReduceアルゴリズムの分割

MapReduce は 2 つの古典的な機能を組み合わせます。

マッピングは、コレクション内の各オブジェクトに同じ操作を適用します。つまり、スプレッドシート内のすべてのセルを 2 倍にしたい場合、この関数を各セルに個別に適用することがマッピングになります。

削減コレクションの要素を反復処理して複合結果を返します。つまり、表内の数値の列の合計を出力するタスクは、削減に属します。

上記のMapReduceアルゴリズムの例をもう一度見てみましょう

元の散在カードの例をもう一度見てみると、MapReduce データ分析の基本的な方法がわかります。注意: これは厳密な例ではありません。この例では、人々はコンピュータを表し、同時に作業するため、 クラスターを形成します。ほとんどの実際のアプリケーションでは、データがすでに各コンピューター上にあると想定されます。つまり、カードを配布することは MapReduce のステップではありません。 (実際、コンピューターのクラスター全体にファイルを保存する方法こそが、Hadoop の真髄です。)

カードを複数のプレイヤーに分割し、個別に数えることで、各プレイヤーが同時に数えるため、計算を並行して実行できます。これにより、同じ問題に取り組んでいる複数の人が、隣の人が何をしているかを知る必要がなくなるため、作業が分散されます。

全員にカードを数えるように指示することで、各カードを調べる作業を計画します。 彼らにスペードを渡してもらうように頼むのではなく、あなたが望むものを数字にまとめるように頼むのです。

もう一つの興味深い点は、カードが均等に分配されていることです。 MapReduce は、データがシャッフルされていることを前提としています。つまり、スペードのカードがすべて 1 人のプレイヤーに配られた場合、そのプレイヤーは他の人よりもカードを数えるのが遅くなる可能性があります。

十分な人数がいれば、「カードの山の平均はいくらか（ブラックジャックのアルゴリズム）」など、もっと興味深い質問をするのはかなり簡単でしょう。 「すべてのカードの値の合計はいくらですか？」と「カードは何枚ありますか？」という質問を組み合わせることで答えを得ることができます。この合計をカードの枚数で割ると平均が出ます。

MapReduceアルゴリズムの結論

MapReduce アルゴリズムの仕組みはこれよりもはるかに複雑ですが、分散コンピューティングを通じて大量のデータを分析するという基本的な考え方は同じです。 Facebook、NASA、あるいは小さなスタートアップであっても、MapReduce は現在、インターネットレベルのデータを分析するための主流の方法です。興味深いことに、MapReduce は 10PB を超えるデータになると速度が低下する傾向があるため、Google は今年の IO カンファレンスで、MapReduce ではもはや十分ではないと報告しました。