use*_*609 46 c++ algorithm data-structures
磁盘上有1 TB数据,每个数据记录大约1 KB.如何使用512 MB RAM和无限磁盘空间找到重复项？
jem*_*nch 20
到目前为止提供的解决方案似乎过于复杂 一个布隆过滤器,同时是数据结构大谈特谈在过去的几年,是不是最好在这样的情况下应用:因为没有数据可以用散列的内容相关联,就必须不仅保持布隆过滤器,但你必须仍然记录每个(只有6位!)哈希值并记录到磁盘,破坏布隆过滤器的好处,并具有荒谬的高冲突率.
另一方面,对整个TB的合并排序不仅要进行O(n log n)比较,还要进行O(n log n)磁盘流量,因为大多数中间文件必须从磁盘而不是从内存合并.任何真正的解决方案都应该尽可能地减少磁盘流量,因为这是我们的主要瓶颈.
我的解决方案很简单,做出一个假设:数TB的数据记录在有效的一个文件中.
迭代terabyte文件的记录并散列它们.加密哈希在这里是不必要的,昂贵的和太大的; 相反,使用类似64位版本的murmurhash.它可以散布超过2 GiB /秒(比我们可能需要的速度快得多,因为这些天的存储速度)并且具有出色的(尽管不是加密安全的)碰撞阻力.使用64位散列,我们预计第一次碰撞将在2 ^ 32,因此我们大约10亿条记录很可能根本不会发生任何碰撞.
将散列及其关联的记录偏移写入另一个文件.由于记录包含任意二进制数据,因此我们不能依赖Unix的sort(1)对其进行排序,因为某些散列和偏移可能包含sort(1)将解释为换行符.我们将简单地将记录写为固定宽度(可能是16个字节:murmur2 64位散列为8个字节,terabyte文件中的偏移量为8个字节)记录.根据我们的记录数量,生成的文件大约应为16 GB.
我们可以通过读取安全地放入内存并对其进行排序的记录数量来排序此文件,将已排序的块刷新回磁盘.我们可以使用heapsort(它使用O(1)空间)将更多记录放入内存中,而不是使用quicksort(使用O(log n)内存用于调用堆栈),但在大多数实现中,quicksort凭借其内存局部性和较低的指令数而获胜.这些中间文件(应该有35-40个)将写入磁盘.
最后一步是合并这些文件(在内存中;不需要在磁盘上存储结果)收集所有哈希冲突并查找TB级文件中的相关记录,比较重复记录和发出记录(或他们的抵消)以问题指明的方式.
据我所知,这个任务比任何其他提供的解决方案都要少得多,而且它在概念上非常简单:哈希记录,在哈希中查找重复项,并在实际记录中进行验证.
对于磁盘I/O,它将读取TB级数据文件,将16 GB写入磁盘,从磁盘读取16 GB并将其重新分类,然后读取并返回重复项.作为优化,对记录进行散列处理的进程可以在将它们刷新到磁盘之前将它们累积到内存中,然后在执行此操作之前对它们进行排序:切断16 GB中间文件,并允许进程从散列直接转移到合并和报告重复项.
Pot*_*ter 18
使用Bloom过滤器:同时哈希表.根据维基百科,哈希的最佳数量是ln(2) * 2^32 / 2^30 ? 2.77 ? 3.(嗯,插入4会产生较少的误报,但3对于此应用程序仍然更好.)这意味着你有一个512兆字节或4千兆位的表,处理每个记录在这个巨大的海域设置三个新位.如果已经设置了所有三个位,那么这是一个潜在的匹配.将三个哈希值记录到文件中.否则,将它们记录到另一个文件.记下记录索引以及每个匹配项.
(如果可以容忍5%的错误率,请省略大文件并使用小文件作为结果.)
完成后,您应该有一个约49M可能的正匹配文件和一个975M负数的文件,但可能与肯定匹配.将前者读入a vector<pair<vector<uint32_t>,vector<uint32_t> > >(后者中的索引vector,前者可以是a array)并对其进行排序.把索引放在另一个vector<uint32_t>; 他们已经分类了.读取大文件,但不是设置表的位,而是在中查找哈希值vector.(例如,使用equal_range.)使用正文件索引列表来跟踪否定文件中当前记录的索引.如果未找到匹配项,请忽略.否则,附加记录的索引match->second.push_back(current_negative_record_index).
最后,遍历地图和记录索引的向量.任何具有多个条目的存储桶"几乎"肯定包含一组重复项,但您已经走到这一步,所以请查看它们并完全比较它们以确保.
总同步磁盘I/O :(一次通过= 1 TiB)+(每条记录96个哈希位= 12 GiB)+(每个正32个索引位= ~200 MiB).
最后的编辑(认真):第二个想法,Bloom Filter方面可能并没有真正帮助到这里.散列数据的数量更多是误报数量的限制因素.仅使用一个散列函数,散列数据的总量将为4 GiB,并且1.24亿个预期误报的索引将为~500 MiB.这应该全球优化这一战略.
澄清(得到一个downvote):Bloom过滤器的误报和哈希冲突之间存在区别.除非返回原始记录并进行比较,否则无法解决哈希冲突,这很昂贵.可以通过返回原始哈希值并比较它们来解决Bloom误报,这是该算法的第二次传递.因此,在第二个想法,"最终"编辑中描述的单哈希过滤器将不适当地导致磁盘搜索.双哈希布隆过滤器会增加在match地图的单个桶中结束的误报数量,并且会使误报数量减少到数千万.
mjv*_*mjv 13
这是很多记录;-)大约1,000,000,000.最好是聪明一点......
记录的性质未指定:我们是否只是通过顺序读取它们来发现它们,或者是否有某种索引,或者它们是否存储在各种目录中的文件中？问题中未指定的是dbms的可用性,我们可以将其用于类索引数据(而不必使用我们自己的代码对其进行排序).对重复数量的[甚至粗略]想法也有助于将一些选择引向有效的过程.
如果没有索引,我们可以/应该创建一个; 这可以在第一次通过数据时完成.相同的传递将用于为每个记录生成各种类型的消息摘要(散列)(或者为了效率目的,可能为记录的前几百个字节).
一般的想法是快速生成一个索引,可用于识别可能的重复项,并最终确定实际重复的列表,可能通过并行处理.
索引中有用的信息是:
散列的选择至关重要:应该以牺牲完全分布的算法为代价来支持快速算法; 每个记录的散列字节数也是一个折衷方案,可能100到200个字节(即大约10到20%的平均记录大小)是一个很好的值,取决于重复的预期比例,并取决于节省时间这提供了(与散列整个记录相比).(见下面的编辑)
一旦这样的索引可用,我们可以[相对快速/毫不费力地]获得可能重复的计数; 基于这一结果,可以完成旨在提高指数质量的第二次通过(如果认为不够有选择性)(省略了容易被认为是唯一的记录).该第二遍可以在整个记录(不包括第一个散列的前x个字节)上或在记录的另一个子集上计算另一个散列.请注意,由于索引,如果可能的话,第二遍可以是多线程的.
第二次或最后一次传递需要在一组可能的匹配(相同长度,相同的哈希码,相同的前x个字节)内对记录进行排序.这可以通过Pax Diablo描述来实现,索引的优点是这样的操作可以再次是多线程的并且涉及更小的集合(其中许多).补充:在这里,尼克约翰逊再次强调,如果我们使用长哈希码(他建议使用128字节长的SHA1),第二遍可能是不必要的.假设部分散列记录没有任何好处,这是一个非常合理的解决方案,因为索引可以驻留在磁盘上,但是比我们整理/存储整个记录时更快地排序和存储.
编辑:尼克约翰逊提出了一个很好的观点,即磁盘存储中的搜索延迟可能使得简单的顺序读取更快,并且瓶颈是磁盘I/O绑定,同时运行的快速哈希函数可能实际上比顺序更快阅读,因此不会添加到整个过程中.这是一种可能的可能性(特别是如果有效地要求检测每个记录开始/结束等顺序读取),这就是为什么我通过写" 取决于节省时间提供 ......"来"削减我的赌注".这表示磁盘上记录的实际结构是问题的开放参数之一(例如,如果我们只是从目录中的单个文件读取,因此强制执行非顺序读取),并且可能还有TeraByte大小的存储由花哨的RAID支持,其中寻求延迟同时保持关注通常得到很大改善.
我坚持我的建议,两遍通过方法可能比每条记录完全散列的方法更有效,但我希望我强调了单通方法的可能性和好处.与许多面试问题一样,手头的情况有几个特点没有说明; 这个想法并不是要让申请人提供绝对正确的答案(尽管有些答案可能是错误的!)而是要深入了解他/她的思维过程以及识别选项和决策点的能力.
找到合适的散列函数并散列每条记录,将带有索引的散列列表存储到文件中.现在按哈希对哈希文件进行排序.最后检查匹配哈希的整个记录是否真实重复.
当然,这取决于您希望找到多少重复项以及之后您将如何处理这些信息.