两个大文本文件的高效文件比较

在我们的使用案例中，我们从我们的客户（大小约30GB）获得大量快照文本文件（tsv，csv等）以及数百万条记录。数据是这样的：两个大文本文件的高效文件比较

ItemId (unique), Title, Description, Price etc. 
shoe-id1, "title1", "desc1", 10 
book-id-2, "title2", "desc2", 5

无论何时，我们从客户得到的快照，我们需要计算一个“增量”：

插入 - 插入的记录（只存在于最新的文件，而不是以前的一个），
更新 - 在任何其他列
删除（只存在于PR的ID相同，但不同的价值这个文件并不是最新的）。

（数据可能在后续文件中没有顺序，并且没有在任何列上真正排序）。

我们需要能够为不同的客户每天运行多次。

我们当前将所有来自快照文件1的数据存储到SQL服务器（12个分片（由customerId分区），总共包含10亿行），并在收到快照文件2时使用多个查询计算差异。这被证明是非常低效的（小时，删除特别棘手）。我想知道是否有更快的解决方案。我愿意接受任何技术（例如hadoop，nosql数据库）。关键是速度（最好是分钟）。

来源

2017-10-12 user5121292

我正在考虑将独特的id读入两个Perl哈希中 - 一个用于旧的旧哈希，另一个可能是每个记录的剩余字段的CRC/SHA校验和作为存储在哈希中的项目。检查通用/独特的会员资格应该非常快。尝试添加一个Perl标签也许。 –

你提到过关于文件大小。我可以知道速度是多少？意思是，你多久会得到这个后续文件。 –

每天约20K次 – user5121292

正常情况下，判断数据集中是否出现id的最快方法是使用散列法，因此我将使用id作为关键字并将其余列的MD5校验和或CRC作为存储在那把钥匙。如果你的数据有很多列，这应该可以缓解内存压力。我为什么这么想？因为你说你有数百万条记录的GB数据，所以我推断每条记录的大小必须是千字节的数量 - 即相当宽。

所以，我能合成的在Perl 13M旧值的哈希和15M新值的哈希，然后找到添加，更改，如下面取出。

#!/usr/bin/perl 
use strict; 
use warnings; 

# Set $verbose=1 for copious output 
my $verbose=0; 

my $million=1000000; 
my $nOld=13*$million; 
my $nNew=15*$million; 

my %oldHash; 
my %newHash; 
my $key; 
my $cksum; 
my $i; 
my $found; 

print "Populating oldHash with $nOld entries\n"; 
for($i=1;$i<=$nOld;$i++){ 
    $key=$i-1; 
    $cksum=int(rand(2)); 
    $oldHash{$key}=$cksum; 
} 

print "Populating newHash with $nNew entries\n"; 
$key=$million; 
for($i=1;$i<=$nNew;$i++){ 
    $cksum=1; 
    $newHash{$key}=$cksum; 
    $key++; 
} 

print "Part 1: Finding new ids (present in newHash, not present in oldHash) ...\n"; 
$found=0; 
for $key (keys %newHash) { 
    if(!defined($oldHash{$key})){ 
     print "New id: $key, cksum=$newHash{rkey}\n" if $verbose; 
     $found++; 
    } 
} 
print "Total new: $found\n"; 

print "Part 2: Finding changed ids (present in both but cksum different) ...\n"; 
$found=0; 
for $key (keys %oldHash) { 
    if(defined($newHash{$key}) && ($oldHash{$key}!=$newHash{$key})){ 
     print "Changed id: $key, old cksum=$oldHash{$key}, new cksum=$newHash{$key}\n" if $verbose; 
     $found++; 
    } 
} 
print "Total changed: $found\n"; 

print "Part 3: Finding deleted ids (present in oldHash, but not present in newHash) ...\n"; 
$found=0; 
for $key (keys %oldHash) { 
    if(!defined($newHash{$key})){ 
     print "Deleted id: $key, cksum=$oldHash{$key}\n" if $verbose; 
     $found++; 
    } 
} 
print "Total deleted: $found\n";

这需要53秒在我的iMac上运行。

./hashes 
Populating oldHash with 13000000 entries 
Populating newHash with 15000000 entries 
Part 1: Finding new ids (present in newHash, not present in oldHash) ... 
Total new: 3000000 
Part 2: Finding changed ids (present in both but cksum different) ... 
Total changed: 6000913 
Part 3: Finding deleted ids (present in oldHash, but not present in newHash) ... 
Total deleted: 1000000

出于测试的目的，我从0..12,999,999在oldHash运行键和按键在newHash运行从1,000,000..16,000,000那么我可以很容易地知道，如果它的工作，因为新的键应该是13,000,000..16,000,000和删除的键应该是0..999,999。我也使checksums在0和1之间交替，这样50％的重叠ID应该看起来不同。

已经在一个相对简单的方式来完成它，现在我可以看到，你只需要校验部分找到改变的ID，这样你就可以做1部分和第3无校验以节省内存。在加载数据时，您也可以一次执行第2部分的一个元素，因此您不需要将所有旧的和所有新的ID都预先加载到内存中。相反，当您将另一组ID传输到内存中时，您将加载较小的旧数据集和新数据集，然后逐个检查一个ID是否更改，这会降低对内存的要求。最后，如果这种方法有效，它可以很容易地在C++中重新完成，例如，进一步加快速度并进一步减少内存需求。

来源

2017-10-15 10:23:44

两个大文本文件的高效文件比较

回答

相关问题