3

大きなデータセット (約 1 億 9100 万のレコード、今後さらに増える予定) があり、すべてのレコードにはフィルターの値 (11 個のフィルター - 日時と整数値) といくつかの追加データ (コスト) が含まれています。例えば:

Depature City = 1
Arrival City = 5
Country Id = 7
Check In Date = 2013-05-05
    ... etc

Cost 1250
    ... etc

11 個のフィルターを備えた検索インターフェイスがあります。すべてのフィルターで、ユーザーは次のいずれかを選択できます: 1 つの値、一連の値、すべての値。

すべてのフィルターには、可能な値の異なるセットがあり、4 から 5000 の値まで変化する可能性があります。

検索結果はコストの昇順で並べ替える必要があり、ページングがあります (1 ページあたり 50 件の結果)

すべての検索クエリは 100 ミリ秒で完了する必要があり、通常は 50 ~ 70 リクエスト/秒 (最大 200 リクエスト) が予想されます。

データは頻繁に変更されますが、データ変更の速度は優先順位が低く、このプロセスが遅くなる可能性があります。

そのような検索エンジンを整理する最良の方法は何ですか? メモリ内のデータ (いくつかのツリー アルゴリズムを試しました)、Map-Reduce (Hadoop?)、OLAP?

更新します。インメモリソリューションについてどう思いますか? レコードは、検索およびソート構造に適した操作メモリにロードできます。どのような構造が最適ですか?

本番環境では、クライアントは優れたソリューションに適したハードウェアを提供できます。

一般に、.NET ソリューションがあるため、このモジュールはそれと互換性がある必要があります。

4

5 に答える 5

4

[TrollModeOn] 問題が発生しました....SQL を使用しないソリューションで解決しようとしましたが、2 つの問題があります [/TrollModeOff]。

私には思われるように、no-sql ソリューションは、非常に多くのフィルターのものを処理するには適していません。私はSQLベースのソリューションから始めます。たとえば、ms sql サーバーがある場合、フィルターにユーザー定義のテーブル型を使用できます。

CREATE TYPE [FilterTable] AS TABLE(
    [id] [int] NOT NULL   --or any datatype needed
)

その後、次のように、テーブルの種類をパラメータとしてストアド プロシージャのフィルタリングに渡すことができます (または SQL クエリを使用して実行します)。

CREATE PROCEDURE [SomeFilterProcedureName]
    @Filter1 FilterTable READONLY,
    @Filter2 FilterTable READONLY
    ....

そして、あなたのクエリは次のようなものになります:

SELECT
    field1,
    field2,
    field3
FROM MyTable t
WHERE
    (@Filter1 IS NULL OR t.field1 IN (SELECT id FROM @Filter1))
    AND (@Filter2 IS NULL OR t.field2 IN (SELECT id FROM @Filter2))
    ....
ORDER BY
    whatever

したがって、基本的に、パラメーターに値が含まれているかどうかを確認し、含まれている場合は、フィルターパラメーターデータに従って列の値を除外します。

RDBMS は膨大な量のデータの格納、検索、フィルタリング、および並べ替えに優れた作業を行いますが、より高速に動作させるには適切な方法で調整する必要があります。たとえば、インデックスを正しく設定する必要があります。また、一定期間データをキャッシュすることもできますが、さまざまなパラメーターに応じてキャッシュキーを正しく作成してください。

1 秒あたり 200 件のクエリを処理するには db サーバーが十分でない場合は、クラスターを作成するか、同じデータを持つ複数の db サーバーを維持して、ある種の db バランサーを使用することをお勧めします。

更新: 大きすぎてコメントに入れることができません

It the worst case he can select "All" for every 11 filter and we have to sort 192 million records to find 20-100 with the lowest cost

オールフィルター、最低コスト?と同じではありませんか: Select top(20) * from someTableName order by cost.

  1. Db Locks. インデックスとクエリの作業を改善する
  2. Sorting. フィルターに適合するレコードが 1 億件あります。どのようにそれらを並べ替えるつもりですか? QSort、MergeSort、BubbleSort? それともstackoverflowSort?どのアルゴリズムを選択する必要があるか知っていますか? しかし、最初に - DBMS が知っていて、状況に応じて最適なアルゴリズムを選択します。これは、統計があるためです。次に、もちろん、データはインデックスに事前に並べ替えられて格納されます。したがって、100m レコードの並べ替え操作ごとに、no-sql ソリューションが強制終了されますが、rdbms では完全に機能します
  3. High load. それは私たちが話していることではありませんか?あなたの場合、実際の高負荷ではありません。毎月 1 億から 1 億 5,000 万人のアクティブ ユーザーを抱え、非常に大きなデータベースを持ち、1 秒あたり数千のクエリを実行している企業があり、rdbms を使用しています。数十台のサーバー、シャーディング、バランシング、そして完璧に機能します。
于 2013-07-11T15:02:48.860 に答える
3

インメモリ ソリューションが実行可能な場合があります。12 個の値 x 200M レコードを格納する必要があるため、正味約 20GB の RAM が必要になります (値ごとに 8 バイトと仮定)。最適化する必要があります (可能な場合は 1/2/4 バイトの値を格納し、メモリ アラインメントを無効にします)。実際には、おそらく 64GB 以上のマシンが必要になるでしょう。

余裕がないと思うのは、大量の小さなメモリ割り当てを必要とするデータ構造を使用することです。データを 1 つの巨大なバッファーに格納する場合でも、ツリー構造のインデックス用に多数の小さな割り当てが必要になる可能性があります。

ツリーが問題にあまり適していない別の理由があります。ユーザーは各フィルターの一連の値を選択する可能性があるため、任意の組み合わせを検索してツリーをトラバースする必要があります。これは、膨大な数のツリー トラバーサルになる可能性があります。

もっと簡単な解決策はどうですか?データセットをグループの最大数に分割する 2 つのフィルターを選択します (これはおそらく ~5000 の値を持つフィルターです)。2D 配列を使用します。各セルが空でない場合は、残りの 10 個の値すべて (9 フィルター + コスト) の構造体の配列を格納します。これらの配列は、3 番目に支配的なフィルターで並べ替えることができます。

ユーザー クエリで、2D 配列内の関連するセルを特定し、関連するセルの各値に対して入力をチェックします (3 番目に支配的なフィルターによって並べ替えられます)。ほとんどのセルでは、チェックする値は 1000 よりはるかに少なくなります。

データ分布によっては、2D 配列の代わりに疎行列を使用することで、メモリを節約できます。一部の .NET 疎行列の実装は、オンラインで入手できます。

于 2013-07-15T05:17:35.473 に答える
2

これはまさに SQL が設計されたシナリオです

最新のシステム (8 GB の RAM を搭載したクアッド コア CPU など) 上の SQL Server は、必要な期間内にすべてのフィルターを簡単に処理するか、フィルターをまったく処理しません。

Sergio のストアド プロシージャを使用してフィルターを実装できます。しかし、それは問題です。C# (または VB.NET) で正しい SQL ステートメントを直接生成するのと同じくらい簡単です。

プロフィール、プロフィール、プロフィール

Map-Reduce やその他の (b) 最先端のテクノロジを探す前に、SQL を試してください。テーブルとインデックスの作成は約 15 分で完了し、クエリの時間を計ることができます。要件に近い場合は、フィルターに基づいて正しい SQL SELECT を生成するコードの記述を開始できます。SQL クエリが要件よりも遅い場合は、最適化するか、他の場所を探すかを決定できます。 しかし、プロファイルを作成するまでは、他のことを試す理由はまったくありません。

于 2013-07-14T06:49:15.463 に答える