通过多线程处理大文件

Question

通过多线程处理大文件

6

磁盘上有一个非常大的文件（>10G），文件中每一行都由一个行号和一个人名组成，就像这样：

1 Jane
2 Perk
3 Sime
4 Perk
.. ..

我需要读取这个大文件，并找出每个姓名的频率，最后按照频率降序输出结果，格式如下：

Perk 2
Jane 1
Sime 1

正如面试官要求的那样，上述工作应尽可能高效地完成，并且允许使用多线程。我的解决方案大致如下：

由于文件太大，我将文件分成几个小文件，每个小文件约为100M，通过lseek可以定位每个小文件的开始和结束位置(beg, end)；
对于这些小文件，有一个共享的哈希映射，使用人名作为键，目前为止显示次数作为值；
对于每个小文件，有一个单独的线程遍历它，每当线程遇到一个人名时，它就会在共享哈希映射中增加相应的value；
当所有线程完成后，我认为是时候按value字段对哈希映射进行排序了。

但是因为该文件中可能有太多的名称，所以排序速度会很慢。我没有想出好的方法来按降序输出名称。

希望有人能帮我解决上述问题，给我一个更好的多线程处理和排序的解决方案。

- Alcott

你好。在你的问题中，面试官明确表示“允许使用多线程”。这基本上意味着面试官要求编写一个程序，你可以（如果选择）控制是否使用线程，以及使用多少个线程。我认为你最初的提议非常接近（其他帖子也是如此）。然而，问题并没有要求使用shell命令或其他方法。在选择最终答案时，请考虑这一点。谢谢！ - aps2012

5个回答

6

如果我在面试中使用“高效”这个词提出这个问题，我希望得到的答案是类似于“cut -f 2 -d ' ' < file | sort | uniq -c”的回答，因为效率通常是关于不浪费时间解决已经解决过的问题。实际上，这是一个好主意，我会在我们的面试问题中添加类似的内容。

你的瓶颈将是磁盘，所以各种多线程都会过度设计解决方案（这也有助于“效率”）。像这样拆分阅读将使事情变慢，如果有旋转磁盘，或者至少使缓冲高速缓存更加混乱，不太可能采用落后算法。这是个坏主意，不要这样做。

- Art

1

如果它在单个磁盘上，这些工具会为此情况进行疯狂的优化。再加1。 - Sanjeev Satheesh

1

@art，我认为您误解了OPs的问题。问题可能措辞不清，但问题的精神是明显的：这是一个_编程_问题，预期要有一个_编程解决方案_。这里的关键词是“多线程”，而不仅仅是“效率”。任何留给候选人选择使用多线程的问题都要求编写程序，因为控制解决方案的线程_需要编写程序_。在这种情况下依赖于 shell 几乎肯定会被视为未回答该问题。 - aps2012

@aps2012 我不同意。 "当你手中只有一把锤子时，每个问题都看起来像一个钉子"。当我面试程序员时，我寻找的是能够解决问题的人，而不是每次需要完成任务就拿出他们的编辑器和编译器的人。世界上充满了过度设计的重新发明的轮子。在这种情况下，很明显，除非我们谈论连接到20年前的CPU的闪电般快速的磁盘的某些非常特殊的情况，否则多线程将不会使解决方案受益。它可能被提及为一个红鲱鱼。"编写一个在C中添加两个数字的函数，允许使用异或运算符。" - Art

3

面试官最初的问题陈述为“...并且允许使用多线程”。然而，这个问题的措辞可能有点含糊，但问题的精神是显而易见的：面试官要求候选人编写一个程序来解决问题，并分析/证明在所提出的解决方案中使用（或不使用）多线程的用途。这是一个简单的问题，用于测试候选人思考大规模问题并解释他们所做的算法选择的能力，确保候选人不只是从互联网网站上复制一些东西而没有理解。

鉴于此，无论是否使用多线程，这个特定的面试问题都可以高效地在O（n log n）（渐近意义上）内解决，而多线程可以被用来对实际执行时间进行对数加速。

解决方案概述

如果您被一家顶级公司问到OP的问题，以下方法将显示您真正理解了问题和涉及的问题。我们提出了一个两阶段的方法：

1.首先将文件分区并读入内存。 2.在分区上使用特殊版本的归并排序，同时在文件排序时计算每个名称的频率。

例如，让我们考虑一个包含32个名字的文件，每个名字只有一个字母，每个名字的初始频率计数为1。上述策略可以可视化如下：

1. File:           ARBIKJLOSNUITDBSCPBNJDTLGMGHQMRH                32 Names

2. A|R|B|I|K|J|L|O|S|N|U|I|T|D|B|S|C|P|B|N|J|D|T|L|G|M|G|H|Q|M|R|H 32 Partitions
   1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1|1 with counts

3.  AR  BI  JK  LO  NS  IU  DT  BS CP  BN  DJ  LT  GM  GH  MQ  HR  Merge #1
    11  11  11  11  11  11  11  11 11  11  11  11  11  11  11  11  and tally

4.   ABRI    JKLO    INSU    BDST   BCNP    DJLT    GHM     HMQR   Merge #2
     1111    1111    1111    1111   1111    1111    211     1111   and tally

5.     ABIJKLOR         BDINSTU       BCDJLNPT         GHMQR       Merge #3
       11111111         1111211       11111111         22211       and tally

6.           ABDIJKLNORSTU                  BCDGHJLMNPQRT          Merge #4
             1212111111211                  1112211211111          and tally

7.                       ABCDGHIJKLMNOPQRSTU                       Merge #5
                         1322111312132113121                       and tally

因此，如果我们从头到尾在内存中读取最终列表，它将产生排序后的列表：

A|B|C|D|G|H|I|J|K|L|M|N|O|P|Q|R|S|T|U
-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-+-
1|3|2|2|1|1|1|3|1|2|1|3|2|1|1|3|1|2|1 = 32 Name instances (== original file).

为什么这个解决方案是有效的

无论使用哈希表（原始帖子建议的）还是使用多线程，此问题的任何解决方案都不能比O（n log n）更有效，因为必须执行排序。在此限制下，有两种可以采用的策略：

从磁盘读取数据，使用哈希表管理名称/频率总计，然后对哈希表内容进行排序（原始帖子建议的方法）
从磁盘读取数据，从文件初始化每个名称及其频率总计，然后同时合并排序名称并汇总每个名称的所有总计（此解决方案）。

解决方案（1）要求在读入所有数据后对哈希表进行排序。解决方案（2）在排序时执行频率统计，因此已删除了哈希表的开销。即使根本不考虑多线程，在解决方案（1）中使用最有效的哈希表实现，解决方案（2）已经更加高效，因为它根本没有哈希表的开销。

多线程的限制

在解决方案（1）和解决方案（2）中，假设解决方案（1）使用了有史以来最有效的哈希表实现，则两个算法在O（n log n）方面执行相同。只是它们的操作顺序略有不同。然而，当多线程运行解决方案（1）时，实际上会使其执行速度减慢，但是多线程运行解决方案（2）将大幅提高其速度。这怎么可能呢？

如果我们在解决方案（1）中进行多线程工作，在磁盘读取或之后进行排序，我们会遇到一个竞争哈希表的问题，因为所有线程都尝试同时访问哈希表。特别是对于写入表格，这种竞争可能使解决方案（1）的执行时间严重受损，甚至可能导致不使用多线程可以获得更快的执行时间。

为了使多线程能够提供执行时间加速，有必要确保每个线程执行的工作块与每个其他线程独立。这将允许所有线程以最大速度运行，而没有共享资源的争用，并且可以更快地完成工作。解决方案（2）完全做到了这一点，删除了哈希表，并采用归并排序，这是一种分而治之算法，可以将问题分解为相互独立的子问题。

多线程和分区以进一步提高执行时间

为了实现合并排序的多线程，可以将文件分成若干个分区，并创建新线程来合并每对相邻的分区。由于文件中的名称长度不固定，因此必须从头到尾按顺序扫描文件才能进行分区；不能使用文件的随机访问。然而，由于任何解决方案都必须至少扫描一次文件内容，因此仅允许串行访问文件仍然可以产生最佳解决方案。

对于多线程解决方案（2），可以期望在执行时间上获得怎样的加速？这种算法的分析非常棘手，尽管很简单，已经成为各种白皮书的研究对象。然而，将文件分成n个分区将使程序比在单个CPU上不分区执行快(n / log(n))倍。简单地说，如果单个处理器需要1小时处理一个640GB的文件，则将文件分成64个10GB的块，并在具有32个CPU的机器上执行，程序将在约6分钟内完成，增加了10倍（忽略磁盘开销）。

- aps2012

3

我认为多线程不是一个好主意。程序的“慢”部分是从磁盘读取数据，而将从磁盘读取操作多线程化并不能使其更快。这只会使其变得更加复杂（例如，对于每个块，您必须找到第一个“完整”的行，您必须协调各个线程，并且每次访问共享哈希映射时都必须锁定它）。您可以使用“本地”哈希映射，然后在结束时合并它们（当所有线程完成（在10 GB末尾）时，部分哈希映射被合并）。现在您无需同步访问共享映射。

如果完整的哈希映射可以保留在内存中，我认为排序结果最容易。您只需将其复制到malloc（ed）的内存块中，然后按其计数器qsort它即可。

- xanatos

“local” hashmap 是什么意思？每个小文件都有独立的hashmap吗？ - Alcott

@Alcott 假设您从“主”程序中启动了10个线程。每个线程都有一个哈希映射。主程序等待所有10个线程完成。主程序将10个哈希映射合并成一个超级哈希映射（它可以重用其中一个10个线程的哈希映射并总结其他哈希映射），然后创建报告。 - xanatos

关于排序部分，在所有的哈希映射合并成一个超级哈希映射之后，一次性对这个超级哈希映射进行排序不会很慢吗？ - Alcott

@Alcott 如果可以将哈希映射保留在内存中，那么我认为快速排序不会有问题。 - xanatos

3

在解决方案中，你的第2步和第4步使其基本上是顺序执行的（第二步引入了锁定以保持哈希映射的一致性，最后一步尝试对所有数据进行排序）。

最后对哈希映射进行单步排序有点奇怪，应该使用增量排序技术，如堆排序（需要锁定数据结构）或归并排序（对“直方图”文件的部分进行排序，但避免在“一个主线程中合并所有内容”的情况下合并所有内容-尝试创建排序网络，并在每个排序步骤中混合输出文件的内容）。

多线程读取可能是一个问题，但随着现代SSD驱动器和积极的读取缓存，多线程不是主要的减速因素。重点在于同步结果排序过程。

这里是归并排序并行化的示例：http://dzmitryhuba.blogspot.com/2010/10/parallel-merge-sort.html 再次强调，某些排序网络可能有助于实现有效的并行排序，但不能采用直接的“等待所有子线程并对其结果进行排序”的方法。如果你有很多处理器，可以考虑比特农排序。

- Viktor Latypov

不用谢。我认为并行化的实际方案在这里非常重要。酷炫的“map-reduce”参考并没有说明为什么“reduce”阶段可以通过多线程快速完成。假设你有一千个线程来构建“直方图”文件。当有一个“主线程”时，它必须单独处理所有工作线程的输出。这至少是O(n)，并且几乎没有从最初的并行化中获得任何收益。 - Viktor Latypov

我不太理解你回答中提到的“增量排序技术”，你提到了heapsort和mergesort，但我无法想象它们如何工作。通过heapsort，你是指当一个线程完成一个小块时，它应该对其中出现的所有名称进行堆排序；当所有线程都完成时，合并所有已排序的小块？但是，不同的已排序块可能包含相同的名称，这会使合并变得复杂。 - Alcott

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- betabandido · Accepted Answer

使用map-reduce方法可能是解决您问题的好方法。该方法包含两个步骤：

Map：从文件中读取数据块并创建线程来处理这些数据
Reduce：主线程等待所有其他线程完成，然后将来自每个单独线程的结果合并。

这种解决方案的优点在于，由于每个线程都会操作不同的数据块，因此您不需要在线程之间进行锁定。使用共享数据结构，如您所提出的，也可以是一种解决方案，但由于锁定争用可能会产生一些开销。

您需要在减少步骤时进行排序部分，当来自所有线程的数据可用时。但是您可能希望在映射步骤中执行一些工作，以便更容易（更快地）完成完整的排序。

如果您想避免最后的顺序排序，可以使用一些自定义数据结构。我会使用一个映射（类似于红黑树或哈希表），以便快速查找名称。此外，我会使用堆来保持名称之间频率的顺序。当然，您需要拥有这些数据结构的并行版本。根据并行化的粒度，您可能会遇到锁争用问题。