如果磁盘上的数据集为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“最低”即可。 例如，两个文件a和b ：
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来计算出现的时间。
