MongoDbとMapReduceを使用して製品フィルターを構築するための簡単な手法

MapReduceに初めて出会ったとき、長い間、実際のアプリケーションの例を探していました。 MapReduceに関する2番目の記事で見つかるテキスト内の単語の悪名高い検索は、望ましい例とは見なされません。 最後に、 Courseraのビッグデータに関する2つのコースで、実例だけでなく、何が起こっているのかをより深く理解するための理論的背景を見つけました。 習得した知識を適用する機会はすぐに来ました。



この短い記事では、何万ものホテルのデータベースによる検索とフィルタリングのタスクが出現する観光ポータルの基準に従って、ほとんどのオンラインストア製品フィルタリングシステムにクラシックを実装した経験を共有したいと思います。各タスクは、多数のパラメーターと提供される数十のサービスの存在によって記述されます何百もの可能性から。

問題の声明

数万のオブジェクトのホテルのデータベースがあります。 各ホテルの説明は次のとおりです。

1. それぞれに少数の可能なオプションがあるパラメータに近い。 たとえば、ホテルの星の評価：1〜5。またはホテルの食事の種類：それらの多くもありません。 などなど。 ここでの難しさは、各ホテルの一部のパラメーターについては1つの値しか使用できないこと、および一部の可能なセットについてのみです。 ただし、可能なオプションは少数ですが、これはまだ問題ではありません。
2. 価格 タスクを簡素化するために、明日到着する場合の1日2倍の最低価格が基本価格として採用されます。 そして、この価格の範囲は0（ああ、もし...）から最大で数千までです。 フィルタリングには、いくつかの価格帯があります。 したがって、一定の期間内に価格が下がるホテルを探す必要があります。
3. 地域所属。 状況はパラグラフ1と同じですが、基準「国」の可能なオプションの数は200、および「都市」の推定オプションはすでに数千と見積もられています。 このタスクは、各ホテルが国と都市のパラメーターに対して独自の重要性を持つという事実によって促進されます。
4. そして最後に、最も興味深いのは、ホテルが提供するサービスのリストです。 この問題を解決し始めて、サービスのリストは700以上のアイテムでした。 手動で「不要なものをすべて捨てる」こととグループ化の助けを借りて、サービスの数は300に削減されましたが、これも少なくありません。 次にやることが脅かしていること。

実際には、タスク：ホテルを説明する可能なパラメーター値の任意の組み合わせの任意のセットでフィルタリングし、フィルターのリストを表示するときに、各フィルターの反対側のホテルの数を表示します。 フィルターの各組み合わせには明確なURLを使用し、再現されたホテルの選択を反映する必要があります。



数万のオブジェクトの数と相対的な静的情報の条件を使用した基準によるホテルの検索は、各リクエストを手動で分析/最適化し、インデックスを構築することにより、ほぼ無痛で実装されます。正規化されたデータベースの場合は20個のテーブル、またはパスが選択されている場合は1つのワイドテーブル非正規化により問題を解決します。



しかし、ここでは、検索パラメーターの可能な値ごとにサンプルに該当するホテルの数を数えるという形の小さな「かわいさ」が、これらの値の数が1000に近づくと、最初は小さな混乱を引き起こしました。

ちょっとした組み合わせ

遠い過去の価格アグリゲーターの同様のタスクは正面から解決され、多くの制限がありました。事前に計算されたフィルターの組み合わせと各組み合わせの商品の量を含む巨大なテーブルがデータベースに保存されました。 テーブルは毎晩完全に再計算され、この操作にはかなり長い時間がかかりました。



この場合、たとえば、同時に設定されるフィルターの数など、制限のない、より普遍的なことを行います。 この状態はなぜそんなに重要なのですか？ Excelと組み合わせの基礎知識を備えたこの質問に答えます。



この目的のために、Excelには素晴らしい機能「NUMBER COMB」があります。これは、選択された要素の特定の数に対する要素の特定の数の組み合わせの数を返します。 明確にするために、10個の要素を取り、選択した1、2、3などの要素の可能な組み合わせの数を検討します。 テーブルを取得します。

1	10
2	45
3	120
4	210
5	252
6	210
7	120
8	45
9	10
10	1

合計：1023オプション。 したがって、可能な10個のフィルターについて、1023個のフィルターの組み合わせを持つテーブルを作成する必要があります。それぞれのフィルターの組み合わせに該当するホテルの数を計算する必要があります。 すべては問題ありませんが、フィルターの数が増えると、オプションの数が増えて個人的にショックを受けました。



200に等しいサービス数（ただし実際にはもっと多くあります）および選択したサービスの可能な数で、10〜63度の組み合わせの数を取得します。 つまり、計算された数のホテルで10億億のエントリを保持するテーブルを作成する必要があります。このエントリも毎日更新する必要があります。

結論：ビットマップを使用し、情報を更新することでさえ、データベースに同様のものを保持することは、非現実的です。 まさか。 別の方法を探す必要があります。

MongoDBを使用する

10億を超えるホテルの価格を保存するために観光ポータル用のデータベースが選択されたとき、 MongoDBは最前線でテストされました。 当時、私は上記のベースでコースを完了したばかりで、すべてが虹色に見えました：シャーディング、レプリケーション、ドキュメント指向データベース、高性能...しかし、すべてが即座にクラッシュしました： コレクションレベルでのロックのチケットは10gen（多数の複合インデックスを含むドキュメントの非常に遅い競合挿入：彼らの汚い行為を行いました：多くの実験の後、データベースは大きなマキユキでスクラップに送られました。 それは永遠に思えます。 しかし、人生でしばしば起こるように、各タスクごとに-独自のツール。 そして、MongoDbは翼で待っていました。

なぜMongoDBなのか？

タスクについては、スキーマレスでドキュメント指向のMongaであり、それ以上に優れたものはありません。各ホテルを、任意の属性セットを持つドキュメントとして表し、（重要！）各属性の値の配列を格納する機能を備えています。 つまり、ドキュメント内の配列に複数の値を同時に取得できるサービスおよびその他のパラメーターのリストを格納し、それらのインデックスを作成し、ドキュメントのコレクション全体で任意の検索を実行できます。 もちろん、MongoDBに加えて、他のNoSQLデータベースのオプションも検討されましたが、そのシンプルさとドキュメント内のコレクションでインデックス検索を保存および実行する機能で勝ったのはMongaでした。



ホテルを説明するドキュメントのトリミングされた（hello、NDA）構造をもたらします。

"_id" : ObjectId(), "hotel_id" : int, "country_id" : int, "city_id" : int, "category_id" : int, "services" : [int, int, int...]
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

王冠によると、このコレクションは、Mongovsky upsertを使用してメインデータベースからの情報に基づいて更新されます。



また、このコレクションから、任意のフィルターセットを持つホテルのリストを取得するのに問題はありません。 例：

1. {country_id：1、サービス：{$ all：[10、20]}}-同時にサービス10と20を持つ国1のすべてのホテル。
2. {category_id：5、サービス：{$ in：[20、30]}}-サービスが10または20のすべてのカテゴリ5ホテル。

サービスだけでなく、ホテルを説明する他のすべてのパラメーターに対してもまったく同じフィルターが形成されます。 したがって、10階建てのSQLクエリをメインデータベースに書き込む必要はありません。 同時に、生産性は非常に高いレベルのままです。 数千または数万のドキュメントの比較的静的なコレクションと、適切な複合インデックスと十分なRAMにより、MongoDBは素晴らしい仕事をします。

いいね！ MapReduceはそれと何の関係がありますか？

そのため、フィルターを使用してGETリクエストのパラメーターを解析した後、MongoDbでホテルのリストを取得するリクエストを作成できます。 ここで、フィルターのリストを作成し、各フィルターに該当するホテルの数を取得します。 このツールは、記事のタイトルMongoDB＆MapReduceから明らかです。



MapReduce理論を長い間描いていません。 データ処理へのこのアプローチは、マッピングと畳み込みの2つの段階で構成されていることを思い出してください。 さらに、各ステージは複数のコア/プロセッサ/サーバー/クラスターで並行して発生し、単一のデータ配列で動作します。 共有メモリ（この場合はMongaを使用）を介してマッピング操作によってデータが準備されると、このデータは折りたたまれ、最終的な処理と目的の配列への変換が行われます。

この理論を理解すると、実際にはすべてが驚くほどシンプルになります。 マップのソースコードを指定し、メソッドを減らします。

 var map = function() { emit({"category": this.category_id}, 1); if (this.services) this.services.forEach(function(value) { emit({"service": value}, 1); }); if (this.types) this.types.forEach(function(value) { emit({"type": value}, 1); }); // …................................. // And a large number of other filters }; var reduce = function(key, values) { return Array.sum(values); };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

どのように機能しますか？

とても簡単です！



MongoDbデータベースに保存されている各ホテルはマッピング関数に入り、各サービス/種類の食べ物/ホテルの場所（リスト内など）に対して、emit（）関数が呼び出されます。これは、メモリの連想配列に番号「1」で追加されますサービス。

限界までの畳み込み関数は簡単です。マッピング段階で取得した連想配列の各要素の数量の桁を合計します。



以上です！



出口で、各サービスのホテル数を計算したすべてのサービスの配列を取得します。 この操作全体が完全に並列であるとすると、この配列の形成速度は数分の1秒です。 もちろん、キャッシュを忘れないでください。 私たちのケースでは、キャッシングを最大限に活用できます。 情報は比較的静的であり、選択はスペースをほとんど消費せず、元のGETリクエストに基づいたWhirlpoolハッシュからのキーによってmemcachedに安全に保存できます。



主なトリックは、MapReduce関数をホテルコレクションの一部に使用できることです。 つまり MapReduce関数を使用するときに生成された同じリクエストを使用してホテルのリストを取得し、ごく少数のホテルですべてのアクションを頻繁に実行できます。 このアプローチの副作用として、サービスアレイでは、目的の選択のホテルが持つサービスのみを受け取り、現在の選択のホテルが持つサービスのみをサイトの前面に非常に簡単に表示できます。最終的にユーザビリティにプラスの効果があります。

最適化することは可能ですか？

はい、できます。 実際には、多数のホテル（たとえば10万件）を処理し、各ホテルに合計100個のパラメーター値のセットがある場合、1000万回の呼び出し（）が行われます。並列化のため。 そして解決策が見つかりました：

 var map = function() { var obj = { "categories": {}, "services": {} // Other params }; if (this.category_id > 0) obj.categories[this.category_id] = 1; var attrs = ["services", "types"]; for (var i = 0; i < 2; i++) { var attrKey = attrs[i]; var attrsArray = this[attrKey]; for (var key in attrsArray) { obj[attrKey][attrsArray[key]] = 1; } } emit("attrs", obj); }; var reduce = function(key, values) { var obj = { "categories": {}, "services": {} // Other params }; var attrs = ["categories", "services"]; for (var j = 0; j<2; j++) { attrObjArray = []; for (var i = 0; i < values.length; i++) { attrValuesArray = values[i][attrs[j]]; for (var attrKey in attrValuesArray) { var val = parseInt(attrValuesArray[attrKey]); if (!attrObjArray[attrKey]) { attrObjArray[attrKey] = val; } else { attrObjArray[attrKey] += val; } } } finalAttrObj = {}; for (i = 0; i < attrObjArray.length; i++) { var val = attrObjArray[i]; if (val) { finalAttrObj[i] = val; } } obj[attrs[j]] = finalAttrObj; } return obj; };
      
      

        
        
        
      

    
        
        
        
      
      

        
        
        
      

    
     

最適化されたソリューションでは、複数の放出の代わりに、マッピング操作ごとにホテルのパラメーターがオブジェクトにパッケージ化され、オブジェクトが放出に転送され、アンパック、カウント、および畳み込みが実行されます。 視覚的には、ソリューションははるかに困難であることが判明しましたが、パッケージの数はホテルの数に削減されました。 当然、オブジェクトの梱包と開梱のより難しい操作のため。 その結果、このソリューションは非常に大きなホテルのサンプルでのみ効果的に機能し、サンプルで最大1万のホテルを失うことが保証されます。 私たちのプロジェクトの現実に基づいて、それぞれのケースで異なるタイプのMapReduceの不要なチェックと呼び出しでコードを積み上げず、このメソッドを「保留」のままにすることを決定しました。

次は？

もちろん、この記事では、ホテルのサンプルを取得してフィルタリングシステムを構築する基本的な原則のみを説明します。これは、最初はホテルの価格もMongoDBに保存されるという仮定により大幅に簡素化されました。 実際、すべてがやや複雑であり、ユーザーが価格でフィルターを選択すると、本当の魔法が始まります。サービスフィルターに該当し、特定の間隔から特定の人数/泊/日付の価格のすべてのホテルを見つけることが必要になります。 特に、ホテルの価格はRESTサービスへのリクエストを使用して取得されることを考慮してください。 数百万のデータベースを操作するこの魔法と、コールドキャッシュと最も難しいクエリで最大100ミリ秒の応答時間を達成する方法については、次の記事でもゆっくりと公開する予定です。

合計

MongoDBとMapReduceを使用して、非常に使いやすいリソース、非常に理解しやすい、拡張性の高いソリューションを作成することができました。

私は質問に喜んでいるでしょう！

ご清聴ありがとうございました！