4

JSON形式で到着する大きなデータセットの操作を開始しました。残念ながら、データフィードを提供するサービスは、重要な数の重複レコードを配信します。利点として、各レコードには、64ビットの正の整数（Java long）として格納された一意のID番号があります。

データは週に1回到着し、各配信で約1,000万レコードです。現在の配信内の重複と、以前のバッチにあったレコードを除外する必要があります。

重複排除の問題を攻撃するための力ずくのアプローチは、ID番号をJavaセットにプッシュすることです。Setインターフェースには一意性が必要なため、挿入中に失敗すると重複が示されます。

問題は、レコードをインポートする限り、重複を探すためのより良い方法はありますか？

私はHadoopを使用してデータをマイニングしているので、Hadoopを使用してレコードの重複排除を行う良い方法があれば、それはボーナスになります。

4

3 に答える 3

5

マップ出力が一意の ID 番号のキーを持つ MapReduce タスクを作成できますか? そうすれば、reduce タスクで、その ID 番号を持つすべての値の反復子が渡されます。最初の値のみを出力すると、削減された出力に重複がなくなります。

于 2011-09-13T00:22:08.733 に答える
1

そうねぇ。それぞれjava.lang.Long24 バイトを使用します。それぞれHashMap$Entryにも 24 バイトが必要で、の配列にHashMapは 4 バイトが必要です。したがって、マップ用のヒープ ストレージは 52 * 10M = 512M になります。ただし、これは 1 週間の 10M レコード用です。

64 ビット システムを使用している場合は、ヒープ サイズを 5 GB に設定するだけで、どこまで到達できるかを確認できます。

java.util.Setエントリごとに約 16 バイトしか消費しないの他の実装があるはずなので、 の 3 倍のデータを処理できますjava.util.HashSet。私は自分で書いたことがありますが、共有することはできません。代わりに GNU Trove を試すことができます。

于 2011-09-12T19:58:52.410 に答える
0

HDFS に一意の ID のリストを保持し、バッチ ロードのたびに再構築する必要があります。

ケースのカーディナリティが非常に大きいため (1 年間で 10 億を超える一意のレコードが期待できます)、一意の ID リストを複数の部分 (N など) に分割する必要があります。パーティション アルゴリズムはドメイン固有です。一般的なアプローチは、ID を長いハッシュ文字列 (16 バイトで問題ありません) に変換し、2^k バケットを作成することです。

たとえば、k =8 の場合:

バケット #1 には、ハッシュ値が 0 で始まるすべての ID が含まれます バケット #2 には、ハッシュ値が 1 で始まるすべての ID が含まれます ... バケット #256 には、ハッシュ値が 255 で始まるすべての ID が含まれます

新しいバッチを受け取るたびに、最初に重複排除ジョブを実行します。Map は records を読み取り、レコード ID を取得してハッシュし、Key=bucket# (この場合は 0..255) と Value = ID を出力します。各レデューサーは、特定のバケットのすべての IDS を受け取ります。Reducer は、システムで既に認識されている特定のバケットのすべての一意の ID を内部セットにロードし、この内部セットを使用してすべての着信レコード ID をチェックします。レコードにまだ不明な ID がある場合は、内部 Set を更新してレコードを出力します。

レデューサーを閉じると、一意の ID の内部セットが HDFS に出力されます。

ID のセット全体をいくつかのバケットに分割することで、適切にスケーリングするソリューションを作成します。

于 2012-12-10T22:10:04.353 に答える