如何从大数据馈送中排除重复记录？

我已经开始使用以JSON格式到达的大型数据集。不幸的是，提供数据馈送的服务提供了不平凡数量的重复记录。另一方面，每条记录都有一个唯一的Id号码存储为64位正整数（Java long）。如何从大数据馈送中排除重复记录？

数据每周到达一次，每次交付约为10M条记录。我需要排除当前交付中的重复项以及之前批次中的记录。

攻击重复数据删除问题的蛮力方法是将Id号码推送到Java Set。由于设置接口需要唯一性，插入过程中的失败将表明重复。

现在的问题是：有没有更好的方法来寻找重复的长作为我导入记录？

我正在使用Hadoop来挖掘数据，所以如果有一种很好的方法可以使用Hadoop来重复记录，那将是一种奖励。

来源

2011-09-12 gras

您可以创建一个MapReduce任务，其中地图输出具有唯一ID号的密钥吗？这样，在你的reduce任务中，你将传递一个具有该ID号的所有值的迭代器。只输出第一个值，减少的输出将不会有重复。

来源

2011-09-13 00:22:08 salexander

这是比Rolands更好的解决方案。 –

@salexander - 我可以为新批数据做到这一点，但是如何识别前几周现有记录的重复项。例如，以前的数据有ID [1..10];新数据包含[11,11,9]。 map/reduce作业会找到重复的11，但9在这个集合中是唯一的，但与整个集合相比不是这样。我知道我可以重新运行整个数据集，但这看起来很愚蠢。 – gras

在这种情况下，我们需要将所有密钥放在一个简化器中，这可能会减慢过程 – sunitha

让我看看。每个java.lang.Long需要24个字节。每个HashMap$Entry也需要24个字节，并且HashMap的数组需要4个字节。所以你有52 * 10M = 512M的地图堆存储空间。尽管如此，这是一周的10M记录。

如果您使用的是64位系统，则可以将堆大小设置为5 GB，然后查看得到的结果。

应该有一个java.util.Set的其他实现，每个条目只消耗大约16个字节，因此您可以像处理java.util.HashSet一样处理三倍的数据。我自己写了一篇，但我无法分享。您可以尝试使用GNU Trove。

来源

2011-09-12 19:58:52

您必须保留HDFS中的唯一标识列表，并在每批加载后重建它。

由于您的案例中的基数非常大（您可以预计一年内> 1B的唯一记录），您的唯一ID列表需要拆分为多个部分，比如N。分区算法是特定于域的。在一般的方法是ID转换为长的散列字符串（16个字节是OK），并创建2 ^ķ桶：

对于k = 8，例如：

桶＃1包含其哈希值开始的所有ID 0 桶＃2包含其散列值开始的所有ID与1 ... 斗＃256包含其散列值255

开始您收到第一次运行重复数据删除作业每一批新的所有ID：地图读取记录，取记录ID，将其散列并输出Key = bucket＃（在我们的例子中为0..255）和Value = ID。每个Reducer接收给定桶的所有IDS。 Reducer将系统中已知的给定桶的所有唯一ID加载到内部Set中，并使用此内部Set来检查所有输入记录ID。如果记录有尚未知道的ID，则更新内部设置并输出记录。

在缩小器关闭时输出内部将唯一ID集返回到HDFS。

通过将整套ID分成多个桶，您可以创建可以很好扩展的解决方案。

来源

2012-12-10 22:10:04

如何从大数据馈送中排除重复记录？

回答

相关问题