MapReduce

MapReduceは、クラスター上で並列分散アルゴリズムを用いてビッグデータセットを処理および生成するためのプログラミングモデルおよび関連実装です。[ 1 ] [ 2 ] [ 3 ]

MapReduceプログラムは、フィルタリングとソート（例えば、生徒を名前順にキューに振り分け、名前ごとにキューを1つずつ割り当てる）を実行するマッププロシージャと、集計操作（例えば、各キューの生徒数をカウントし、名前の頻度を算出する）を実行するリデュースメソッドで構成されています。「MapReduceシステム」（「インフラストラクチャ」または「フレームワーク」とも呼ばれます）は、分散サーバーをマーシャリングし、様々なタスクを並列実行し、システムの様々な部分間のすべての通信とデータ転送を管理し、冗長性とフォールトトレランスを提供することで、処理を調整します。

このモデルは、split-apply-combine戦略をデータ分析向けに特殊化したものである。[ 4 ] これは関数型プログラミングでよく使われるmap関数とreduce関数にヒントを得ているが、[ 5 ] MapReduceフレームワークにおけるそれらの目的は、元の形式とは異なる。[ 6 ] MapReduceフレームワークの重要な貢献は、map関数とreduce関数そのもの（例えば、1995 Message Passing Interface標準の[ 7 ] reduce [ 8 ]操作やscatter [ 9 ]操作に似ている）ではなく、並列化によって様々なアプリケーションで実現されるスケーラビリティと耐障害性である。そのため、 MapReduceのシングルスレッド実装は通常、従来の（MapReduce以外の）実装よりも高速ではなく、何らかの利点は通常、マルチプロセッサハードウェア上のマルチスレッド実装でのみ見られる。[ 10 ]このモデルは、最適化された分散シャッフル操作（ネットワーク通信コストを削減する）とMapReduceフレームワークのフォールトトレランス機能が作用する場合にのみ有益です。通信コストの最適化は、優れたMapReduceアルゴリズムにとって不可欠です。[ 11 ]

MapReduceライブラリは、様々なプログラミング言語で書かれており、最適化のレベルも様々です。分散シャッフルをサポートする人気のオープンソース実装は、 Apache Hadoopの一部です。MapReduceという名称は、もともとGoogle独自の技術を指していましたが、後に一般的な商標になりました。2014年までに、Googleは主要なビッグデータ処理モデルとしてMapReduceを使用しなくなり、 [ 12 ] Apache Mahoutの開発は、完全なマップとリデュース機能を組み込んだ、より高性能でディスク指向の少ないメカニズムへと移行しました。[ 13 ]

概要

MapReduceは、多数のコンピュータ（ノード）を使用して大規模なデータセット全体で並列化可能な問題を処理するためのフレームワークです。これらのコンピュータ（ノード）は、総称してクラスタ（すべてのノードが同じローカルネットワーク上にあり、同様のハードウェアを使用している場合）またはグリッド（ノードが地理的および管理的に分散されたシステム間で共有され、より異機種混合のハードウェアを使用している場合）と呼ばれます。処理は、ファイルシステム（非構造化）またはデータベース（構造化）のいずれかに保存されたデータに対して行うことができます。MapReduceはデータの局所性を活用し、通信オーバーヘッドを最小限に抑えるために、保存場所の近くでデータを処理します

MapReduce フレームワーク (またはシステム) は通常、次の 3 つの操作 (またはステップ) で構成されます。

  1. マップ:各ワーカーノードはmap関数をローカルデータに適用し、出力を一時ストレージに書き込みます。マスターノードは、冗長な入力データのコピーが1つだけ処理されることを保証します。
  2. シャッフル:ワーカー ノードは、関数によって生成された出力キーに基づいてデータを再配布しmap、1 つのキーに属するすべてのデータが同じワーカー ノードに配置されるようにする。
  3. 削減:ワーカー ノードは、キーごとに出力データの各グループを並列に処理するようになりました。

MapReduceは、マップ操作とリダクション操作の分散処理を可能にします。各マッピング操作が互いに独立している限り、マップ操作は並列に実行できます。ただし、実際には、独立したデータソースの数や各ソースの近くにあるCPUの数によって制限されます。同様に、同じキーを共有するマップ操作のすべての出力が同じリダクションに同時に渡されるか、リダクション関数が結合的である場合、複数の「リダクション」がリダクションフェーズを実行できます。このプロセスは、リダクション処理の複数のインスタンスを実行する必要があるため、よりシーケンシャルなアルゴリズムと比較して非効率的であるように見えることがよくありますが、MapReduceは単一の「コモディティ」サーバーが処理できるよりもはるかに大きなデータセットに適用できます。大規模なサーバーファームでは、MapReduceを使用することで、わずか数時間でペタバイト規模のデータをソートできます。 [ 14 ]並列処理により、操作中にサーバーやストレージの部分的な障害から回復する可能性も提供されます。1つのマッパーまたはリデューサーに障害が発生した場合、入力データがまだ利用可能であると仮定すると、作業を再スケジュールできます。

MapReduce を別の視点から見ると、5 段階の並列分散計算となります。

  1. Map() 入力を準備します- 「MapReduce システム」は Map プロセッサを指定し、各プロセッサが処理する入力キーK1を割り当て、そのキーに関連付けられたすべての入力データをそのプロセッサに提供します。
  2. ユーザー提供の Map() コードを実行します– Map() は各K1キーに対して 1 回だけ実行され、キーK2別に整理された出力を生成します。
  3. Map 出力を Reduce プロセッサに「シャッフル」します。MapReduce システムは、Reduce プロセッサを指定し、各プロセッサが処理するK2キーを割り当て、そのキーに関連付けられたすべての Map 生成データをそのプロセッサに提供します。
  4. ユーザー提供の Reduce() コードを実行します。Reduce() は、Map ステップで生成されたK2キーごとに 1 回だけ実行されます。
  5. 最終出力を生成します– MapReduce システムはすべての Reduce 出力を収集し、K2でソートして最終結果を生成します。

これら 5 つのステップは、論理的には順番に実行されると考えられます。各ステップは、前のステップが完了した後にのみ開始されますが、実際には、最終結果に影響がない限り、これらのステップを交互に実行できます。

多くの場合、入力データは既に複数の異なるサーバーに分散（「シャーディング」）されている可能性があります。その場合、ローカルに存在する入力データを処理するMapサーバーを割り当てることで、ステップ1を大幅に簡素化できる場合があります。同様に、処理が必要なMap生成データに可能な限り近いReduceプロセッサを割り当てることで、ステップ3を高速化できる場合があります。

論理ビュー

MapReduceのMap関数とReduce関数はどちら も、（キー、値）のペアで構造化されたデータに対して定義されています。Map関数は、あるデータドメイン内の型を持つ1つのデータペアを受け取り、別のドメイン内のペアのリストを返します

Map(k1,v1)→list(k2,v2)

Map関数k1は、入力データセット内のすべてのペア（キーは ）に並列に適用されます。これk2により、呼び出しごとにペア（キーは ）のリストが生成されます。その後、MapReduceフレームワークは、すべてのリストから同じキー（k2）を持つすべてのペアを収集し、それらをグループ化して、キーごとに1つのグループを作成します

次に、Reduce関数が各グループに並列に適用され、同じドメイン内の値のコレクションが生成されます。

Reduce(k2, list (v2))→ list((k3, v3))[ 15 ]

各Reduce呼び出しは通常、1つのキーと値のペア、または空の戻り値のいずれかを生成しますが、1回の呼び出しで複数のキーと値のペアを返すこともできます。すべての呼び出しの戻り値は、目的の結果リストとして収集されます。

このようにMapReduceフレームワークは、（キー、値）ペアのリストを別の（キー、値）ペアのリストに変換します。[ 16 ]この動作は、任意の値のリストを受け取り、mapによって返されるすべての値を組み合わせた単一の値を返す、典型的な関数型プログラミングのmapとreduceの組み合わせとは異なります。

MapReduceを実装するには、マップとリデュースの抽象化の実装は必須ですが、それだけでは十分ではありません。MapReduceの分散実装には、マップフェーズとリデュースフェーズを実行するプロセスを接続する手段が必要です。これは分散ファイルシステムなどです。他の方法としては、マッパーからリデューサーへの直接ストリーミングや、マッピングプロセッサがクエリを実行するリデューサーに結果を提供するといった方法があります。

例

標準的なMapReduceの例では、文書セット内の各単語の出現回数をカウントします。[ 17 ]

function map (String name, String document): // name: 文書名// document: 文書内の各単語 wの文書内容 : 放出（w, 1） function reduce (String word, Iterator partialCounts): // word: 単語// partialCounts: 集計された部分カウントのリスト 合計 = 0 partialCounts内の各PCについて: 合計 += pc 放出する（単語、合計）

ここでは、各文書が単語​​に分割され、各単語はmap関数によってカウントされ、その単語が結果のキーとして使用されます。フレームワークは、同じキーを持つすべてのペアをまとめ、同じreduce呼び出しに渡します。したがって、この関数は、入力値をすべて合計するだけで、その単語の出現回数を計算できます。

別の例として、11億人のデータベースで、年齢に応じて個人の平均ソーシャルコンタクト数を計算したいとします。SQLでは、このようなクエリは次のように表現できます。 

SELECT age , AVG ( contacts ) FROM social . person GROUP BY age ORDER BY age

MapReduce を使用すると、K1キー値は 1 から 1100 までの整数 (それぞれ 100 万件のレコードのバッチを表す) になり、K2キー値は人の年齢 (年) になり、この計算は次の関数を使用して実行できます。 

関数マップは、1から1100までの整数K1を入力とし 、これは100万のsocial.personレコードのバッチを表します。K1 バッチ内の各social.personレコードについて、Yをその人の年齢とし 、Nをその人の連絡先の数とし、 1つの出力レコード(Y,(N,1)) を生成します。繰り返し、関数の終了関数Reduceは入力です:年齢(歳) Y 各入力レコード(Y,(N,C))に対して SにN*Cの合計を累積するC new にC の合計 を 累積し、 A を S/C newとして繰り返し、1つの出力レコード(Y,(A,C new )) を生成します。関数の終了

なお、 Reduce関数では、Cは合計 N 件の連絡先を持つ人の数です。したがって、Map関数では、すべての出力ペアが 1 人の連絡先を参照するため、 C=1 と記述するのが自然です。

MapReduceシステムは1100個のMapプロセッサを整列させ、それぞれに対応する100万件の入力レコードを提供します。Mapステップでは、 Y値が例えば8から103の範囲にある11億件の(Y,(N,1))レコードが生成されます。その後、MapReduceシステムは、年齢ごとの平均が必要であるため、キーと値のペアのシャッフル操作を実行して96個のReduceプロセッサを整列させ、それぞれに対応する数百万件の入力レコードを提供します。Reduceステップでは、わずか96個の出力レコード(Y,A)のみに大幅に削減されたセットが生成され、最終結果ファイルにYでソートされて格納されます。

処理を複数回削減する場合、レコード内のカウント情報は重要です。レコードのカウントを追加しないと、計算された平均値は誤ったものになります。例えば、次のようになります。 

-- マップ出力 #1: 年齢、連絡先の数 10, 9 10, 9 10, 9 
-- マップ出力2: 年齢、連絡先の数 10, 9 10, 9 
-- マップ出力3: 年齢、連絡先の数 10, 10

ファイル1と2を削減すると、10歳の人の連絡先が平均9件（(9+9+9+9+9)/5）の新しいファイルが作成されます 

-- ステップ 1 を削減: 年齢、連絡先の平均 10, 9

ファイル#3で削減すると、既に参照したレコード数が失われるため、10歳の人の連絡先の平均数は9.5件（(9+10)/2）になりますが、これは誤りです。正解は9.1 66 = 55 / 6 = (9×3+9×2+10×1)/(3+2+1)です。

データフロー

ソフトウェアフレームワークのアーキテクチャは、オープンクローズ原則に準拠しており、コードは変更不可能な凍結スポットと拡張可能なホットスポットに効果的に分割されます。MapReduceフレームワークの凍結スポットは、大規模な分散ソートです。アプリケーションが定義するホットスポットは次のとおりです

  • 入力リーダー
  • マップ関数​
  • パーティション関数​
  • 比較機能​
  • 削減関数​
  • 出力ライター

入力リーダー

入力リーダーは入力を適切なサイズの「分割」（実際には通常64MBから128MB）に分割し、フレームワークは各Map関数に1つの分割を割り当てます。入力リーダーは安定したストレージ（通常は分散ファイルシステム）からデータを読み取り、キーと値のペアを生成します

一般的な例としては、テキスト ファイルがいっぱい入ったディレクトリを読み取り、各行をレコードとして返します。

マップ関数

マップ関数は、一連のキーと値のペアを受け取り、それぞれを処理して、0個以上の出力キーと値のペアを生成します。マップの入力と出力の型は、互いに異なる場合があり、多くの場合異なります

アプリケーションが単語数をカウントする場合、map関数は行を単語に分割し、各単語のキーと値のペアを出力します。各出力ペアには、単語がキーとして、その単語が行内に出現する回数が値として含まれます。

パーティション関数

各Map関数の出力は、シャーディングのためにアプリケーションのパーティション関数によって特定のリデューサーに割り当てられます。パーティション関数にはキーとリデューサーの数が与えられ、目的のリデューサーのインデックスを返し ます

典型的なデフォルトは、キーをハッシュ化し、そのハッシュ値をリデューサーの数で割った値を使用することです。負荷分散のために、シャードごとにほぼ均一なデータ分散を実現するパーティション関数を選択することが重要です。そうしないと、MapReduce操作が低速なリデューサー（つまり、不均一に分割されたデータの大部分をリデューサーに割り当てている）の終了を待つ間、処理が遅延する可能性があります。

mapステージとreduceステージの間では、データがシャッフル（並列ソート／ノード間で交換）され、データを生成したmapノードからreduce先のシャードへ移動します。ネットワーク帯域幅、CPU速度、生成されるデータ、mapおよびreduce計算にかかる時間によっては、シャッフルに要する時間が計算時間よりも長くなる場合があります。

比較関数

各Reduceの入力は、 Mapが実行されたマシンから取得され、アプリケーションの比較関数 を使用してソートされます

Reduce関数

フレームワークは、ソートされた順序で一意のキーごとにアプリケーションのReduce関数を1回呼び出します。Reduce関数は、そのキーに関連付けられた値を反復処理し、0個以上の出力を生成します

単語カウントの例では、Reduce関数は入力値を受け取り、それらを合計して、単語と最終的な合計の単一の出力を生成します。

出力ライター

出力ライターは、R ​​educeの出力を安定ストレージに 書き込みます

理論的背景

モノイドの性質は、MapReduce操作の妥当性を保証するための基礎となります。[ 18 ] [ 19 ]

Algebirdパッケージ[ 20 ]では、Map/ReduceのScala実装にモノイドクラス型が明示的に必要です。[ 21 ]

MapReduce の操作は、マッピングされる入力データのタイプAと、削減される出力データの タイプBの 2 つのタイプを扱います。

Map操作は、タイプAの個々の値を受け取り、各a:Aに対して値b:Bを生成します。Reduce操作には、タイプBの値に対して定義されたバイナリ操作が必要です。この操作は、利用可能なすべてのb:Bを単一の値に 折りたたむことから構成されます。

基本的な要件の観点から見ると、MapReduce操作は、削減対象のデータを任意に再グループ化する機能を備えている必要があります。この要件は、操作の2つの特性に相当します。

  • 結合法則: ( x • y ) • z = x • ( y • z )
  • すべてのx:Bに対してe • x = x • e = xとなる中立元eの存在。

2 番目の特性は、複数のノードに並列化された場合に、処理するデータがないノードが結果に影響を与えないことを保証します。

これら2つの特性は、演算•を持ち中立要素eを持つ型Bの値にモノイド( B ,•, e )を持つことに等しい。

型Aの値には制約はありません。任意の関数A → B をMap演算に使用できます。これは、異型写像A* → ( B , •, e )が存在することを意味します。ここでA*はクリーネスター（Kleene star ）を表します。 これはA上のリスト型としても知られています。

Shuffle操作自体は MapReduce の本質とは関係ありませんが、クラウド上で計算を分散するために必要です。

上記から、すべてのバイナリReduce操作がMapReduceで動作するわけではないことがわかります。以下に反例を示します。

  • サブツリーからツリーを構築する: この操作は結合的ではなく、結果はグループ化に依存します。
  • 平均の直接計算: avgも結合的ではありません (中立要素がありません)。平均を計算するには、モーメントを計算する必要があります。

パフォーマンスに関する考慮事項

MapReduceプログラムは必ずしも高速であるとは限りません。このプログラミングモデルの主な利点は、プラットフォームの最適化されたシャッフル操作を利用し、プログラムのMap部分とReduce部分のみを記述すればよいことです。しかし実際には、MapReduceプログラムの作成者はシャッフル処理を考慮する必要があります。特に、パーティション関数とMap関数によって書き込まれるデータ量は、パフォーマンスとスケーラビリティに大きな影響を与える可能性があります。Combiner関数などの追加モジュールは、ディスクに書き込まれるデータ量とネットワーク経由で送信されるデータ量を削減するのに役立ちます。MapReduceアプリケーションは、特定の状況下では線形以下の速度向上を実現できます。[ 22 ]

MapReduceアルゴリズムを設計する際には、計算コストと通信コストの適切なトレードオフ[ 11 ]を選択する必要があります。通信コストは計算コストを支配し[ 11 ] 、 [ 22 ]、多くのMapReduce実装はクラッシュリカバリのためにすべての通信を分散ストレージに書き込むように設計されています。

MapReduceのパフォーマンスチューニングにおいては、マッピング、シャッフル、ソート（キーによるグループ化）、そしてリデュース処理の複雑さを考慮する必要があります。マッパーによって生成されるデータ量は、マッピングとリデュース処理の間で計算コストの大部分を左右する重要なパラメータです。リデュース処理には、非線形の複雑さを伴うソート（キーのグループ化）が含まれます。したがって、パーティションサイズを小さくするとソート時間は短縮されますが、リデューサーの数を多くすることは現実的ではないため、トレードオフが生じます。分割ユニットサイズの影響はわずかです（特に不適切なサイズ、例えば1MB未満を選択しない限り）。一部のマッパーがローカルディスクから負荷を読み取ることによるメリットは、平均的にはわずかです。[ 23 ]

プロセスがすぐに完了し、データが単一のマシンまたは小規模なクラスターのメイン メモリに収まる場合、通常、MapReduce フレームワークを使用しても効果的ではありません。これらのフレームワークは、計算中にノード全体が失われた場合に回復するように設計されているため、中間結果を分散ストレージに書き込みます。このクラッシュ回復はコストが高く、計算に多数のコンピューターが関与し、計算の実行時間が長い場合にのみ効果があります。数秒で完了するタスクは、エラーが発生した場合に再開するだけで済みますが、クラスターのサイズが大きくなると、少なくとも 1 台のマシンに障害が発生する可能性が急速に高まります。このような問題では、すべてのデータをメモリに保持し、ノード障害時に計算を単純に再開する実装や、データが十分に小さい場合は非分散ソリューションの方が、MapReduce システムよりも高速になることがよくあります。

流通と信頼性

MapReduce は、データセットに対する多数の操作をネットワーク内の各ノードに分割することで信頼性を実現します。各ノードは、完了した作業とステータスの更新を定期的に報告することが求められます。あるノードがその間隔よりも長い間沈黙した場合、マスターノード（Google File Systemのマスターサーバーに類似）はそのノードをデッドノードとして記録し、そのノードに割り当てられた作業を他のノードに送信します。個々の操作では、並行して競合するスレッドが実行されていないことを確認するために、ファイル出力に名前を付けるためのアトミック操作が使用されます。ファイルの名前を変更する場合、タスク名に加えて別の名前でコピーすることもできます（副作用を考慮）。

削減操作もほぼ同じように動作します。並列処理の特性が劣るため、マスターノードは、処理対象のデータを保持しているノードと同じノード、または同じラックで削減操作をスケジュールしようとします。この特性は、データセンターのバックボーンネットワーク全体の帯域幅を節約できるため、望ましいものです。

実装は必ずしも高い信頼性を備えているわけではありません。例えば、Hadoopの旧バージョンでは、 NameNodeが分散ファイルシステムの単一障害点でした。Hadoopの最新バージョンでは、「NameNode」のアクティブ/パッシブフェイルオーバーにより高可用性が実現されています。

用途

MapReduceは、分散パターンベース検索、分散ソート、ウェブリンクグラフ反転、特異値分解[ 24 ] 、ウェブアクセスログ統計、転置インデックス構築、ドキュメントクラスタリング、機械学習[ 25 ]、統計的機械翻訳など、幅広いアプリケーションで役立ちます。さらに、MapReduceモデルは、マルチコアおよびメニーコアシステム[ 26]、[ 27 ] 、 [ 28 ]、デスクトップグリッド[ 29 ] 、 マルチクラスタ[ 30 ] 、ボランティアコンピューティング環境[ 31 ] 、動的クラウド環境[ 32 ] 、モバイル環境[ 33 ] 、高性能コンピューティング環境[ 34 ]など、さまざまなコンピューティング環境に適応されています

Googleでは、MapReduceを用いてGoogleのワールドワイドウェブのインデックスを完全に再生成しました。これは、インデックスの更新や様々な分析を行う従来のアドホックプログラムに取って代わりました。 [ 35 ]その後、Googleの開発はPercolator、FlumeJava [ 36 ]、MillWheelといった技術へと移行しました。これらの技術はバッチ処理ではなくストリーミング処理と更新を提供し、インデックス全体を再構築することなく「ライブ」検索結果を統合できるようになりました。[ 37 ]

MapReduceの安定した入力と出力は通常、分散ファイルシステムに保存されます。一時データは通常、ローカルディスクに保存され、リデューサーによってリモートで取得されます。

批判

新規性の欠如

並列データベースとシェアード・ナッシング・アーキテクチャを専門とするコンピュータ科学者のDavid DeWitt氏とMichael Stonebraker氏は、MapReduceが使用できる問題の広範さについて批判的である。[ 38 ]彼らはMapReduceのインターフェースが低レベルすぎると述べ、支持者が主張するようなパラダイムシフトを本当に実現しているのかどうか疑問視した。 [ 39 ]彼らはMapReduce支持者の新規性の主張に異議を唱え、20年以上前から存在する先行技術の例としてTeradataを挙げた。また、彼らはMapReduceプログラマーとCODASYLプログラマーを比較し、どちらも「低レベルのレコード操作を実行する低レベル言語で記述している」と指摘した[ 39 ] MapReduceの入力ファイルの使用とスキーマサポートの欠如は、 Bツリーやハッシュパーティションなどの一般的なデータベースシステム機能によって実現されるパフォーマンスの向上を妨げますが、 Pig（またはPigLatin）、Sawzall、Apache Hive、[ 40 ] HBase [ 41 ]およびBigtable [ 41 ] [ 42 ]などのプロジェクトはこれらの問題の一部に対処しています。

グレッグ・ジョーゲンセンはこれらの見解を否定する記事を書いた。[ 43 ]ジョーゲンセンは、MapReduceはデータベースとして使用されることを想定して設計されたものではないため、デウィットとストーンブレーカーの分析はすべて根拠がないと主張している。

デウィットとストーンブレーカーはその後、2009年にHadoopのMapReduceとRDBMSのアプローチをいくつかの特定の問題でパフォーマンスを比較した詳細なベンチマーク研究を発表しました。[ 44 ]彼らは、リレーショナルデータベースは、特に複雑な処理や企業がデータを使用するような多くの種類のデータ使用において真の利点を提供するが、MapReduceは単純な処理タスクや1回限りの処理タスクにはユーザーにとって導入しやすいかもしれないと結論付けました。

MapReduceプログラミングパラダイムは、ダニー・ヒリスの1985年の論文[ 45 ]でも説明されており、コネクションマシンでの使用を想定していました。そこでは「xapping/reduction」 [ 46 ]と呼ばれ、mapとreduceの両方を高速化するためにマシンの特殊なハードウェアに依存していました。コネクションマシンで最終的に使用された方言である1986年のStarLispは並列*mapとreduce!![ 47 ]を備えており、これは非並列と[ 48 ]が組み込まれた1984年のCommon Lispに基づいています。[ 49 ]コネクションマシンのハイパーキューブアーキテクチャが時間内に実行するために使用するツリー状のアプローチ[ 49 ]は、Googleの論文で先行研究として言及されているアプローチと実質的に同じです。[ 3 ] : 11mapreducereduce

2010年、GoogleはMapReduceに関する特許を取得しました。この特許は2004年に出願されたもので、Hadoop、CouchDBなどのオープンソースソフトウェアによるMapReduceの利用をカバーする可能性があります。Ars Technicaの編集者は、MapReduceのコンセプト普及におけるGoogleの役割を認めつつも、この特許の有効性や新規性については疑問を呈しました。[ 50 ] [ 51 ] 2013年、Googleは「オープン特許非主張（OPN）誓約」の一環として、この特許を防御目的のみで使用することを誓約しました。[ 52 ] [ 53 ]この特許は2026年12月23日に失効する予定です。[ 54 ]

制限されたプログラミングフレームワーク

MapReduceタスクは、バッチジョブスケジューラによって実行される非巡回データフロープログラム、すなわちステートレスマッパーとそれに続くステートレスリデューサとして記述する必要がある。このパラダイムはデータセットの繰り返しクエリを困難にし、グラフ処理[ 55 ]などの分野では、単一のワーキングセットを複数回再訪する反復アルゴリズムが標準となっている。また、ディスクベースの高レイテンシデータが存在する場合、アルゴリズムが各パスでデータへのシリアルアクセスを許容できるにもかかわらず、データの複数回のパスが必要となる機械学習の分野でも、制限が課せられる。[ 56 ]

参照

MapReduceの実装

参考文献

  1. ^ 「MapReduceチュートリアル」Apache Hadoop。2019年7月3日閲覧
  2. ^ 「Google、データセンターの内部事情にスポットライトを当てる」 cnet.com 、 2008年5月30日。 2013年10月19日時点のオリジナルよりアーカイブ。2008年5月31日閲覧。
  3. ^ a b「MapReduce: 大規模クラスターでの簡素化されたデータ処理」(PDF) . googleusercontent.com .
  4. ^ Wickham, Hadley (2011). 「データ分析のための分割・適用・結合戦略」 . Journal of Statistical Software . 40 : 1–29 . doi : 10.18637/jss.v040.i01 .
  5. ^「私たちの抽象化は、Lispや他の多くの関数型言語に存在するmapとreduceのプリミティブからインスピレーションを得ています。」 -「MapReduce：大規模クラスタでの簡素化されたデータ処理」、Jeffrey DeanとSanjay Ghemawat著、Google Researchより
  6. ^ Lämmel, R. (2008). 「GoogleのMapReduceプログラミングモデル — 再考」. 『コンピュータプログラミングの科学』 . 70 : 1–30 . doi : 10.1016/j.scico.2007.07.001 .
  7. ^ http://www.mcs.anl.gov/research/projects/mpi/mpi-standard/mpi-report-2.0/mpi2-report.htm MPI 2 標準
  8. ^ 「MPI Reduce と Allreduce · MPI チュートリアル」。mpitutorial.com 。
  9. ^ 「MPI による並列ランクの実行 · MPI チュートリアル」。mpitutorial.com 。
  10. ^ 「MongoDB：MapReduceのパフォーマンスがひどい」。Stack Overflow。2010年10月16日。MongoDBのMapReduce実装は、どうやらMapReduceとはほとんど関係がないようです。私が読んだ限りでは、MapReduceはシングルスレッドであるのに対し、MapReduceはクラスター上で高度な並列処理を行うことを想定しているからです。…MongoDB MapReduceは単一サーバー上でシングルスレッドです…
  11. ^ a b c Ullman, JD (2012). 「優れたMapReduceアルゴリズムの設計」 . XRDS: Crossroads, the ACM Magazine for Students . 19 : 30–34 . doi : 10.1145/2331042.2331053 . S2CID 26498063 . 
  12. ^ Sverdlik, Yevgeniy (2014年6月25日). 「Google、MapReduceを廃止し、新たなハイパースケール分析システムを採用」 . Data Center Knowledge . 2015年10月25日閲覧。「私たちはもうMapReduceをあまり使っていません」[Googleの技術インフラ担当上級副社長、Urs Hölzle氏]
  13. ^ 「なぜMapReduceは大規模機械学習において依然として主要なアプローチなのか」 Analytics India、2019年4月5日。
  14. ^チャコウスキー、グジェゴシュキ;マリアン・ドヴォルスキー。ジェリー・チャオ;マイケル・コンリー（2011年9月7日）。「MapReduce を使用したペタバイトの並べ替え – 次のエピソード」。2014 年4 月 7 日に取得。
  15. ^ 「MapReduce チュートリアル」。
  16. ^ “Apache/Hadoop-mapreduce” . GitHub . 2021年8月31日.
  17. ^ 「例: 単語の出現回数を数える」。Google Research 。 2013年9月18日閲覧。
  18. ^ Fegaras, Leonidas (2017). 「分散型ビッグデータ分析のための代数」. Journal of Functional Programming . 28 e27. doi : 10.1017/S0956796817000193 . S2CID 44629767 . 
  19. ^ Lin, Jimmy (2013年4月29日). 「Monoidify! Monoids as a Design Principle for Efficient MapReduce Algorithms」. arXiv : 1304.7544 [ cs.DC ].
  20. ^ 「Scala の抽象代数」。
  21. ^ 「左折り畳みによるモノイドとしてのMap-Reduceのエンコード」 2016年9月5日。
  22. ^ a b Senger, Hermes; Gil-Costa, Veronica; Arantes, Luciana; Marcondes, Cesar AC; Marín, Mauricio; Sato, Liria M.; da Silva, Fabrício AB (2015-01-01). 「MapReduce操作におけるBSPコストとスケーラビリティ分析」. Concurrency and Computation: Practice and Experience . 28 (8): 2503– 2527. doi : 10.1002/cpe.3628 . hdl : 10533/147670 . ISSN 1532-0634 . S2CID 33645927 .  
  23. ^ベルリンスカ、ジョアンナ;ドロズドフスキ、マチェイ (2010-12-01)。 「分割可能な MapReduce 計算のスケジュール設定」。並列および分散コンピューティングのジャーナル。71 (3): 450–459。土井: 10.1016/j.jpdc.2010.12.004。
  24. ^ Bosagh Zadeh, Reza; Carlsson, Gunnar (2013). 「MapReduceを用いた次元非依存の正方形行列」(PDF) .スタンフォード大学. arXiv : 1304.1467 . Bibcode : 2013arXiv1304.1467B . 2014年7月12日閲覧.
  25. ^ン、アンドリュー Y.;ブラッドスキー、ゲイリー。チュー、チェンタオ。オルコトゥン、クンレ;キム・サンギュン;リン、イアン。ユウ、ユアンユアン（2006）。「マルチコアでの機械学習のための Map-Reduce」。 NIPS 2006。2010年 6 月 20 日のオリジナルからアーカイブ。2009 年 11 月 24 日に取得。
  26. ^ Ranger, C.; Raghuraman, R.; Penmetsa, A.; Bradski, G.; Kozyrakis, C. (2007). 「マルチコアおよびマルチプロセッサシステムにおけるMapReduceの評価」. 2007 IEEE 第13回国際高性能コンピュータアーキテクチャシンポジウム. p. 13. CiteSeerX 10.1.1.220.8210 . doi : 10.1109/HPCA.2007.346181 . ISBN  978-1-4244-0804-7. S2CID  12563671 .
  27. ^ He, B.; Fang, W.; Luo, Q.; Govindaraju, NK; Wang, T. (2008). 「Mars：グラフィックスプロセッサ上のMapReduceフレームワーク」(PDF) .第17回並列アーキテクチャおよびコンパイル技術国際会議 – PACT '08 の議事録. p. 260. doi : 10.1145/1454115.1454152 . ISBN 9781605582825 . S2CID  207169888
  28. ^ Chen, R.; Chen, H.; Zang, B. (2010). 「Tiled-MapReduce: マルチコアにおけるデータ並列アプリケーションのリソース使用率の最適化（タイル化による）」第19回並列アーキテクチャおよびコンパイル技術国際会議 – PACT '10 議事録. p. 523. doi : 10.1145/1854273.1854337 . ISBN 9781450301787. S2CID  2082196 .
  29. ^ Tang, B.; Moca, M.; Chevalier, S.; He, H.; Fedak, G. (2010). 「デスクトップグリッドコンピューティングのためのMapReduceに向けて」(PDF) . 2010 International Conference on P2P, Parallel, Grid, Cloud and Internet Computing . p. 193. CiteSeerX 10.1.1.671.2763 . doi : 10.1109/3PGCIC.2010.33 . ISBN  978-1-4244-8538-3. S2CID  15044391 .
  30. ^ Luo, Y.; Guo, Z.; Sun, Y.; Plale, B .; Qiu, J.; Li, W. (2011). 「クロスドメインMapReduce実行のための階層的フレームワーク」(PDF) .生命科学のための新たな計算手法に関する第2回国際ワークショップ (ECMLS '11) の議事録. CiteSeerX 10.1.1.364.9898 . doi : 10.1145/1996023.1996026 . ISBN  978-1-4503-0702-4. S2CID  15179363 .
  31. ^ Lin, H.; Ma, X.; Archuleta, J.; Feng, WC; Gardner, M.; Zhang, Z. (2010). 「MOON: Opportunistic eNvironmentsにおけるMapReduce」(PDF) .第19回ACM国際高性能分散コンピューティングシンポジウム – HPDC '10 議事録. p. 95. doi : 10.1145/1851476.1851489 . ISBN 9781605589428. S2CID  2351790 .
  32. ^ Marozzo, F.; Talia, D.; Trunfio, P. (2012). 「P2P-MapReduce：動的クラウド環境における並列データ処理」 . Journal of Computer and System Sciences . 78 (5): 1382– 1402. doi : 10.1016/ j.jcss.2011.12.021
  33. ^ Dou, A.; Kalogeraki, V.; Gunopulos, D.; Mielikainen, T.; Tuulos, VH (2010). 「Misco: モバイルシステム向けMapReduceフレームワーク」.第3回支援環境関連PErvasive Technologies国際会議 – PETRA '10 議事録. p. 1. doi : 10.1145/1839294.1839332 . ISBN 9781450300711 . S2CID  14517696
  34. ^ Wang, Yandong; Goldstone, Robin; Yu, Weikuan; Wang, Teng (2014年5月). 「HPCシステムにおけるメモリ常駐型MapReduceの特性評価と最適化」. 2014 IEEE 第28回国際並列分散処理シンポジウム. IEEE. pp.  799– 808. doi : 10.1109/IPDPS.2014.87 . ISBN 978-1-4799-3800-1. S2CID  11157612 .
  35. ^ 「How Google Works」 . baselinemag.com. 2006年7月7日。ディーン氏のプレゼンテーションによると、10月時点でGoogleはMapReduceを通じて1日あたり約3,000件のコンピューティングジョブを実行しており、これは数千マシン日に相当する。これらのバッチルーチンは、最新のウェブページを分析し、Googleのインデックスを更新するなど、様々な処理を行っている
  36. ^ Chambers, Craig; Raniwala, Ashish; Perry, Frances; Adams, Stephen; Henry, Robert R.; Bradshaw, Robert; Weizenbaum, Nathan (2010年1月1日). 「FlumeJava」.第31回ACM SIGPLANプログラミング言語設計・実装会議論文集(PDF) . pp.  363– 375. doi : 10.1145/1806596.1806638 . ISBN 9781450300193. S2CID  14888571 . 2016年9月23日時点のオリジナル（PDF）からアーカイブ。2016年8月4日閲覧
  37. ^ Peng, D., & Dabek, F. (2010年10月). 分散トランザクションと通知を用いた大規模増分処理. OSDI (第10巻, pp. 1-15).
  38. ^ 「データベースの専門家が MapReduce の脅威を飛び越える」。
  39. ^ a b David DeWitt、Michael Stonebraker、「MapReduce：大きな後退」 craig-henderson.blogspot.com 。 2008年8月27日閲覧。
  40. ^ 「Apache Hive – Index of – Apache Software Foundation」。
  41. ^ a b「HBase – HBase ホーム – Apache Software Foundation」。
  42. ^ 「Bigtable: 構造化データ用の分散ストレージ システム」(PDF)。
  43. ^ Greg Jorgensen . 「リレーショナルデータベースの専門家がMapReduceのサメを飛び越える」 . typicalprogrammer.com . 2009年11月11日閲覧。
  44. ^ Pavlo, Andrew; Paulson, Erik; Rasin, Alexander; Abadi, Daniel J.; DeWitt, Deavid J.; Madden, Samuel; Stonebraker, Michael. 「大規模データ分析へのアプローチの比較」ブラウン大学. 2010年1月11日閲覧。
  45. ^ヒリス、W. ダニー (1986). 『コネクション・マシン』 . MITプレス. ISBN 0262081571。
  46. ^ 「コネクションマシン モデル CM-2 技術概要」（PDF）Thinking Machines Corporation . 1987年4月1日. 2022年11月21日閲覧
  47. ^ 「*Lispリファレンスマニュアル補足」(PDF) . Thinking Machines Corporation . 1988年9月1日. 2022年11月21日閲覧。
  48. ^ 「Rediflowアーキテクチャ概要」（PDF） .ユタ大学コンピュータサイエンス学部. 1986年4月5日. 2022年11月21日閲覧。
  49. ^ Ranka, Sanjay (1989). 「2.6 データ合計」.画像処理とパターン認識のためのハイパーキューブアルゴリズム(PDF) . フロリダ大学. 2022年12月8日閲覧。
  50. ^ Paul, Ryan (2010年1月20日). 「GoogleのMapReduce特許：Hadoopにとって何を意味するのか？」 Ars Technica . 2021年3月21日閲覧。
  51. ^ 「米国特許：7650331 - 大規模データ処理の効率化のためのシステムおよび方法」uspto.gov。2013年9月21日時点のオリジナルよりアーカイブ。 2010年1月19日閲覧。
  52. ^ Nazer, Daniel (2013年3月28日). 「Google、特許のオープン非主張誓約を発表し、新たなライセンスモデルを提案」 .電子フロンティア財団. 2021年3月21日閲覧。
  53. ^ King, Rachel (2013). 「Google、データセンター管理に関するオープン特許誓約を79件に拡大」 ZDNet . 2021年3月21日閲覧。
  54. ^ 「大規模データ処理を効率的に行うシステムおよび方法」 Google Patents Search. 2004年6月18日. 2021年3月21日閲覧。
  55. ^ Gupta, Upa; Fegaras, Leonidas (2013-10-06). 「MapReduceにおけるマップベースのグラフ分析」(PDF) . Proceedings: 2013 IEEE International Conference on Big Data . 2013 IEEE International Conference on Big Data. Santa Clara, California : IEEE . pp.  24– 30.
  56. ^ Zaharia, Matei; Chowdhury, Mosharaf; Franklin, Michael; Shenker, Scott; Stoica, Ion (2010年6月). Spark: ワーキングセットを用いたクラスターコンピューティング(PDF) . HotCloud 2010.
Wikimedia Commons にはMapReduceに関連するメディアがあります。
「 https://en.wikipedia.org/w/index.php?title=MapReduce&oldid=1309829279」より取得