5

約200万件のレコードがあり、それぞれに重複がないかチェックする必要のある文字列フィールドが約4つあります。具体的には、フィールドとして名前、電話番号、住所、父親名があり、残りのデータとともにこれらすべてのフィールドを使用して重複排除を確認する必要があります。結果の一意のレコードをdbに記録する必要があります。

すべてのレコードのmapreduce、iterateを実装することができました。タスクレートは100/sに設定され、バケットサイズは100に設定されています。請求が有効になっています。

現在、すべてが機能していますが、パフォーマンスは非常に遅いです。10,000レコードのテストデータセットの中で、6時間で1000レコードの重複排除処理しか完了できませんでした。

Javaの現在の設計は次のとおりです。

  1. マップの反復ごとに、現在のレコードを前のレコードと比較します
  2. 前のレコードはdb内の単一のレコードであり、マップの反復ごとに別の前のレコードで上書きするグローバル変数のように機能します
  3. 比較はアルゴリズムを使用して行われ、結果は新しいエンティティとしてdbに書き込まれます
  4. 1つのMapreduceジョブの最後に、プログラムで別のジョブを作成します
  5. 前のレコード変数は、ジョブが残りのデータを含む次の候補レコードと比較するのに役立ちます

これを最短時間で達成するために、GAEリソースをいくらでも増やす準備ができています。

私の質問は次のとおりです。

  1. 重複排除（重複のチェック）の精度は、並列ジョブ/タスクによって影響を受けますか？
  2. この設計をどのように改善できますか？
  3. これは2000万レコードに拡大しますか
  4. 1つのmapreduceジョブ全体で使用できる、マップの反復中に変数（カウンターだけでなく）を読み書きするための最速の方法は何ですか。

フリーランサーはこれを支援することを大いに歓迎します。

ご協力いただきありがとうございます。

4

5 に答える 5

4

レデューサーを利用して、各フィールドに対してsort-uと同等の処理を実行する必要があります。フィールドごとに1つのM/Rジョブを実行する必要があります。マッパーでキーを比較するフィールドを作成し、レデューサーで同じ名前のすべてのレコードをグループ化してマークを付けることができます。2番目のパスは電話など用です。クラスターのサイズに応じて、各パスは非常に高速である必要があります。

編集：@Olafは、OPがおそらく完全にユニークなレコードを望んでいると指摘しました。マルチパートキーを使用すると、これは一意のセットを取得するための1行のhadoopストリーミングコマンドになります。すぐに追加します。

Edit2：ファイル全体に対してsort-uを実行する約束されたストリーミングコマンド。これは、各フィールド（名前、父名、電話番号、住所）がディレクトリhdfs：// example / dedup /input/の1つ以上のファイルで区切られた1行のタブごとに1つのレコードを持つファイルがあることを前提としています。実際のhdfsパスは何でもかまいませんが、単一のファイルを使用することもできます。出力は、hdfs：// example / dedup /output/内の複数のpart-*ファイルになります。また、hadoop-streaming.jarが少し異なる場所にある可能性があるため、コマンドを変更する必要がある場合もあります。4つを超えるフィールドがある場合は、stream.num.map.output.key.fieldsの値を変更します。

   $HADOOP_HOME/bin/hadoop jar $HADOOP_HOME/hadoop-streaming.jar \
-input hdfs://example/dedup/input/ -output hdfs://example/dedup/output/ \
-mapper org.apache.hadoop.mapred.lib.IdentityMapper \
-reducer /usr/bin/uniq \
-D stream.num.map.output.key.fields=4

ローカルファイルシステムファイル内のファイルに固有の結果を取得するには、次のコマンドを実行します。

    $HADOOP_HOME/bin/hadoop fs -cat \
 'hdfs://example/dedup/output/part-*' > results.txt

1つの注意点は、すべての列がキーストリーミングであるため、null値が追加されるため、各行の最後に追加のタブがあります。それは簡単に剥ぎ取られます。

uniq出力を取得するだけでなく、/ usr / bin / uniqを使用するのではなく、独自のJavaクラスまたはコマンドラインプログラムを配置することもできます。そのクラスは、たとえば、レコードDB IDである入力に5番目の列を追加することにより、重複していることがわかったすべてのレコードを更新できます。デフォルトでは、Hadoopはキー全体でパーティションを作成するため、重複するレコードの各グループはレデューサーと一緒にストリーミングされ、これはすべて並行して行われます。詳細については、ストリーミングドキュメントをご覧ください。

于 2011-07-21T03:16:19.697 に答える
3

この問題に取り組むには2つの方法があります。

  1. （1回だけ実行する必要がある場合）AppEngineは、エンティティ内のすべてのプロパティのプロパティインデックスを作成します（実行しないように要求しない限り）。バックエンドを作成し、カーソルを使用してクエリ「SELECT * FROM ORDER BY」をバッチで実行し、重複するプロパティを特定して、それらを修正/削除します。これを並列化できるかもしれませんが、シャードの境界では注意が必要であり、おそらくすべてのコードを自分で作成する必要があります。

  2. マッパーフレームワークを使用して速度を落とすことができますが、並行して実行します。このアプローチにより、挿入時にデータを効率的に重複排除することもできます。一意のプロパティ値を保持する新しいエンティティを導入します。「UniquePhoneNumber」と言います。エンティティは、キーとして電話番号を保持し、この電話番号を持つエンティティへの参照を保持する必要があります。次に、マップを実行して、UniquePhoneNumberを検索します。見つかってその参照が有効な場合は、重複を削除します。そうでない場合は、正しい参照で新しいものを作成してください。このようにして、必要に応じて、他の参照への参照を再ポイントすることも可能です。必ずUniquePhoneNumberを読み、新しいものを作成するか、単一のトランザクション内で新しいものを更新してください。そうしないと、重複は検出されません。

于 2011-07-21T18:28:15.670 に答える
1

各レコードのハッシュコードを生成します。Setレコードをループして、ハッシュコードに基づいて各レコードをに挿入します。これSetで、O（N）の重複排除リストになりました。

于 2011-07-21T03:21:29.427 に答える
1

現在のアプローチを使用するべきではありません。一度に1つのプロセスのみがエンティティを更新できるため、mapreduce全体がその1つのエンティティでボトルネックになります。さらに、mapreduceでは現在、結果セットの順序を指定できないため、すべて（またはほとんど）の重複が見つかる保証はありません。

今のところ、最善の選択肢はおそらく独自のソリューションを構築することです。カーソルを使用して、重複排除するフィールドで並べ替えられた種類のクエリを実行し、重複をスキャンして、重複をチェックし、重複を見つけたら（RPCを減らすためにバッチで）削除します。別のタスクをチェーンする必要がある場合（10分のタスク制限のため）、カーソルを使用して、中断したところから新しいタスクが再開されるようにします。

これを並列化する場合は、重複排除する値の変更が検出されるまでレコードをスキップして各シャードを開始し、そこから開始することができます。シャードの終わりで、グループの終わりに達するまで待ってから停止します。このようにして、シャード境界の端に配置された重複を見逃さないようにします。

于 2011-07-21T05:06:47.010 に答える
0

これは、MapReduceを使用したハッシュ化された自己結合に基づくソリューションです。また、距離編集アルゴリズムを使用してファジー重複マッチングを実行することもできます。重複検出に使用するレコードからフィールドを選択できます。レデューサーは重複したスコアを出力します。

https://pkghosh.wordpress.com/2013/09/09/identifying-duplicate-records-with-fuzzy-matching/

于 2015-05-09T01:30:48.287 に答える