如果磁盘上的数据集为1 TB,每个数据logging约为1 KB,那么如何使用512 MB RAM和无限磁盘空间来查找重复数据?

磁盘上有1 TB数据,每个数据logging大约1 KB。 如何使用512 MB RAM和无限磁盘空间查找重复项?

使用布隆filter :同时哈希表。 根据维基百科,散列的最佳数目是ln(2) * 2^32 / 2^30 ≈ 2.77 ≈ 3 。 (嗯,插入4会减less误报,但是对于这个应用程序来说更好3)。这意味着你有512兆字节或者4千兆字节的表格,并且处理每个logging在这浩瀚的大海中设置三个新的位。 如果所有三位都已经设置好了,那么这是一个潜在的匹配。 将三个散列值logging到一个文件中。 否则,将它们logging到另一个文件。 请注意logging索引以及每个匹配项。

(如果5%的错误率是可以接受的,则省略大文件,并使用小文件作为结果。)

完成后,你应该有一个约49M可能的正面匹配文件和一个975M底片文件,但可能匹配正面。 将前者读入一个vector<pair<vector<uint32_t>,vector<uint32_t> > > (后一个vector索引,前者可以是一个array ),然后对其进行sorting。 将索引放入另一个vector<uint32_t> ; 他们已经sorting。 读取大文件,而不是设置表的位,findvector的哈希值。 (例如,使用equal_range 。)使用正文件索引列表来跟踪负文件中当前logging的索引。 如果找不到匹配,请忽略。 否则,追加logging的索引match->second.push_back(current_negative_record_index)

最后,遍历地图和logging索引的向量。 具有多个条目的任何存储桶“几乎”肯定包含一组重复,但是你已经走到了这么远,所以查看它们并完全比较它们。

总同步磁盘I / O :(一次通过= 1个TiB)+(每个logging96个哈希位= 12个GiB)+(每个正向32个索引位=〜200个MiB)。

最后的编辑 (认真):第二个想法,布卢姆filter方面可能没有真正帮助这里。 哈希数据的数量比误报的数量更受限制。 仅使用一个散列函数,散列数据的总数将是4 GiB,并且1.24亿个预期误报的指数将是〜500 MiB。 这应该全球优化这个战略。

澄清 (得到一个downvote):布卢姆filter的假阳性和散列冲突之间有区别。 哈希碰撞不能解决,除非通过返回原始logging和比较,这是昂贵的。 布卢姆假阳性可以通过返回原始哈希值并比较它们来解决,这是该algorithm的第二遍。 因此,第二个想法是,“最终”编辑中描述的单哈希filter会不当地导致磁盘寻道。 两个哈希值的Bloomfilter会增加match映射的单个桶中的误报数量,并将误报的数量降低到数千万。

目前提供的解决scheme似乎太复杂了。 布卢姆filter虽然是过去数年的数据结构,但在这种情况下并不是最好的应用:因为没有数据可以与散列的内容相关联,所以您不仅必须维护布卢姆filter,仍然必须logging每个(只有6位!)散列值并logging到磁盘,破坏布隆filter的好处并具有非常高的冲突率。

另一方面,对整个TB进行合并sorting不仅要进行O(n log n)比较,还要进行O(n log n)磁盘通信,因为大部分中间文件必须从磁盘合并,而比从记忆。 任何真正的解决scheme都应尽可能地减less磁盘stream量,因为这是我们的主要瓶颈。

我的解决scheme很简单,做一个假设:数据的TB级被logging在一个文件中。

迭代terabyte文件的logging并将其散列。 一个密码散列是不必要的,这里成本太高, 而是使用类似64位版本的murmurhash 。 它可以散列超过2吉比特/秒(远快于我们可能需要,考虑到这些天的存储速度),并具有优良的(虽然不是密码安全的)碰撞阻力。 对于64位散列, 我们预计我们的第一次冲突为2 ^ 32 ,所以我们的大约10亿条logging很可能根本没有任何冲突。

将散列及其关联的logging偏移写入另一个文件。 由于logging包含任意的二进制数据,所以我们不能依靠Unix的sorting(1)对它进行sorting,因为一些散列和偏移量可能包含(1)将被解释为换行符。 我们简单地将logging写成固定宽度(可能是16字节:murmur2 64位散列为8字节,TB字节为偏移量为8字节)。 根据我们的logging数量,结果文件应该是大约16 GB。

我们可以通过读取将安全地放入内存中的logging数量并对它们进行sorting来对这个文件进行sorting,将已sorting的块刷新到磁盘。 我们可以使用heapsort(它使用O(1)空间)比使用快速sorting(对于调用堆栈使用O(log n)内存O(log n)将更多logging放入内存中,但是在大多数实现中,快速sorting凭借其内存局部性和较低的指令数量。 这些中间文件(应该有35-40个)将写入磁盘。

最后一步是合并这些文件(在内存中;为此不需要在磁盘上存储结果),收集所有的散列冲突并在TB文件中查找关联的logging,比较logging的重复和发送logging(或他们的偏移量)以任何方式指定。

据我所知,这个任务比任何其他提供的解决scheme都要less得多,而且它在概念上非常简单:散列logging,在哈希中查找重复项,并在实际logging中进行validation。

对于磁盘I / O ,它将读取terabyte数据文件,将16 GB写入磁盘,从磁盘读取16 GB并将其写回已sorting,然后读取并返回重复项。 作为一种优化,logging的过程散列可以在将它们刷新到磁盘之前累积到内存中,在这之前对它们进行sorting:删除16 GB的中间文件,并允许进程从哈希直接迁移到合并和报告重复项。

这是很多logging;-)在10亿的数量级。 最好是明智的…

logging的性质是没有说明的:我们只是通过顺序读取来发现它们,或者是某种索引,或者是将它们存储为各种目录中的文件? 在这个问题中还没有指定的是dbms的可用性,我们可以使用索引式数据(而不是用我们自己的代码进行sorting)。 对重复数目的一个[甚至是粗略的]概念将有助于将一些select导向有效的过程。

如果没有索引存在,我们可以/应该创build一个; 这可以通过数据的第一遍完成。 对于每个logging(或者为了效率的目的,对于logging的前几百个字节),将使用相同的通道来产生各种logging的消息摘要(散列)。

总体思路是快速生成一个可用于识别可能的重复的索引,并可能通过并行处理来最终确定实际重复的列表

在索引中有用的信息是:

  • logging的长度
  • 前几个字节的文字
  • 哈希码(更多在这下面)
  • 也可以是文件中的偏移量或任何指向数据的指针,但当然不像上述3个元素,这不能用于识别潜在的匹配。

散列的select是至关重要的:应该以一个完美分布的代价来支持快速algorithm; 每个logging散列的字节数也是一个折衷scheme,根据预期的重复比例,可能有100到200个字节(即大约平均logging大小的10到20%)是一个很好的值,并且取决于节省的时间这提供了(与整个logging的哈希相比)。 (见下面的编辑)

一旦这样的索引可用,我们可以[相对快速/毫不费力地]获得可能重复的计数; 基于这个结果,第二遍旨在提高指数的质量,如果它被认为是不够有select性的话,可以完成(省去很容易被认为是唯一的logging)。 第二遍可以计算另一个散列,整个logging(不包括第一个散列的前x个字节),或另一个logging子集。 请注意,由于索引,如果可能的话,第二遍可以是multithreading的。

第二遍或最后一遍要求在一组可能的匹配(相同的长度,相同的散列码,相同的前x字节)内sortinglogging。 这可以通过Pax Diablo所描述的来实现,索引的优点是这样的操作同样可以是multithreading的并且涉及更小的集合(其中许多集合)。 补充 :在这里尼克·约翰逊再次提出了一个很好的观点:如果我们使用一个长的散列码(他build议128字节长的SHA1),第二遍可能是不必要的。 假设部分散列logging没有任何好处,这是一个非常合理的解决scheme,因为索引可以驻留在磁盘上,而且比sorting/存储整个logging更快速地进行sorting和存储。


编辑尼克约翰逊是一个优秀的观点,在磁盘存储寻求的延迟可能是这样一个简单的顺序读取速度更快,瓶颈磁盘I / O绑定,一个快速哈希函数并行运行可能会有效地比顺序阅读,因此不会增加整个过程。 这是一个可能的可能性(特别是如果有效地要求检测每个logging开始/结束时的顺序读取等),这就是为什么我通过写入“ 取决于节省的时间提供 …”来“削弱我的赌注”。 这表示磁盘上的logging的实际结构是问题的开放参数之一(例如,如果我们只是从目录中的单个文件读取,因此施加非顺序读取),并且也可能是TeraByte大小的存储由一个奇特的RAID支持,寻求延迟,同时保持关注通常大大改善。
我支持我的build议,一个两通的方法可能比每个logging完全散列的方法更有效率,但是我希望我已经强调了单通方法的可能性和好处。 和许多面试问题一样,手头的情况的几个特点是没有说明的; 这个想法并不是为了看到申请人提供绝对的正确答案(尽pipe有些答案可能是错误的!),而是要了解他/她的思维过程以及确定选项和决策点的能力。

find一个合适的哈希函数并散列每条logging,将散列索引存储到一个文件中。 现在通过散列对散列文件进行sorting。 最后检查匹配散列的整个logging​​是否为真正的重复。

当然,这取决于你期望find多less重复数据,以及随后将如何处理这些信息。

将数据一次加载到内存512M中,然后对该块进行sorting并将其写入磁盘(作为自己的文件)。 一旦整个1T完成了这样的工作,将各个文件合并为一个大的文件,然后依次读取这个大的(sorting的)文件,将其写入最终文件,同时删除重复的logging。

1T,每次512M,将会有大约210万个文件(假设SI单位的二进制定义而不是十进制)。 1K条logging512M一次只允许524,288条logging在内存中,所以你可能不得不分两步进行合并sorting。 换句话说,将四百一十万个文件合并sorting,创build四个较大的文件,然后将这四个文件合并sorting为大的sorting文件。 那么这就是你按顺序处理删除重复的东西。

合并sorting就是简单地合并多个已sorting的文件,只需从每个文件中select第一个剩余logging并select“最低”即可。 例如,两个文件ab

 ab 7 6 3 5 1 4 2 \_/ 1 (a) 2 (b) 3 (a) 4 (b) 5 (b) 6 (b) 7 (a) 

生成每个logging的散列; 将logging编号和散列logging在内存中,在必要时溢出到文件(在写入文件之前按照散列顺序对数据进行sorting)。 当你想出一个新的哈希,检查它是否已经存在于内存中 – 这是一个早期检测。 (这可能会也可能不是主要的好处)。

当你读完所有的数据后,你将会得到几个哈希加上logging号的文件,这些文件已经被sorting了。 将这些文件合并在一起,随时查找重复项。 你甚至不需要做更多的事情来logging这个应用程序的副本,所以你可以放弃散列,一旦他们被certificate是独一无二的。

给定的大小 – 0.5 GB的内存,1000 GB的数据,每个logging1 KB,所以约10亿logging – 假设一个256位散列(虽然128位可能是足够的),我们会使用32个字节的散列和4个字节的logging号和约10亿条logging,我们需要约36 GB的sorting文件,在500 MB文件(对应于可用的内存)生成,所以将有70-80文件合并在最后,这似乎相当易于pipe理。 该列表会给你logging的数字 – 你将不得不访问1 TB文件来读取logging。 你需要考虑一下你将要做什么与重复; 你是否需要关于最初的logging额外信息,这是重要的你保留和你拒绝哪些重要。 等等。

首先,在无限大的驱动器上configuration无限大的交换文件的计算机…

您可以使用散列来减less问题的大小。 例如,如果您有1 TB的数据,那么您可以定义一个散列函数,并将数据分成10个文件(每个文件的大小小于1 TB)。 之后,如果一个文件仍然太大,重复该过程直到文件可以存储在内存中。 最后,你可以通过sorting来计算出现的时间。