6

Hadoop と map/reduce の境界を理解しようとしていますが、map/reduce が役に立たないことがわかっている重要な問題、または問題のクラスを知ることは役に立ちます。

問題の 1 つの要因を変更することで、map/reduce からの単純化が可能になる場合は、確かに興味深いでしょう。

ありがとうございました

4

5 に答える 5

6

次の 2 つのことが思い浮かびます。

  1. リアルタイム/インタラクティブ/低遅延の応答時間を必要とするもの。Hadoop に送信されたジョブには固定料金が発生します。

  2. 恥ずかしいほど並列ではない問題。Hadoop は、reduce フェーズでレコードが結合されるため、データ間の単純な相互依存性を必要とする多くの問題を処理できます。ただし、特定のグラフ処理および機械学習アルゴリズムは、相互に依存する操作が多すぎるため、Hadoop で記述するのが困難です。一部の機械学習アルゴリズムでは、大量のデータ セットへの非常に短い待機時間とランダム アクセスが必要ですが、Hadoop ではそのままでは提供されません。

于 2010-08-06T15:51:41.240 に答える
3

「map/reduceが役に立たないことはわかっています」とはどういう意味かは完全には明確ではありません。他の回答は、簡単ではない、簡単ではない、またはそれほど難しくない場合にいくつかの例で満足しているように見えます。個人的には、何かができないという定理にもっと満足していると思います。計算の複雑さを見ると、並列化が難しい問題、P-完全問題のクラスがあります。よく知られているそのような問題は、文脈自由文法認識（コンパイラにとって重要）、線形計画法、および圧縮におけるいくつかの問題です。ウィキペディアのエントリにはさらに多くのものがあります。

一部の人々は、マップリデュースのための新しい複雑さのクラスを作り上げています。私は非常に懐疑的ですが、陪審員はそれらがどれほど役立つかについて考えています。

もう1つの質問は、mapreduceで並列アルゴリズムをシミュレートできるかどうかです。確かに、P-completeの問題を超えてマップリデュースすることはできませんが、並行して解決できるがmapreduceでは解決できない問題がいくつかある可能性があります。そのような問題については知りませんが、Michael T.Goodrichによる「MapReduceフレームワークでの並列アルゴリズムのシミュレーションと並列計算幾何学への応用」といういくつかの仮定の下ではありますが、反対方向を指している論文を知っています。

実際には、マップリデュースの方法を考えたり、このモデルに固有のアルゴリズム手法を開発したりする時間はほとんどありませんでした。マップリデュースソリューションに新しい問題が発生しているのがわかります。ほこりが落ち着くと、mapreduceが最初に思っていたよりも強力であることがわかるかもしれません。

于 2010-10-05T07:57:59.540 に答える
0

他の人が述べているように：問題は、独立して処理できる断片に簡単に切り刻む必要があります。

それでは、WebAnalyticsアーキテクトとしての過去の2つの例を挙げましょう（基本的に、Hadoopが現在提供していることを...Hadoopなしで...複数のCPUコアを備えた単一のシステムでbashシェルスクリプトを使用して実行しようとしていました）。これらの2つが、これらの境界が実際にどのように見えるかについての洞察を与えてくれることを願っています。

コンテクスト：

Webサーバーからの大量のログラインがあると仮定します。そして、訪問者の行動を分析したいとします。どのリクエストがどのユーザーによって行われたかを確実に伝えるプロパティが必要です。

私の2つの例：

  1. 動作を相互に関連付けるために使用するプロパティは、一部の部分で不良です（たとえば、sessionid）。これは、サイトがJavaScript（YUCK！）を使用してこの要素を配置した場合によく発生します。その場合、この相関するプロパティを修正する作業を分割することは非常に困難になります（私の経験から：ほぼ不可能です）。これは「単一の巨大なパーティション」で実行する必要があるため、MapReduceは役に立ちません。
  2. これで、すべてのデータを管理可能なチャンクに分割するために必要なプロパティが信頼できるようになります（つまり、単一の個々のブラウザーがサイトで実行したすべてのこと）。データのサブセットを多数作成することが非常に簡単になります。大規模なサイトの処理を数百のシステムに簡単に拡張できます。

過去に、流体力学方程式（ナビエ-ストークス）を「マッピング可能な」部分に分割することはできないと誰かが私に言ったことがあります。これが当てはまる理由にはいくつかの論理がありますが（流体のすべての部分が流体の他のすべての部分に影響を与えます）; 私はこれらの方程式を理解しようとさえしないことを明確にすべきです。

これらの例が境界を見つけるのに役立つことを願っています。

于 2010-08-07T19:06:32.337 に答える
0

Gangadhar への返信 (申し訳ありませんが、コメント ボックスに十分なスペースがありません):

分割統治についてのあなたの回答は気に入っていますが、追加する警告があります。Mapreduce は、特定の d/c アルゴリズムのサブ問題の組み合わせが最終的に 1 つのキーに縮小されることに依存するため、分割統治アルゴリズムの再帰的な側面をうまく処理しません。マージソートアルゴリズムを例にとると(Mapreduce 実装の重要な順序付けプロパティのために、Hadoop ではソートが自明であることは今のところ無視します): マッパーを使用して、任意の ID を使用してデータを 2 つのチャンクに分割します。鍵。reduce フェーズでは、それぞれのキーの値リストを一緒にマージします。

7 3 2 4 1 5 8 9 would map to 
1->[[7],[3]] 2->[[2],[4]] 3->[[1],[5]] 4->[[8],[9]] would reduce to
3,7 2,4 1,5 8,9 would map to 
1->[[3,7],[2,4]] 2->[[1,5],[8,9]] 
etc.

キーの数が 2 つ (または d/c アルゴリズムに使用する任意のチャンク係数) 減り、最​​終的にソートされたリストのキーが 1 つになることがわかります。これは並列処理にとっては悪いことです。

したがって、mapreduce には分割統治の分割の側面が明らかに必要ですが、結果がデータ並列アイテムのコレクションになるように、征服フェーズでもデータ並列処理が必要です。FFT は、mapreduce とうまく連携する分割統治アルゴリズムの良い例です。

于 2010-08-19T18:37:18.053 に答える
0

分割統治で解決できない問題は、hadoop ではうまく機能しないと思います。アルゴリズムを変更してサブタスクを作成できるようになれば、Hadoop でうまく実行できると思います。

あなたの質問に追加するために (答えではなく、コメントのこの部分を作成しますか?)、問題を分解できるサブタスクがあるがfilter、hadoop のフェーズを実行する明確な方法がない場合はどうなりますか? フェーズにHadoop を使用mapして、1 台のマシンでリダクションを実行できると思います。

于 2010-08-06T19:46:04.797 に答える