8

私の仕事では、次の問題の解決策を開発して実装することでした。

30M レコードのデータセットが特定のデータセット フィールドから (キー、値) タプルを抽出し、それらをキーと値でグループ化し、各キーの同じ値の数を格納します。各キーの上位 5000 個の最も頻度の高い値をデータベースに書き込みます。データセットの各行には、シリアル化された XML の形式で最大 100 個の (キー、値) タプルが含まれます。

私はこのような解決策を思いつきました( Spring-Batchを使用):

バッチ ジョブの手順:

ステップ 1.データセットの行を繰り返し処理し、(キー、値) タプルを抽出します。一定数のタプルを取得すると、それらをディスクにダンプします。各タプルは名前パターン「/chunk-」のファイルに移動するため、指定されたキーのすべての値が 1 つのディレクトリに格納されます。1 つのファイル内で値がソートされて格納されます。

ステップ 2.すべての '' ディレクトリを繰り返し処理し、それらのチャンク ファイルを同じ値をグループ化した 1 つのファイルにマージします。値はソートされて保存されるため、O(n * log k) の複雑さでそれらをマージするのは簡単です。ここで、「n」はチャンク ファイル内の値の数、「k」はチャンクの初期数です。

ステップ 3.マージされた各ファイル (つまり、各キー) について、PriorityQueueを使用してその値を順番に読み取り、すべての値をメモリにロードすることなく、上位 5000 の値を維持します。キューの内容をデータベースに書き込みます。

このタスクに約 1 週間を費やしました。これは主に、Spring-Batch を使用したことがないことと、マルチスレッド部分の正確な実装を必要とするスケーラビリティーを重視しようとしたことによるものです。

問題は、私のマネージャーが、このタスクはあまりにも簡単すぎて、それほど多くの時間を費やすことができないと考えていることです。

そして質問は、より効率的なソリューションを知っていますか、それとも実装が簡単な効率の悪いソリューションを知っていますか? そして、私のソリューションを実装するのにどれくらいの時間が必要ですか?

MapReduce のようなフレームワークがあることは知っていますが、アプリケーションは 3 コア、Java ヒープに 1GB の単純な PC で実行することになっているため、使用できません。

前もって感謝します！

UPD: 質問を明確に述べていなかったと思います。別の言い方で質問させてください：

問題があり、プロジェクト マネージャーまたは少なくともタスクのレビュー担当者である場合、私の解決策を受け入れますか? また、このタスクにどのくらいの時間を割きますか?

4

4 に答える 4

1

あなたの解決策は合理的で効率的だと思われますが、私はおそらくSQLを使用します。

キーと値のペアを解析しているときに、SQLテーブルに挿入/更新します。次に、テーブルで上位レコードを照会します。

これはT-SQLのみを使用した例です（SQL 2008ですが、この概念はほとんどすべてのmordern rdbmsで機能するはずです）

/START/と/END/の間のSQLは、コードで実行する必要のあるステートメントになります。

BEGIN
-- database table
DECLARE @tbl TABLE (
    k INT -- key
    , v INT -- value
    , c INT -- count
    , UNIQUE CLUSTERED (k, v)
)
-- insertion loop (for testing)
DECLARE @x INT
SET @x = 0
SET NOCOUNT OFF
WHILE (@x < 1000000)
    BEGIN
    --
    SET @x = @x + 1
    DECLARE @k INT
    DECLARE @v INT
    SET @k = CAST(RAND() * 10 as INT)
    SET @v = CAST(RAND() * 100 as INT)
    -- the INSERT / UPDATE code
    /* START this is the sql you'd run for each row */
    UPDATE @tbl SET c = c + 1 WHERE k = @k AND v = @v
    IF @@ROWCOUNT = 0
        INSERT INTO @tbl VALUES (@k, @v, 1) 
    /* END */
    --
    END
SET NOCOUNT ON
-- final select
DECLARE @topN INT
SET @topN = 50
/* START this is the sql you'd run once at the end */
SELECT 
    a.k
    , a.v 
FROM (
    SELECT 
        ROW_NUMBER() OVER (PARTITION BY k ORDER BY k ASC, c DESC) [rid]
        , k
        , v
    FROM @tbl
) a
WHERE a.rid < @topN
/* END */
END
于 2012-10-15T15:18:50.327 に答える
1

このアプローチは、XML ファイルのプレスキャンを実行してすべてのキーを抽出し、XML ファイルをキーごとに何度も解析するよりも高速であると確信していますか? このソリューションでは多くのファイル管理タスクを実行していますが、これは無料ではありません。

コアが 3 つあるため、同時に 3 つのキーを解析できます (ファイル システムが負荷を処理できる限り)。

于 2012-10-15T10:42:53.837 に答える
0

データのサイズが原因で「単純な」ソリューションを使用できない場合、次の選択肢はSQLデータベースを使用することです。ただし、これらのほとんどはかなりのメモリを必要とするため（RAMで過負荷になるとクロールになります）、検索をMongoDBなどのNoSQLデータベースのようなものにリダイレクトする必要があります。これは、ほとんどがディスクベースの場合でも非常に効率的です。 。（基本的に必要な環境で、使用可能なヒープは1GBのみです）。

NoSQLデータベースは、すべての基本的なブックキーピング（データの保存、すべてのインデックスの追跡、並べ替え）を実行し、すべてのデータが並べ替えられ、挿入時にすでにインデックスが作成されており、/ branch-ファイルの行を並べ替えたり、マージしたりする余分な手順を削除しています。

最終的には、管理がはるかに簡単なソリューションになります。また、この特定のケースにのみ最適化するのではなく、さまざまな種類のクエリを設定することもできます。

プロジェクトマネージャーとして、私はあなたの現在の解決策に反対しません。それはすでに高速であり、問​​題を解決します。ただし、アーキテクトとしては、ソリューションの保守が少し難しいことと、基本的に自分でコーディングしたものと部分的に同じことを行う実証済みのテクノロジーを使用していないことを理由に反対します。最新のデータベースのツリーとハッシュの実装に勝るものはありません。

于 2012-10-15T18:53:39.180 に答える
0

ねえ、メモリ内でそれを行うという昔ながらの方法を試すのはそれほど手間がかからないようです。

私は最初にそれをやってみます、そしてあなたがメモリを使い果たしたら、実行ごとに1つのキーを試してください（@Storstampの答えに従って）。

于 2012-10-15T15:49:01.630 に答える