Clever Geek Handbook

MongoDBを例として使用したMap-Reduce

最近、Big DataとNoSQLの共通名で結ばれた一連のデータ処理アプローチと方法論が人気を集めています。 大量のデータに適用される計算モデルの1つは、Googleの腸で開発されたMap-Reduceテクノロジーです。 この投稿では、このモデルがMongoDB非リレーショナルDBMSでどのように実装されるかについてお話します。



一般的な非リレーショナルデータベース、特にMap-Reduceテクノロジーの将来に関しては、このトピックについては無期限に議論することができますが、投稿ではそのことについてまったく言及していません。 いずれにせよ、たとえば関数型プログラミング言語に精通することが命令型言語のみを扱うプログラマーに役立つように、代替の従来のDBMSデータ処理方法に精通することは、プログラマーの一般的な開発に役立ちます。



MongoDB非リレーショナルDBMSは、JSON形式のドキュメントのコレクションの形式でデータを提示し、このデータを処理するさまざまな方法を提供します。 特に、Map-Reduceモデルのカスタム実装があります。 この特定の実装を実際の目的に使用することがいかに実用的かについては後述しますが、ここでは、Map-Reduceパラダイム自体に慣れることに制限します。



それでは、Map-Reduceの何が特別なのでしょうか？



大規模なオンラインアプリケーションを開発しており、そのデータが世界中のいくつかのサーバーに分散して保存されているとします。 さらに、ユーザーには関心が示されます。 この関心を共有するユーザーの数を単純に決定することにより、各関心の人気を計算することにしました。 リレーショナルDBMSを使用し、すべてのユーザーを1つのサーバーに保存した場合、 group by操作を使用した簡単なクエリが答えを得るのに役立ちます。 異なるノードの場合、このグループ化を並行して実行し、すべてのサーバーを均等にロードするようにします。 リレーショナルDBMSとSQLクエリの世界では、これを想像するのはかなり困難ですが、Map-Reduceの助けを借りて、この問題はかなり解決可能です。



データベースに、次の形式の要素を持つユーザーコレクションがあるとします 。 



{ name : "John", age : 23, interests : ["football", "IT", "women"] }


出力では、このタイプのコレクションを取得します。 



 { key: "football", value: 1349 }, { key: "MongoDB", value: 58 }, //...


実行中、システムはデータに対してMapおよびReduce操作を実行します。これらの操作はプログラマーが決定します。 MongoDBでは、これらの操作はJavascriptで記述された関数の形式です。 つまり、プログラマーが関数自体を作成し、Mongoが呼び出しを管理します。



最初に、 マップ操作がコレクション内の各ドキュメントに適用され、 <key、value>ペアを形成します 。 これらのペアは、 キー付きのグループ化された形式でreduce関数に渡されます。 Reduce操作は、1つの<key、value>ペアを形成します。 キーおよび値として、オブジェクトを含む任意の変数を使用できます。



この例のマップ関数を考えてみましょう。 



 function map(){ for(var i in this.interests) { emit(this.interests[i], 1); } }


ご覧のとおり、 マップ操作が適用されるドキュメントには、 thisポインターからアクセスできます。 放出関数は、次のペア<key、value>を転送してさらに処理するために使用されます。 ご覧のとおり、1つのドキュメントのMap操作では、複数の<key、value>ペアを生成できます。 この例では、すべてが単純です。この場合、関心は1回だけ満たされるため、関心をキーとして、1つを値として渡します。



生成されたペアはキーごとにグループ化され、 <key、list of values>の形式でreduce関数に渡されます 。 この例のreduce関数は次のようになります。 



 function reduce(key, values) { var sum = 0; for(var i in values) { sum += values[i]; } return sum; }


最終的な値を取得するために、 values配列にあるすべての値を要約します 。 Reduce操作でキーを変更することは提供されていないため、関数は結果の値を結果の形式で単に返します。



スマートリーダーは次の質問をする場合があります。値が1に等しいことがわかっている場合に、 値配列全体を実行してその要素を追加するのはなぜですか。 配列の長さを返すのは簡単ではありませんか？ この質問に対する答えは「いいえ」です。この説明は、Map-Reduceの主要な機能に光を当てます。



実際には、MongoDBはReduce操作を開始して中間集計を実行します。 同じキーを持つ複数のペアが形成されるとすぐに、MongoDBはそれらに対してReduceを実行できます。これにより、1つの<key、value>ペアを取得し、 Map操作を使用して取得したかのように他のペアと一緒に処理されます。



これにより、 reduce関数の実装に特定の要件が課されます。 ここにあります：



  1. reduce関数の戻り値の型は、 map関数（ emit関数の2番目のパラメーター）によって返される値の型と一致する必要があります
  2. 同等でなければなりません： reduce（key、[A、reduce（key、[B、C]）]）== reduce（key、[A、B、C]）
  3. 受け取ったペア<key、value>に対してReduce操作を繰り返し適用しても、結果に影響はありません（べき等性）
  4. reduce関数に渡される値の順序は結果に影響しません。


2番目の要件は、何が起こる可能性があるかを示す例でもあります。 <key、B>と<key、C>のペアが一方のノードで受信され、 <key、A>がもう一方のノードで受信された場合、最初のノードでReduce操作を予備実行すると、ネットワークトラフィックが減少し、並列性が向上します。 ただし、これに対する代償は、上記のIDを維持する必要があるため 、 reduce関数に大きな制限があります。



すべてのMapおよびReduce操作が完了すると、フォームの要素のコレクションが出力で形成されます 



 { key:"football", value: 1349 },


このような操作を開始するには、mongoシェルコンソールでこれらの2つの関数を宣言し、コマンドを実行する必要があります。 



 db.users.mapReduce(map, reduce,{out:"interests"})


別の問題を考えてみましょう。 さまざまな年齢の人々の関心の平均数を知りたいとします。 この場合のマップ関数の形式は次のとおりです。 



 function map(){ emit(this.age, {interests_count: this.interests.length, count: 1}); }


ここでのキーは年齢であり、オブジェクトは値として渡されます-関心の数と、これらの関心を共有する特定の年齢の人の数（1つのドキュメントの場合は単位です）。



reduce関数の要件を注意深く見ると、この数学演算は2番目の要件を満たしていないため、フレームワークでは算術平均を計算できないことが明らかになります。 したがって、 reduce関数の一部としてできることは、関心の数とユーザーの数を別々に追加することだけです。 



 function reduce(key, values) { var sum = 0; var count = 0; for(var i in values){ count += values[i].count; sum += values[i].interests_count; } return {interests_count: sum, count: count}; }


最終コレクションで目的の算術平均を取得するには、 Finalize操作を使用できます。これは、 キーキーを使用したすべてのReduce操作の実行後に取得される最終ペア<key、value>に適用されます 。 



  function finalize(key, reducedValue) { return reducedValue.interests_count / reducedValue.count; }


呼び出すコマンド： 



  db.users.mapReduce(map, reduce, {finalize: finalize, out:"interests_by_age"})


Apache Hadoopを含むMap-Reduceの他の実装では、 Reduceの操作にそのような制限がないことに注意してください。 そこでは、キーに関連する値の完全なリストが常にreduce関数に提供されます。 また、中間集約は、 Reduceと意味的に類似した別の操作Combineを介して実行できます。



次に、MongoでのMapReduceのネイティブ実装の実用化の実現可能性について少し説明します。 このDBMSで集計を実行するために、Aggregation Frameworkと呼ばれる強力なツールがあります。これは、Map-Reduceよりも約5〜10倍速く同じ集計を実行します。 ただし、この場合の並列処理は、並べ替えとグループ化が始まるところで終了します。 また、操作で消費されるRAMには特定の制限があります。



一般に、Aggregation Frameworkは高速応答が必要な場合に使用する必要がありますが、Map-Reduceは生の情報を前処理するように設計されています。 Mongoは、Map-Reduceの実装がネイティブよりも効率的に機能するHadoopと対話する機会を提供します。 何らかの方法で、MongoDBを使用すると、Apache Hadoopのような比較的重いツールをインストールして構成しなくても、Map-Reduceモデルに慣れることができます。


More articles:


All Articles